Location: TB Homepage > Puzzles > Game theory and probability

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

In a group of 23 people the chances are better than evens that two will share a birthday. Consider a variety of other random choices, such as thinking of a playing card, picking a lottery ticket, etc. Say that we have a match if there are two people that make the same choice.

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 (or whatever) of a sequence of people, what's the expected number until we find the first match?

[TB, 24 Jan 2002]

Spoiler --- Top of page

Simpson's paradox

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]

Spoiler --- Top of page

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]

Spoiler --- Top of page

Trading by basket

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

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.