Uncooperative Crickets

My Spring Break

Here is how I spent one of my spring break days (yesterday). First, I wrote up a draft of a paper. Then, I proceeded to look at three coin problems.

1. Suppose that you are sitting at a square table with an upside down cup on each of the four corners. There is a coin under each cup. Your goal is to make it so that either all four coins are heads, or all four coins are tails. Here are the rules:
   
   There will be "turns." Each turn, you are allowed to pick up any two of the cups, and then change those two coins to be in whatever orientation you like (e.g. heads/heads, tails/tails, heads/tails, or tails/heads). Once you put the coins down (and the cups over them, again), one of two things happen: either all four coins are matching, which is indicated by a light going off in the middle of the table, or the table spins around. When the table spins, you are unable to follow it because it is spinning so fast. The table will stop, and you will be allowed another "turn." You may, again, pick any two of the cups, although you will not be able to tell which cups you looked at last turn (because of all of the spinning). Continue this process of picking two coins followed by the table spinning until you have won.
   
   Question: is there a strategy that will allow you to win without getting lucky? If so, what is it? You should assume that you have the worst luck in the world, and cannot ever say "eventually I will have to win with this process."
   
   If there is no such strategy, prove that there is no such strategy.
   
   (this was from an email from one of Skye's friends)
   
   
2. Assume that you are sitting at a table, blindfolded and gloved. On the table in front of you are some number of coins. You can feel the coins well enough so that you know how many coins there are total, but you cannot feel them well enough to determine if they are "heads" or "tails" (because of the gloves). Suppose also that someone tells you how many "heads" there are on the table. So you know the total number of coins, and the total number of heads, but nothing else. You can pick up any of the coins and flip them over, and you can repeat this process as often as you like. You can do nothing else.
   
   Question: can you sort the coins into two piles so that each pile contains the same number of heads?
   
   (this was from a book by Ed Burger)
   
   
3. Suppose that you have 12 coins that look absolutely identical. In fact, 11 of the coins are completely identical. The 12th coin is counterfeit, and weighs either just a little more or a little less than the other 11 coins. You do not know which coin is the counterfeit.
   
   Your task is to find the the counterfeit coin by using a balance (one of the old scales that you see kicking around the justice department). Can you find the counterfeit coin by only doing three weighings (or fewer)?
   
   (this is an old problem that hangs around math, physics, and computer science departments. I had solved it before)
   
   
4. You have 10 bags of gold coins, 10 coins per bag, 10 grams per coin, but one bag of coins weigh only 9 grams per coin (because of low quality). How do you find out which bag contains low quality gold coins? You may use a scale (now a bathroom-type scale, rather than a balance) only one time.
   
   (another oldie. I had remembered this solution, so that wasn't much fun).
   
   

Then I started to look for other problems. I went to Just Riddles and More (which has a completely ridiculous name), and found this problem:

Q: You have 9 gold coins. All 9 coins look exactly the same but one coin is a fake and is either lighter or heavier than the other 8 coins. You have a scale - balance type with 2 trays - but can only load it twice. How do you find the fake gold coin?

I worked on this for a while, and decided that it was probably impossible. I was right. The solution totally cheats. This frustrates me. Then I noticed some alternate solutions to problems similar to the ones I asked above, and they were solved similarly. Some people should not be allowed to have webpages. I should have known not to go to the website just by the web address.

posted by Dirk Awesome @ 1:08 PM