Coin Riddle

The Game Room
1

I don’t want to hijack the enjoyable Monty Hall discussion in the “Lateral Thinking” thread, so I figured I’d just post this riddle on its own:

You receive an authentic and valuable coin as a gift. You so admire this rare coin that you realize it would bring you great pleasure to have more. The coins are supposed to bring good luck and all.

One day you see an ad in the paper offering to a whole bag of these exact coins as a prize if you can solve a puzzle.

You go and visit the wily old collector on his island.

The grizzled old man shows you his collection of fourteen coins.

"One of these coins is a fake, and the other thirteen are real. The one fake coin either is slightly heavier or slightly lighter than the real coins. You cannot tell by look or feel.

“I will lend you a simple balance scale. You may make up to three weighings, and then you must positively identify the fake coin. If you cannot positively identify the counterfeit coin, you will be fed to my lions. However, if you do identify the fake coin, the other thirteen will be yours.”

“Many have come, but none have dared to accept my challenge.”

You realize that unless you can positively guarantee that you will discover the fake coin, you should not take the gamble. The risk of death would be to great. You understand why no one else would try. In the background you hear the angry lions roaring in their lair. A guarantee seems impossible.

As you start to leave, an idea suddenly comes to you. After a moments thought you turn to the old man, look him straight in the eye, and say:

“I accept your challenge!”

What is your plan to guarantee success?

2

Shoot the old coot in the head and take all the coins to weigh at my leisure.

What? He was going to throw me to lions!

3

I forgot to mention the 6 heavily armed (BUT VERY FAIR) guards who will make sure that the agreement is carried out to the letter. This is a very fair, but cruel, island.

4

I don’t have a solution yet, but I suspect I’ve got an idea that may help:

You don’t just have fourteen coins; you’ve got fourteen coins plus one known genuine coin. That might make all the difference.

5

Oh, heh, I forgot all about this. Luckily, the way you’ve posed it makes it easier to see what you were getting at last time. Unfortunately, Heller Highwater already beat me to posting that realization. So I guess to make any contributions now, I have to figure out how to actually make use of it…

6

I swear I got this before looking at Heller’s spoiler!

[spoiler]Start by weighing 5 unknown coins versus 4 unknown coins and the known coin.

If they are even, then one of the remaining 5 coins is fake. Weigh 3 of them against 3 known coins. If they are even, one of the remaining 2 coins is fake and you can weigh 1 of them against a known coin to decide which. If not, then you have 3 potential fakes and you know if the fake is heavy or light. Thus one more weighing suffices (one on each side).

If the original weighing is not even, then you have 9 potential fakes, without loss of generality we may say 5 are potentially light, and 4 are potentially heavy. Put 2 potential lights and 1 potential heavy on each side. If it is even, then there are 3 potential fakes left (2 heavies, 1 light). Put a heavy and a light versus 2 genuines. If it is not even, there are still 3 potential fakes (2 lights, one heavy). Do the same. Done.[/spoiler]

7

My thought was to start by

splitting the old guy’s coins into 2 groups of 7 and swapping your own coin for any one in either pile. If they are both evenly weighted, you know the fake is the one you removed. If not, one group is going to be lighter or heavier than the other. That’s the one with the fake in. Not sure of the next step, tho.

8

Carmady got it!

I think the addition of the real coin to the old classic puzzle of 12 (or 13) coins is interesting. The balance scale /fake coin puzzle is all about solving the mystery in as few weighings as possible.

Now correct me if I’m wrong, but it seems to me that there are only 2 cases where bringing a real coin to the puzzle will reduce the number of weighings to 3 or less compared to not having an extra real coin.

The first case is if you have only 2 coins. In that example you can never determine the fake coin with a balance scale unless you have an additional real coin. Once you bring in an additional known coin, the solution is simple with one weighing.

However (and again, correct me if I’m wrong), other than the 2 coin situation, the only time an additional authentic coin would reduce the weighings to three or less is at the level of 14 coins. At 15 coins, even bringing an additional authentic coin or two won’t help. 15 and up always requires at least four weighings.

With 3 to 5 coins, you will always need two weighings whether you bring an extra known coin or not.

With 6 to 13 coins, you will always need three weighings. An extra real coin does not help.

God help me, but now I’m wondering what the coin level is that forces the number of required weighings to five. Must take a break.

9

Well, with 4 weighings, if you imagine drawing out a little flowchart of exactly what you do with exactly what outcomes, your flow chart will have 81 possible endpoints (because it branches in 3 each time). So if the puzzle was a bit simpler than it is, for instance if you knew that the counterfeit was heavier than real, then you could find the counterfeit among 81 possible coins with 4 weighings… outcome #1 is that coin #1 is fake, outcome #2 is that coin #2 is fake, etc. As it is, however, you end up needing two outcomes for each coin, because the path you go down to find out that coin #1 is heavy is different than the path you go down to find that coin #2 is light. BUT, it’s possible to have one and only one coin that is you end up discovering is counterfeit without ever discovering if it’s heavy or light, because you never actually weigh it, but rather you end up weighing your 2nd to last against a known good one, seeing that it’s good, so the final coin must be counterfeit.

