Olympiad Maths Prep

Track / Stage 6 / 304 of 400 #1304 of 2000

Problem 1304

National olympiad, first round
Combinatorics Difficulty 6.6 Prove it Saudi Arabian Mathematical Competitions · Saudi Arabia

In the popular game of Minesweeper, some fields of an a×ba \times b board are marked with a mine and on all the remaining fields the number of adjacent fields that contain a mine is recorded. Two fields are considered adjacent if they share a common vertex. For which k{0,1,2,3,4,5,6,7,8}k \in \{0, 1, 2, 3, 4, 5, 6, 7, 8\} is it possible for some aa and bb, ab>2021ab > 2021, to create a board whose fields are covered in mines, except for 2021 fields who are all marked with kk?

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

For k=0k = 0 this is impossible, since at least one non-mine field will be adjacent to the bombs unless the entire field is covered with bombs.

* For k=1k = 1 we take a=1,b=310111a = 1, b = 3 \cdot 1011 - 1, and 1011 mines spaced two-spaces apart, with one on one of the endpoints, so the total number of fields marked 1 is 2021.

* For k=2k = 2 we again take a=1,ba = 1, b large enough, and place 2021 empty fields in isolation of each other, and not on any of the endpoints.

* For k=3k = 3, we take a=2,ba = 2, b large enough, and 2019/32019/3 mutually isolated L-triminoes as empty spaces, with two corner points on opposite sides of the longer edge also empty.

* For k=4k = 4, we take a=3,ba = 3, b large enough, and 1008 pairs of adjacent empty fields on the edge, with one empty field on the middle row surrounded on all diagonals by 4 empty fields on the edge, resembling an X shape.

* For k=5k = 5 we take a=3,ba = 3, b large enough, and place 2021 isolated empty fields on the edge.

* For k=6k = 6 we take aa and bb large enough, and place 2013/32013/3 isolated empty L-triminoes and 2 diamond-shaped regions of 4 fields each.

* For k=7k = 7 it is impossible to place an empty field on the edge and since each empty field in the interior is adjacent to exactly one other empty field it follows that the empty fields are paired and thus their total number cannot be 2021, an odd number.

* For k=8k = 8 we simply take 2021 isolated empty fields in the interior.

Thus, the set of solutions is: {1,2,3,4,5,6,8}\{1, 2, 3, 4, 5, 6, 8\}. \square

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.