Back to Mathematical Olympiad
Difficulty: 6/102018 IMO 2018 (Q4)

A site is any point in the plane such that and are both positive integers less than or equal to . Initially, each of the sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two red stones is not equal to . On his turn, Ben places a new blue stone on any unoccupied site. They stop when a player cannot move. Find the greatest such that Amy can ensure placing at least stones.

Options:

  • .

  • B.

    .

  • C.

    .

  • D.

    .

Guide / Hint

Hint 1: Model the problem as a graph where sites are vertices and edges connect sites at distance . This is essentially the knight's graph on a board.

Hint 2: Amy needs to place stones on an independent set. Find the maximum independent set size and think about how Ben's blocking affects it.

Hint 3: Consider a pairing strategy: pair up sites that are at distance . Amy plays in one site of each pair that Ben hasn't blocked.

Solution

Step 1 (Graph model): Build a graph on the 400 sites where two sites are adjacent if their distance is (i.e., they differ by or — a knight's move in chess). Amy needs an independent set in this graph.

Step 2 (Coloring the grid): Color the grid in a checkerboard pattern using blocks. Partition the 400 sites into 100 groups of 4, where each group forms a square. Within each square, no two sites are at distance from each other (distances within a square are , , or ).

However, sites from DIFFERENT blocks can be at distance .

Step 3 (Amy's strategy for K = 100): Amy uses a pairing strategy. She partitions the 400 sites into 100 pairs such that each pair consists of two sites at distance . On each turn, whatever site Ben occupies, Amy responds by occupying a site that avoids distance conflicts. Since Amy goes first and there are 100 such independent positions available, Amy can guarantee stones.

Step 4 (Ben's strategy to limit K ≤ 100): Ben can ensure Amy places at most 100 stones by blocking key sites in the knight-move graph. The maximum independent set in the knight graph on a board has size 200 (alternate coloring), but Ben's blocking reduces this to 100.

Answer: .

Ready to track your progress and master these topics?

Create a free account