Consider the configurations of integers $a_{1,1}$ $a_{2,1} \quad a_{2,2}$ $a_{3,1} \quad a_{3,2} \quad a_{3,3}$ $\dots \quad \dots \quad \dots$ $a_{2017,1} \quad a_{2017,2} \quad a_{2017,3} \quad \dots \quad a_{2017,2017}$ Where $a_{i,j} = a_{i+1,j} + a_{i+1,j+1}$ for all $i,j$ such that $1 \leq j \leq i \leq 2016$. Determine the maximum amount of odd integers that such configuration can contain.
Problem
Source: Iberoamerican 2017 p. 3
Tags: combinatorics, Iberoamerican, international competitions
proglote
25.11.2017 02:45
Let's replace 2017 by $n$, I claim the answer is $\left \lceil \frac{n(n+1)}{3} \right \rceil$ Construction: $a_{i,j} = (3 \nmid i+j) \mod 2$, easy to see it satisfies the additive constraint (mod 2) Upper bound: the key idea is that it's not possible to have $a_{i,j}. a_{i+1,j}, a_{i+1,j+1}$ all odd for $1 \le j \le i < n$. So let's relax the sum condition to "every such triangle must contain at least one even". It suffices to show we need to have at least $\frac{n(n+1)}{2} - \left \lceil \frac{n(n+1)}{3} \right \rceil = \left \lfloor \frac{n(n+1)}{6} \right \rfloor$ evens. It's easy to check it for $n < 3$. For $n \ge 3$ we proceed by induction. It suffices to chop away the first $n-3$ rows and show the remaining band requires $\left \lfloor \frac{n(n+1)}{6} \right \rfloor - \left \lfloor \frac{(n-3)(n-2)}{6} \right \rfloor = n-1$ evens. We again prove this by induction. It's easy to check it for $n \le 4$. The band has three rows: $n-2, n-1$ and $n$. If $a_{n-1, 2}$ is even, note that one of $a_{n,1}, a_{n-1,1}, a_{n,2}$ is also even, so we found two evens and can chop away the first two "columns" to apply the inductive hypothesis. If $a_{n-1,2}$ is not even, note that we need to have three evens in the first three columns, so again we can apply the inductive hypothesis to see that the band requires $n-1$ evens. We conclude that the array requires $\left \lfloor \frac{n(n+1)}{6} \right \rfloor$ evens, as desired.