Part b is also quite easy. Simply put the number $$k(n+j)$$in the cell in the $j$th row from the bottom and the $k$th column from the left. This works for all $n$.

laegolas wrote: Part b is also quite easy. Simply put the number $$k(n+j)$$in the cell in the $j$th row from the bottom and the $k$th column from the left. This works for all $n$. The $n^2$ integers should be pairwise distinct ..

Edit: I see what you say now

It is indeed true...

laegolas wrote: Part b is also quite easy. Simply put the number $$k(n+j)$$in the cell in the $j$th row from the bottom and the $k$th column from the left. This works for all $n$. For example, when $n=17$, we have $12(17+7)=16(17+1)$. But this construction work for small $n$. In fact, this problem is not hard, but it's a bit long. So I'm too lazy to write the solution.

Part (a) is trivial. For part (b), the only ones which work are $2,4$. Constructing a minimal Benelux square for these is pretty easy, if you understand the principles used in the actual proof below: Suppose a minimal Benelux square exists. Note that if all entries are less than $2n^2$, we must have not have any of the $2n$ distinct gcds exceeding $2n$. First, we rearrange the rows and columns so that the rows/columns are in descending order of gcd from the top left. WLOG, the 1st row is the one with gcd $2n$. This row is filled with the first $n$ multiples of $2n$. Note that none of these are divisible by $2n-1$, so we can't have a column with gcd $2n-1$. So the second row is the one with gcd $2n-1$, and it contains the first $n$ multiples of $2n-1$. Now, the gcd of a full column is a divisor of the gcd of any two entries. But if you consider the $2 \times n$ grid comprised of the first two rows, you will get maximum gcd for a column at $n$ (since $2n-1, 2n$ are co-prime). So the gcds for columns can't exceed $n$ i.e. these gcds will be the numbers from $1$ to $n$. So all the numbers $n+1$ to $2n$ will be gcds of rows. Note that $2n-2$ has $n+1$ multiples smaller than $2n^2$, one of which is $2n(n-1)$ and thus used in the 1st row. Now, suppose we have an odd prime $p$ with $p|n$. Let $n=pk$. Then we must have $k$ columns where the gcd and thus every number is divisible by $p$. But of the $n+1$ multiples of $2n-2$ smaller than $2n^2$, exactly $k$ are divisible by $p$. But one of these was used in the 1st row, so we can't have $k$ entries in the 3rd row with gcd $2n-2$ which are divisible by $p$. Thus $n$ is not divisible by any odd primes i.e. it is a power of 2. Finally, to disprove for higher powers of $2$, consider the cells which must have numbers divisible by $6$. If the column/row gcd is divisible by $2$ while the row/column gcd is $3$, the cell must have an entry divisible by $6$. And if either of the row/column gcds is divisible by $6$, we'll have the cell entry divisible by $6$. If you count it all up, you'll find that the number of cells which must have a number divisible by $6$ is larger than $[ \frac{2^n}{6} ]$ once $n>2$. Using the fact that: $$ [ \frac{2^n}{3} ] =\left\{\begin{array}{cc} \dfrac{2^n-1}{3},&\mbox{ if } n \mbox{ even}\\\dfrac{2^n-1}{3}, & \mbox{ if } n \mbox{ odd} \end{array}\right.$$ This is just some algebra, which I'll leave you to do (QED).

Zawadx wrote: Now, the gcd of a full column is a divisor of the gcd of any two entries. But if you consider the $2 \times n$ grid comprised of the first two rows, you will get maximum gcd for a column at $n$ (since $2n-1, 2n$ are co-prime). So the gcds for columns can't exceed $n$ i.e. these gcds will be the numbers from $1$ to $n$. So all the numbers $n+1$ to $2n$ will be gcds of rows. Sorry for reviving, but i cant understand this part. perhaps i misunderstood it I think this is counterexample: $n=25$, $(1, 1)=50 \times 7=350 , (1, 2)=49 \times 25=1225$ (here, $(i, j)$ means the intersection of $i$th row and $j$th column.) then, $gcd(350, 1225)=175$, which is bigger than $25$

sansae wrote: Zawadx wrote: Now, the gcd of a full column is a divisor of the gcd of any two entries. But if you consider the $2 \times n$ grid comprised of the first two rows, you will get maximum gcd for a column at $n$ (since $2n-1, 2n$ are co-prime). So the gcds for columns can't exceed $n$ i.e. these gcds will be the numbers from $1$ to $n$. So all the numbers $n+1$ to $2n$ will be gcds of rows. Sorry for reviving, but i cant understand this part. perhaps i misunderstood it I think this is counterexample: $n=25$, $(1, 1)=50 \times 7=350 , (1, 2)=49 \times 25=1225$ (here, $(i, j)$ means the intersection of $i$th row and $j$th column.) then, $gcd(350, 1225)=175$, which is bigger than $25$ Thank you for revving and pointing out the flaw! It goes to show how fragile proofs can be. You are correct, that statement is incorrect (or at least requires better proof). And without the rigidity that step, the rest of the arguments can't be patched up to work very easily. I guess we must find a way to prove this lemma, or change approaches entirely.

Zawadx wrote: Thank you for revving and pointing out the flaw! It goes to show how fragile proofs can be. You are correct, that statement is incorrect (or at least requires better proof). And without the rigidity that step, the rest of the arguments can't be patched up to work very easily. I guess we must find a way to prove this lemma, or change approaches entirely. I think one can use Bertrand's postulate to finish the proof.

Exactly, like sansae said. By the bertrand's postulate we know that there exist a prime $p$ such that $n<p<2n-2$ for $n>3$, then, there exist a prime $p$ such that $n/2 < p < n$, also $n <2p < 2n$, now we see that WLOG we have the colums with the gcd = $2p$, $2n$ and the rows with gcd =$p$, $n$. Then just see that the intersection of the colum $2p$, the row $n$ and the colum $2n$, row $2p$ have a numbers which are multiples of $2np$, then at the one of them is $>=4np >2n^2$. contradiction.