As promised, I’m back to tell you more about myself and tickle your brain! I’m terribly sorry for giving such a short description of my background in my last post. If I had to describe myself in another $latex leq 5$ words, I’d write: “Breakdancing, bodybuilding physicist… Ladies: single.”
Problem 1: A thousand balloons numbered 1, 2, … , 1000 are arranged in a circle. Starting with balloon 1, every alternating balloon is popped. So balloon 1 is popped, balloon 3 is popped, balloon 5 is popped, and so on until balloon 999 is popped. But the process does not stop here! We keep going around the circle with the remaining balloons and pop every other one. So next balloon 2 is popped, balloon 4 is skipped, balloon 6 is popped, and so on. This process continues until only one balloon is left remaining; which is the last balloon standing?
It is of course easy to solve Problem 1 via brute force, but can you think of a more elegant solution? Do you really need to go around the circle $latex log(n)$ times? If you get stuck, try working on Problem 2 for a while:
Problem 2: A thousand people stand in single file on a game show. Each person is wearing a hat which is either black or white. Each person can see the hats of all the people in front of them in line but they cannot see their own hat. Starting with the person at the back of the line and progressing forward, the game show host will ask, “What color is your hat?” Each contestant is only permitted to answer “black” or “white.” For each correct answer, the host will donate $1 to charity. If the contestants are allowed to discuss a strategy before they are lined up and given their hats, how much can they guarantee will be donated to charity?
If you managed to solve Problem 2, Problem 3 should be easy.
Problem 3: Now each person is given a hat which is one of $latex n$ colors, and is allowed to answer the host’s question by giving any of the $latex n$ colors. How much can the contestants guarantee will be donated to charity?
Problem 4: You are given ten coin-making machines which produce coins weighing 2 grams each. Each coin-maker can produce infinitely many coins. One of the ten machines, however, is defective and produces coins weighing 1 gram each. You are also given a scientific balance (with a numerical output). How many times must you use the balance to determine which machine is defective? What if the weight of the coins produced by the rogue machine is unknown?
I happen to be very good personal friends with Count von Count. One day as we were walking through Splash Castle, the Count told me he had passed his arithmetic class and was throwing a graduation party! Alas, before he could host the get-together, he needed to solve a problem on injective mappings from powersets to subsets of the natural numbers…
Problem 5: The Count has a thousand bottles of apple juice for his party, but one of the bottles contains spoiled juice! This spoiled juice induces tummy aches roughly a day after being consumed, and the Count wants to avoid lawsuits brought on by the innocent patrons of Sesame Place. Luckily, there is just enough time before the party for ten of the Count’s friends to perform exactly one round of taste-testing, during which they can drink from as many bottles as they please. How can the ten friends determine which bottle is both tummy ache- and lawsuit-inducing? You can assume Count’s friends have promised not to sue him if they get sick.
Please let me know what you think of these problems in the comments! Too easy? Too hard? Want more? Tell me so!