2
$\begingroup$

Let $n$ be a positive integer. Show that one cannot fill a $n \times n$ square grid with numbers $1, 2, \dots, n^2$ such that sum of numbers on each row and column is a power of 2.

My attempt: Assume the contrary. Let the sum of the columns be $2^{a_i}, 1\leq i \leq n$ and the sum of the rows be $2^{b_i}, 1 \leq i \leq n$. Observe that $n$ must be even (otherwise we have sum of all the numbers on the grid is $\dfrac{n^2(n^2+1)}{2}$ not divisible by 2). Then from the identity $\displaystyle\sum_{i=1}^n2^{a_i} = \sum_{i=1}^n2^{b_i}$ I think of the binary representation of this number, but it doesn't seem to work since the $a_i$'s are not necessarily distinct. Then I got stucked from here.

$\endgroup$
  • 3
    $\begingroup$ The trivial $1\times1$ case actually works $\endgroup$ – Peter Woolfitt Nov 27 '15 at 17:11
  • $\begingroup$ Ever looking at the parity of the rows and columns? For n greater than 1, perhaps it would be easier to note how there have to be an even number of odd numbers in each row and column which isn't going to work, e.g. in the 2 x 2 case there are only 2 odd numbers to allocate, etc. Could be an easier route to take. $\endgroup$ – JB King Nov 27 '15 at 17:18
  • 2
    $\begingroup$ @JBKing Actually that can work - you just need $4\mid n$. For example $\left[\begin{matrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{matrix}\right]$ $\endgroup$ – Peter Woolfitt Nov 27 '15 at 17:19
  • 2
    $\begingroup$ @Mirko The example was not an answer to the question, but rather a counterexample to the preceding comment - that is an example where each row and column sum is even $\endgroup$ – Peter Woolfitt Nov 27 '15 at 17:42
  • 2
    $\begingroup$ If one considers what are the minimum and maximum sums of a row and then looks for what powers of 2 exist between those extremes that may be another part of the proof here. In the case of $n=4$, the minimum is 10 and the maximum is 58 for the 1-16 square though the powers of 2 then would be 16 and 32 which does reduce things quite a bit as the overall sum of all 4 rows would be 8*17=136 ($\frac{16*17}{2}$, as 1-16 get used, which isn't divisible by 16. Maybe that is the secret to the approach here. $\endgroup$ – JB King Nov 27 '15 at 17:42
4
$\begingroup$

The sum is $\frac{n^2(n^2+1)}{2}$. For $n\gt 1$, $n$ odd is impossible.

Let $2^k$ be the highest power of $2$ that divides $n$. Then the highest power of $2$ that divides our sum is $2^{2k-1}$, which is $\le \frac{n^2}{2}$.

Consider the smallest row or column sum. Say it is a row sum, and is equal to $2^l$. Then all row sums are $\ge 2^l$, and powers of $2$. So the sum of the row sums, that is, $1+2+\cdots +n^2$, is congruent to $0$ modulo $2^l$.

The smallest possible row sum is $\ge 1+2+\cdots +n$, which is $\frac{n(n+1)}{2}$. This is greater than $\frac{n^2}{2}$, contradicting the fact that the highest power of $2$ that divides $1+2+\cdots +n^2$ is $\le \frac{n^2}{2}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 nice. @PeterWoolfitt it looks like the answer was fixed since your comment. $\endgroup$ – Colm Bhandal Nov 27 '15 at 18:45
2
$\begingroup$

Consider taking the sum of the minimum $n$ values to determine a floor of the lowest power of 2 that could be computed and note that the sum of all the numbers of in the square $\frac{n^2(n^2+1)}{2}$ has to be divisible by this value.

Note that for odd $n$, the parity argument I state in the comments could be used to remove those cases. Looking at the low even cases:

$n=2$, the sum of 1-2 is 3, which would make 4 the lowest power of 2 sum for any row. However, the sum of the entire square 1-4 is 10 which isn't divisible by 4.

$n=4$, the sum of 1-4 is 5*2=10 which would make 16 the lowest power of 2 sum of any row. However, the sum of the entire square 1-16 is 17*8 which isn't divisible by 16.

$n=6$, the sum of 1-6 is 7*3=21 which would make 32 the lowest power of 2 sum of any row. However, the sum of the entire square is 1-36 is 37*18 which isn't divisible by 32.

$n=8$, the sum of 1-8 is 9*4=36 which would make 64 the lowest power of 2 sum of any row. However, the sum of the entire square 1-64 is 65*32 which isn't going to be divisible by 64.

$n=10$ the sum of 1-10 is 11*5=55 which would make 64 the lowest power of 2 sum of any row. However, the entire square has a sum of 1-100 is 101*50 which isn't divisible by 64.

$n=12$, the sum of 1-12 is 13*6=78 which would make 128 the lowest sum of a row. However, the entire square's sum is 1-144 is 145*72 which isn't divisible by 128.

$n=16$, the sum would be 17*8=136 making 256 the lowest sum. Yet, the entire square is 1-256 which is 257*128.

$n=32$, the sum would be 33*16=528, making 1024 the lowest sum. Yet, the entire square is 1-1024 which is 1025*512.

$n=64$, the sum would be 65*32=2080, making 4096 the lowest sum. Yet, the entire square is 1-4096 which is 4097*2048.

In general:

For each $n=2^x$, the minimal row sum would be $(2^x+1)(2^{x-1})$ (which is $\frac{n(n+1)}{2}$), making $2^{2x}=n^2$ the lowest power of 2 that can be a sum, yet the sum of the entire square will be $2^{2x-1}(2^{2x}+1)$ which isn't divisible by $2^{2x}$ and thus we are done. The key point is to consider that the minimal sum would be a common factor of all $n$ sums and thus the overall total of 1-$n^2$ has to be divisible by this but it isn't.

The space between the powers of 2 keeps going up quite a bit but there is something to the minimal factor having to be in the sum that is part of where for $n>1$ this isn't easy to do.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You may consider the generalized case, $n=2^xt$ where $t$ is an odd number. In that case your solution will still work, because we only consider $e_2(n)$ (the highest power of 2 that divides $n$). Thanks for your beautiful solution. $\endgroup$ – primitiveroot Nov 27 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.