Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 IMO Problems/Problem 3"
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
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 <math>1</math> to <math>10</math>
 
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 <math>1</math> to <math>10</math>
  
Line 7: Line 9:
  
 
Does there exist an anti-Pascal triangle with <math>2018</math> rows which contains every integer from <math>1</math> to <math>1 + 2 + 3 + \dots + 2018</math>?
 
Does there exist an anti-Pascal triangle with <math>2018</math> rows which contains every integer from <math>1</math> to <math>1 + 2 + 3 + \dots + 2018</math>?
 +
 
== Solution ==
 
== Solution ==
 +
 +
Trivially it is required that every positive integer from <math>1</math> to <math>1+2+3+\cdots+2018</math> appears exactly once.
 +
 +
Let <math>M_n</math> denote the maximum number in the <math>n</math>th row and let <math>m_n</math> denote the minimum number in the <math>n</math>th row.
 +
 +
Now assume <math>n\leq 2017</math> and consider the numbers directly below <math>M_n</math>. Call these <math>a</math> and <math>b</math> where w.l.o.g. <math>a>b</math>. Then <math>a-b=M_n</math>. Since <math>a\leq M_{n+1}</math> and <math>b\geq m_{n+1}</math>, we obtain that <math>M_{n+1}\geq M_n+m_{n+1}</math>.
 +
 +
Thus, for <math>1\leq i<j\leq 2018</math>, <cmath>M_j\geq M_i+\sum_{k=i+1}^j m_i</cmath>
 +
 +
In particular, since <math>M_1=m_1</math>, <cmath>M_{2018}\geq \sum_{k=1}^{2018} m_k</cmath>
 +
 +
Thus <math>M_{2018}</math> is a sum of 2018 distinct positive integers. However, <math>M_{2018}\leq 1+2+3+\cdots+2018</math>. Thus <math>M_{2018}=1+2+3+\cdots+2018</math> and <math>\{m_1,m_2,m_3,\dots,m_{2018}\}</math> is a permutation of <math>\{1,2,3,\dots,2018\}</math>. Also, this implies that the other inequalities are also equalities and, for any <math>1\leq j\leq 2018</math>, <cmath>M_j=\sum_{k=1}^j m_k</cmath>
 +
 +
Now let any positive integer <math>n\leq 2018</math> be "small" and let any positive integer <math>1+2+3+\cdots+2017\leq n\leq 1+2+3+\cdots+2018</math> be "large". Since <math>\{m_1,m_2,m_3,\dots,m_{2018}\}</math> is a permutation of <math>\{1,2,3,\dots,2018\}</math>, there is exactly one small number in each row.
 +
 +
If <math>n\leq 1954</math>, we have <cmath>M_n=\sum_{k=1}^n m_k \leq 2018+2017+2016+\cdots+65</cmath> <cmath>=(1+2+3+\cdots+2018)-(1+2+3+\cdots+64)</cmath> <cmath>=(1+2+3+\cdots+2018)-2080</cmath> <cmath><1+2+3+\cdots+2017</cmath>
 +
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 <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.
 +
 +
==See Also==
 +
 +
{{IMO box|year=2018|num-b=2|num-a=4}}

Latest revision as of 00:45, 19 November 2023

Problem

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.

See Also

2018 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_IMO_Problems/Problem_3&oldid=204584"