Maths Olympiad Prep

Library / /7 of 8

Combinatorics Difficulty 7.0 National olympiad Prove it Romania

Given a positive integer nn, a triangular array (ai,j)(a_{i,j}) of zeroes and ones, where ii and jj run through the positive integers such that i+jn+1i + j \le n + 1, is called a *binary anti-Pascal n-triangle* if ai,j+ai,j+1+ai+1,j1(mod2)a_{i,j} + a_{i,j+1} + a_{i+1,j} \equiv 1 \pmod 2 for all possible values ii and jj may take on. Determine the minimum number of ones a binary anti-Pascal nn-triangle may contain.

Solution

In what follows, part of the generic configurations referred to may not exist for the first few values of nn; in this case, simply consider the corresponding induced

We now show by induction on nn that a binary anti-Pascal nn-triangle contains at least n(n+1)/6\lfloor n(n+1)/6 \rfloor ones, of which at least n1n-1 lie on the bottom three rows (and since the transpose of a binary anti-Pascal triangle is again one such, the same holds for the leftmost three columns).
The cases n=1,2,3n=1, 2, 3 are easily dealt with, so let n4n \ge 4, and let AA be a binary anti-Pascal nn-triangle. The lower left 3×33 \times 3 subarray AA' (induced if n=4n=4) contains at least 3 ones, unless the lower left and central entries are both one and the other entries are all zero, in which case there are only 2 ones in AA'.
In the former case, consider the binary anti-Pascal (n3)(n-3)-triangle consisting of the rightmost n3n-3 columns of AA. By the induction hypothesis, the bottom three rows of this triangle contain at least n4n-4 ones, so the bottom three rows of AA contain at least 3+(n4)=n13 + (n-4) = n-1 ones.
In the latter case, the statement clearly holds if n=4n=4, so let n5n \ge 5 and notice that the bottom two entries of the column of AA adjoining AA' along the right flank are both one. Thus, the 3×43 \times 4 subarray of AA extending AA' rightwards contains at least 4 ones. The rightmost n4n-4 columns of AA form a binary anti-Pascal (n4)(n-4)-triangle whose bottom three rows contain at least n5n-5 ones, by the induction hypothesis. Hence the bottom three rows of AA contain at least 4+(n5)=n14 + (n-5) = n-1 ones.
In either case, the bottom three rows of AA contain at least n1n-1 ones. Finally, by the induction hypothesis, the binary anti-Pascal (n3)(n-3)-triangle atop the bottom three rows of AA contains at least (n3)(n2)/6\lfloor(n-3)(n-2)/6\rfloor ones, so AA contains at least n1+(n3)(n2)/6=n(n+1)/6n-1 + \lfloor(n-3)(n-2)/6\rfloor = \lfloor n(n+1)/6 \rfloor ones. This completes the induction and concludes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.