How smart is ATOT? *tough riddle thread*

silverpig

Lifer
Jul 29, 2001
27,703
12
81
Whoever correctly answers this problem gets to post the next (and gets respect).

Everyone knows the classic 9-marble-and-one-is-heavier problem. You have 9 marbles, one is heavier than the rest, and a balance. How do you find the heavy one with 2 weighs?

The answer is to split the marbles into 3 groups of 3. Weigh group A vs group B. The heavy ball will be in the heavy group if one is heavier than the other. If they are the same, you know the heavy marble is in group C. Pick any two marbles from the heavy group and weigh them. Apply the same logic as to the groups in order to determine which is the heavy ball.

Too simple? Well here ya go:

You have a balance and 12 marbles, 11 of which are of the same weight. The other marble may be lighter or heavier than the rest, but you do not know which. Is it possible for you to point out the deviating marble AND tell whether it is lighter or heavier than the rest using only 3 weighs? If your answer is yes, you must provide a method which will always work. If your answer is no, you must prove that you will require at least 4 weighs.
 

Turin39789

Lifer
Nov 21, 2000
12,218
8
81
i just know someone else will have replied by the time i finish

but 4 marbles on both sides of the scale. If one side is heavier that side contains the heavy marble, if they are equal it is amongst the four you didnt weigh. Take the group with the heavy marble, weigh any two of the marbles. If one side is heaver it is the lucky marble, otherwise it is one of the two that wasnt weighed. For the third weigh, if needed, weigh the two remaining marble and the heavier is the heavier.

Alternately after you have narrowed it down after the first weigh to four marbles, you can put two on each side, the heavier side will contain the heavy marble. Then for the third weigh just test those two to figure out the answer. This method garuntees it in three weighs, while the first may answer it in two.

My question.

If pants are outlawed, then what?
 

ROTC1983

Diamond Member
Oct 2, 2002
6,130
0
71
Originally posted by: Turin39789
i just know someone else will have replied by the time i finish

but 4 marbles on both sides of the scale. If one side is heavier that side contains the heavy marble, if they are equal it is amongst the four you didnt weigh. Take the group with the heavy marble, weigh any two of the marbles. If one side is heaver it is the lucky marble, otherwise it is one of the two that wasnt weighed. For the third weigh, if needed, weigh the two remaining marble and the heavier is the heavier.

Alternately after you have narrowed it down after the first weigh to four marbles, you can put two on each side, the heavier side will contain the heavy marble. Then for the third weigh just test those two to figure out the answer. This method garuntees it in three weighs, while the first may answer it in two.

My question.

If pants are outlawed, then what?

Looks like no one beat you to it :)
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
Originally posted by: Turin39789
i just know someone else will have replied by the time i finish

but 4 marbles on both sides of the scale. If one side is heavier that side contains the heavy marble, if they are equal it is amongst the four you didnt weigh. Take the group with the heavy marble, weigh any two of the marbles. If one side is heaver it is the lucky marble, otherwise it is one of the two that wasnt weighed. For the third weigh, if needed, weigh the two remaining marble and the heavier is the heavier.

Alternately after you have narrowed it down after the first weigh to four marbles, you can put two on each side, the heavier side will contain the heavy marble. Then for the third weigh just test those two to figure out the answer. This method garuntees it in three weighs, while the first may answer it in two.

My question.

If pants are outlawed, then what?

Actually, that's incorrect. Note that the deviant marble may be either lighter or heavier than the rest. So in your first measurment, how do you know that the heavy side contains a heavy marble rather than having the light side contain a light marble?
 

bmd

Golden Member
Feb 17, 2001
1,043
0
0
Originally posted by: silverpig
Originally posted by: Turin39789
i just know someone else will have replied by the time i finish

but 4 marbles on both sides of the scale. If one side is heavier that side contains the heavy marble, if they are equal it is amongst the four you didnt weigh. Take the group with the heavy marble, weigh any two of the marbles. If one side is heaver it is the lucky marble, otherwise it is one of the two that wasnt weighed. For the third weigh, if needed, weigh the two remaining marble and the heavier is the heavier.

Alternately after you have narrowed it down after the first weigh to four marbles, you can put two on each side, the heavier side will contain the heavy marble. Then for the third weigh just test those two to figure out the answer. This method garuntees it in three weighs, while the first may answer it in two.

My question.

If pants are outlawed, then what?

Actually, that's incorrect. Note that the deviant marble may be either lighter or heavier than the rest. So in your first measurment, how do you know that the heavy side contains a heavy marble rather than having the light side contain a light marble?

Edit: see my post below for my explanation/my thoughts on the puzzle.
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
It took me about 35 minutes to come up with the solution and a proof... I just hope that everyone will have to think about this one like I did, and no one will ask someone who's heard the solution before.
 

Turin39789

Lifer
Nov 21, 2000
12,218
8
81
ok
keep the three groups of four
first weigh one side will be heavier
if not then the lighter or heavier marble is in group 3

otherwise leave the heavy group on and put the third group on the other side
if they are equal the odd ball will be in the removed group
if the heavier side is still heavier, it contains a heavy ball, if they are equal then the group off of the scale contains a lighter marble

