You run a courier company in a city whose streets form a perfect grid. Couriers only ever walk east or north, 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 must work for any size of city and any closure, and you must justify each one.
List every distinct arrangement of AAB. Then count AAAB, AABB, AABBB and AAABBB. Write out the lists for the short words.
Find a rule that predicts all your counts. Use it for BANANA without listing.
Prove your rule for any word, including words with several different repeated letters.
No calculator: the number of arrangements of MISSISSIPPI. Show the cancellation.
How many of them have all four I’s together in one block?
How many have no two S’s next to each other?
A courier walks from the south-west corner to the north-east corner, moving only east or north. An \(a \times b\) grid has \(a\) blocks east and \(b\) blocks north. List every route of the \(2 \times 2\) grid. Then count routes for \(3 \times 2\), \(3 \times 3\) and \(4 \times 4\).
Write each route as a string of R (east) and U (north). Find a formula for an \(a \times b\) grid and use it for \(5 \times 5\).
A route is decided by which steps are east. Write the number of routes as a choose-number and prove it equals your formula from 2b.
(i) Routes in a \(7 \times 4\) grid? (ii) Show \(a \times b\) and \(b \times a\) have the same count, two ways (algebra, and a story about the city). (iii) Smallest \(n \times n\) grid with over 1,000,000 routes? State the formula you type in.
Close the intersection \((2,2)\). How many routes remain?
Every courier must pass through \((2,3)\). How many routes?
\((2,2)\) is closed and couriers must pass through \((2,3)\). How many routes?
Both \((2,2)\) and \((3,3)\) are closed. How many routes remain?
Close exactly one intersection (not D or ★). Predict which removes the most routes, then find out. Prove your answer.
Label every intersection of the \(5 \times 5\) grid with its number of routes from D. Find a rule that fills each label from labels you already know, and fill the whole grid.
Prove your rule for a general intersection. Rewrite it as an equation about choose-numbers. Where have you seen these numbers?
Add the labels at all intersections with \(x+y=n\), for several \(n\) up to 5. What do you find? Prove it for any \(n\) using routes.
(i) 10 identical sweets to 4 children (some may get none): how many ways? How many if every child gets at least one? (ii) Add skyscrapers so a courier may also climb up. Routes across a \(3 \times 3 \times 3\) block, and a formula for \(a \times b \times c\).