USA tops International Math Olympiad for first time in 21 years

Re:USA tops International Math Olympiad for first time in 21... by graycat on Saturday July 18, 2015 @10:42PM (#9909837)

For Problem 6 given in the OP, the claim is false:

Notation: We borrow subscript and superscript notation from D. Knuth's TeX. So, a with a subscript j is written a_j.

Consider the simple graph, based just on typing, below. The graph shows the first four values of a specific sequence a_j. This sequence is a contradiction to claim of Problem 6.

In this graph, the values of j = 1, 2, ... are plotted on the horizontal axis with 1, 2, ..., and the values of the a_j are plotted on the vertical axis from 1 to 2015. We plot a value of a_j as just 'a'. Due to constraint (ii), we indicate by 'x' points that, due to prior values of a_j, cannot have an 'a'. So, the graph is:

       2015
          .
          .
          .
     a_j  .
          5
          4
          3 a a
          2  x x    ...
          1  axax

            123456789
                j

Then the first two terms of the sequence a_j are:

     a_1 = 3

     a_2 = 1

and generally for j = 1, 2, ..., a_j is:

             /
             | 3 if j is odd
             |
     a_j =  <
             |
             | 1 if j is even
             \

Then for any positive integer b and j = 1, 2, ...

     (a_j - b) + (a_{j + 1} - b) >= 2

More generally for positive integers m and k,

     sum_{j = m + 1}^{m + 2k} (a_j - b) >= 2 k

Then for any positive integer N, we can set m = N and n = m + 2(1007^2) and get

     | sum_{j=m+1}^n (a_j - b) |

     = sum_{j=m+1}^n (a_j - b)

     = 2 (1007^2) > 1007^2

showing that the claim is false.

[ Parent | on HN ]

Re:USA tops International Math Olympiad for first time in 21... by paulfr on Sunday July 19, 2015 @01:08AM (#9910111)

There are no absolute values in the summands, so in your example pairs of consecutive terms sum to 0 when you choose b = 2.

The theorem seems entirely correct to me. You can prove it with these sub-steps:

(1) the set of all j + a_j is the set of nonnegative integers minus a finite number of gaps

(2) thus for large enough n you can express \sum_{j=1}^n (j + a_j) as a quadratic function of n, plus a residual term e(n) of magnitude at most 1007^2/2

(3) more precisely, \sum_{j=m+1}^n a_j = g (n-m) + e(n) - e(m) where g is the number of gaps in (1)

Then choosing b = g solves the problem.

Hope that helps.

[ Parent | on HN ]