8
$\begingroup$

Inspired by this puzzle.

In the country Dragonia, there are only two types of coins: genuine ones and fake ones. All genuine coins have the same weight, and all fake coins have the same weight. It is not known whether a fake coin is lighter, heavier, or equal in weight to a genuine one.

Cosmo puts 48 coins on the table and tells Fredo: "There are exactly 2 fake coins among these 48 coins. Please divide them into two groups of equal total weight, and tell me whether the fake coins are lighter, heavier, or equal in weight to the genuine coins!". Then Cosmo leaves the room. On the table, there is a balance with two pans.

Can Fredo accomplish both of these tasks by using the balance at most five times?

Bonus questions (I don't know the answer to these):

  • What is the highest number of coins where it is possible to do this in 5 weighs?

  • What is the lowest number of coins where it is not possible to do this in 5 weighs?

Improve this question
$\endgroup$
9
  • $\begingroup$ I feel like I'm pretty close, but I need to figure out how to make two equal piles out of 12 coins (two groups of 6, where one group can have one or both fakes) with 2 fakes of known weight, with one check on the balance. $\endgroup$
    – Nick T
    Commented May 5, 2016 at 3:07
  • 2
    $\begingroup$ FYI, 40 is spelled "forty". $\endgroup$
    – Peregrine Rook
    Commented May 5, 2016 at 3:09
  • $\begingroup$ Lowest number possible: three. $\endgroup$
    – SendersReagent
    Commented May 5, 2016 at 7:11
  • $\begingroup$ @ghosts_in_the_code Newp. You can do it with 4, 6, 8, but not with 3. $\endgroup$
    – SendersReagent
    Commented May 5, 2016 at 10:40
  • $\begingroup$ @SendersReagent Oh ok, I didn't know that was possible. $\endgroup$
    – ghosts_in_the_code
    Commented May 5, 2016 at 10:45

3 Answers 3

Reset to default
4
$\begingroup$

divide the coins into 3 sets of 16.

Then

1st weigh: 1st 2 sets on the scale.if they are equal,

then the possibilities are:

1 fake coin each in each of the 1st 2 sets, or 2 fake coins in 3rd set, or fake coins weigh the same.

Next,

weigh 2: set 1 with set 3.

Possibile outcomes:

set 1 and 3 are equal. which mean, the fake coins weigh the same as the real ones and we are done.

or

set 1 and 3 are unequal. Which means,1 fake coin each in each of the 1st 2 sets or 2 fake coins in 3rd set.

Next,

Weigh 3: 8 coins v/s 8 coins from set 3.

Possible outcomes,

equal. Implying there is one fake coin on each side or there are no fake coins in set 3. In which case, use Weigh 4: dividing any one of the sets of 8 into 4v/s 4. If equal, we know the that 1 fake coin was in the 1st set of 16 and the other in the 2nd. we also know if they are heavier or lighter from results of weigh 2. If weigh 4 was unequal, we know that there are 2 fake coins in set 3 and know if they are heavier or lighter from results of weigh 2.

or

unequal. we know that there are 2 fake coins and know if they are heavier or lighter from results of weigh 2. Weigh 4: take the set with the fake coins and weigh them 4 v/s 4. if equal, we are done. If unequal, Weigh 5: take the set with the fake coins and weigh them 2 v/s 2. then we are done.

If weigh one was unequal,

weigh 2: set 1 with set 3. If equal, repeat the above procedure for the remaining weighs with set 2. if unequal, repeat the above procedure for the remaining weighs with set 1

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very nice! but you overlooked something: "weigh 5: 2 v/s 2 from any one set. If equal we know the that 1 fake coin was in the 1st set of 16 and the other in the 2nd". Not quite, it is possible that there is 1 fake coin in each of the 2 sets. $\endgroup$
    – shoopi
    Commented May 5, 2016 at 12:43
  • $\begingroup$ No, it is not possible. Because if there is 1 in each (2 v/s 2) then weigh 4 (4 v/s 4) would not have been equal. $\endgroup$
    – Electric_monk
    Commented May 6, 2016 at 5:51
  • $\begingroup$ I see that you edited your answer. You're actually almost there! just one thing that needs fixing: "Weigh 4: dividing any one of the sets of 8 into 4v/s 4. If equal, we know that 1 fake coin was in the 1st set of 16 and the other in the 2nd" this is incorrect since it is still possible there's a fake coin in each of the 4's, hence the balance. $\endgroup$
    – shoopi
    Commented May 6, 2016 at 11:25
  • 1
    $\begingroup$ No man, it is not possible because in the previous weigh we got 8vs 8 equal. Implying, there's '1' fake coin on each side or no fake coins at all. So, when we weigh 4 vs 4 , there is possibly only one fake coin in that 8 and there cant be 1 on each side. $\endgroup$
    – Electric_monk
    Commented May 6, 2016 at 11:38
  • $\begingroup$ Hmm that's right.. my apologize my thoughts must have been drifted from the different lines. Alright then you solved my puzzle, well done! $\endgroup$
    – shoopi
    Commented May 6, 2016 at 12:17
4
$\begingroup$

I think I found a solution for 54 coins. (52 legit + 2 fake coins)

Split 54 coins into 3 groups: A, B, C; each group has 18 coins.
Weigh (A, B), (B, C). (2 weighs)
If all three groups are equal weight, then we're done.

If not, you can always know the group that has different weight since we know all legit coins weigh the same, and both fake coins also weigh the same. e.g. If the result is (A < B) and (B > C), B is the group that weighs different.

Let's assume A has heavier weight; At this moment, we know that either (1) 2 fake coins are in A, or (2) one fake coin in B, and other in C.

Split A into three groups: A1, A2, A3; each group has 6 coins.
Weigh (A1, A2) (3rd weigh)
If (A1 < A2), we know that A has two fake coins, and thus fake coin is heavier (since A > B = C).
We also know that possible fake coin distributions are:
(3) two in A2
(4) one in A2 and other in A3

Take A2, split it into two: A2_1, A2_2; each group has 3 coins.
Weigh (A2_1, A2_2) (4th weigh)
If (A2_1 = A2_2), we're done. since we know A2_1 has one fake coin, and A2_2 also has one fake coin; Also fake coin is heavier.
If (A2_1 < A2_2), we know that heavier group(A2_2) contains at least one fake coin.
- Take two coins(x, y) from A2_2, and compare. (5th weigh); let's call the remaining one z.
-- If (x = y), x and y are fake coins OR z is a fake coin, and the other is in A3.
---- Split coins like such: (x+z+25 legit coins) vs (y+A3+20 legit coins)
-- If (x < y), y and z are fake coins OR y is a fake coin, and the other is in A3.
---- split coins like such: (y+26 legit coins) vs(z+A3+20 legit coins)
In any case, we're done since we can split coins into two groups of same weight.

Case (A1 < A2) is done.


If (A1 = A2), we know that possible fake coin distributions are:
(2) one in B, and other in C
(5) one in A1, and other in A2
(6) two in A3

Take A3, split it into two: A3_1, A3_2; each group has 3 coins.
Weigh (A3_1, A3_2) (4th weigh)
If (A3_1 < A3_2), we know that A has fake coins; thus fake coin is heavier (since A > B = C). Then, two fake coins are in A3_2.
Take two coins(x, y) from A3_2, and compare. (5th weigh)
- If (x = y), x and y are fake coins.
- If (x < y), y(heavier one) and remaining other coin in A2_2 are fake coins.
- In any case, we're done since we know two fake coins.

If (A3_1 = A3_2), We know that possible fake coin distributions are:
(2) one in B, and other in C
(5) one in A1, and other in A2
(7) one in A3_1 and other in A3_2

Weigh (A2, A3) (5th weigh) - Note that we should still remember which coins belong to A3_1 and A3_2.
If (A2 = A3), it means A1 = A2 = A3 => A doesn't have fake coins. Since A > B = C, fake coin is lighter than legit coin.
Also we can split two groups: (A/2 + B) vs (A/2 + C). And they should have same weight.

If (A2 < A3), it means that A contains two fake coins, thus fake coin is heavier. (since A > B = C). Also fake coin distribution is (7) one in A3_1 and other in A3_2. (Since A2 < A3)
We can then split coins into two groups of same weight: (A3_1 + rest/2) vs (A3_2 + rest/2)

If (A2 > A3), it again means that A contains two fake coins, and fake coin is heavier. This time, fake coin distribution is (5): one in A1, and other in A2.
We can then split coins into two groups of same weight: (A1 + rest/2) vs (A2 + rest/2)

Case (A1 = A2) is done.

Same logic applies even if A was lighter than B and C.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @shoopi, Can you check if my logic for 54 coins is correct? $\endgroup$
    – Shaun
    Commented May 6, 2016 at 23:14
  • $\begingroup$ Firstly, once again impressive stuff and very good logic, I like how you maximized the division into 3 equal groups strategy. At first I was thrown off by this: "If (A2_1 < A2_2), we know that heavier group(A2_2) contains two fake coins." - this is not correct since A2_2 may contain one and A3 the other. However, you DO account for this later on with x,y and z (brilliantly, too). After checking everyting I do think you got a 54 coin solution! well done, this is what I was looking for. Excellent strategy and logic :) $\endgroup$
    – shoopi
    Commented May 7, 2016 at 12:58
  • $\begingroup$ @shoopi, thanks for confirming :). I forgot to edit that sentence when I was editing my original solution for 54 coins (which I forgot to account the other case). $\endgroup$
    – Shaun
    Commented May 7, 2016 at 14:38
  • $\begingroup$ In the final paragraph you forgot to write about A2>A3, though it should be obvious what to do. Nice solution, +1 $\endgroup$
    – ffao
    Commented May 7, 2016 at 16:09
  • $\begingroup$ @ffao, added the case. $\endgroup$
    – Shaun
    Commented May 7, 2016 at 16:21
