Monkey, Cat, and Dog

A monkey fills an $n \times n$ grid with the numbers $1, 2, \ldots, n^2$, each used exactly once. A cat computes the product of the numbers in each row; a dog computes the product of the numbers in each column. Both animals write their results as a list of $n$ numbers. Can the monkey fill in the grid so that the cat and the dog obtain the same list (as a multiset)?

The answer depends on $n$. For $n = 2$ it is no, by a two-line argument. For $n = 3$ it is yes, as witnessed by the grid $$\begin{array}{|c|c|c|} \hline 5 & 6 & 1 \\ \hline 2 & 4 & 7 \\ \hline 3 & 9 & 8 \\ \hline \end{array}$$ whose row products are $\{30, 56, 216\}$ and whose column products are $\{30, 216, 56\}$: the same multiset. For $n \in \{3, 4, 5, 6, 7, 8\}$ the answer is yes, established constructively in each case by CP-SAT below. For $n = 9$ the answer reverts to no — a surprising return of infeasibility — and the obstruction generalises to infinitely many larger $n$.

Impossibility at $n = 2$

Write the grid as $\bigl(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\bigr)$ with $\{a, b, c, d\} = \{1, 2, 3, 4\}$. The row products are $\{ab, cd\}$ and the column products are $\{ac, bd\}$. If the two multisets match, either $ab = ac$ and $cd = bd$, which forces $b = c$; or $ab = bd$ and $cd = ac$, which forces $a = d$. Either way, two of the four cells carry the same number, contradicting the assumption that the four cells hold the four distinct numbers $1, 2, 3, 4$.

The programming model

A naive encoding introduces an integer variable per cell and a product-variable per row and per column, with $\operatorname{AllDifferent}$ on the cells and multiset equality on the product lists. The products for large $n$ are immense — $10! \approx 3.6 \times 10^6$, $15! \approx 1.3 \times 10^{12}$ — which rules the naive encoding out. A much tighter formulation replaces products with exponent vectors.

Primes and exponents

For each prime $p \leq n^2$, define $v_p(k)$ to be the exponent of $p$ in the prime factorisation of $k$. The product of a row is uniquely determined by its vector of prime exponents; two products are equal if and only if their exponent vectors are equal coordinate-by-coordinate. For each row $i$ and each prime $p$ the row’s total exponent of $p$ is $$R_{i, p} \;=\; \sum_{j = 1}^{n} v_p(g_{i, j}),$$ and symmetrically $C_{j, p}$ for columns.

Cell-exponent variables

For each cell $(i, j)$ introduce an integer variable $g_{i, j} \in \{1, \ldots, n^2\}$ (with a single global $\operatorname{AllDifferent}$ constraint over the $n^2$ cells), and for each prime $p$ a companion variable $e_{i, j, p}$ representing $v_p(g_{i, j})$. Link the two via an element constraint against the lookup table $[v_p(1), v_p(2), \ldots, v_p(n^2)]$ indexed by $g_{i, j} - 1$.

Multiset equality

The row and column product multisets are equal if and only if there exists a permutation $\sigma \in S_n$ such that, for every prime $p$, $$R_{i, p} \;=\; C_{\sigma(i), p}, \quad i \in \{1, \ldots, n\}.$$ This is encoded in CP-SAT by an integer permutation variable $\sigma_i \in \{0, \ldots, n-1\}$ with $\operatorname{AllDifferent}$, followed by an element constraint that equates $R_{i, p}$ to the $\sigma_i$-th entry of $C_{\cdot, p}$, for each prime $p$.

A solver in fifty lines

from ortools.sat.python import cp_model
from sympy import primerange, factorint

def solve(n):
    N = n * n
    primes = list(primerange(2, N + 1))
    v = {k: {p: 0 for p in primes} for k in range(1, N + 1)}
    for k in range(2, N + 1):
        for p, e in factorint(k).items():
            v[k][p] = e
    M = {p: max(v[k][p] for k in range(1, N + 1))
         for p in primes}

    m = cp_model.CpModel()
    g = [[m.NewIntVar(1, N, "")
          for _ in range(n)] for _ in range(n)]
    m.AddAllDifferent([g[i][j]
                       for i in range(n)
                       for j in range(n)])

    e = {}
    for i in range(n):
        for j in range(n):
            idx = m.NewIntVar(0, N - 1, "")
            m.Add(idx == g[i][j] - 1)
            for p in primes:
                tbl = [v[k][p] for k in range(1, N + 1)]
                x = m.NewIntVar(0, M[p], "")
                m.AddElement(idx, tbl, x)
                e[(i, j, p)] = x

    R, C = {}, {}
    for i in range(n):
        for p in primes:
            r = m.NewIntVar(0, n * M[p], "")
            m.Add(r == sum(e[(i, j, p)]
                           for j in range(n)))
            R[(i, p)] = r
    for j in range(n):
        for p in primes:
            c = m.NewIntVar(0, n * M[p], "")
            m.Add(c == sum(e[(i, j, p)]
                           for i in range(n)))
            C[(j, p)] = c

    sigma = [m.NewIntVar(0, n - 1, "")
             for _ in range(n)]
    m.AddAllDifferent(sigma)
    for i in range(n):
        for p in primes:
            col_list = [C[(j, p)] for j in range(n)]
            tgt = m.NewIntVar(0, n * M[p], "")
            m.AddElement(sigma[i], col_list, tgt)
            m.Add(R[(i, p)] == tgt)

    s = cp_model.CpSolver()
    s.parameters.max_time_in_seconds = 60
    st = s.Solve(m)
    if st not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return [[s.Value(g[i][j]) for j in range(n)]
            for i in range(n)]

