This continues on the comment I submitted yesterday on the ball weighing problem.
Using a balance n times, one can find out one ball out of f(n) balls that are all of the same weight except one, and also determine whether it is heavier or lighter. The formula is
f(n) = (3^n - 1)/2 - n + 2
We have f(3) = 12, f(4) = 38, f(5) = 118, f(6) = 360, etc.
The solution for the n problem is to leave f(n -1) balls untouched, divide the rest into 2 piles and put one pile to each side of the balance.
If the balance balances, then the odd ball is in the untouched f(n - 1) balls and the problem reduces to the one of f(n-1) balls.
If the balance does not balance, then move 3^(n-1) balls out from one side, move the same number of balls from the other side to replace the moved-out ones, and move the same number from the untouched pile to replace these ones. Now one of three things can happen:
1. If the scale now balances, then the odd ball is among the 3^(n-1) ones and we know whether it is heavier or lighter. Then we can find it out in n-2 tries (see below).
2. If the scale tips to change, then the oddball is among the 3^(n-1) moved across the scale and we can again find it out in n-2 tries.
3. If the scale remains the same and does not tip, then the oddball is among the unmoved ones. Then we repeat the above process by further moving f(n-2) balls.
The solution relies on the fact that if one knows the oddball is heavier or lighter, then one can find it in 1 try for 3 balls, in 2 tries for 3^2=9 balls, etc. and in n-2 tries in 3^(n-1) balls as asserted in the above.
Thus for 12 balls in 3 tries we place 4 on each side to begin. If scale
balances, then compare 3 of the remaining 4 with 3 of the known good ones. If scale unbalances, then move 3 across the scale and replace the moved 3 by 3 of the known good ones. Watch the scale and the rest is easy.
This continues on the comment I submitted yesterday on the ball weighing problem.
Using a balance n times, one can find out one ball out of f(n) balls that are all of the same weight except one, and also determine whether it is heavier or lighter. The formula is
f(n) = (3^n - 1)/2 - n + 2
We have f(3) = 12, f(4) = 38, f(5) = 118, f(6) = 360, etc.
The solution for the n problem is to leave f(n -1) balls untouched, divide the rest into 2 piles and put one pile to each side of the balance.
If the balance balances, then the odd ball is in the untouched f(n - 1) balls and the problem reduces to the one of f(n-1) balls.
If the balance does not balance, then move 3^(n-1) balls out from one side, move the same number of balls from the other side to replace the moved-out ones, and move the same number from the untouched pile to replace these ones. Now one of three things can happen:
1. If the scale now balances, then the odd ball is among the 3^(n-1) ones and we know whether it is heavier or lighter. Then we can find it out in n-2 tries (see below).
2. If the scale tips to change, then the oddball is among the 3^(n-1) moved across the scale and we can again find it out in n-2 tries.
3. If the scale remains the same and does not tip, then the oddball is among the unmoved ones. Then we repeat the above process by further moving f(n-2) balls.
The solution relies on the fact that if one knows the oddball is heavier or lighter, then one can find it in 1 try for 3 balls, in 2 tries for 3^2=9 balls, etc. and in n-2 tries in 3^(n-1) balls as asserted in the above.
Thus for 12 balls in 3 tries we place 4 on each side to begin. If scale
balances, then compare 3 of the remaining 4 with 3 of the known good ones. If scale unbalances, then move 3 across the scale and replace the moved 3 by 3 of the known good ones. Watch the scale and the rest is easy.
For 38 balls, place 13 on each side, etc.