Start Simple Basic

Lecture Notes

Starting with a simple case when solving a brain teaser is always a crucial technique. Many brain teasers use large numbers to create an illusion of difficulty and complexity. If you're unsure how to tackle such a problem, first ignore the large number. Instead, begin with the simplest case and gradually increase the number, aiming to discern a pattern and, thereby, the solution.

Quite often, such problems may evolve into recursive problems. For example, the challenge below may seem extremely daunting. You're not alone if you feel stumped. However, by considering the cases with just $2$ or $3$ passengers, it becomes relatively easy to see that the odds remain constant at $50%$. Thus, an educated guess would be that the probability always stays at $50%$, regardless of the number of passengers.

This solution is indeed correct. The challenge lies in justifying the result, which involves the concept of recursion: Can we make the case of $100$ passengers equivalent to a scenario with a smaller number? If so, by repeating the process, we can demonstrate that the scenario with $100$ passengers is equivalent to the case of $2$, i.e., $100\rightarrow \cdots \rightarrow 3 \rightarrow 2$.



$\textbf{Seat on a Flight}$

There are $100$ airline passengers waiting in line to board a $100$-seat plane. For convenience, let the $n^{th}$ passenger in line hold a ticket for the $n^{th}$ seat. For some reasons, the first passenger decides to pick a random seat instead of his assigned seat (it is still possible that he or she picks the $1^{st}$ seat). Everybody will sit on his or her assigned seat unless this seat is occupied. In the latter case, that passenger will pick a random seat for himself or herself. Find the probability that the last passenger will sit on his or her assigned seat.

Assignment >>>

Don't worry if you can't solve this example; it is indeed a very challenging problem. The assignment itself is much easier. However, the purpose of starting with a challenging example is to highlight that brain teasers emphasize the method of thinking rather than specific subject matter knowledge. In this example, the key lies in finding a way to reduce the number of passengers, which plays a crucial role. Although this essentially involves recursion (or induction), a fundamental technique in mathematics and programming, one does not need a background in these fields to discover a solution.