Stand Up & Math · Teacher Answers
Gridlock
Not for distribution · Arrangements with repeats · Lattice paths · Full worked solutions
Same recipe as The Starting Five: the first idea in each phase (divide by the repeats, a route is a word, subtract the roadblock routes, add the neighbours’ labels) is quick to find, and the weight sits in the proofs, in combining two conditions without double counting, and in Task 3e, where intuition (“close the middle”) turns out to be wrong. Phase 2 reuses The Starting Five in a new costume: a route is at once an arrangement with repeats and a selection of positions. Phase 4 proves Pascal’s rule a second time. Do not accept “it worked for a few grids” as a proof. Hint ladders are for you only: one rung at a time, only if a group is stuck on the idea rather than the write-up.
“You run a courier company in a city whose streets form a perfect grid. Couriers only ever walk east or north, never backtracking, so every route from the south-west depot to a north-east address has the same length. The council prices deliveries by how many different routes exist, and its road crews keep closing intersections. Your formulas have to work for any size of city and any closure, not just the map in front of you, and you will need to justify each one.”
Students work entirely on their whiteboard. Display phase content on student devices only after each gate is unlocked.
| 0–2 min | Oral launch; random groups at whiteboards |
| 2–15 min | Phase 1, Twin Trouble (1f is the long task) |
| 15–27 min | Phase 2, Crosstown |
| 27–41 min | Phase 3, Detour (3e is the long task) |
| 41–54 min | Phase 4, Pascal’s Grid |
| 54–60 min | Consolidation; challenge groups present |
When some letters are identical
Compare with \(n!\): \(3!=6,\ 4!=24,\ 4!=24,\ 5!=120,\ 6!=720\). The ratios are \(2,\ 6,\ 4,\ 12,\ 36\), which are exactly \(2!\,1!,\ 3!\,1!,\ 2!\,2!,\ 2!\,3!,\ 3!\,3!\).
The ratio pattern is the discovery. Groups that tabulate (word, \(n!\), count, ratio) find it fastest. A tempting first rule is “divide by the number of repeated letters”: AABB seems to support it (\(24 \div 4 = 6\)), but AAAB breaks it (\(24 \div 3 = 8\), not 4). That moment is the point: the data forces \(a!\), not \(a\).
Give the identical letters different colours so that all \(n\) letters are distinct. Then there are \(n!\) arrangements.
Now group together the coloured arrangements that become the same word once the colours are removed: they differ only in how the \(a\) identical A’s are shuffled among their own positions, how the \(b\) B’s are shuffled, and so on. That is \(a! \times b! \times c! \times \cdots\) arrangements in every group, and every group has the same size.
So the number of distinct words is \(\dfrac{n!}{a!\,b!\,c!\cdots}\).
This is the same “equal-sized groups, so divide” argument as Task 1d of The Starting Five (each squad is counted \(r!\) times) and Round Table Trouble. If groups have done those activities, listen for them to say so unprompted.
Letters: M ×1, I ×4, S ×4, P ×2, total 11.
Second route (choose the positions, from The Starting Five): \(\binom{11}{1}\binom{10}{4}\binom{6}{4}\binom{2}{2} = 11 \times 210 \times 15 \times 1 = 34\,650\). This agrees, and it is the identical expression from Task 3e of The Starting Five.
Glue the four I’s into one block. Then the objects are M, the block, S, S, S, S, P, P: 8 objects with S repeated 4 times and P repeated twice. The I’s are identical, so there is no ordering inside the block.
Multiplying by \(4!\) for the order inside the block. That factor belongs in Round Table Trouble, where the guests are different people. Here the I’s are identical, so there is nothing to order.
Arrange the 7 non-S letters (M, I, I, I, I, P, P) first:
These 7 letters leave 8 gaps (one before, one after, and six between). The four S’s must go into four different gaps, and since the S’s are identical only which gaps matter:
This is the hard task of Phase 1 and many groups will try to subtract the “bad” arrangements from 34,650. That approach is possible but very messy (S’s can be adjacent in many overlapping ways); let them try it for a few minutes, then offer the last rung of the ladder. The gap method is the new idea of the lesson, and it returns on the worksheet.
Counting only 6 gaps (forgetting the two ends), or counting \({}^{8}P_{4}\) instead of \(\binom{8}{4}\) (the S’s are identical, so which S goes in which gap does not matter).
Require: the rule \(\dfrac{n!}{a!\,b!\cdots}\) with the “equal-sized groups” proof, 34,650 with visible cancellation, 840, and 7,350. If time is short, a group with a working idea for 1f (gaps) but an arithmetic slip can proceed.
Every route is a word
A \(2 \times 2\) grid has 6 routes:
Groups will either list systematically (a good sign) or fill in the number of ways to reach each intersection by adding (which anticipates Phase 4). Both are fine here. Make sure they write each route as an R/U word; that is the bridge to Phase 1.
Every route is a word of \(a\) R’s and \(b\) U’s, so its length is \(a+b\). Counting words with repeated letters (Phase 1):
A route has \(a+b\) steps. Once we choose which \(a\) of those steps are east, the other \(b\) steps must be north, so the route is completely determined; and every choice of \(a\) steps gives a different route. So the number of routes is the number of ways to choose \(a\) positions from \(a+b\):
This agrees with 2b. A route is simultaneously an arrangement of a word with repeated letters and a selection of positions.
Arrangements with repeats and selections turn out to be the same thing seen from two sides: choosing which positions get the R’s is exactly the same decision as arranging the word. Ask: “Which would you rather use to count MISSISSIPPI, and could you have used the other?” The answer (yes: \(\binom{11}{1}\binom{10}{4}\binom{6}{4}\binom{2}{2}\)) closes the loop with Phase 1.
(ii) Algebra: \(\dfrac{(a+b)!}{a!\,b!}\) is unchanged when \(a\) and \(b\) are swapped. Or: \(\binom{a+b}{a} = \binom{a+b}{b}\) by the Mirror rule. Story: reflect the whole city in the diagonal through the depot, swapping east and north. Every \(a \times b\) route becomes a \(b \times a\) route and vice versa, so the two grids have equally many routes. (Or: choosing which steps are east is the same as choosing which are north.)
Require: all six routes of the \(2 \times 2\) grid, the formula with its choose-number form and the proof that they agree, 252 and 330, and both explanations in 2d(ii). The calculator check in (iii) must name \(\binom{2n}{n}\) (nCr on the GDC), not just a number.
When the road crews arrive
3a Routes through \((2,2)\): \(\binom{4}{2} \times \binom{6}{3} = 6 \times 20 = 120\) (journey D to \((2,2)\), then \((2,2)\) to ★).
3b D to \((2,3)\): \(\binom{5}{2} = 10\). \((2,3)\) to ★ (3 east, 2 north): \(\binom{5}{2} = 10\).
3c Two methods that must agree:
3d Routes through both closed intersections: \(6 \times 2 \times 6 = 72\) (D to \((2,2)\), then \((2,2)\) to \((3,3)\), then \((3,3)\) to ★). Inclusion and exclusion:
In 3d, subtracting \(120 + 120 = 240\) and answering 12. The 72 routes that use both closures were subtracted twice. Ask the group which routes those are and how many, then have them repair the count. This is the same “subtract twice, add back once” idea as the Round Table Trouble challenge.
In 3a, subtracting only the 6 routes to (2,2) and forgetting that each of them can finish in 20 ways. A route through (2,2) has two halves, so the bad routes number \(6 \times 20 = 120\), not 6.
The number of routes through \((x,y)\) is \(\binom{x+y}{x} \times \binom{10-x-y}{5-x}\). Computing it for every intersection (the grid is unchanged by reflecting in the diagonal \(x \leftrightarrow y\) and by turning it through 180 degrees, so only a few distinct values are needed) gives:
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 5 | 1 | 6 | 21 | 56 | 126 | ★ |
| 4 | 6 | 25 | 60 | 105 | 140 | 126 |
| 3 | 21 | 60 | 100 | 120 | 105 | 56 |
| 2 | 56 | 105 | 120 | 100 | 60 | 21 |
| 1 | 126 | 140 | 105 | 60 | 25 | 6 |
| 0 | D | 126 | 56 | 21 | 6 | 1 |
Most groups predict the middle, around \((2,2)\) or \((3,3)\), which removes only 120. The reason: every route must leave D through \((1,0)\) or \((0,1)\), and routes are most concentrated near the start and the end where they have been funnelled together. \((1,1)\) is the busiest intersection, but even \((0,1)\) (126) beats the centre. Any group that tabulates correctly deserves the full proof mark; a group that only argues intuitively has not proved anything.
Predicting the centre and then checking only the centre. The prediction step is deliberate: being wrong is the point. Praise groups who found the error through computation.
Require: 132, 100, 40 (two methods), 84 with the add-back explained, and for 3e a table or formula for through-counts and the correct maximum. Groups that run out of time on 3e may get the code if 3a to 3d are solid and they have a correct formula for through-counts.
Counting the whole city at once
The left column and the bottom row are all 1 (only one route goes straight along an edge). Every other label is the sum of the label to its left and the label below it:
Groups may fill the grid either by adding or by using \(\binom{x+y}{x}\). Both give the same grid; ask which they used and whether they can get the other to confirm it. Check the corner: the label at \((5,5)\) is 252, matching Phase 2.
Every route to \((x,y)\) ends with a final step, and that step is either east (coming from \((x-1,y)\)) or north (coming from \((x,y-1)\)). No route is both, and every route is one or the other. So the routes to \((x,y)\) split into two separate groups, and their sizes add.
Since label\((x,y) = \binom{x+y}{x}\), put \(n = x+y\) and \(r = x\):
These are the numbers of Pascal’s triangle: along the diagonal \(x + y = 4\) the labels read \(1, 4, 6, 4, 1\), and along \(x+y=5\) they read \(1, 5, 10, 10, 5, 1\).
This is the second proof of the identity from the challenge in The Starting Five (“does the star player make the squad?”). The first counted squads by whether a given player is in or out; this one counts routes by their last step. Ask the class to say what the two proofs have in common: both split a set into two disjoint pieces by one yes-or-no question, and then count each piece.
Proof. A route of exactly \(n\) steps from D is a word of \(n\) letters, each R or U, so there are \(2^n\) such words. Every word ends at exactly one intersection with \(x + y = n\), and the number of words ending at \((x,y)\) is by definition its label. So the labels on that diagonal add to \(2^n\). (Inside this \(5 \times 5\) grid, this works for \(n \le 5\); beyond that the edge of the city cuts routes off.)
This is the row-sum result from Task 4b of The Starting Five, proved again by a completely different route (yes-or-no at every step becomes R or U at every step).
Require: the completed grid with the adding rule, the last-step proof, the choose-number identity, and the \(2^n\) proof for diagonal sums.
(i) Stars and bars. Write a handing-out as a string of 10 stars (sweets) and 3 bars (dividers between the 4 children); for example \(\star\star|\star\star\star\star|\,|\star\star\star\star\) means 2, 4, 0, 4. Every handing-out is exactly one such string, and every string is one handing-out. The number of strings is an arrangement of 13 symbols with repeats (Phase 1):
If every child must receive at least one: give each child one sweet first (4 used), then hand out the remaining 6 with no restriction: \(\dfrac{9!}{6!\,3!} = \binom{9}{3} = 84\).
(ii) A 3D city. A route is a word of \(a\) E’s, \(b\) N’s and \(c\) U’s, so by Phase 1:
(Equivalently \(\binom{9}{3}\binom{6}{3} = 84 \times 20 = 1680\): choose which steps are east, then which of the rest are north. This is the same product as Task 3e of The Starting Five.)
Few groups will reach these. If one does reach the stars-and-bars question, have them show the star-and-bar string model to the class, because it turns a distribution problem into a Phase 1 problem and is the single most reusable counting trick in the lesson.
1. Have a group present the Phase 1 proof and say where they have seen “equal-sized groups, so divide” before (The Starting Five 1d, Round Table Trouble).
2. Ask: “In 2c, a route is both a word with repeated letters and a choice of positions. Why are those the same problem?”
3. Reveal the answer to 3e on the board and ask groups what they predicted and why it was wrong. The funnelling explanation is worth having a student say.
4. Put the two proofs of Pascal’s identity side by side (star player from The Starting Five, last step from Phase 4b) and ask what they have in common.
5. Tease the next topic: “Where do you think the numbers \(1, 4, 6, 4, 1\) would show up if you expanded \((a+b)^4\)?” Do not answer it today.