One idea, one picturePlace kings on a 6×6 board so that no two touch (not even diagonally). First place as many as you can; then choose a way of cutting the board for the argument. Look at the ruler below. Can the two arrows meet?
Loading figure…
In one sentence
“The largest is M” is two statements: ① M can really be reached (give a construction); ② more than M is impossible (give an argument). Without either one, it is just a guess.
Draw the two statements on a ruler. The construction pushes from the left, the argument presses from the right, and between them is the “don't know yet” zone. The problem is solved only when the two arrows meet.
The most kings on a 6×6 board, no two neighbors
Step 1 / 5
Loading figure…
Place some at random
Place 4 at random, no two neighbors. Now we know the answer is at least4. Every better construction moves the left arrow to the right.
4≤M
First argument: cut into rows
A tidier placement
A tighter argument: 2×2 blocks
Pinned down
A common way to argue is from local to global: cut the whole into small pieces where “at most how many” is obvious at a glance, then add up. Choosing the cut is exactly “building the boxes” from the pigeonhole principle.
Predict first
Now take a 5×5 board. What is the largest number of kings you can place with no two neighbors?
kings
Choose an answer first; then you can see the result.
✓You predicted it!✗Not what you expected — which is exactly why it is worth a pause.
A 5×5 board does not cut neatly into 2×2 blocks, but it can be cut into 4 blocks of 2×2, 4 of 1×2 (or 2×1) and 1 single square: still 9 pieces, each holding at most 1 king. And the 9 crossings of rows 1, 3, 5 with columns 1, 3, 5 hold exactly 9. The board got smaller, but the answer did not change.
Loading figure…
In the four stops below the problems differ, but the “squeeze from both sides” method is exactly the same.
Stop 1 · Chessboard: bishops
A bishop moves along diagonals. What is the largest number of bishops on a 5×5 board with no two attacking each other?
Place them first. Then try the three cuts: cutting into rows is almost useless; cutting into diagonals gives an upper bound; a little finer, and you can push it down by 1 more.
Loading figure…
“Diagonals, two corners joined”: the bottom-left and top-right corners are each a diagonal with only 1 square, but they lie on the same diagonal in the other direction and attack each other, so together they can hold only 1 bishop.
There are 9 diagonals in one direction, each holding at most 1 bishop, so the upper bound is 9. But two of those diagonals have just one square each, the two opposite corners, and these two squares attack each other, so they cannot both be used. The bound drops to 8. Construction: fill the first row with 5, and put 3 in the middle of the last row.
Stop 2 · Sets of numbers: no difference of 4
Choose numbers from 1 to 16 so that no two of them differ by 4. What is the largest number you can choose?
Loading figure…
Two of the ways of sorting push the upper bound down to the same number. Which numbers does each one lock up together?
Pair the numbers that differ by 4: (1,5),(2,6),(3,7),(4,8), (9,13),…,(12,16). That is 8 pairs, and you can choose at most 1 from each, so at most 8. Construction: 1,2,3,4 and 9,10,11,12.
Stop 3 · Sets of numbers: no doubles
Choose numbers from 1 to 16 so that no number is twice another. What is the largest number you can choose?
Predict first
Guess first: what is the most you can choose? (“All the odd numbers” gives 8. Can you do better?)
Choose an answer first; then you can see the result.
✓You predicted it!✗Not what you expected — which is exactly why it is worth a pause.
Split the numbers into “doubling chains”: 1→2→4→8→16, 3→6→12, 5→10, 7→14, and 9,11,13,15 each on their own. Two neighbors in a chain cannot both be chosen, so chains of length 5,3,2,2 allow at most 3,2,1,1, and each of the four single numbers allows 1:
3+2+1+1+4=11.
For the construction, follow the chains: 1,4,16; 3,12; 5; 7; 9,11,13,15. Set it up below and watch the ruler close.
Loading figure…
This time the “max” of a good box is not always 1. A box may hold more than one, as long as you can work out its capacity exactly.
Stop 4 · The other way round: the fewest needed
For a minimum, the directions are reversed: the construction says “this few is enough”, and the argument says “any fewer is impossible”.
A guard watches the square it stands on and the ring of squares around it. What is the smallest number of guards that can watch a whole 6×6 yard?
Loading figure…
First place guards until the whole yard is watched, using as few as you can. Then switch to “Witness”: choose some squares so that no guard, wherever it stands, can see two of them.
The four corners make good witnesses: a guard who can see the top-left corner must stand in the top-left 2×2 block, too far from the other three corners. Each of the four corners needs a different guard, so at least 4 are needed. And 4 guards standing at the crossings of rows 2, 5 with columns 2, 5 each watch one 3×3 region, covering all 36 squares.
What if nothing can reach the upper bound?
Break it
Counterexample lab: remove one condition
Conclusion: That upper bound is the answer← still true?
Cut into 2×2 blocks and the upper bound is 9. Place 9 kings and the ruler closes.
Loading figure…
Now only “rows” is allowed: the upper bound is 18. Try to place 18 kings, or at least more than 9.
Loading figure…
The two arrows on the ruler stop at 9 and 18, and the gap between them never closes. “M≤18” is a true statement, but it is not the answer: it only shows that this argument is not good enough, and you need a different cut.
Practice
Exercise 1Basic
What is the largest number of kings you can place on a 7×7 board with no two neighbors (diagonal neighbors included)?
Hint · direction
Two jobs: place them, then prove you cannot place more. First think about the tidiest placement.
Hint · method
Construction: skip every other row and column. Argument: cut the board into pieces, as many of them 2×2 as possible; each piece holds at most 1 king.
Hint · first step
The crossings of rows 1,3,5,7 with columns 1,3,5,7: 4×4=16 kings, no two neighbors.
Full solution
Argument: group rows 1–2, 3–4, 5–6 and 7 into 4 groups, and the columns the same way. The board is cut into 16 pieces (2×2, 2×1, 1×2 or single squares). Any two squares in a piece are neighbors, so each piece holds at most 1 king: no more than 16 in all. The construction reaches 16, so the answer is 16.
Exercise 2Basic
What is the largest number of rooks you can place on an 8×8 board with no two attacking each other? (A rook attacks every square in its row and column.)
Hint · direction
Can a row hold two rooks?
Hint · method
Argument: cut into rows; each row holds at most 1. Construction: find 8 squares, no two in the same row or column.
Hint · first step
8 rows, at most 1 rook each, so no more than 8.
Full solution
Put the 8 rooks on a diagonal: no two share a row or a column, so none attack each other. Upper bound 8, construction 8: the answer is 8.
Exercise 3Advanced
Choose numbers from 1 to 15 so that no two of them differ by 3. What is the largest number you can choose?
Hint · direction
Which numbers “get in each other's way”? 1 blocks 4, 4 blocks 7, …
Hint · method
Sort by the remainder on division by 3 into three chains; two neighbors in a chain cannot both be chosen.
Hint · first step
The three chains: 1,4,7,10,13; 2,5,8,11,14; 3,6,9,12,15. Each has 5 numbers.
Full solution
In a chain of 5 numbers with no two neighbors chosen, you can choose at most 3 (the 1st, 3rd and 5th). Three chains give at most 3×3=9. Construction: the 1st, 3rd and 5th of each chain, that is 1,7,13; 2,8,14; 3,9,15. Two numbers in the same chain differ by 6 or 12; two numbers from different chains have different remainders on division by 3, so their difference is not a multiple of 3. So no two differ by 3. The answer is 9.
Exercise 4Advanced
What is the largest number of bishops you can place on a 6×6 board with no two attacking each other?
Hint · direction
Go back to Stop 1. For 5×5 the answer was 8=2×5−2.
Hint · method
Argument: count the diagonals in one direction, and look carefully at the two diagonals with only one square. Construction: use the first and last rows.
Hint · first step
There are 2×6−1=11 diagonals in one direction, each holding at most 1 bishop. The two one-square diagonals are a pair of opposite corners, which attack each other, so together they hold only 1.
Full solution
The upper bound is 11−1=10. Construction: fill the first row with 6 bishops, and put 4 in the middle of the last row (leaving out both ends). Bishops in the same row do not attack each other. The first and last rows are 5 rows apart, so to attack each other two bishops would have to be 5 columns apart, which happens only for the end squares, and those are empty. That is 10 bishops, so the answer is 10.
Exercise 5Challenge
Take the guard problem from Stop 4 and make the yard 7×7. What is the smallest number of guards needed?
Hint · direction
For 6×6, 4 guards each watch one 3×3 region. 7×7 has one more row and one more column. Are 4 still enough?
Hint · method
Argument: find a set of witness squares such that no guard can see two of them; it is enough for any two to be at least 3 apart in row or column. Construction: make the guards' 3×3 regions cover the whole yard.
Hint · first step
Witnesses: the 9 crossings of rows 1,4,7 with columns 1,4,7. Any two of them are at least 3 apart in row or column, while two squares seen by one guard are at most 2 apart in both row and column.
Full solution
So at least 9 guards are needed. Construction: put guards at the 9 crossings of rows 2,4,6 with columns 2,4,6. The guards in row 2 cover rows 1–3, those in row 4 cover rows 3–5, and those in row 6 cover rows 5–7; the columns work the same way, so all 49 squares are watched. The answer is 9.
The wrong step: Place kings on a 6×6 board so that no two are neighbors. Each row holds at most 3, and there are 6 rows, so at most 3×6=18 kings fit.
What went wrong? Think first, then open
Diagnosis“At most 18” is true, but nobody can actually place 18: once a row has 3 kings, the next row has almost no room. An upper bound that cannot be reached is not the answer.
✓
The right step: Cut the board into 9 blocks of 2×2. Each block holds at most 1 king, so the upper bound is 9; then actually place 9. Only when the two sides are equal is the answer 9.
“Every upper bound needs a construction to meet it”
Exhibit
“I can't add any more” is not the same as “the most”
✗
The wrong step: On a 5×5 board I placed 4 kings, no two neighbors (at the crossings of rows 2, 4 and columns 2, 4), and there is nowhere to add a 5th, so the most is 4.
What went wrong? Think first, then open
DiagnosisBeing unable to add one only shows that this particular placement is stuck. A different placement, at the crossings of rows 1, 3, 5 and columns 1, 3, 5, holds 9.
✓
The right step: “The most” needs an argument that holds for every placement (cutting the board into blocks, for example), not an observation about your own placement.
“A dead end does not mean you have gone the farthest”
Exhibit
The “witnesses” in the argument are not independent
✗
The wrong step: In a 6×6 yard, each of the 6 squares in the first row must be watched by a guard, so at least 6 guards are needed.
What went wrong? Think first, then open
DiagnosisOne guard can watch 3 neighboring squares in the same row at once. “Every square must be watched” does not mean “every square needs its own guard”.
✓
The right step: Choose witness squares that are far enough apart: the four corners. No guard can see more than one corner, so at least 4 guards are needed, and 4 really are enough.
“When you count “at least how many”, first make sure no one can do two jobs”
Extremal Problems in Combinatorics ← → step · F full screen · Esc exit