You are given four cards. Each has a symbol on it. The symbols are A,D,3, and 7. You are told that each card has a number on one side and a letter on the other. Which cards must you turn over to establish the following rule: If a card has an A on one side, then it has a 3 on the other.
19 comments:
All four.
No, wait. You don't need to turn over the card marked "3." But the other three, you do.
No, sorry. It is given that there is a number on one side and a letter on t'other.
You have to flip A and 7.
Now, let's say your reward for playing this game is 12 gold coins. However, because we're living in Logic Puzzle Land, one of the coins is a fake; you can identify it because it does not weight the same as the other 11 coins. You need to find the fake both so you can sue Logic Industries, Inc. for nonpayment and so you don't accidentally introduce impurities when you melt down the coins to make a solid-gold slide rule. That'll impress the other Mathletes.
Your only measurement tool is a simple balance scale, where you can put coins on both sides and see if they balance. You do not have a set of known weights, a known-good coin, or anything else that might help, because EVERYTHING in Logic Puzzle Land (except the coins) is made out of the same massless material used to make weightless potato sacks.
How many weighings does it take to find the fake coin?
Well, the best I can do is four weighings with a one-in-three chance of being done in three.
Laura, I have absolutely no idea.
Seriously, this stuff is so confusing.
I think three is the minium. Do four and four to start, and from that you know which group of 4 the different coin is. (If even, it's the four you didn't weigh). From that group of 4, do 2 and 2, so you'll know which group of 2 the different coin is in, and then one and one and you're all set.
If you weigh two sets of 4 and they don't weigh the same, you still don't know which set has the fake coin in it. You don't know whether the fake coin is heavier, or lighter than a regular coin.
Laura, you don't flip the 3 because you don't care what's on the other side. If an A is on the other side you're fine, and if any other letter is on the other side, you're fine also because it's not part of the "if..then." However, you DO flip the 7 because you want to be sure there isn't an A on the other side, which would make your statement false.
Anonymous,If you weigh four against four and they are unequal you still have eight coins in the mix after one weighing.
My approach: Split the 12 into 4 groups of 3. weigh one group against another. If equal, it's in one of the other two groups. If unequal, it's in one of the two groups and the other two groups are good. 2nd weighing: weigh a known good group against one of the suspected bad groups which will tell you which group of three is bad. Third weighing: two of the three coins from the bad group. If equal, the bad coin is the one not weighed. If unequal, weigh one against a known good coin and you're done.
Ah, I thought we know one was lighter.
Hint: your goal should be to have at most 3 potential fakes after the second weighing, and to have proven that each potential fake could only be fake in one way.
In other words, you would have three suspect coins at the end, and each would be potentially heavy or potentially light but not both.
James, is or isn't the method I outlined two posts above yours the solution? After two weighings I have three potentially bad coins. I can identify the specific coin after, at most, two more weighings. Is there some way to identify the specific coin in three weighings total? The original problem didn't mention determing whether it was light or heavy, just that it was bad.
Nope, the fake coin can always be found in three weighings, and, while it wasn't part of the problem, you can also figure out if it's light or heavy. (Actually, you can crank it up to 13 coins in 3 weighings if you don't care about knowing which kind of fake you have.)
The trick is to eliminate as many fake-coin possibilities as you can at every step. You start out with 24 possibilities -- each coin could be heavy or light. Let's say the coins are numbered 1-12. By putting 1-4 on one side and 5-8 on the other for the first weighing, you always eliminate 16 possibilities:
1) If there is an imbalance, you know that the four on the light side can't be heavy, the four on the heavy side can't be light, and 9-12 are neither heavy nor light.
2) If the scale balances, you know that 1-8 are neither heavy nor light.
The next step is to eliminate another 5 possibilities to get down to the 3-possibility case that we know can be solved in a single weighing. We'll get back to case (1). In case (2), you can then weigh 9 and 10 against 11 and a known-good coin (call it G). If they balance, 12 is bad and you can use the last weighting to check whether it's heavy or light compare to G.
(This is the place where 13 would sneak in -- if 12 balanced with G, you'd know 13 was the fake.)
Otherwise...well, to make it less tortured, let's say 9 and 10 are heavier than 11 and G. Put 9 on one side and 10 on the other; the heavier one is the fake, and, if they balance, 11 is a light fake.
Now, case (1). Let's assume 1-4 were heavier than 5-8. Load up the scale with 1,2,5,6 on the left side and 3,G,G,G on the right. If there's an imbalance -- let's say the the right is heavier-- we have at most three possibilities remaining (5 or 6 could be light, 3 could be heavy), and we showed before how to deal with that case. If the scale balances, then 4 is heavy or 7 or 8 is light, and...we showed before how to deal with that.
I know you were around for my birth, but I wasn't around for yours. Maybe you were adopted!
James, great solution. I think there was zero chance of my coming up with it from a cold start. Feel free to post another if you are so inclined.
Lucy, pretty funny.
I like coin problems because they make you squeeze every last drop of information out of a simple measurement. (And because I'm a weirdo.) The method actually ends up being pretty close to Tom's approach -- it's really just two more coins on the scale for the first measure and some clever arrangement on the second to, in effect, compare three groups of three (okay, really 3-2-3) with a known good set. Of course, these optimizations make for a very counterintuitive process.
For a really counterintuitive version, check out this solution. It turns out you can find the fake coin in three predetermined weighings (i.e., you always put the same coins on each side of the scale regardless of the results of the last weighing).
James, it's time to go back to work. Waaaay too much time on your plate!
Oh, Scott, leave him alone. He's entertaining the Murphies. BTW, does "too much time on your plate" mean you're "having seconds"?
James, the independent weighing solution is brilliant. I believe you can do 39 coins in four weighings. I'm working out the kinks-the hard part is eliminating the itineraries that are opposites and having an equal number of coins on each side. Stay tuned.
Post a Comment