Therefore, the maximum number of coins that can be distinguished between with 81 weighings is, theoretically, 41 (40 having 2 outcomes each, 1 having 1 outcome). That would in fact be quite possible if you had something very useful in puzzles like that, namely a store of known-good coins. That makes the puzzle WAY easier. Step 1 is to weight 27 of your coins against 27 known-good coins, proceed from there.

So anyhow, 41 is clearly the theoretical cap. But is it actually solvable in 4 weighings? Well, your first weighing is obviously n vs n, leaving m aside (n+n+m = 41). One outcome is that they balance, in which case you have 3 weighings to do m, but have a store of known-good. So m must be 14 or less. So what’s n? If n is 13, then m ends up being 15. Which is no good. If n is 14, on the other hand, then in the case that the scales do NOT balance, you have 28 potentially counterfeit coins and only 3 more weighings to distinguish them, which is clearly impossible. So there’s an off-by-one even/odd error, and 41 can NOT be solved with 4 weighings. UNLESS, of course, you have one additional known-good coin, in which case you start by weight 14 vs 13+1, leaving 14 aside, and after one weighing have either 27 possible counterfeits, each known to be possibly-heavy or possibly-light, or else 14 possible counterfeits, about which you know nothing, etc.
The solution I assume everyone came up with is:

Weigh 5 of his coins vs 4 of his coins + yours. If they balance, the counterfeit is one of the other 5 of his. Weigh 3 of them vs 3 now-known-good. If they balance, then you have 2 others, one of them counterfeit. Weight it against a known good. If they don’t balance, you have 3 coins, one of them counterfeit, but you know heavy/light, so you weight 2 against each other.

If your initial weighing does not balance, you now have 9 possible counterfeits, 5 or which are maybe-light (L) and 4 of which are maybe-heavy (H) (or the other way around) Weigh LLH vs LLH. If they balance, then you have LHH possibly counterfeit, weigh H against H. If they don’t balance, the counterfeit is either one of the Ls on the light side of the scale, or the H on the heavy side. Weight the two Ls against each other.

10

MaxTheVool: You have now ruined my day off. Instead of doing the hours of yardwork I promised my wife, I will have to spend the day designing flowcharts and attempting to prove a true value for “n”. Curses!

And for anyone still interested in the original riddle, I have this addenda/question:

Suppose instead of a real authentic coin, you had brought an exact duplicate of the one fake coin to the island. You still don’t know if the fake coin is heavier or lighter than the real coins. Your challenge is still to find the other fake coin in 3 weighings from amongst the old man’s 14 coins. Do you still take the dare?

11

Okay.

Right now I think I can solve a 36 unknown coin puzzle in four weighings. This is without having an extra known good coin. If it can be done with more coins but only four weighings, I don’t see how at this point…

12

I think I can do 40 coins in four weighings without a known coin.

[spoiler]Start with 13 on each side. If it is even, you are in the original case of this thread which you can solve.

If they are not even you have 13L and 13H. Put 6H and 3L on each side.

If it is even, then you are left with 1H and 7L. Put 3L vs 3L. From here it is easy.

If it is not even, then you are left with 6H and 3L. Put 2H and 1L on each side. From here it is easy.[/spoiler]

I think you can always do anything below the theoretical limit (3^n+1)/2 without a known coin, but to do the theoretical limit always requires one extra known coin for the even/odd reason already mentioned.

So for 2, 5, 14, 41, 122, etc. unknown coins, a known coin will reduce the required weighings by one.

13

Brilliant Carmady!

I plugged around with this all morning without hitting that solution. Under no circumstances will I attempt the 121 coin problem, however.:stuck_out_tongue:

14

Wasn’t that more or less exactly what I said? (Sulk!)

15

I wouldn’t phrase it as an even-odd issue, but a modulo-three issue. The first weighing must always divide the coins into three categories: The coins on the left pan, the coins on the right pan, and the coins not in either pan. Optimal efficiency (which is obviously required for a case at the information-theory limit) requires that all three categories be of equal size, which means that the total number of coins must be a multiple of three, but (3^n + 1)/2 = 2 mod 3, which means that you always need to add one known good coin for such cases (but never need two known good).

Also note that you only ever need to use the coin you brought for the first weighing, because after the first weighing, you’ll always have a set of coins from the unknown batch that have been proven good.

16

Indeed MaxTheVool. No slight intended.

Carmady merely spelled out the steps for this more slow-witted poster.

17

I disagree. You’re going to be weighing two groups against each other, with some number left unweighed. You always want the number left unweighed to be (the solution to the problem with n-1 weighings). Therefore the number you’re weighing is going to be the total number minus that number. If the number you’re weighing is even, you win. If it’s odd, you lose. So naively, if we were told “for n weighings, the most coins you can solve it for is x. For n+1 weighings, can you solve it for y?”, what matters is whether y-x is even or not.

18

I’m not saying that that reasoning is invalid, just that that’s not the way of expressing it that seems most natural to me. As with many math problems, there are many different ways of reaching the same conclusion.