Maths Olympiad Prep

Library / /454 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it

An anti-Pascal pyramid is a finite set of numbers, placed in a triangle-shaped array so that the first row of the array contains one number, the second row contains two numbers, the third row contains three numbers, and so on; and, except for the numbers in the bottom row, each number equals the absolute value of the difference of the two numbers below it. For instance, the triangle below is an anti-Pascal pyramid with four rows, in which every integer from 1 to 1+2+3+4=101 + 2 + 3 + 4 = 10 occurs exactly once:
265783109. \begin{array}{ccccc} & & & \\ & 2 & 6 & \\ & 5 & 7 & \\ 8 & 3 & 10 & 9 . \end{array}
Is it possible to form an anti-Pascal pyramid with 2018 rows, using every integer from 1 to 1+2++20181 + 2 + \cdots + 2018 exactly once? (Iran) Answer: No, it is not possible.

Solution

Let TT be an anti-Pascal pyramid with nn rows, containing every integer from 1 to 1+2++n1+2+\cdots+n, and let a1a_{1} be the topmost number in TT (Figure 1). The two numbers below a1a_{1} are some a2a_{2} and b2=a1+a2b_{2}=a_{1}+a_{2}, the two numbers below b2b_{2} are some a3a_{3} and b3=a1+a2+a3b_{3}=a_{1}+a_{2}+a_{3}, and so on and so forth all the way down to the bottom row, where some ana_{n} and bn=a1+a2++anb_{n}=a_{1}+a_{2}+\cdots+a_{n} are the two neighbors below bn1=a1+a2++an1b_{n-1}=a_{1}+a_{2}+\cdots+a_{n-1}. Since the aka_{k} are nn pairwise distinct positive integers whose sum does not exceed the largest number in TT, which is 1+2++n1+2+\cdots+n, it follows that they form a permutation of 1,2,,n1,2, \ldots, n. ! Figure 1 ! Figure 2 Consider now (Figure 2) the two 'equilateral' subtriangles of TT whose bottom rows contain the numbers to the left, respectively right, of the pair an,bna_{n}, b_{n}. (One of these subtriangles may very well be empty.) At least one of these subtriangles, say TT^{\prime}, has side length (n2)/2\ell \geqslant\lceil(n-2) / 2\rceil. Since TT^{\prime} obeys the anti-Pascal rule, it contains \ell pairwise distinct positive integers a1,a2,,aa_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{\ell}^{\prime}, where a1a_{1}^{\prime} is at the apex, and aka_{k}^{\prime} and bk=a1+a2++akb_{k}^{\prime}=a_{1}^{\prime}+a_{2}^{\prime}+\cdots+a_{k}^{\prime} are the two neighbors below bk1b_{k-1}^{\prime} for each k=2,3,k=2,3 \ldots, \ell. Since the aka_{k} all lie outside TT^{\prime}, and they form a permutation of 1,2,,n1,2, \ldots, n, the aka_{k}^{\prime} are all greater than nn. Consequently, b(n+1)+(n+2)++(n+)=(2n++1)212n22(2n+n22+1)=5n(n2)8, \begin{array}{r} b_{\ell}^{\prime} \geqslant(n+1)+(n+2)+\cdots+(n+\ell)=\frac{\ell(2 n+\ell+1)}{2} \\ \geqslant \frac{1}{2} \cdot \frac{n-2}{2}\left(2 n+\frac{n-2}{2}+1\right)=\frac{5 n(n-2)}{8}, \end{array} which is greater than 1+2++n=n(n+1)/21+2+\cdots+n=n(n+1) / 2 for n=2018n=2018. A contradiction. Comment. The above estimate may be slightly improved by noticing that bbnb_{\ell}^{\prime} \neq b_{n}. This implies n(n+1)/2=bn>b(n2)/2(2n+(n2)/2+1)/2n(n+1) / 2=b_{n}>b_{\ell}^{\prime} \geqslant\lceil(n-2) / 2\rceil(2 n+\lceil(n-2) / 2\rceil+1) / 2, so n7n \leqslant 7 if nn is odd, and n12n \leqslant 12 if nn is even. It seems that the largest anti-Pascal pyramid whose entries are a permutation of the integers from 1 to 1+2++n1+2+\cdots+n has 5 rows.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.