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

(→Solution) |
m (→Solution) |
||

Line 26: | Line 26: | ||

so the <math>n</math>th row cannot contain any large numbers. | 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. | 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. |

## Latest revision as of 09: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 to

Does there exist an anti-Pascal triangle with rows which contains every integer from to ?

## Solution

Trivially it is required that every positive integer from to appears exactly once.

Let denote the maximum number in the th row and let denote the minimum number in the th row.

Now assume and consider the numbers directly below . Call these and where w.l.o.g. . Then . Since and , we obtain that .

Thus, for ,

In particular, since ,

Thus is a sum of 2018 distinct positive integers. However, . Thus and is a permutation of . Also, this implies that the other inequalities are also equalities and, for any ,

Now let any positive integer be "small" and let any positive integer be "large". Since is a permutation of , there is exactly one small number in each row.

If , we have so the th row cannot contain any large numbers.

If , let be a large number in the th row. Let the numbers directly below be and where w.l.o.g. . We have and so, because is large, so is small. Thus so is directly above . Thus there are at most 2 large numbers in the 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 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 . However, their difference is small and in the 2017th row but not , which is a contradiction. Thus there is no such anti-Pascal triangle.