Given a positive integer $n$. A triangular array $(a_{i,j})$ of zeros and ones, where $i$ and $j$ run through the positive integers such that $i+j\leqslant n+1$ is called a binary anti-Pascal $n$-triangle if $a_{i,j}+a_{i,j+1}+a_{i+1,j}\equiv 1\pmod{2}$ for all possible values $i$ and $j$ may take on. Determine the minimum number of ones a binary anti-Pascal $n$-triangle may contain.
Problem
Source: Stars of Mathematics 2019, Senior, P4
Tags: combinatorics
02.12.2019 01:21
We'll call the set of numbers $\{a_{1, i}, a_{2, i-1}, \cdots, a_{i-1, 2}, a_{i, 1}\}$ the $i$th row of the triangular array. We will say that two numbers $a_{x, y}$ and $a_{z, w}$ are adjacent if one of the following holds. 1) $x = z, |y-w| = 1$ 2) $y = w, |x-z| = 1$ 3) $x+y = z+w, |x-y| = 1$. We will show that the answer is $\left \lfloor \frac{n(n+1)}{6} \right \rfloor.$ Let's first show how to construct this. Color the array with three colors so that no two adjacent numbers are the same color. Now, let all the numbers of the least common color be $1$'s and the others be $0.$ Now, we'll show that this is optimal by induction on $n$. For $n = 1, 2, 3$, this is obvious. Suppose it holds for $n < k$, for some $k \ge 4.$ When $n = k$, consider the last three rows of the array. There are a total of $(k-2) + (k-1) + k = 3k-3$ numbers in these three rows, so if we show that at least $k-1$ of them are ones, we're done. We'll use a separate induction to show this fact. More specifically, if we have three rows of sizes $i, i+1,$ and $i+2$ one on top of the other (so that they are the last three rows of a triangular array), then at least $i+1$ of the numbers are $1$'s. When $i = 1$ this is trivial. Suppose it holds for $i < t.$ When $i = t$, consider the three numbers at the end of each row ($a_{i, 1}, a_{i+1, 1}, a_{i+2, 1}$). If any is a $1$, we're done by the inductive hypothesis for $i = t-1$.. Else, it's clear that $a_{i, 2}, a_{i+1, 2}$ are both $1$. Hence, we may again use the inductive hypothesis, but for $i = t-2$, to finish. Let's now return to the original induction. We've now shown that at least $k-1$ of the numbers in the last three rows are $1$'s, and so by the inductive hypothesis for $n = k-3$, the induction is complete. Hence, the problem is also complete, and the answer is $\boxed{\left \lfloor \frac{n(n+1)}{6} \right \rfloor}.$ $\square$