Two genuine and two fake coins

In the country Argonia, 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. The weight of a genuine coin is greater than the weight of a fake coin.

Cosmo puts four coins on the table and tells Fredo: "I think that two of these coins are genuine and two of them are fake." Then Cosmo leaves the room. On the table, there is a balance with two pans.

Can Fredo decide whether Cosmo's statement is true by using the balance at most twice?

Yes.

Solution:

Let's label the coins A, B, C, and D.

First weigh A and B against C and D. This will leave 2 cases:

First case: If they weigh the same then weigh A against B. If A=B, then all coins weigh the same - they are all fake or all genuine. If they differ, then C and D must differ too, which means that Cosmo's statement is true.

Second case: If the first weighting is not in balance, then let's assume without loss of generality that A and B are the heavier pair. This can also be restated as Lemma 1: At least one of A and B are genuine and at least one of C and D are fake. Now weigh A and C against B and D. If this weighting comes out in balance, it means that A + C = B + D. By Lemma 1, it is then easy to see that both A and B are genuine, and C and D are fake, validating Cosmo's statement. If it is not in balance, for example if A + C > B + D, we know that A is genuine, D is fake, that C and D are the same type. By symmetry, if A + C < B + D, then B is genuine, C is fake, and A and D are the same type.

Yes.

Label the coins at random A, B, C and D.

First weigh A+B against C+D. They will either way the same, or not the same.

* If they are the same: the two pans must have the same distribution of fake/genuine, so either all the coins are fake, or all the coins are genuine, or there is a fake coin and a genuine coin in each pan. By weighing A against B, you determine which the situation is, as if A weighs the same as B all the coins must be the same weight, and Cosmo is wrong. If A and B weigh a different amount then Cosmo is right.

* if they are different: the two pans must have a differing distribution of fake/genuine. The only way Cosmo could be right here is if the lighter pan contained two fake coins and the heavier two genuine coins. So swap a coin from the lighter pan and the heavier pan, and if they are now equal, Cosmo is right. Else he is wrong.

This seems to be a different answer to waxwing I think it might be a little easier to understand.

Edit: actually it's the same decision tree as what waxwing proposes but despite a supposed mathematical background I didn't realise that for a good while, and it's proved in a different way, so I shall leave this up.

Yes, and Fredo only needs to use the balance once.

Place all four suspect coins in one of the balance's pans. In the other pan, put two known-genuine coins and two known-fake coins. If the two pans weigh the same amount, then Cosmo is correct. If not, he is wrong.

This is an outside-the-box solution, taking advantage of the fact that the puzzle doesn't actually specify that Cosmo's coins are the only ones which may be weighed; only that the balance must be the instrument of judgement, and that it may not be used more than twice. This answer may or may not be contrary to the spirit of the puzzle, depending upon whether or not Gerhard was intentionally fishing for this trick answer.

