Problem-Solving Strategies

Fence posts are placed every $2$ m along a straight $10$ m fence, including both ends. How many posts? The reflex answer $10 \div 2 = 5$ counts the gaps. A drawing shows posts at $0, 2, 4, 6, 8, 10$: six posts for five gaps. Understanding the problem — here, literally drawing it — is the step that catches the error.

How many regions do $n$ lines in general position (no two parallel, no three through a point) cut the plane into? $n = 0, 1, 2, 3$: $1, 2, 4, 7$. Differences $1, 2, 3$: the $n$th line crosses the $n - 1$ earlier ones at $n - 1$ points, which cut it into $n$ pieces, and each piece splits one region in two. So $R(n) = R(n - 1) + n$, and $R(n) = 1 + (1 + 2 + \cdots + n) = 1 + \dfrac{n(n + 1)}{2}$, proved by induction with exactly that step.

Seven cups, all face up; a move flips exactly two. Can all end face down? Each move changes the number of face-up cups by $-2$, $0$, or $+2$: the parity of face-up cups never changes. It starts odd ($7$) and the goal is $0$, even. Impossible. $\blacksquare$

Remove two opposite corners of an $8\times8$ board. Can the rest be tiled by dominoes? Each domino covers one dark and one light square. Opposite corners have the same color, so $30$ of that color and $32$ of the other remain, and $31$ dominoes would need $31$ of each. No. $\blacksquare$

Three numbers $3, 4, 5$ are on a board. A move replaces two of them, $a$ and $b$, by $0.6a - 0.8b$ and $0.8a + 0.6b$. Can the board ever read $4, 6, 12$? The sum of squares is invariant: $(0.6a - 0.8b)^2 + (0.8a + 0.6b)^2 = (0.36 + 0.64)a^2 + (0.64 + 0.36)b^2 = a^2 + b^2$, since the $ab$ terms cancel. It starts at $9 + 16 + 25 = 50$, while $16 + 36 + 144 = 196$. Impossible. $\blacksquare$

Color a $5 \times 5$ board like a checkerboard with dark corners: $13$ dark and $12$ light cells. Remove a light cell next to a corner: $13$ dark and $11$ light remain, and $12$ dominoes would need $12$ of each, so no tiling exists. Remove a corner instead: $12$ and $12$ remain, and the coloring proves nothing — in fact that board can be tiled. A balanced count is not a proof of possibility.

Can a $6 \times 6$ board be tiled by $9$ T-shaped pieces of four cells? Checkerboard it: $18$ dark and $18$ light. Wherever a T is placed, its row of three alternates (two cells of one color around a middle of the other), and the fourth cell, touching the middle, has the color opposite to the middle. So each T covers $3$ cells of one color and $1$ of the other: an odd number of dark cells. Nine odd numbers add to an odd number, but the board has $18$ dark cells. No tiling. $\blacksquare$

Can a $6 \times 6$ board be tiled by $1 \times 4$ bars? The area, $36$, is a multiple of $4$, and the checkerboard balances ($18$ and $18$) — neither rules it out. Color cell $(i, j)$ by $(i + j) \bmod 4$. Any bar, horizontal or vertical, covers four consecutive values of $i + j$, one of each class. So $9$ bars cover $9$ cells of each class. But the classes $0, 1, 2, 3$ have $9, 10, 9, 8$ cells. No tiling. $\blacksquare$

A row of numbers is sorted by repeatedly swapping two neighbors that are out of order. Does it always finish? Count the inversions: pairs (not just neighbors) in the wrong order. Swapping an out-of-order neighboring pair fixes that pair and changes no other pair's order, so the count drops by exactly $1$. It cannot drop below $0$, so the process stops — and it takes exactly as many swaps as there were inversions. For $3, 1, 4, 2$ the inversions are $(3, 1), (3, 2), (4, 2)$: exactly $3$ swaps.

Prove that the members of any club can be split into two rooms so that everyone has at most half of their friends in their own room. Start with any split. If someone has more than half of their friends in their room, move them. Their friendships inside a room change from (friends in old room) to (friends in new room), a strict decrease; nobody else's friendships inside rooms change. So the total number of friendships inside rooms strictly decreases, and since it is a non-negative integer, the moves stop. When they stop, nobody has more than half of their friends in their own room. $\blacksquare$

There are $21$ counters. Two players alternately take $1$, $2$ or $3$; whoever takes the last counter wins. The first player wins: take $1$, leaving $20$. Whenever the opponent takes $k$, take $4 - k$. After each of your turns the number left is a multiple of $4$ — the property you restore — so the opponent never faces $0$ on their turn, and you take the last counter.

The numbers $1, \ldots, 10$ are on a board; a move erases $a, b$ and writes $|a - b|$. What can the last number be? Flawed: "the sum is invariant, so the last number is $55$". It is not invariant — erasing $7$ and $3$ and writing $4$ lowers the sum by $6$. What is invariant is the PARITY of the sum: $a + b$ and $|a - b|$ differ by $2\min(a, b)$, an even number. The sum starts at $55$, odd, so the last number is odd. The invariant does not say which odd number; that would need a further argument.