Track / Stage 5 / 20 of 400 #1100 of 2444

Problem 1100

AIME late

Combinatorics Difficulty 5.0 Prove it Taiwan IMO Selection Camp · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty, ordering) added by this project.