2
$\begingroup$

Yes. When I say fakes are equal weight in this answer I mean they have the same weight as a normal coin.

Put 24 coins on one side of the scale, and 24 on the other

I will address this in two cases, first, if the scale doesn't tip:

You know you have fake coins in each pile, or the fake coins are equal weight

Then

Divide one side of 24 into two piles of 12 and weigh these. One of these piles must contain one and only one fake (or two but they would have to weigh the same as normal coins, so we can easily check this)

If the scale tips one way:

The fake is lighter, or heavier but not the same

If the scale doesn't tip:

The fakes are equal weight

So now you know if they're the same weight, and have used at most 2 weighs. If they're not the same weight,

Then:

Weigh your two piles of 12 (record which way the scale tilts).

Then

Select just two coins at random from the pile and place them on one end of the scale. Then put two other coins at the other end. Record which way the scale tilts.

If the scale tips one way

Then take off the coins you just put on one side of the scale and put two different coins on the scale. If in this weigh the scale stays the same then the previous coins were fake, and the direction the scale tilted indicates their weight.

If the scale doesn't tip, repeat this previous step 3 times at most (5 weighs in total at most), and:

You will either have had a trial containing the fake coin and will know which coin is fake by the way the scale tilted after adding (as per above). Or, if you haven't, then you chose the pile of 12 that didn't have a fake, and that means in the first test (with the two piles of 12), if the scale tilted down towards the pile you were just testing, the coins are lighter, otherwise heavier.

