Difference between revisions of "2018 IMO Problems/Problem 3"

Revision as of 08:00, 8 September 2018

An anti-Pascal triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it. For example, the following is an anti-Pascal triangle with four rows which contains every integer from $1$ to $10$

$4$ $2\quad 6$ $5\quad 7 \quad 1$ $8\quad 3 \quad 10 \quad 9$

Does there exist an anti-Pascal triangle with $2018$ rows which contains every integer from $1$ to $1 + 2 + 3 + \dots + 2018$ ?

Solution

Trivially it is required that every positive integer from $1$ to $1+2+3+\cdots+2018$ appears exactly once.

Let $M_n$ denote the maximum number in the $n$ th row and let $m_n$ denote the minimum number in the $n$ th row.

Now assume $n\leq 2017$ and consider the numbers directly below $M_n$ . Call these $a$ and $b$ where w.l.o.g. $a>b$ . Then $a-b=M_n$ . Since $a\leq M_{n+1}$ and $b\geq m_{n+1}$ , we obtain that $M_{n+1}\geq M_n+m_{n+1}$ .

Thus, for $1\leq i<j\leq 2018$ , $M_j\geq M_i+\sum_{k=i+1}^j m_i$

In particular, since $M_1=m_1$ , $M_{2018}\geq \sum_{k=1}^{2018} m_k$

Thus $M_{2018}$ is a sum of 2018 distinct positive integers. However, $M_{2018}\leq 1+2+3+\cdots+2018$ . Thus $M_{2018}=1+2+3+\cdots+2018$ and $\{m_1,m_2,m_3,\dots,m_{2018}\}$ is a permutation of $\{1,2,3,\dots,2018\}$ . Also, this implies that the other inequalities are also equalities and, for any $1\leq j\leq 2018$ , $M_j=\sum_{k=1}^j m_k$

Now let any positive integer $n\leq 2018$ be "small" and let any positive integer $1+2+3+\cdots+2017\leq n\leq 1+2+3+\cdots+2018$ be "large". Since $\{m_1,m_2,m_3,\dots,m_{2018}\}$ is a permutation of $\{1,2,3,\dots,2018\}$ , there is exactly one small number in each row.

If $n\leq 1954$ , we have $M_n=\sum_{k=1}^n m_k \leq 2018+2017+2016+\cdots+65$ $=(1+2+3+\cdots+2018)-(1+2+3+\cdots+64)$ $=(1+2+3+\cdots+2018)-2080$ $<1+2+3+\cdots+2017$ so the $n$ th row cannot contain any large numbers.

If $1955\leq n\leq 2017$ , let $l$ be a large number in the $n$ th row. Let the numbers directly below $l$ be $a$ and $b$ where w.l.o.g. $a>b$ . We have $b=a-l$ and $a\leq 1+2+3+\cdots+2018$ so, because $l$ is large, $b\leq 2018$ so $b$ is small. Thus $b=m_{n+1}$ so $l$ is directly above $m_{n+1}$ . Thus there are at most 2 large numbers in the $n$ th row.

Thus there are at most 126 large numbers outside the bottom row. Since there are 2019 large numbers, there are at least 1893 large numbers in the bottom row so at most 125 non-large numbers in the bottom row. Now there are 2017 pairs of adjacent large numbers in the bottom row. We remove the pair directly beneath $m_{2017}$ and at most 250 other pairs containing a non-large number. Thus we can find a pair of adjacent large numbers in the bottom row, not directly beneath $m_{2017}$ . However, their difference is small and in the 2017th row but not $m_{2017}$ , which is a contradiction. Thus there is no such anti-Pascal triangle.

@@ Line 26: / Line 26: @@
 so the <math>n</math>th row cannot contain any large numbers.
-If <math>1955\leq n\leq 2017</math>, let <math>l</math> be a large number in the <math>n</math>th row. Let the numbers directly below <math>l</math> be <math>a</math> and <math>b</math> where w.l.o.g. <math>a>b</math>. We have <math>b=a-l</math> and <math>a\leq 1+2+3+\cdots+2018</math> so, because <math>l</math> is large, <math>b\leq 2018</math> so b is small. Thus <math>b=m_{n+1}</math> so <math>l</math> is directly above <math>m_{n+1}</math>. Thus there are at most 2 large numbers in the <math>n</math>th row.
+If <math>1955\leq n\leq 2017</math>, let <math>l</math> be a large number in the <math>n</math>th row. Let the numbers directly below <math>l</math> be <math>a</math> and <math>b</math> where w.l.o.g. <math>a>b</math>. We have <math>b=a-l</math> and <math>a\leq 1+2+3+\cdots+2018</math> so, because <math>l</math> is large, <math>b\leq 2018</math> so <math>b</math> is small. Thus <math>b=m_{n+1}</math> so <math>l</math> is directly above <math>m_{n+1}</math>. Thus there are at most 2 large numbers in the <math>n</math>th row.
 Thus there are at most 126 large numbers outside the bottom row. Since there are 2019 large numbers, there are at least 1893 large numbers in the bottom row so at most 125 non-large numbers in the bottom row. Now there are 2017 pairs of adjacent large numbers in the bottom row. We remove the pair directly beneath <math>m_{2017}</math> and at most 250 other pairs containing a non-large number. Thus we can find a pair of adjacent large numbers in the bottom row, not directly beneath <math>m_{2017}</math>. However, their difference is small and in the 2017th row but not <math>m_{2017}</math>, which is a contradiction. Thus there is no such anti-Pascal triangle.

Page

Toolbox

Search

Difference between revisions of "2018 IMO Problems/Problem 3"

Revision as of 08:00, 8 September 2018

Solution