• Actually, the original question's stipulation of "by using the balance at most twice" could be interpreted either of two ways, one of which breaks this method, and the other of which makes this method unnecessarily difficult. In the first case, as implied by your comment that the balance "must be the instrument of judgement", the original statement could imply that Fredo must figure it out using only the balance and the tested coins, in which case your introduction of new test gear (4 more coins) is invalid. Alternately, you could interpret it to mean only that A) the balance must be used... – Matthew Najmon Feb 1 '15 at 17:20
• ... and B) that it must be used no more than twice. In this case, using other stuff in addition to the provided balance is allowed. This would permit your 4 known coins, but would just as well permit a set of standard weights and a chart of weights of standard coins, or a second balance (use the provided balance once, and yours thereafter, for unlimited measurements), or a phone call to the Argonian Mint Commission to be reminded that fake coins also have a smiling face on them, while the real-coin face frowns. (The challenge also doesn't stipulate identical appearances of the coins) – Matthew Najmon Feb 1 '15 at 17:24
• @MatthewNajmon The question was this: "Can Fredo decide (...) by using the balance at most twice?" According to the puzzle, Fredo must make the decision informed only by knowledge derived from using the balance. That's explicitly in the problem statement. Your "chart of weights" approach therefore violates that constraint. So does "use an extra balance" and so does "call the Mint". – Trevor Powell Feb 1 '15 at 22:28
• As I pointed out in my answer, it probably was not an answer the author intended to be legal. This type of puzzle usually comes with a "without using any other objects," clause which is missing in this one. That requirement is so common in story-puzzles that people will often just assume it must be there, even when it's not. I posted my answer just in case the author had deliberately withheld that standard clause, to make it a sort of 'trick question'. – Trevor Powell Feb 1 '15 at 22:41
• "According to the puzzle, Fredo must make the decision informed only by knowledge derived from using the balance." No. You're putting words into the OP's mouth, or rather one word, specifically "only". The OP did NOT say "only by using...", but "by using...", without the "only". If the OP had included the "only", that would have disqualified your solution equally with any of mine. – Matthew Najmon Feb 1 '15 at 23:32

There can be two outputs by weighing only two coins.

1. The balance is in alignment if two coins are exact same weight. Then you weight another two coins and if they are in alignment we can assume that Cosmo was correct but cannot be sure because there could be four coins that weigh the same.

2. The balance is not in alignment when we put two coins. Fredo weights another two coins and if they aren't in alignment we can assume that Cosmo was correct.

I think that it can't be done with only two weighing, there must be third to be sure that there are only two same coins.

ALSO

We can weigh four coins at once!

If we put two of the same weight balance will not be in alignment, so we switch from left to right and right to left and if the balance is in alignment we are 100% sure that Cosmo was correct!

But if balance is in alignment in start with four coins we cannot be certain that he was correct because all four coins can be of the same weight so changing won't change the scale and we can only think that we switched two coins of same weight!

This does not answer the question. But assuming that Cosmo's belief is accurate, this algorithm (written in t-SQL) can determine which coins are which.

DECLARE @coins TABLE(cID NVARCHAR(1), cSeed DECIMAL(8,8), cRank INT, cWeight DECIMAL(2,1), cStatus NVARCHAR(4))

INSERT INTO @coins (cID, cSeed, cStatus) SELECT 'A', RAND(), 'UNKN'
INSERT INTO @coins (cID, cSeed, cStatus) SELECT 'B', RAND(), 'UNKN'
INSERT INTO @coins (cID, cSeed, cStatus) SELECT 'C', RAND(), 'UNKN'
INSERT INTO @coins (cID, cSeed, cStatus) SELECT 'D', RAND(), 'UNKN'

;WITH r
AS (
SELECT *, RANK() OVER (ORDER BY cSeed DESC) rRank
FROM @coins
)

UPDATE r
SET cRank = rRank

UPDATE @coins
SET cWeight = 0.9 WHERE cRank > 2

UPDATE @coins
SET cWeight = 1 WHERE cRank < 3

IF (SELECT cWeight FROM @coins WHERE cID = 'A') > (SELECT cWeight FROM @coins WHERE cID = 'B')
BEGIN
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'A'
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'B'
IF (SELECT cWeight FROM @coins WHERE cID = 'A') > (SELECT cWeight FROM @coins WHERE cID = 'C')
BEGIN
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'C'
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'D'
END
ELSE
BEGIN
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'C'
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'D'
END
END
ELSE IF (SELECT cWeight FROM @coins WHERE cID = 'A') = (SELECT cWeight FROM @coins WHERE cID = 'B')
BEGIN
IF (SELECT cWeight FROM @coins WHERE cID = 'A') > (SELECT cWeight FROM @coins WHERE cID = 'C')
BEGIN
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'A'
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'B'
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'C'
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'D'
END
ELSE
BEGIN
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'A'
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'B'
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'C'
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'D'
END
END
ELSE
BEGIN
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'A'
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'B'
IF (SELECT cWeight FROM @coins WHERE cID = 'B') > (SELECT cWeight FROM @coins WHERE cID = 'C')
BEGIN
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'C'
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'D'
END
ELSE
BEGIN
UPDATE @coins SET cStatus = 'REAL' WHERE cID = 'C'
UPDATE @coins SET cStatus = 'FAKE' WHERE cID = 'D'
END
END

SELECT * FROM @coins