Gene has 2n pieces of paper numbered 1 through 2n. He removes n pieces of paper
that are numbered consecutively. The sum of the numbers on the remaining pieces of paper
is 1615. Find all possible values of n.
Here is the key observation:
Let be a consecutive block of intergers summing to . Then if we shift over by one, i.e. this block would sum to .
Okay let be some given number. If by removing first numbers then we have their sum is . Now this is the highest possible attainable sum. So if then it is impossible to pick such a consecutive block. The solution to this inequality in integers is , thus if is any in these numbers then it is impossible because the highest possible sum cannot reac 1615. Thus we must have that .
Similarly if we remove the last numbers then we have their sum is . Now this is the lowest possible attainable sum. So if thus if this is impossible. Hence we require that .
Thus, the only possible values are .
So this is what we do we choose the lowest possible sum involving the first integers. If this is 1615 we are done. If not we shift blocks by 1 by the key observation above this sum is one more. If it is 1615 we are done. We continue doing this. The important thing is that the highest possible attainable sum is more than 1615 thus there is some point when we have to get exactly 1615. (This is like the intermediate value theorem for integers).
Sorry for being a little late I did not see it before. I made a minor mistake in my first line. If we shift the sequence by 1 over it is not 1 more (like I mistakely said) but by k. Thus, we need to see if it is congruent by mod k. If you do that you should get that result.