UNSW CSE Puzzles

§§§

2. Puzzles related to probability Understanding probability theory is necessary for evaluating the behaviour of an algorithm in average (i.e., in finding the expected time of an algorithm for given probability distribution of inputs). Probability is tricky and often teases our “naïve” common sense, as you might experience yourselves.

2.1 Throwing Darts You throw two darts at a dart board, aiming for the center. The second lands farther from the center than the first. You then throw another dart at the board, aiming for the center. Assume your skill level is consistent. What are the chances that this third dart also lands farther from the center than the first?

2.2 Ten Letters A secretary typed 10 letters and addressed 10 corresponding envelopes. Her 3 year old daughter put these letters in the envelopes at random, one letter per envelope. What is the probability that exactly 9 letters will be placed in the correct envelopes?

2.3 “Truel” On an early morning, three rivals get together on an open spot in a dark wood to compose a quarrel by means of guns. A kind of duel, but with three persons: A, B and C. The rules of the game are:

They draw lots who may fire first, second and third.
Next, they will continue firing at each other in this order until only a single person is alive.
Every person decides himself at which person he fires.
Everyone knows that A hits (kills) in 100% of all shots, B hits (kills) in 80% of all shots and C hits (kills) in 50% of all shots.
Each person chooses his ideal strategy.
No one is killed by a stray bullet.

The Question: Who has the largest chance of surviving the ``truel’’, and how big is this chance?

2.4 Three Cards There are 3 cards: one is all red, one is all blue, and the third is blue on one side and red on the other. The cards are shuffled. You pick one at random and it is blue on the side facing you. What are the odds that it is also blue on the other side?

VARIANT: A bag contains a single bean, known to be either white or black, with equal probability. A new white bean is added to the bag, and it is shaken. A bean is taken back out, and it is white. What are the chances the remaining bean is also white?

2.5 Money in Boxes Someone shows you two boxes and he tells you that one of these boxes contains two times as much as the other one, but he does not tell you which one this is. He lets you choose one of these boxes, and opens it. It turns out to have $10. Now he gives you the opportunity to choose the other box instead of the current one (and skip the $10 of the first box), because the second box could contain twice as much (i.e. $20).
You reason as follows:

The second box contains either half of the money of the first box or twice as much as the first box. Thus, it either contains $20 with chance one half, or it contains only $5 with chance also one half. Thus the expected value is 1/2 * $20 + 1/2 * $5 = $12.5. Consequently, since the expected value is larger than the value of the first box, I should switch.

Question: Is your reasoning correct??

2.6 Quiz You are a participant in a quiz. The quizmaster shows you three closed doors. He tells you that behind one of these doors there is a prize, and behind the other two doors there's nothing. You select one of the doors, but before you open it the quizmaster deliberately picks out a remaining empty door and shows that there is nothing behind it. The quizmaster offers you a chance to switch doors with the remaining closed door.
The Question: Should you stick to your choice?

2.7 Unfair Coin Generate even odds from an unfair coin. For example, if you thought a coin was biased toward heads, how could you get the equivalent of a fair coin with several tosses of the unfair coin?

2.8 Buss Stop On a bus stop two busses arrive, A and B, going towards my home. Each of them arrives in exact 15 minute intervals. I travel every day, and pick the FIRST bus to come after I arrive at the bus stop. I come to the bus stop at random times. After one year, it turned out that, even though the bus schedule did not change, I took bus A four times more often than bus B. How is this possible?

2.9 Hats Three people are given hats. Each hat is either red or blue, chosen at random. Each person can see the other 2 hats, but not their own. They each must simultaneously either guess their own hat's color, or pass. No communication is allowed, although they can agree on a strategy ahead of time. What strategy will give them the best chances of at least one person guessing right, and nobody guessing wrong?