I don't remember where the last Puzzle Land left off, so I'll pretend that you were stuck in jail with a warden who used to be a villain in a James Bond movie. He gives each prisoner a black or white hat and forbids anyone to communicate by any means other than his pet homing pigeon, which is trained to fly around the prison counterclockwise while counting each cell that it encounters and stopping whenever it reaches a prime number. After reading the remainder of the rules and leaving everyone in their cells to work out their hat color with the pigeon, you're the first to get the pigeon.
Realizing that the warden never specifically forbade taking off your own hat and looking at it, you do so. You let the pigeon loose so that any other prisoners who have enough sense to look at their own hats will go free, and good riddance to those who would depend on some cockamamie bird-brained scheme to escape.
After being released from prison, you then visit the castle of Puzzle Land and are called in service to the king. One of his knights takes you to a room with a pile of 27 coins, and explains that they are all gold and of equal weight except for one counterfeit that is slightly heavier (with the difference in weight between the counterfeit and a real coin being much smaller than the weight of a real coin). Your job, using only three weighings with the Royal Balance, is to identify the counterfeit and throw it away so the knight can bring the real coins to the king.
Knowing full well how to handle this, you place nine coins on one pan and nine on the other. Seeing that one of the pans is heavier, you say "All right, looks like the counterfeit is among these nine."
The knight, sounding as though something is amiss, says “Uh, you do know that's the Royal Balance, right?"
You: Yes, what of it?
Knight: Don't be too sure that the counterfeit is among those nine.
You: What? Why not? They were in the heavier pan compared to another with an equal number of coins, so the counterfeit must be in there.
Knight: Like I said, this is the Royal Balance. The one we use to trade with merchants. The pan that was lowest is the one that always weighs one coin heavier than the other.
You: ...
Knight: Well how do you think the king built such an empire? Magical royal elves?
You: ...
Knight: That counts as one of your three weighings, by the way.
You: ... now you know there's no way for me to identify the counterfeit in two more weighings, right?
Knight: Well then just find as many as you can that are genuine. As long as we don't give him a fake, maybe he won't bother to count them and figure out that you screwed up.
You: …
Knight: Look, I'll even make it easy for you by de-rigging the balance so it works like normal.
As the knight finishes messing with the balance and you're about to get started, the royal kitteh comes along, hops up onto one pan of the balance, and (because it's a kitteh) promptly falls asleep. The knight warns you that aggravating the royal kitteh in an attempt to get it to move is punishable by instant slaying, so the cat will stay where it lays. But he tells you that the kitteh weighs exactly the same as N real gold coins. Using that fact, and the fact that the kitteh is not completely blocking you from putting some coins on the same pan with it, with two more weighings you get the worst possible luck as far as narrowing down where the counterfeit lies, but you toss out N+1 coins and give the rest to the king without being beheaded for giving him a counterfeit. As it turns out, if the kitteh were any heavier, you would have ended up tossing out N or fewer coins instead of N+1.
To clarify that last bit, if the kitteh did not weigh N coins but instead weighed M = N+X coins for any positive integer X, then you would have tossed out M or fewer coins rather than M+1 coins in the worst case scenario.
Question
plasmid
I don't remember where the last Puzzle Land left off, so I'll pretend that you were stuck in jail with a warden who used to be a villain in a James Bond movie. He gives each prisoner a black or white hat and forbids anyone to communicate by any means other than his pet homing pigeon, which is trained to fly around the prison counterclockwise while counting each cell that it encounters and stopping whenever it reaches a prime number. After reading the remainder of the rules and leaving everyone in their cells to work out their hat color with the pigeon, you're the first to get the pigeon.
Realizing that the warden never specifically forbade taking off your own hat and looking at it, you do so. You let the pigeon loose so that any other prisoners who have enough sense to look at their own hats will go free, and good riddance to those who would depend on some cockamamie bird-brained scheme to escape.
After being released from prison, you then visit the castle of Puzzle Land and are called in service to the king. One of his knights takes you to a room with a pile of 27 coins, and explains that they are all gold and of equal weight except for one counterfeit that is slightly heavier (with the difference in weight between the counterfeit and a real coin being much smaller than the weight of a real coin). Your job, using only three weighings with the Royal Balance, is to identify the counterfeit and throw it away so the knight can bring the real coins to the king.
Knowing full well how to handle this, you place nine coins on one pan and nine on the other. Seeing that one of the pans is heavier, you say "All right, looks like the counterfeit is among these nine."
The knight, sounding as though something is amiss, says “Uh, you do know that's the Royal Balance, right?"
You: Yes, what of it?
Knight: Don't be too sure that the counterfeit is among those nine.
You: What? Why not? They were in the heavier pan compared to another with an equal number of coins, so the counterfeit must be in there.
Knight: Like I said, this is the Royal Balance. The one we use to trade with merchants. The pan that was lowest is the one that always weighs one coin heavier than the other.
You: ...
Knight: Well how do you think the king built such an empire? Magical royal elves?
You: ...
Knight: That counts as one of your three weighings, by the way.
You: ... now you know there's no way for me to identify the counterfeit in two more weighings, right?
Knight: Well then just find as many as you can that are genuine. As long as we don't give him a fake, maybe he won't bother to count them and figure out that you screwed up.
You: …
Knight: Look, I'll even make it easy for you by de-rigging the balance so it works like normal.
As the knight finishes messing with the balance and you're about to get started, the royal kitteh comes along, hops up onto one pan of the balance, and (because it's a kitteh) promptly falls asleep. The knight warns you that aggravating the royal kitteh in an attempt to get it to move is punishable by instant slaying, so the cat will stay where it lays. But he tells you that the kitteh weighs exactly the same as N real gold coins. Using that fact, and the fact that the kitteh is not completely blocking you from putting some coins on the same pan with it, with two more weighings you get the worst possible luck as far as narrowing down where the counterfeit lies, but you toss out N+1 coins and give the rest to the king without being beheaded for giving him a counterfeit. As it turns out, if the kitteh were any heavier, you would have ended up tossing out N or fewer coins instead of N+1.
To clarify that last bit, if the kitteh did not weigh N coins but instead weighed M = N+X coins for any positive integer X, then you would have tossed out M or fewer coins rather than M+1 coins in the worst case scenario.
How much does the kitteh weigh?
Edited by plasmidLink to comment
Share on other sites
8 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.