Now for the case when weighing the 24 piles if the scale does tip:

Split into four piles of 12, and place one pile of 12 on one side

Then

Place each of the three remaining piles of 12 on the scales. If it tips for one but not the others, then the direction the scale tilted for that one trial indicates if the coins are heavier or lighter.

To divide into two groups. After performing your trials:

If in the first weigh of 24 they are equal great, you have your groups

If not:

You have groups of 12 after the second process, and you know by weighing which ones contain fakes. In this case, you combine the two fake groups with the two non fake groups and voilla, you have two sorted groups.

Sorry if this is hard to understand, I write in code, not in English, so it was hard not calling functions to express this :P

Improve this answer
$\endgroup$
3
  • $\begingroup$ You determined whether the fakes are lighter or heavier, but this is what the question asks: "Please divide them into two groups of equal total weight". I don't see those groups specified. $\endgroup$
    – ffao
    Commented May 5, 2016 at 7:55
  • $\begingroup$ Sorry, will edit shortly to tell how to do this $\endgroup$
    – Liam Daly
    Commented May 5, 2016 at 8:04
  • 1
    $\begingroup$ Very interesting strategy! However - in the case where the scales tip in the beginning, after dividing into 4 groups of 12, you forgot to account for the possibility that one of those groups contains both fakes. In that case, you wouldn't be able to divide it into two even groups unless you're lucky :) $\endgroup$
    – shoopi
    Commented May 5, 2016 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.