2014 Indonesia MO Problems/Problem 1

Problem 1

Is it possible to fill a grid with each of the numbers once each such that the sum of any two numbers sharing a side is prime?

Solution 1

All prime numbers are odd except 2. However, it is impossible to arrange the number so that each square that shares a side sums to 2, since the smallest possible sum is 3 since all numbers appear once. Therefore, all the squares that share a side must sum to an odd prime number. Since this is the case, the squares that share a side cannot have the same parity. Since there are 5 odds and 4 evens we must place, the corners and the center must be odd, while the rest is even, as this is the only way to place the odd and even numbers so that no squares that share the same sides have the same parity. Notice that the center square shares a side with every single even number. Also note that 9 and 15 aren't primes, as they are all multiples of 3.

Case 1: Center number is 1

We can't place 8 anywhere, as 1+8=9

Case 2: Center number is 3

We can't place 6 anywhere, as 3+6=9

Case 3: Center number is 5

We can't place 4 anywhere, as 5+4=9

Case 4: Center number is 7

We can't place 2 anywhere, as 7+2=9

Case 5: Center number is 9

We can't place 6 anywhere, as 9+6=15

Since no number can be placed in the center, there are no such grids. We are done.