Competition problem — Combinatorics

Library / /9 of 42

Combinatorics Difficulty 5.3 AIME, harder Prove it Romania

Is it possible to arrange the first 49 positive integers in a $7 \times 7$ array, so that each cell contains exactly one number and no two primes are neighbours?

Two neighbours are numbers from cells with a common side or a common vertex.

Solution

It is possible. The positive primes less than $49$ are $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ , $31$ , $37$ , $41$ , $43$ , $47$ , that is $15$ numbers.

Number the lines and the columns from $1$ to $7$ , set the primes in $15$ of the $16$ squares with both odd indexes and the other $34$ numbers in the remaining cells.

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 and solution reproduced as published; topic and difficulty added by this site.