Misdirected Letters Puzzle

This puzzle describes a random matching of personalized items to labeled destinations, with the twist that a successful outcome requires a complete mismatch: no item may land where it "belongs." In the story, job application letters are placed into addressed envelopes by someone who is not paying attention, and you are asked for the probability that every letter is misdirected. It is a canonical example of counting arrangements that avoid all "natural" matches, often used in combinatorics courses and interview settings to test comfort with structured counting rather than ad hoc casework.

Mathematically, the question leans on the concept of derangements and on the Inclusion-Exclusion Principle as the systematic way to handle overlapping constraints. An interviewer wants to see if the candidate can model the situation as permutations with forbidden fixed points, set up the counting cleanly, and avoid double counting. They are also checking for an ability to translate a word problem into a symbolic framework, recognize a standard structure, and express the final probability in a simplified, logically justified form.

What it tests

The core structure here is the enumeration of arrangements with forbidden positions, known as derangements. More generally, when counting the number of ways to assign objects to slots with constraints (such as 'no object in its original slot'), the Inclusion-Exclusion Principle systematically corrects for overcounting by alternately adding and subtracting the counts of arrangements that violate increasing numbers of constraints. The reason this works is that direct subtraction of all single violations removes too much—so we must add back in the cases where two constraints are violated, subtract those with three, and so on, ensuring each arrangement is counted exactly once. This principle applies to any problem where objects must avoid certain positions or matches, and the constraints overlap. The alternating sum arises because each arrangement with $k$ fixed points is included in exactly $\binom{n}{k}$ terms, so the principle ensures proper accounting.