For even positive integer $n$ we put all numbers $1,2,...,n^2$ into the squares of an $n\times n$ chessboard (each number appears once and only once). Let $S_1$ be the sum of the numbers put in the black squares and $S_2$ be the sum of the numbers put in the white squares. Find all $n$ such that we can achieve $\frac{S_1}{S_2}=\frac{39}{64}.$
Problem
Source: Greek Mathematical Olympiad 2014
Tags: Euler, modular arithmetic, combinatorial geometry, combinatorics proposed, combinatorics, Discrete intermediate value theorem
17.03.2014 19:30
What a weird problem! Suppose we have such an arrangement. Then $103 S_1 = 64(1 + 2 + \ldots + n^2) = 32n^2(n^2 + 1)$. Now Fermat's Theorem (though, I think, first proved by Euler) establishes that when $n$ is even, $n^2 + 1$ is divisible only by primes of the form $4k + 1$. However, $103 \equiv 3 \pmod 4$. Thus, it is a necessary condition that $103 \mid n^2$ and so $103 \mid n$. We construct a solution for any such $n$ using the discrete intermediate value theorem ( ): start by placing the numbers $1, 2, \ldots, n^2/2$ on the black squares and the remaining numbers on the white squares. This gives the sum of the entries on black squares as \[ \sum_{i = 1}^{n^2/2} i = \frac{n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i < \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \] It is possible to go from this arrangement to one in which the distribution of values on colors is reversed by successively adding 1 to some black square and subtracting 1 from some white square. At the end of this process, we end up with an arrangement in which the sum of the entries on the black squares is \[ \sum_{i = 1 + n^2/2}^{n^2} i = \frac{3n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i > \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \] In the interim, we pass through every integer sum, including exactly the desired $ \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i$.
11.03.2016 07:45
Nice Solution!
27.07.2017 03:54
JBL wrote: What a weird problem! Suppose we have such an arrangement. Then $103 S_1 = 64(1 + 2 + \ldots + n^2) = 32n^2(n^2 + 1)$. Now Fermat's Theorem (though, I think, first proved by Euler) establishes that when $n$ is even, $n^2 + 1$ is divisible only by primes of the form $4k + 1$. However, $103 \equiv 3 \pmod 4$. Thus, it is a necessary condition that $103 \mid n^2$ and so $103 \mid n$. We construct a solution for any such $n$ using the discrete intermediate value theorem ( ): start by placing the numbers $1, 2, \ldots, n^2/2$ on the black squares and the remaining numbers on the white squares. This gives the sum of the entries on black squares as \[ \sum_{i = 1}^{n^2/2} i = \frac{n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i < \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \]It is possible to go from this arrangement to one in which the distribution of values on colors is reversed by successively adding 1 to some black square and subtracting 1 from some white square. At the end of this process, we end up with an arrangement in which the sum of the entries on the black squares is \[ \sum_{i = 1 + n^2/2}^{n^2} i = \frac{3n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i > \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \]In the interim, we pass through every integer sum, including exactly the desired $ \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i$. Your entire proof falls apart because $1+2+...+n^2 = \frac{n(n+1)(2n+1)}{6}$. Not sure where you got that alternative formula from.
27.07.2017 04:07
skrublord420 wrote: JBL wrote: What a weird problem! Suppose we have such an arrangement. Then $103 S_1 = 64(1 + 2 + \ldots + n^2) = 32n^2(n^2 + 1)$. Now Fermat's Theorem (though, I think, first proved by Euler) establishes that when $n$ is even, $n^2 + 1$ is divisible only by primes of the form $4k + 1$. However, $103 \equiv 3 \pmod 4$. Thus, it is a necessary condition that $103 \mid n^2$ and so $103 \mid n$. We construct a solution for any such $n$ using the discrete intermediate value theorem ( ): start by placing the numbers $1, 2, \ldots, n^2/2$ on the black squares and the remaining numbers on the white squares. This gives the sum of the entries on black squares as \[ \sum_{i = 1}^{n^2/2} i = \frac{n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i < \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \]It is possible to go from this arrangement to one in which the distribution of values on colors is reversed by successively adding 1 to some black square and subtracting 1 from some white square. At the end of this process, we end up with an arrangement in which the sum of the entries on the black squares is \[ \sum_{i = 1 + n^2/2}^{n^2} i = \frac{3n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i > \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \]In the interim, we pass through every integer sum, including exactly the desired $ \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i$. Your entire proof falls apart because $1+2+...+n^2 = \frac{n(n+1)(2n+1)}{6}$. Not sure where you got that alternative formula from. Nope, $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ JBL simply uses the formula for summing till the n-th term.
28.07.2017 03:15
Salty_Titanium wrote: skrublord420 wrote: JBL wrote: What a weird problem! Suppose we have such an arrangement. Then $103 S_1 = 64(1 + 2 + \ldots + n^2) = 32n^2(n^2 + 1)$. Now Fermat's Theorem (though, I think, first proved by Euler) establishes that when $n$ is even, $n^2 + 1$ is divisible only by primes of the form $4k + 1$. However, $103 \equiv 3 \pmod 4$. Thus, it is a necessary condition that $103 \mid n^2$ and so $103 \mid n$. We construct a solution for any such $n$ using the discrete intermediate value theorem ( ): start by placing the numbers $1, 2, \ldots, n^2/2$ on the black squares and the remaining numbers on the white squares. This gives the sum of the entries on black squares as \[ \sum_{i = 1}^{n^2/2} i = \frac{n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i < \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \]It is possible to go from this arrangement to one in which the distribution of values on colors is reversed by successively adding 1 to some black square and subtracting 1 from some white square. At the end of this process, we end up with an arrangement in which the sum of the entries on the black squares is \[ \sum_{i = 1 + n^2/2}^{n^2} i = \frac{3n^2 + 2}{4n^2 + 4} \cdot \sum_{i = 1}^{n^2} i > \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i. \]In the interim, we pass through every integer sum, including exactly the desired $ \frac{39}{103} \cdot \sum_{i = 1}^{n^2} i$. Your entire proof falls apart because $1+2+...+n^2 = \frac{n(n+1)(2n+1)}{6}$. Not sure where you got that alternative formula from. Nope, $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ JBL simply uses the formula for summing till the n-th term. You're correct. Now I have to redo my proof!