SERVING THE QUANTITATIVE FINANCE COMMUNITY

BobM
Topic Author
Posts: 132
Joined: November 12th, 2002, 2:14 pm

### Brainteaser

12 balls, one is different (either heavier or lighter but you dont know which). you can use oldfashioned two arm scales to weigh the balls but you can only use this 3 times, and each time the scales can only hold a max of 6 balls (i.e. a max of 3 balls in each of the two weighing buckets) - how can you find out which is the odd one, AND whether it is lighter or heavier than the rest????

MobPsycho
Posts: 1946
Joined: March 20th, 2002, 2:53 pm

### Brainteaser

Last edited by MobPsycho on August 17th, 2003, 10:00 pm, edited 1 time in total.

MobPsycho
Posts: 1946
Joined: March 20th, 2002, 2:53 pm

### Brainteaser

Last edited by MobPsycho on August 17th, 2003, 10:00 pm, edited 1 time in total.

BobM
Topic Author
Posts: 132
Joined: November 12th, 2002, 2:14 pm

### Brainteaser

Not sure if your method works, maybe I am not following correctly. Say ABC is heavier than DEF then you weigh AE against DB is that what you say ? Say the second weighing balances then you know it is either C or F but not which one. You know C is heavier than F but not whether C is heavier than all the others or F lighter ??As for the original question I dont know of an answer. I can solve it forgetting the only six balls allowed on the scales (ie by starting off weighing 4 against 4) and I think you can solve with the six ball question in four steps (I havent actually tried !!) but combining I dont know ??I was thinking that the solving it is loosly based around base three and thus to exactly recover 12 unique numbers at some stage you must have eight balls on the scales...............Any suggestions ??

MobPsycho
Posts: 1946
Joined: March 20th, 2002, 2:53 pm

### Brainteaser

Last edited by MobPsycho on August 17th, 2003, 10:00 pm, edited 1 time in total.

zerdna
Posts: 3856
Joined: July 14th, 2002, 3:00 am

### Brainteaser

i posted solution to this one in Monday morning puzzle thread. It's somewhere there.

MobPsycho
Posts: 1946
Joined: March 20th, 2002, 2:53 pm

### Brainteaser

Last edited by MobPsycho on August 17th, 2003, 10:00 pm, edited 1 time in total.

zerdna
Posts: 3856
Joined: July 14th, 2002, 3:00 am

### Brainteaser

Hmm, didn't see the limitation of 3 balls/bucket. cannot do indeed
Last edited by zerdna on February 12th, 2003, 11:00 pm, edited 1 time in total.

MobPsycho
Posts: 1946
Joined: March 20th, 2002, 2:53 pm

### Brainteaser

Last edited by MobPsycho on August 17th, 2003, 10:00 pm, edited 1 time in total.

BobM
Topic Author
Posts: 132
Joined: November 12th, 2002, 2:14 pm

### Brainteaser

OK maybe I am missing something here but you seem to have the solution involving eight balls ??? I apologise if the six baller is there infront of me and I just dont see it. It is Thursday afternoon and time for a caffeine injection I fear so my mind is probably playing tricks.....................

csparker
Posts: 396
Joined: October 3rd, 2001, 7:53 am

### Brainteaser

<Edited to remove smart ass comment about Zerdna solving the wrong problem>I have an approach based on the first weighing being between balls (1, 2, 3) and (4, 5, 6), the second weighing is (1, 2, 3) against (7, 8, 9). You can get the odd ball from one further weighing of one ball on each side - the balls you weigh depend on the combined outcome of the first two weighings, but there is one case where you don't know if it is lighter or heavier. The rogue case comes when the first two weighings are even. Do we know whether a solution exists?
Last edited by csparker on February 12th, 2003, 11:00 pm, edited 1 time in total.

Symplecto
Posts: 40
Joined: January 28th, 2003, 8:34 pm

### Brainteaser

