Can the bijection for the Lost Boarding Pass Probability Problem, be formulated or pictured?
The two proofs below moot "bijection", but I don't see a formula. 1. Does the bijection have an explicit formula?
- Can this bijection be pictorialized? My 16 y.o. kid doesn't understand the abstract, Daedalian phrasing below.
hunter's answer dated Dec. 4 2013
Claim 3: There is a bijection between the set of admissible seatings in which the final passenger gets his seat and the set where he doesn't.
Proof: Suppose for an admissible seating $S$ that passenger $n$ is the first to choose one of {first passenger's seat, last passenger's seat}. By claim $2$, there is a unique admissible seating $T$ which agrees with $S$ except that passenger $n$ and the final passenger make the opposite decision ($T$ matches $S$ until passenger $n$ sits, then by Claim 2, $T$ must continue to match $S$ until the final passenger).
azjps comments on A combinatorics problem that I was never able to solve.
Here's a bijective proof: let all $n$ individuals find a seat according to the rule. For each sequence in which the $n$th person sits in the seat assigned to the $k$th person, consider the corresponding sequence in which the $n$th and $k$th individuals are swapped (so the last person is in the right seat). Both sequences have equal probability and it is not difficult to verify that this correspondence is a bijection, so the answer is 1/2.
1 answer
The bijection is just to swap the people sitting in the first and last seats.
I feel like a ‘formula’ is more machinery than this simple concept is worth, but here, if this helps: let $P$ be the set of permutations on $\{0\ldots n - 1\}$, where for $p \in P$, $p(s)$ is the number of the passenger who sits in seat $s$. Then there exists a bijection $-_{\operatorname{swap}} : P \to P$, defined with the following formula: $$ p_{\operatorname{swap}}(s) = \left\{\begin{array}{ll} \, p(n - 1) \quad & \text{if} \, s = 0\\ \, p(s) \quad & \text{if} \, 0 < s < n - 1\\ \, p(0) \quad & \text{if} \, s = n - 1 \end{array}\right. $$
I'm not going to draw a picture of the people in the first and last seats switching places. Please try to imagine that yourself.
0 comment threads
0 comment threads