A Touch of Luck | Puzzles for Programmers and Pros

The movie Intacto posits a world in which luck is a more or less permanent quality of a person. Lucky people are lucky at the gambling table and they are lucky at traffic intersections. But such people have to avoid physical contact with a certain group of people who know how to steal their luck by touch. Finding lucky people is the quest of one of the movie’s protagonists. In one case he tests the luck of possible recruits by having them run blindfolded through a forest. The winner is the one who gets to the destination first. Many others crash into one of the trees.

We will try a physically gentler game. In its general form, there are N people and B chances to bet. Every player knows the value of both N and B. Each person starts with an initial (not necessarily equal) wealth in units.

Each bet is an even money bet depending on the flip of a shared fair coin. So, if you bet an amount x and win, your wealth increases by x more. Otherwise you lose the x wagered.

Before each flip, each person bets an amount of his/her choosing (from 0 to any amount he/she has at that point) on either heads or tails.

The winner is the person having the greatest number of units after all B bets are done. If two people tie, then nobody wins. The units are worthless after the betting is done. So, a player receives a reward if and only if he or she is the absolute winner.

Warm-Up

Bob and Alice have the same number of units and Bob must state his bet first. Suppose there is just one remaining flip of the shared coin. What is Alice’s chance of winning?

Solution to Warm-Up

If Bob bets x on heads, then Alice could bet x+1 on heads and Alice will win on heads and will lose on tails. Alternatively, Alice could bet nothing and then Alice will win on tails. Either way, Alice has a probability of 1/2 to win.

Warm-Up 2

Alice and Bob are the only players again. Alice has more units than Bob. There are five more coin flips to do. If Bob must state his bet before Alice on every flip, then how can Alice maximize her chance to win?

Solution to Warm-Up 2

Alice can win the game every time. For each flip, Alice simply copies Bob’s bet. Suppose Bob bets b on heads. Alice bets b on heads too. Whether the shared coin lands on heads or tails, Alice will end up ahead of Bob.

Now here are some challenges for you.

Bob, Carol, and Alice play. Alice has 51 units, whereas Bob and Carol have 50 each. Bob must state his bet first, then Carol, and then Alice. Bob and Carol collude to share the reward if either wins. How can Bob and Carol maximize the probability that at least one of them will win if there is just one coin flip left?
Does the result change if Alice must state her bet first?
Suppose Bob has 51 units, and Alice 50. There are two coin flips left. Bob bets first for the penultimate flip. Alice bets first for the last flip. Does Bob have more than a 1/2 chance of winning? If so, how much more?
Suppose Bob has 51 units and Alice 50. Again, there are two coin flips left. This time, Alice bets first for the penultimate flip. Bob bets first for the last flip. Does Bob have more than a 1/2 chance of winning? If so, how much more?
Suppose Bob has 51 units and Alice 50. Again, there are two coin flips left. Again, Alice states her bet first in the penultimate round and Bob states his bet first in the final one. This time, Bob announces that he will bet 20 in the penultimate round, though he will wait to see Alice’s bet before saying whether he will bet on heads or tails. Can Alice arrange to have more than a 1/2 chance to win?

Like joining a ballet company, winning the Olympics, or getting ahead in a narrow hierarchy of power, the more competition there is for fewer spots, the more risk one must take. Let’s see whether you agree.

Bob, Alice, Rino, and Juliana have 100 units each and there are two flips left. Each person is out to win - no coalitions. Bob and Alice have bet 100 on heads. Rino has bet 100 on tails. Juliana must now state her bet, knowing that she will state her bet first on the last flip. What are her chances of winning if she bets 90 on either heads or tails? What should she bet?