A game show has n closed doors. A car is behind one of them, equally likely to be any door, and goats are behind the rest. The contestant points at one door. The host, who knows where the car is, then opens k of the other doors, always choosing only doors with goats (at random among those, if there is a choice). The contestant may now
- stay with the door first chosen, or
- switch to one of the doors that are still closed (not the first choice), picked at random, each equally likely.
Write many_doors(n, k) that returns (stay, switch): the exact probability of winning the car with each strategy, each as a tuple (numerator, denominator) in lowest terms.
Examples
Input: n = 3, k = 1
Output: ((1, 3), (2, 3))
Explanation: the classic game: staying wins only if the first choice was right.
Input: n = 5, k = 2
Output: ((1, 5), (2, 5))
Explanation: after the host opens 2 goat doors, 2 doors are left to switch to.
Input: n = 10, k = 0
Output: ((1, 10), (1, 10))
Explanation: with no doors opened, switching is just another random guess.
Constraints
3 <= n <= 10**90 <= k <= n - 2
Goals
- Split a random process into cases whose probabilities are easy to find
- Reason about what the host's knowledge does and does not change
- Check a formula against a brute-force enumeration of small cases