2
$\begingroup$

Can you place the first 9 natural numbers (1 to 9) in a 3x3 grid such that every row and column sums to a prime? The sums do not need to be distinct. Bonus: can you also make both diagonals sum to a prime?

$\endgroup$
1
  • 1
    $\begingroup$ Maybe those puzzles could benefit from the no-computers tag because my work around was simply to brute force the possibilities which are not so numerous! $\endgroup$
    – JKHA
    Feb 19 at 15:15

2 Answers 2

3
$\begingroup$

I can do it with:

$\begin{array}{|c|c|c|} \hline 2 & 8 & 3 \\ \hline 4 & 6 & 9 \\ \hline 1 & 5 & 7 \\ \hline \end{array}$
row sums: 13, 19, 13
col sums: 7, 19, 19
This is not the unique solution has there are $1152$ possibilities

About diagonals:

I can't make it, indeed, this Julia codes enumerates all possibilities and none is eligible!
enter image description here

$\endgroup$
3
  • $\begingroup$ $1152/8=144$ distinct solutions, of which $48$ have one prime diagonal sum. $\endgroup$ Feb 19 at 18:29
  • $\begingroup$ @DanielMathias, that depends. If you consider [1 2 ; 3 4] to be distinct from [1 3 ; 2 4], there are 1152 distincts solution, am I right? $\endgroup$
    – JKHA
    Feb 19 at 18:34
  • $\begingroup$ Yes, there are 1152 solutions. Distinction generally considers rotations and reflections to be equivalent, leaving just 144 distinct solutions. Ignoring the diagonal sums, we can freely swap rows or columns, further reducing the number of base solutions. $\endgroup$ Feb 19 at 18:44
3
$\begingroup$

JKHA's comment suggests a solution. Here's one.

Subquads

Let's take a moment to define a useful term. If we delete any 1 row and 1 column of a 3x3 matrix, we obtain one of 9 possible 2x2 submatrices. Let's call any of these 2x2 submatrices of the original 3x3 matrix a subquad.

Reframing

The sum of 3 distinct numbers from 1 to 9 ranges from 6 to 24. Because every sum is strictly between 3 and $5^2=25$, primality is equivalent to not being a multiple of 2 or 3.

Multiples of 2

Let's first restrict ourselves to all rows and column having an odd sum. Then each row or column must have an odd number of odds, equivalently an even number (0 or 2) of evens. Because there are exactly 4 evens, this means that 2 rows have 2 evens each, and 1 row has 0 evens. Analogously, 2 columns have 2 evens each, and 1 column has 0 evens. Therefore, the evens form a subquad.

Multiples of 3

Let's now restrict ourselves to having no rows or columns sum to a multiple of 3. Then the only thing that matters about a number is its remainder when divided by 3, so let's further restrict ourselves to the remainders 0, 0, 0, 1, 1, 1, 2, 2, 2.

Consider the 3 remainders of any row or column. Observe that if all 3 are equal, then they will sum to a multiple of 3. Similarly, if all 3 are different, then they will sum to a multiple of $3$. Therefore, there must be 2 that are equal, and 1 that is different.

Applying this to all 3 rows, each row must have a pair of equal remainders, and no 2 of these pairs can be equal (requiring 4 equal remainders in total), so each row must have a unique pair. Analogously, each column must have a unique pair of equal remainders.

Consider any group of 3 equal remainders. We know that 2 of them must belong to the same row, and 2 of them must belong to the same column. Therefore, every group of remainders belongs to a subquad. Because these 3 subquads are unique, we will refer to the subquad containing group X as "X's subquad."

We'll also show the following: No subquad has 2 pairs of equal remainders. Indeed, suppose one did. There are three cases of what this subquad could look like (where the third row and third column have been removed).

  1. Diagonals
XO
OX

This leaves no space for X's (or O's) subquad.

  1. Rows
XX
OO

X's and O's subquads will comprise all of 2 columns, leaving no space for the remaining subquad.

  1. Columns
XO
XO

Analogously, X's and O's subquads will comprise all of 2 rows, leaving no space for the remaining subquad.

Combining and Counting

Suppose we have any valid configuration of 3 groups of remainders (when divided by 3). We need to find which subquads we could designate as the even subquad and still find a valid assignment of the numbers from 1 to 9.

  1. The even subquad cannot be any of the 3 subquads that contain an entire group of remainders. Otherwise, we would have 3 numbers with the same remainder when divided by 6, which the range 1 to 9 is too small to satisfy.

  2. The even subquad can be any of the other 6 subquads. Indeed, consider any one of the other 6 subquads (6 choices). We know that it has at most 2 equal remainders, and it cannot have 2 pairs of equal remainders, so it must consist of 1 pair and 2 singletons. For this subquad to be even, the pair must be assigned 2 and 8 (2 choices), and the singletons must be assigned 4 and 6 (2 choices). This leaves a valid assignment of the odd numbers: 5 belongs to the group with 2 and 8 (1 choice), 1 and 7 belong to the group with 4 (2 choices), and 3 and 9 belong to the group with 6 (2 choices). This gives $6\cdot2\cdot2\cdot1\cdot2\cdot2=96$ valid assignments.

More Counting

How many valid configuration of 3 groups of remainders (when divided by 3) are there? Call the group that occupies the central square O. There are 2 cases of O's subgroup (up to rotation/reflection).

  1. Occupying a corner (8 rotations/reflections)
OO.
.O.
...

By inspection, there is only one way valid configuration of the remaining groups.

OOΔ
XOX
XΔΔ
  1. Not occupying a corner (4 rotations)
.O.
OO.
...

Again, there is only one valid configuration.

XOX
OOΔ
XΔΔ

In total there are 12 valid configurations. Therefore, the total number of solutions is $12\cdot96=1152$.

Bonus

Each of the two cases of valid configurations above has an invalid diagonal containing 3 different remainders, so it is impossible to also satisfy both diagonals.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.