All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 One out of ninety (Posted on 2013-12-17)
You are presented with a set of 90 coins, appearing identical.
Actually, 89 of them are identical, but one has a different weight.
Using balance scales you have to find the odd coin,
paying \$10 each time you use the scales.

What is the maximal (i.e. the worst case) cost to accomplish it?

Comments: ( Back to comment list | You must be logged in to post comments.)
 One out of One Hundred Twenty! | Comment 5 of 7 |
With just 5 weighings we can find an odd coin from a total set of 120 coins.

Divide the 120 coins into 12 groups of size {1, 1, 1, 3, 3, 3, 9, 9, 9, 27, 27, 27}.  This is three groups of each of the first four powers of three.  Place one of each size group on the each side of the scale - {1,3,9,27} vs {1,3,9,27}.  Record that weighing.

Now rotate the 27 coin groups - take the left group off, move the right group to the left, and move the group that was off onto the right.  Record that weighing.  If the weighing changed then the odd coin is in one of the groups of 27.

If one weighing was equal and the other was unequal then the odd coin is in the 27 coin group appearing only in the unequal weighing.  If both weighings were unequal (weighted to different sides in this case) then the group with the fake is the 27 coin group that was in both weighings.  In either of these cases we know if the odd coin is light or heavy and can use the last three weighings to find it.

Finally, if the weighings are the same result (both left, both right, or both equal) then all 81 coins in the three 27 coin groups are normal coins.  Now rotate the 9 coin groups.

By similar logic, the odd coin is either found in one of the 9 coin groups or all 27 of those coins are normal coins and then 3 coin groups are next to look at.

Finally if all the 27 coin groups, 9 coin groups, and 3 coin groups are all normal.  That leaves one weighing to sort the last three single coins - but we already know the relative weight of two of them, so the last weighing finishes the task.

This algorithm is easily scalable such that w weighings will suffice to find an odd coin of unknown weight from a set of (3^w-3)/2 coins.

 Posted by Brian Smith on 2015-12-18 00:03:15

 Search: Search body:
Forums (0)