This is a question of my own devising. You have a double pan scale which will tell you whether 2 coins or 2 groups of coins weigh the same or whether one side is heavier than the other side. You have N coins with one coin being heavier or lighter (you don't know which) than the other coins. You are allowed to make 4 weighings in order to find the coin that is heavier or lighter than the others. What is the largest N you can achieve? What if you are allowed to make 5 weighings?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
We know that $3$ weighings suffice for $13$ coins if we have one known good (see here), so for $4$ we can split $39$ coins into three groups of $13$ and weigh two of the groups against each other. If they balance the $26$ coins on the scale are known good and we can follow the standard $13$ coin solution. If they don't balance we number the coins from the light side of the scale $1L$ through $13L$ and the coins from the heavy side of the scale $1H$ through $13H$. We follow the $13$ coin solution putting the $L$ coins as called for and putting the $H$ coins on the opposite side, so the second weighing is $0L,1L,4L,5L,6L,0H,1H,4H,5H,6H$ against $7L,10L,11L,12L,13L,7H,10H,11H,12H,13H$ We need two known good coins. From the last three weighings we can consider the $L$ coins to be suspect. We find the bad coin as in the $13$ case and whether it is light or heavy. For example if the second weighing does not balance but the third and fourth do, the bad coin is either $1L$ or $1H$. The result of the second weighing tells us which coin it is.
For five weighings we can get another tripling. We split $117$ coins into three groups of $39$. If they balance we are in the $39$ case with the coins that were set aside. If they do not, put $13$ coins from the side that was heavy and $13$ coins from the side that was light on each side. If it does not balance you have $13$ possibly heavy coins and $13$ possibly light coins and can follow the previous solution.
-
$\begingroup$ @BobBixler: One group is known to perhaps be light but cannot be heavy. The other is known to perhaps be heavy but cannot be light. You can follow the same approach of putting possibly heavy coins with possibly light coins. Each time the balance tips you can throw out half the coins because they would cause it to tip the other direction. It is just like the two groups of $13$. $\endgroup$ Commented Jul 22 at 18:39
$\begingroup$
$\endgroup$
I would assume that for 4 weighings you could figure out the false coin for n<=27=3^3 without requiring some sort of luck. When you know whether the single coin is heavier or lighter than the rest, this is a fairly well known problem. Starting with 3N coins you can always weigh N coins on the left, N coins on the right and leave N coins on the table to determine which group of N coins contains the outlier. This way you can divide the possible number of contenders by three with each weighing. Determining whether the outlier is heavier or lighter than the other coins should only take one weighing. You can, for example, simply use the division process until the 2 groups you are weighing are different in weight. You then compare the lighter one of them with the group that was left on the table (and which you know to consist of only regular coins) and if it is still lighter then the coin is among that group and is lighter than the rest. If both of these groups weigh the same, then the coin is heavier than the rest and among the group that was initially heavier.