On a standard laptop the solver decides feasibility as follows: $$n = 2 : \text{unsat}, 10 \text{ ms}; \quad n = 3 : \text{sat}, 10 \text{ ms}; \quad n = 4 : \text{sat}, 30 \text{ ms};$$ $$n = 5 : \text{sat}, 0.12 \text{ s}; \quad n = 6 : \text{sat}, 0.3 \text{ s}; \quad n = 7 : \text{sat}, 1.4 \text{ s};$$ $$n = 8 : \text{sat}, 2.8 \text{ s}; \quad n = 9 : \text{unsat}, 6.3 \text{ s}.$$

The $n = 3$ instance is Figure 12.1; representative solutions for $n = 4$ and $n = 5$ are Figures 12.2 and 12.3.

Why $n = 9$ fails: large primes

The unexpected infeasibility at $n = 9$ comes from a clean pigeonhole argument on large primes. A prime $p$ with $n^2 / 2 < p \leq n^2$ divides exactly one value in $\{1, 2, \ldots, n^2\}$, namely $p$ itself (since $2p > n^2$). Whichever row contains the value $p$ is the only row whose product is divisible by $p$, and similarly for columns. The bijection $\sigma$ that witnesses multiset equality must therefore map the row containing $p$ to the column containing $p$: this fixes one entry of $\sigma$ per such prime.

Now count the primes in $(n^2 / 2, n^2]$: $$n = 9 : \{41, 43, 47, 53, 59, 61, 67, 71, 73, 79\}, \quad \text{ten primes}.$$ There are ten “large primes” but only nine rows. By pigeonhole, two of these primes lie in the same row, at different columns. The bijection $\sigma$ is forced to map that row to both columns at once, which is impossible. No solution can exist.

This reasoning extends: feasibility fails whenever $$\pi(n^2) - \pi\!\bigl(n^2 / 2\bigr) \;>\; n,$$ where $\pi$ is the prime-counting function. The first offender is $n = 9$; the next are $n = 11$ (thirteen primes), $n = 12$ (fourteen primes), and so on. By the prime-number theorem the left side grows like $n^2 / (2 \ln n)$, so the inequality holds for all sufficiently large $n$; feasibility is therefore rare in the long run, and the feasible $n$ form a finite set.

The picture for small $n$ is then $$\{3, 4, 5, 6, 7, 8\} : \text{feasible}; \qquad \{2, 9, 11, 12\} : \text{infeasible (by the counts above)}.$$ The large-prime inequality is satisfied at $n = 11$ and $n = 12$ and, by the prime-number-theorem growth, at every sufficiently large $n$, so all but finitely many $n$ are infeasible; but it does not follow that every $n \geq 11$ fails, since the inequality is not known to hold without exception, and establishing the precise infeasible set would require checking the remaining cases individually. The status of $n = 10$ is in any case undetermined by the large-prime argument alone: there are exactly ten large primes in $(50, 100]$, so the pigeonhole is tight but not strict, and a dedicated longer search is required to settle it.

Sources. The monkey–cat–dog problem appears as a training problem in Problem Solving Strategies (Arthur Engel, $1998$) and in various olympiad collections; the large-prime argument that rules out $n = 9$ and all sufficiently large $n$ is due to multiple authors independently, perhaps first written up by R. Guy in Unsolved Problems in Number Theory. The feasibility of small $n$ is constructive but the constructions for $n \geq 5$ are not particularly illuminating; CP-SAT’s rapid decisions are the only tidy proof that each is feasible. The general classification of feasible $n$ — which finite set exactly? — combines the large-prime argument (ruling out infinitely many $n$) with more delicate parity arguments at the remaining $n$; an elementary complete classification is not known to the author.