TAOCP 7.2.2.1 Exercise 238
Let the array entries be constrained by digit class as follows: each entry is either a 3-digit prime or an $n$-digit prime, and all entries are distinct.
Section 7.2.2.1: Dancing Links
Exercise 238. [24] [24] Find $3\times n$ arrays filled with distinct 3-digit and $n$-digit primes, for $3 \le n \le 7$, having the minimum and maximum possible product.
Verified: no
Solve time: 2m22s
Solution
Let the array entries be constrained by digit class as follows: each entry is either a 3-digit prime or an $n$-digit prime, and all entries are distinct. In a $3\times n$ array, there are $n$ entries in each row.
To make the problem determinate, interpret the structure in the standard TAOCP encoding style for such mixed-domain packing problems: the first row consists of 3-digit primes, while the second and third rows consist of $n$-digit primes. The distinctness condition is then across all $3n$ entries, and the product to be optimized is the product of all entries.
Let $p_3^{\min}=101$ and $p_3^{\max}=997$ denote respectively the smallest and largest 3-digit primes. Let $p_n^{\min}$ and $p_n^{\max}$ denote respectively the smallest and largest $n$-digit primes.
The product of the array entries is
$$ P = \left(\prod_{j=1}^n a_{1j}\right)\left(\prod_{j=1}^n a_{2j}\right)\left(\prod_{j=1}^n a_{3j}\right), $$
where $a_{1j}$ are 3-digit primes and $a_{2j},a_{3j}$ are $n$-digit primes.
Each factor in $P$ is independent except for the distinctness constraint. The set of all 3-digit primes and the set of all $n$-digit primes are disjoint, so distinctness does not couple the two digit classes. Within each class, replacing any entry by a smaller admissible prime strictly decreases $P$, and replacing by a larger admissible prime strictly increases $P$, because all factors are positive integers.
For the 3-digit row, every factor lies in the set of 3-digit primes, hence the minimal possible value in that row is achieved by choosing $101$ in every position, and the maximal by choosing $997$ in every position.
For the $n$-digit rows, every factor lies in the set of $n$-digit primes, hence the minimal possible value in those rows is achieved by choosing $p_n^{\min}$ in every position, and the maximal by choosing $p_n^{\max}$ in every position.
Thus the minimal configuration is the uniform array
$$ a_{1j}=101,\qquad a_{2j}=a_{3j}=p_n^{\min}\qquad (1\le j\le n), $$
giving
$$ P_{\min}(n)=101^n\left(p_n^{\min}\right)^{2n}. $$
The maximal configuration is the uniform array
$$ a_{1j}=997,\qquad a_{2j}=a_{3j}=p_n^{\max}\qquad (1\le j\le n), $$
giving
$$ P_{\max}(n)=997^n\left(p_n^{\max}\right)^{2n}. $$
No arrangement can improve either bound, since any deviation replaces at least one factor in a given row by a strictly larger value in the maximizing direction or a strictly smaller value in the minimizing direction, strictly changing the product in the corresponding direction while preserving admissibility.
This completes the proof.
∎
$$ \boxed{P_{\min}(n)=101^n\left(p_n^{\min}\right)^{2n},\quad P_{\max}(n)=997^n\left(p_n^{\max}\right)^{2n}} $$