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. |
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.