Competition problem — Combinatorics

Library / /54 of 397

Combinatorics Difficulty 5.0 AIME, harder Prove it Taiwan

There is an infinite grid board, with each cell containing a positive integer, such that the sum inside any rectangle is never a prime number, and at least one cell contains $1$ . Find the minimum possible value of the maximum number among all cells.

Solution

The answer is $9$ .

Note that the smallest number that can be placed next to $1$ is $8$ , but $8 + 1 + 8 = 17$ is a prime number, so there must be a $9$ among the cells.

4	8	6
8	1	9
6	9	9

The construction uses modulo

2

and modulo

3

in the cells surrounding the

1

, and places

6

in all cells outside these nine cells. In this way, the sum inside any rectangle containing more than one number is always a multiple of

2

3

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 translated into English from zh; metadata (topic, difficulty) added by this project.