Maths Olympiad Prep

Library / /87 of 105

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

The country of Squareland is shaped like a square and is divided into 6464 congruent square cities. We want to divide Squareland into states and assign to each state a capital city so that the following rules are satisfied:

a. Every city lies entirely within one state.

b. Given any two states, the numbers of cities in them differ by at most 11.

c. Any city in a state shares at least one corner with the state's capital.

What is the smallest possible number of states?

Solution

Solution:

In the diagram below, no city shares a corner with any two of the cities marked X. Therefore the nine X's are
Figure 1
in nine different states. The diagram at right shows that nine states are also sufficient ( ∗* denotes capital).
Figure 2

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.