Maths Olympiad Prep

Library / /257 of 383

Combinatorics Difficulty 8.8 Shortlist Prove it IMO

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:
42 65 7 18 3 10 9. \begin{aligned} & 4 \\ & 2\ 6 \\ & 5\ 7\ 1 \\ & 8\ 3\ 10\ 9 . \end{aligned}
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?

Solution

Answer: No, it is not possible.

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 neighbours 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 1
Figure 2
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 neighbours 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.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.