You are a host of a game in which players are given a 10-by-10 grid, and are allowed to fill all of the squares on this grid with natural numbers from 1 to 10, as long as any numbers that share the same side or corner must be coprime.

Players win the game when they finished filling the grid with numbers, and there are no numbers appears more than $a$ times in the grid. If any players win, you'll have to pay them 1000000 dollars.

The question is, what is the largest value of $a$ you can define, such that there is no chance of winning to the players?

The answer is 16.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Suppose that the grid is filled so that touching cells contain coprime integers.

Since all even numbers share the common factor $2$ , it is easy to see that there can be no more than five even numbers in each adjacent pair of rows. The left-hand picture shows a possible choice of five cells that could be even. Similarly, since the numbers $3$ and $9$ share the common factor $3$ , there can be no more than five $3$ s and $9$ s together in each adjacent pair of rows. Thus there can be no more than $25$ even numbers in the whole grid. Similarly the number of $3$ s and $9$ s together in the whole grid cannot exceed $25$ . Thus at least $50$ of the numbers in the grid must be one of $1$ , $5$ or $7$ . Since $3 \times 16 = 48$ , we deduce that at least one of $1$ , $5$ or $7$ must occur at least $17$ times. Thus we deduce that $a \ge 16$ . It remains to show that $a=16$ .

The middle picture shows an arrangement of $25$ even numbers (ten $2$ s, ten $4$ s and five $8$ s), thirteen $3$ s and twelve $9$ s which is acceptable. The right-hand picture adds seventeen $1$ s, seventeen $5$ s and sixteen $7$ s to give a winning grid. Thus the players could win with $a=17$ , and hence $a=16$ .