# Game theory and probability

Sections: Pure, Games, Geometry, Physics, Large.

If you make any progress on any of these puzzles, or if you'd like to contribute a new one, then please do tell me about it.

Puzzles in this section:

### Matching birthdays

Matching birthdays

If we have a group of people, how large does the group have to be before there's a better than evens chance that two of them have the same birthday? "Birthday" here means "day of the year", we assume that all birthdays are equally likely, and we ignore leap years. Call two people with the same birthday a "match". We can ask several such questions:

Q: 1. How many people do we need for the probability of a match to be better than evens?

Q: 2. If we ask the birthdays of a sequence of people, what's the expected number until we find the first match?

Q: 3. If we pick a particular birthday, how many people do we need for the probability that someone is a match with the chosen date to be better than evens?

Q: 4. If we pick a particular birthday and then ask the birthdays of a sequence of people, what's the expected number until we find someone who's a match with the chosen date?

NB Many people (including a professional mathematician in a discussion on Radio 4) confuse Question 1 with Question 2, but they're different questions with different answers.

More generally, consider various other random choices such as thinking of a playing card or picking a lottery ticket, say that we have a match if there are two people that make the same choice, and ask the same questions.

[TB, 24 Jan 2002 and 20 Dec 2018]

Q: If drug B has a higher success rate (%age of cures) than drug A when given to women, and also when given to men, does it have a higher success rate when given to people in general?
[2 Apr 1997]

Q: What's the smallest possible "paradoxical" situation (i.e. smallest total number of people)? There are two versions of the problem depending on whether we allow entries to be 0.
[2 Apr 1997]

Q: Here's another striking version. A greengrocer sells apples at a fixed price per fruit, and oranges similarly. Each day an apple costs more than an orange. I buy fruit on several days. On average, did my apples cost me more per fruit than my oranges?
[20 Mar 2011]

### Throwing a die until running total crosses threshold

Throwing a die until running total crosses threshold

Q: I throw a die until the running total exceeds 12. What is the most likely final total?
[Puzzle Panel, BBC Radio 4, 2 Aug 1998]

Q: ??? Consider a country in which people live in high buildings and buy things from street vendors, using some form of money. Each building is equipped with a pulley in the eaves over which runs a long rope with a basket on it, operable by either party. Is there a system by which a resident and a vendor who don't trust each other can conduct trade? Note that either party may plan to play the opposite role with someone else later.
[rec.puzzles, 11 Apr 1996]

Top of page

### Tree measures

Tree measures

Q: Consider a random finite rooted binary tree. Any given leaf can be reached by a unique shortest sequence of steps from the root. Suppose we pick a leaf uniformly at random, but then take only the first k of these steps from the root. We might reach the leaf we first thought of (maybe in fewer than k steps), or we might reach a node that's a parent of that leaf. Define:

• the uniqueness probability = the probability that we reach the leaf we first thought of;
• the resolution = the reciprocal of the expected number of leaves that are children of the node we reach.

How do these values vary with k, for a large tree? Do the functions approach each other for large k? Do we need to be more specific about what a "random" tree is?

This puzzle was inspired by a discussion of the resolution of my TORUS tune-indexing system, which includes graphs of these functions for the system's database tree.

Top of page

Sections: Pure, Games, Geometry, Physics, Large.