IMO 2015 Problem 6 Solution

I have been thinking of starting a blog for quite a while. Since it’s so exciting to finally make the first move, I decide to post something as exhilarating in my first post!! BOOM!! My take on 2015 IMO P6 Here is the question:

Let’s begin with the conditions

(i) Any number in series A is picked from a set S, containing 1 to 2015.

(ii) Let a[1] = n, then a[2] != n-1 and a[3] != n-2 ……. etc. Hence, the number of integers available in S reduce by 1 for a[2]…a[n+1]. The number that is available to pick can continue to shrink. Let a[1], a[2] = n, then a[3] != n-1 or n-2. The number of integers available in S become 2013 now. The number of banned integers become 2.

Let’s start with our first lemma.

Lemma 1: as j increase, the number of integers available in S for a[j] can only shrink or remain unchanged but never grow.

As we pick a number for a[j], a new integer will be banned for a[j+1] unless the number we pick is 1. We also know that as we move from a[j] to a[j+1], each of the banned integer decrease value by one. Say 3, 6, 8 are banned at a[j], then 2, 5, 7 will be banned at a[j+1]. In order for the number of banned integers at a[j+1] to be less than that at a[j], one of the banned integer at a[j] must be 1. Say 1, 3, 5 are banned at a[j], then 2, 4 will be banned at a[j+1]. Number of banned integers decrease by 1. However, we can not pick 1 for a[j], while 1 is banned at a[j], therefore whatever number we pick for a[j] will introduce new banned integer for a[j+1], hence compensate the decrease in number of banned integers. Thus, Lemma 1 is proved.

Lemma 2: There exist a number N that for all i > j >= N, the number of banned integers at a[i] = the number of banned integer at a[j]

From lemma 1, we know that the number of banned integers can only increase or stay unchanged. We also know the max for the number of banned integers is 2014, as there is no way to ban the integer 2015. It means the number of banned integers can only change 2014 times at most. So, the number of banned integers must stabilize at some point. Thus, Lemma 2 is proved.

Lemma 3: let the number of banned integers be k and remain unchanged for all j, Then

Since we restrict our number of banned integers to k, the banned integers for a[j] are always k integers picked from set S. Let s[j] be the sum of banned k integers at a[j], then s[j+1] — s[j] = a[j] — (k+1). Then

The smallest value of s[j] happens when the k integers are 1, 2, 3 … k and the largest value of s[j] happens when the k integers are 2014, 2013, 2012 … 2014 — (k-1). Therefore, the largest value of s[m] — s[n] is k(2014 — k) and the smallest value is -k(2014-k). Thus Lemma 3 is proved.

We also know from secondary school math class that k(2014 — k) <= 1007² for all k. So we get

Combining with Lemma 2 and we pick b = (k+1) . Then IMO P6 is proved!!!

Originally published at undelusionality.blogspot.com on December 6, 2017.