Question

A monkey has filled in a 3 × 3 grid with the numbers 1, 2, . . . , 9. A cat writes down the three numbers obtained by multiplying the numbers in each horizontal row. A dog writes down the three numbers obtained by multiplying the numbers in each vertical column. Can the monkey fill in the grid in such a way that the cat and dog obtain the same set of three numbers? What if the monkey writes the numbers 1, 2, . . . , 25 in a 5×5 grid? Or 1, 2, . . . , 121 in a 11 × 11 grid? Can you find any conditions on n that guarantee that it is possible or any conditions that guarantee that it is impossible for the monkey to write the numbers 1, 2, . . . , n2 in an n × n grid so that the cat and the dog obtain the same set of numbers?

Answer 1

• yes for 3×3 and 5×5 grids
• no for 11×11 grid
• the odd-degree prime factors in (n²)! must meet certain conditions for the grid to be filled

Explanation:

The monkey can fill an n×n grid if the following conditions are met.

• the number of primes between n²/2 and n² -1 is exactly n-1 (We can call these (and n^2) the "high primes.")
• when the high primes are removed from the set 1..n^2, and the product of the remaining numbers (the "composites") is factored to primes, the number of prime factors of odd degree must be at most n

These conditions are met for n ∈ {3, 5, 7, 8}.

A solution will exist if there are n pairs of tuples of length n-1 such that ...

• the products of the tuples in the pair are the same
• the union of all of the first tuples must equal the set of composites
• the union of all of the second tuples must equal the set of composites
• the intersection of any first tuple and any second tuple must have cardinality at most 1

__

We know of solutions for n=3 and n=5. We have found these by "trial and error." Each pair of tuples represents the set of numbers in a row and in a column whose intersection is one of the high primes (or n^2). The high primes (and n^2) must not reside on the same row or column. Otherwise, considerable latitude is available for creating the square.

One could describe a "canonical form" as having the high primes in order down the diagonal, and the remaining composites arranged in low-high order left-to-right and top-to-bottom as nearly as possible. Rows can be swapped, and columns can be swapped, and the high primes may be assigned to the necessary row-column intersections in any order.

Solutions we have found are:

3×3 grid

Tuples: {(1, 6), (2, 3)}, {(2, 4), (1, 8)}, {(3, 8), (4, 6)}

Cat/Dog products: 6, 8, 24 (less an arbitrary "high prime" factor)

"High primes": 5, 7, 9

Solution:

`\left[\begin{array}{ccc}5&1&6\\2&7&4\\3&8&9\end{array}\right]`

__

5×5 grid

Tuples: {(1, 5, 12, 18), (3, 4, 9, 10)}, {(2, 10, 14, 22), (5, 7, 11, 16)},

{(3, 6, 7, 8), (1, 2, 21, 24)}, {(4, 15, 16, 21), (6, 12, 14, 20)},

{(9, 11, 20, 24), (8, 15, 18, 22)}

Cat/Dog products: 1080, 6160, 1008, 20160, 47520 (less a "high prime" factor)

"High primes": 13, 17, 19, 23, 25

Solution:

`\left[\begin{array}{ccccc}13&3&7&6&8\\1&17&5&12&18\\2&10&19&14&22\\21&4&16&23&15\\24&9&11&20&25\end{array}\right]`

_____

Additional comment

It seems to be all about odd-degree prime factors in (n²)!. There can be at most (n-1) that have degree 1, and no two can occupy the same row or column. This condition ensures it is possible to have cat's products match dog's products.

No doubt there are simple rules that allow solutions to be found easily. We have not discovered them yet. Consequently, we cannot say for certain there are not solutions for n=4 or 6, or that there are definitely solutions for n=7 or 8. We know that solutions for these grid sizes are not ruled out by the distribution of prime numbers.