Heard that one 8 years ago, and was so impressed that actually wrote down a solution back then Here it is:I (1,2,3,4) vs (5,6,7,8)II (1,2,5,9) vs (4,8,11,12)III (2,7,8,12) vs (5,6,10,11)It detects not only the lighter/heavier ball but also if there is none.To verify the solution you must check that no two balls are in the same group (resp. opposite groups) in every weighing.If you impose the restriction of <= 6 balls per weighing then there is no solution, shown as follows.There are the total of 24 "states": 12 balls times 2 (lighter/heavier).Each weighing has three possible outcomes which separate this space into three sets.The first weighing leaves 6 balls out, so one of the sets has at least 12 states in it.The second leaves at least 4 of those 12 in one set and third at least 2 of those 4 in one set - those 2 cannot be distinguished!You see that imposing the restriction on even the first weighing makes the problem unsolvable.Another remark: if you include the possibility of all balls being the same, there are 25 states overall.On the other hand, the total number of possible outcomes after 3 weighings is 3^3 = 27. So the above solution is pretty close to being optimal, in the sense that there are only 2 outcomes out of 27 that can never happen.BobM, are you playing samudra on us? (see another ball brainteaser in this forum)

Chukchi
Posts: 915
Joined: December 15th, 2001, 3:43 am

### Brainteaser

Last edited by Chukchi on July 6th, 2003, 10:00 pm, edited 1 time in total.

Sasquatch
Posts: 36
Joined: March 3rd, 2003, 8:11 pm

### Brainteaser

<blockquote>Quote<hr><i>Originally posted by: <b>BobM</b></i>12 balls, one is different (either heavier or lighter but you dont know which). you can use oldfashioned two arm scales to weigh the balls but you can only use this 3 times, and each time the scales can only hold a max of 6 balls (i.e. a max of 3 balls in each of the two weighing buckets) - how can you find out which is the odd one, AND whether it is lighter or heavier than the rest????<hr></blockquote>It cannot be done.PROOF:I will assume a general algorithm and assume that things go for the worst by taking an adversarial position in the outcome of each weighing.Let the first weighing be (7,8,9) vs. (10, 11, 12), and suppose this weighing balances. Then the bad ball must be in the first six, but you still don't know if it's heavier or lighter. I now have two weighings to determine which of the six is bad, and in which direction.Suppose I choose not to weigh all six balls 1 through 6 on the next try. If I weigh less than 5 balls, then if the scales balance again, I have two balls unweighed. In the third weighing I could not tell which of these is bad if I weigh both; if I weigh only one, then if the unweighed ball is bad I wouldn't know if it was too heavy or too light. So I must either weigh 5 or 6 of the remaining balls on the second weighing.I will choose to weigh only 5 on the second weighing, since I get strictly more information than if I weigh 6. If the scales don't balance, I eliminate the unweighed ball, and if they do balance then I have one more weighing to see if the last ball is heavy or light.Second weighing: (1, 2, 3) vs. (4, 5, X) where X is a normal ball, 7 through 12. Suppose that (1,2,3) is heavier than (4,5,X).For the third weighing, I must weigh at least four of the balls 1 through 5. If I weigh only three or fewer, and the scales balance, I don't know which of the two removed balls caused the imbalance on the second weighing. So, I have two choices: (a) either remove one of (1,2,3) -- let's say 3, or (b) remove 4 or 5 -- let's say 5, or (c) remove none.CASE (a): If I remove 3, I have {1, 2, 4, 5} to weigh. Note that 1 and 2 cannot remain on the same side of the balance, since then they would be indistinguishable -- if either were too heavy, I couldn't tell which. Likewise for 4 and 5. So I must swap two of the balls between sides. It's all symmetric, so let's weigh (1, 5) vs. (2, 4). Suppose the scale doesn't move; (1, 5) is heavier than (2, 4). Then either 1 is heavy or 4 is light, so I can't decide. (If the scale moves, it's either 2 or 5; same story.)CASE (b): I remove ball 5. Now I'm left with 1, 2, and 3. Two of these must remain on the same side of the balance again, and so are indistinguishable. This doesn't work either.CASE (c): Remove none. Then I weigh all 5 again, so at least two of 1, 2, and 3 are on the same side again. Same as case (b).QED.Sasquatch
Last edited by Sasquatch on May 25th, 2003, 10:00 pm, edited 1 time in total.

WaaghBakri
Posts: 732
Joined: March 21st, 2002, 4:07 am

### Brainteaser

You have a box of dominoes and a 8x8 checker board. One can arrange 32 dominoes on the checkerboard such that each domino covers 2 checkerboard squares. Now snip off 2 diagonally opposite squares (extreme) of the checkerboard. On this modified checkerboard, can you layout 31 dominoes such that each domino only covers 2 squares each? PS.: Plucked off elsewhere.......

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...

GZIP: On