Advanced Counting

Why it works. The cases "last piece is a square" and "last piece is a domino" do not overlap and together cover every tiling, so their counts add. Removing the last piece is a one-to-one correspondence with tilings of the shorter strip, so each case is counted by an earlier term. That is the whole recipe: split by what happens at the end, check the cases are disjoint and exhaustive, and identify each case with a smaller instance.

Spotting it. Condition on the last character. If it is $0$, anything valid of length $n - 1$ can precede it. If it is $1$, the character before must be $0$, and anything valid of length $n - 2$ precedes that.

Step 1. $a_n = a_{n-1} + a_{n-2}$, with $a_1 = 2$ ($0$, $1$) and $a_2 = 3$ ($00$, $01$, $10$).

Step 2. $a_3, \dots, a_{10} = 5, 8, 13, 21, 34, 55, 89, 144$. The answer is $144$.

Spotting it. Now condition on how the string ENDS: in $0$, in $01$, or in $011$. These are disjoint, cover every valid string, and in each case what precedes the ending is an arbitrary valid string.

Step 1. $t_n = t_{n-1} + t_{n-2} + t_{n-3}$, with $t_0 = 1$ (the empty string), $t_1 = 2$, $t_2 = 4$.

Step 2. $t_3, \dots, t_{10} = 7, 13, 24, 44, 81, 149, 274, 504$. The answer is $504$.

Check $t_3$: of the $8$ strings of length $3$ only $111$ is excluded ✓

Spotting it. "Condition on the last step" on a grid is Pascal's rule: the paths to a point come from the point to its left or the point below. Two ways to finish: complement, or fill in the grid with $(3, 2)$ set to $0$.

By complement. All paths: $\dbinom{10}{4} = 210$. Paths through $(3, 2)$: $\dbinom52$ ways to reach it times $\dbinom52$ ways to finish, $10 \cdot 10 = 100$. So $210 - 100 = 110$.

By the grid. Write $1$ along the bottom row and left column, add left-plus-below everywhere else, and put $0$ at the blocked point. The top-right entry is $110$, matching.

Why it works. Write the total as a sum of indicators, $X = I_1 + I_2 + \cdots + I_m$, where $I_k$ is $1$ if the $k$th small event happens and $0$ otherwise. Expectation is an average over outcomes, and an average of sums is the sum of the averages, whatever the dependence between the $I_k$. Each $E[I_k]$ is just the probability of its event. So "expected number of ..." becomes "add up the probabilities of each ...", one easy probability at a time.

Spotting it. The pairs overlap and are far from independent, but linearity does not care: sum over the $9$ adjacent positions.

Step 1. For a fixed pair of neighbouring positions, the probability they hold a boy and a girl is $\dfrac{5 \cdot 5 \cdot 2}{10 \cdot 9} = \dfrac{5}{9}$.

Step 2. The expected count is $9 \cdot \tfrac59 = 5$.

Spotting it. One indicator per adjacent pair of positions again.

Step 1. For each $i$, the two numbers in positions $i$ and $i + 1$ are equally likely to be in either order, so the probability of a descent is $\tfrac12$.

Step 2. The expectation is $9 \cdot \tfrac12 = \tfrac92$, so $m + n = 11$.

Spotting it. Count distinct values by one indicator per face value: $I_v = 1$ if the value $v$ appears at least once.

Step 1. $P(v \text{ appears}) = 1 - \left(\tfrac56\right)^3 = \tfrac{91}{216}$.

Step 2. Six values: $6 \cdot \tfrac{91}{216} = \tfrac{91}{36}$, in lowest terms since $91 = 7 \cdot 13$. So $m + n = 127$.

Sanity check: the value lies between $1$ and $3$ ($\tfrac{91}{36} \approx 2.53$) ✓

The expected wait for HH is $6$ flips but for HT only $4$, even though each pattern has probability $\tfrac14$ at any fixed pair of positions. The difference is what a failure costs: from "just saw H", a T sends the HH-hunter back to the start, while an extra H leaves the HT-hunter exactly where it was, one flip from done. State equations capture that; intuition usually does not. Always include the starting state, and give the absorbing states their known values explicitly.

Asking for the probability that a specific person ends up in a specific seat, when the process treats everybody alike, gives $\tfrac1n$ with no computation. The classic case is the airplane-seating problem, whose answer is exactly $\tfrac12$ for any $n \ge 2$, because the process is symmetric between the first passenger's seat and the last passenger's seat.

Step 1 — states: $S$ (no progress), $H$ (one head so far).

Step 2 — $E_S = 1 + \tfrac12E_H + \tfrac12E_S$ and $E_H = 1 + \tfrac12\cdot0 + \tfrac12E_S$.

Step 3 — the first gives $E_S = 2 + E_H$; substituting into the second, $E_H = 1 + \tfrac12(2 + E_H)$, so $E_H = 4$ and $E_S = 6$. Six flips on average — compare HT, which takes $4$.

Spotting it. The future depends only on the current position, so let $p_k$ be the probability of reaching $4$ first from $k$; then $p_0 = 0$ and $p_4 = 1$.

Step 1. One-step equations: $p_k = \tfrac23p_{k+1} + \tfrac13p_{k-1}$ for $k = 1, 2, 3$. Rearranged: $p_{k+1} - p_k = \tfrac12(p_k - p_{k-1})$. The GAPS between consecutive $p$'s halve each step.

Step 2. With first gap $g = p_1 - p_0 = p_1$, the gaps are $g, \tfrac g2, \tfrac g4, \tfrac g8$, and they add to $p_4 - p_0 = 1$: $\tfrac{15}{8}g = 1$, so $g = \tfrac{8}{15}$.

Step 3. $p_1 = \tfrac{8}{15}$, so $m + n = 23$.