so we have done 2 weighs(talking to myself)
now with the narrowed group of four, dance in circles and throw the marbles at an animal. Then eat applesauce till you puke
 

GoingUp

Lifer
Jul 31, 2002
16,720
1
71
I would just throw them at the person asking such a rediculous riddle, then hit them over the head with the scale....

actually Luvly might be good with this question cause shes good with math, so long as it doesn't require the precise calculations of international time zones ;)
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
Heh, good to see some people are getting a bit frustrated already :)

I'll post a few hints later if people are really stuck (I'll have to come up with them too, and I think I'll do it in the most mathematically elegant way I can think of... and that'll take a while for me to define).
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
Originally posted by: Gobadgrs
I would just throw them at the person asking such a rediculous riddle, then hit them over the head with the scale....

actually Luvly might be good with this question cause shes good with math, so long as it doesn't require the precise calculations of international time zones ;)

Ah, but then you wouldn't get the respect, nor the right to ask the next riddle :)


Side bet:

I bet that RossGr will get the solution first. If I am correct and he gets the solution and proof first, then the thread will continue with him asking the next riddle. He and I will then work together formulating an uber-riddle, and we will get to pose this riddle to ATOT in this thread whenever we finish. The uber-riddle will bump the riddle being pondered in the thread at that time, and will become the official riddle of the thread.

I promise I will not give him any extra hints (why would I? I enjoy seeing you ALL squirm hahaha).
 

bmd

Golden Member
Feb 17, 2001
1,043
0
0
Ok, I think you can find the odd marble in 3 steps no matter what, but can't always tell whether it's heavier or lighter in 3. Let's hope no one beats me to this before I finish typing it out =P.

First take 8 out of the 12 marbles and put 4 on each side. If they do balance then it is relatively easy to figure which of the remaining 4 it is in 2 weighs.

Weigh 2 out of the remaining 4. If they balance, weigh one of the remaining 2 with one of the balls you know is "normal" (one of the 8 you weighed the first time). If it doesn't balance, that is the odd marble, if it does the other marble that you never weighed is the odd marble.

If those 2 out of the remaining 4 don't balance, weigh one of the 2 against a marble you know is "normal". Once again if it tips, the non-normal marble is the odd one, if it balances then the remaining marble is the odd one.

--------------------------------------------------------------------------------------------------------------------------------
If it doesn't balance at first with the 8 marbles it gets more complicated.

Let's say you had marbles ABCD on the left in the first weighing and EFGH on the right.

Now put A, a normal marble and E on the left. Put B, C and F on the right.

If this balances either D, G or H must be the odd marble. Put G and a normal on the left, H and a normal on the right. If it tips opposite to the way it did when you weighed the initial 8, G must be the odd marble (because it was moved to the left side). If it tips the same way as the initial weighing H is the odd marble. If it balances, D is the odd marble.

If A, normal, E vs. BCF tips in the same direction as the initial weighing, this means that moving E to the left and B and C to the right had no effect and therefore the odd marble is A or F. Weigh A versus a normal. If it balances, F is the odd. If it doesn't A is the odd.

If A, normal, E vs. BCF tips in the opposite direction as the initial weighing, this means that moving E, B and C around *did* have an effect. Therefore either E, B or C must be the odd marble. Weigh B and a normal vs. C and a normal. If it tips in the same direction as the initial weighing of 8 B is the odd marble. If it tips opposite to the initial weighing, C must be the odd marble. If it balances, E is the odd marble.

There it is, no more than 3 steps for any of them to find the odd marble, BUT it would take a 4th weighing of the odd ball versus any of the normal balls to find if it was heavier or lighter. Initial --> refinement --> find the odd --> heavier/lighter is basically the process for all of it.

Edit 2: I realize this isn't a rigorous mathematical proof and that in some cases you actually do find out on the 3rd weighing whether the odd ball is lighter or heavier, but you can't find out whether every odd ball is lighter or heavier on the 3rd weighing, therefore you would have to be able to weigh 4 times in order to be absolutely sure you could find whether, in any given outcome, the odd ball was light or heavy.
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
Originally posted by: bmd
Ok, I think you can find the odd marble in 3 steps no matter what, but can't always tell whether it's heavier or lighter in 3. Let's hope no one beats me to this before I finish typing it out =P.

First take 8 out of the 12 marbles and put 4 on each side. If they do balance then it is relatively easy to figure which of the remaining 4 it is in 2 weighs.

Weigh 2 out of the remaining 4. If they balance, weigh one of the remaining 2 with one of the balls you know is "normal" (one of the 8 you weighed the first time). If it doesn't balance, that is the odd marble, if it does the other marble that you never weighed is the odd marble.

If those 2 out of the remaining 4 don't balance, weigh one of the 2 against a marble you know is "normal". Once again if it tips, the non-normal marble is the odd one, if it balances then the remaining marble is the odd one.

--------------------------------------------------------------------------------------------------------------------------------
If it doesn't balance at first with the 8 marbles it gets more complicated.

