Thread: 4x5 integer table

Twenty different positive integers are written in a 4 X 5 table. Any two neighbours (numbers in cells with a common side) have a common divisor greater than 1. If n is the largest number in the table, find the smallest possible value of n.

I present you with the following solution.

Spoiler:

Let the minimum such . I came up with the following upper bound: with the following solution to the puzzle



If we inspect this table, we see that it satisfies the conditions for divisibility and the upper bound is correct. Now, if a prime appears explicitly in the table, its neighbors must be divisible by that prime. If the prime appears in the interior, its neighbors must be at least the sizes . If it appears on an edge, the neighbors are at least . If it appears in a corner the neighbors are at least . Using the lowest of these upper bounds , in an optimal solution we must have that , or . That is, the only explicit primes in this table are at most and . No other primes can appear explicitly in the table. As we can see, up to 26, the only numbers that do not appear in this table are and . Since these numbers are not allowed in an optimal solution, the solution I provided must be optimal. Therefore .