Maths Olympiad Prep

Library / /5 of 105

Combinatorics Difficulty 4.3 AIME Find the answer United States

Problem:

How many ways are there to write all numbers from 11 to 99 in the cells of a 3×33 \times 3 grid so that for all integers 1n<91 \leq n < 9, the cell labeled nn shares an edge with the cell labeled n+1n+1?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Apply a checkerboard coloring to the grid so that the corners and the center are black. Then by parity, the 55 odd numbers must be in the 55 black cells and the 44 even numbers in the 44 white cells.

If the center cell is 11, there are 44 ways to pick 22 and 22 ways to pick 33, at which point the rest of the numbers are determined, for a total of 88 possibilities. By symmetry there are 88 possibilities for the center cell to be 99. Likewise, if the center cell is 33, picking 22 and 11 gives 88 more, and another 88 more for the center cell being 77. Finally, if the center cell is 55, the path is still determined by picking 66 and 77. In total, there are therefore 58=405 \cdot 8 = 40 possibilities.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.