Let's say you had marbles ABCD on the left in the first weighing and EFGH on the right.

Now put A, a normal marble and E on the left. Put B, C and F on the right.

If this balances either D, G or H must be the odd marble. Put G and a normal on the left, H and a normal on the right. If it tips opposite to the way it did when you weighed the initial 8, G must be the odd marble (because it was moved to the left side). If it tips the same way as the initial weighing H is the odd marble. If it balances, D is the odd marble.

If A, normal, E vs. BCF tips in the same direction as the initial weighing, this means that moving E to the left and B and C to the right had no effect and therefore the odd marble is A or F. Weigh A versus a normal. If it balances, F is the odd. If it doesn't A is the odd.

If A, normal, E vs. BCF tips in the opposite direction as the initial weighing, this means that moving E, B and C around *did* have an effect. Therefore either E, B or C must be the odd marble. Weigh B and a normal vs. C and a normal. If it tips in the same direction as the initial weighing of 8 B is the odd marble. If it tips opposite to the initial weighing, C must be the odd marble. If it balances, E is the odd marble.

There it is, no more than 3 steps for any of them to find the odd marble, BUT it would take a 4th weighing of the odd ball versus any of the normal balls to find if it was heavier or lighter. Initial --> refinement --> find the odd --> heavier/lighter is basically the process for all of it.

Edit 2: I realize this isn't a rigorous mathematical proof and that in some cases you actually do find out on the 3rd weighing whether the odd ball is lighter or heavier, but you can't find out whether every odd ball is lighter or heavier on the 3rd weighing, therefore you would have to be able to weigh 4 times in order to be absolutely sure you could find whether, in any given outcome, the odd ball was light or heavy.

Close, but not quite there...
 

bmd

Golden Member
Feb 17, 2001
1,043
0
0
What do you mean not quite there? What is missing?

You can always find the odd ball in 3 weighs but cannot always know whether it is lighter of heavier in 3 weighs. Is that wrong?
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
You have just shown that you can find the odd ball in 3 tries and need a 4th to determine if it is light or heavy with your combination of marbles. You haven't proven if this is the most efficient way of grouping the marbles for their weighings.

You have gotten to a certain point. Now you have another task to complete the problem. You must either:

A. Prove that yours is the most efficient method, therefore showing that no matter how you weigh the marbles, you will always require a 4th weighing to determine the nature of the deviation.

B. Find a more efficient method.

:)
 

bmd

Golden Member
Feb 17, 2001
1,043
0
0
Originally posted by: silverpig
You have just shown that you can find the odd ball in 3 tries and need a 4th to determine if it is light or heavy with your combination of marbles. You haven't proven if this is the most efficient way of grouping the marbles for their weighings.

You have gotten to a certain point. Now you have another task to complete the problem. You must either:

A. Prove that yours is the most efficient method, therefore showing that no matter how you weigh the marbles, you will always require a 4th weighing to determine the nature of the deviation.

B. Find a more efficient method.

:)
Bah. Too much work and too much like Ma1 for me. Here I am having wasted time solving this problem (well not completely according to your standards =P) instead of doing my math or phys sets. Oh well, such is the life of a Techer.
 

silverpig

Lifer
Jul 29, 2001
27,703
12
81
I could make it a little bit simpler by telling you whether or not it was possible to know everything in 3 weighs, but I'm not gonna do that... yet :)

You can either:

A. Assume it is possible and search for a solution with 3 weighings, or

B. Assume it is impossible and prove that the most efficient strategy requires at least 4 weighings.


You can actually get the correct answer by doing either strategy.
 

bmd

Golden Member
Feb 17, 2001
1,043
0
0
Originally posted by: silverpig
I could make it a little bit simpler by telling you whether or not it was possible to know everything in 3 weighs, but I'm not gonna do that... yet :)

You can either:

A. Assume it is possible and search for a solution with 3 weighings, or

B. Assume it is impossible and prove that the most efficient strategy requires at least 4 weighings.


You can actually get the correct answer by doing either strategy.
You can keep toying with us if you want, I for one am heading to bed. Got a long day tomorrow :(. Will check back in the morning to see if anyone else has any solutions/comments.
 

NewSc2

Diamond Member
Apr 21, 2002
3,325
2
0
good job bmd for at least figuring all that out. i got turin's first answer, and then i decided that turin's 2nd answer would be the more correct (after silverpig said his first answer wasn't).


*eats applesauce until i puke*
 

RossGr

Diamond Member
Jan 11, 2000
3,383
1
0
Silverpig has kinda put me on the spot here, fact is I have a solution to this which I worked out some time back. I recieved a PM from Aupig about this and he said that if I already had the solution that I shouldn't post it, but rereading that message the critical point seems to be that I work it out on my own rather then ripping it from some one else. I did work out this solution on my own just not recently, I even had the foresite to write up a detailed solution. So I could do a copy paste right now, but.... Since I have since seen a slight varition to my solution also worked, there is more then one way to do this, are there others? seems to me that to post my solution would stiffle your creative jucies. So I'll hold back 'till Aupig says put up or shut up.

This really a very tough problem, it took me a lot longer then 35min.