99 coins,1 of dem's heavy,find the heavy by short method....

[Guest]

You have been given 99 coins and a beam balance, all of the coins are similar, one of these coins is heavier than the other 98 coins. Find a short method by which this heavier coin can be found.

[Guest]

Yay! First To Reply!

This is th solution I found:

You could start by putting 44 on each side of the balance. If the balance is equal, then the coin left is the heavy coin.

If not, then take the coins from the heavier side and split them into 22 on each side.

Then take the heavier side and split into 11 on each side.

Then take the heavier side again and split into 5 and 5. If it is equal, then you have the heavier coin as the one left out.

If not then you again take the heavier side and split it into 2 and 2.

If = you have heavy coin, if not take heavier side and split into 1 and 1.

sounds much more complicated than it really is!

That was a fun one! I hope to see more like it in the future!

[Guest]

Split the coins into groups of 33 each.

Weighing 1. Weigh any group against any other group. The heavier group contains the heavy coin. If the groups weigh the same, the unweighed group contains the heavy coin.

Divide the heavy group into subgroups of 11 each.

Weighing 2. Weigh any subgroup of 11 against any other subgroup, as done previously. The heavy subgroup contains the heavy coin. If both subgroups weigh the same, the unweighed subgroup contains the heavy coin.

Divide the heavy subgroup into sub-subgroups of 3, 3, and 5.

Weighing 3. Weigh the two sub-subgroups of 3. The heavy sub-subgroup contains the heavy coin. If they weigh the same, the sub-subgroup of 5 contains the heavy coin.

If one of the sub-subgroups of 3 contains the heavy coin:

Weighing 4a. Take 2 of the 3 coins and weigh them against each other. The heavier coin is the heavy coin. If both weigh the same, the unweighed coin is the heavy coin.

SOLUTION: 4 WEIGHINGS

If the sub-subgroup of 5 contains the heavy coin:

Weighing 4b. Weigh 1 coin from the 5 against 1 other coin from the 5. If they do not balance, the heavier coin is the heavy coin.

SOLUTION: 4 WEIGHINGS.

If the coins weigh the same:

Weighing 5. Weigh any 2 of the remaining 3 coins against each other. The heavier coin is the heavy coin. If both weigh the same, the unweighed coin is the heavy coin.

SOLUTION: 5 WEIGHINGS

So this method will find the heavy coin in either 4 or 5 weighings.

[Guest]

Yay! First To Reply!

This is th solution I found:

You could start by putting 44 on each side of the balance. If the balance is equal, then the coin left is the heavy coin.

If not, then take the coins from the heavier side and split them into 22 on each side.

Then take the heavier side and split into 11 on each side.

Then take the heavier side again and split into 5 and 5. If it is equal, then you have the heavier coin as the one left out.

If not then you again take the heavier side and split it into 2 and 2.

If = you have heavy coin, if not take heavier side and split into 1 and 1.

Then the heavier side is the heavier coin!

sounds much more complicated than it really is!

That was a fun one! I hope to see more like it in the future!

I think you meant to say to split them up into two groups of 49 coins.

[Guest]

timforyou12's method will find the heavy coin in one, two, or six weighings. In contrast, spoxjox's (my) method requires at either four or five weighings. Still, I believe my method is better, on the average.

timforyou12's method will find the heavy coin in one weighing one time in 99, or just over 1% of the time. It will identify the heavy coin in two weighings one time in 49 multiplied by 98 times in 99, or just over 2% of the time. The other 97% of the time, it will require six weighings. Thus, this method requires an average of 5.87 (actually 5 86/99) weighings to identify the heavy coin.

My (spoxjox's) method will identify the heavy coin in four weighings six times in 11 (if it's in a sub-subgroup of 3) plus another two times in eleven (two in five times five in eleven) (if it's in the sub-subgroup of five and gets picked for the fourth weighing). So eight times in eleven, or just under 73% of the time, the heavy coin is found in four weighings; the other 27% requires five weighings. So the average with my method is 4.27 (actually 4 3/11) weighings, an improvement of 1 59/99 in the average number of weighings.

There is a simple optimization to timforyou12's method, however. At the third weighing, instead of weighing 12 against 12, which you know will produce a heavy side, instead weigh 11 against 11. That will give you an 8.0808...% chance of finding the heavy coin in the unweighed group of two, which will be determined in the fourth weighing.

If it's in one of the groups of 11, you then weigh 5 against 5 for the fourth weighing, giving you an additional 1 chance in 11 (total odds of 8.0808...%) of finding the heavy coin in the fourth weighing. So the total odds of finding the heavy coin on the fourth weighing are 16.1616...%, and the toal odds of finding the heavy coin BY the fourth weighing become 19.1919...%.

If it's in one of the groups of five, then you weigh two against two, and the leftover coin will be the heavy coin in 20% of those cases, or 16.1616...% of the time, found in five weighings. If it's one of the groups of two, then obviously the sixth weighing will determine the heavy coin 100% of the time in that case, or a total of 64.6464...% of the time for six weighings. Thus:

1 weighing: 1.0101...%

2 weighings: 2.0202...%

3 weighings: never

4 weighings: 16.1616...%

5 weighings: 16.1616...%

6 weighings: 64.6464...%

For an average of 5.3838... weighings, or 5 38/99 weighings, to find the heavy coin. This decreases the total weighings required on average by 48/99, or a bit under one half of a weighing. Not bad for a two-coin optimization!

So is my method optimal (4 3/11 average number of weighings), or is there someone who can beat it?

[bonanova]

Method #1. Weigh two coins at random. If they don't balance, you've done it in 1 weighing. Yay!

Method #2. Determine the smallest number of weighings that guarantees finding the heavy coin.

N weighings will distinguish among 3**N possibilities; there are 99 possibilities. 3**4 = 81; 3**5 = 243.

Four weighings are not enough; you need 5 to guarantee.

Weigh coins of equal number [roughly] one/third, and eliminate [roughly] 2/3 of the coins.

You'll guarantee a resolution after the 5th weighing.