Maths Olympiad Prep

Library / /24 of 24

Combinatorics Difficulty 8.1 Shortlist Prove it Netherlands

Sabine has a very large collection of shells. She decides to give part of her collection to her sister.

On the first day, she lines up all her shells. She takes the shells that are in a position that is a perfect square (the first, fourth, ninth, sixteenth, etc. shell), and gives them to her sister. On the second day, she lines up her remaining shells. Again, she takes the shells that are in a position that is a perfect square, and gives them to her sister. She repeats this process every day.

The 27th day is the first day that she ends up with fewer than 1000 shells. The 28th day she ends up with a number of shells that is a perfect square for the tenth time.

What are the possible numbers of shells that Sabine could have had in the very beginning?

Solution

As n>1n > 1. The next day, she therefore gives n1n - 1 shells to her sister and is left with n2n(n1)=(n1)2n^2 - n - (n - 1) = (n - 1)^2 shells, again a perfect square. We see that the numbers of shells that Sabine is left with are alternately a perfect square and a number that is not a perfect square.

Let dd be the first day that Sabine is left with a number of shells that is a perfect square, say n2n^2 shells. Then days d+2,d+4,,d+18d+2, d+4, \dots, d+18 are the second to tenth day that the remaining number of shells is a perfect square (namely (n1)2,(n2)2,,(n9)2(n-1)^2, (n-2)^2, \dots, (n-9)^2 shells). We conclude that d+18=28d+18 = 28, and hence d=10d = 10.

On day 26 the number of remaining shells is at least 1000, but on days 27 and 28 this number is less than 1000. We see that (n9)2<1000(n8)2(n-9)^2 < 1000 \le (n-8)^2. As 312<100032231^2 < 1000 \le 32^2, we see that n8=32n-8 = 32, and hence n=40n = 40. We find that day 10 is the first day that the number of remaining shells is a perfect square, and that this number is 40240^2.

In the remainder of the proof, we will use the following observation.

Observation. On any day, starting with more shells, means that Sabine will have more (or just as many) shells left after giving shells to her sister.

Indeed, suppose that Sabine starts the day with xx shells, say n2x<(n+1)2n^2 \le x < (n+1)^2. After giving away shells, she will be left with xnx - n shells. If she had started with x+1x+1 shells instead of xx, she would have been left with x+1n>xnx+1-n > x-n or x+1(n+1)=xnx+1 - (n+1) = x-n shells.

Let xx be the number of shells remaining on day 8. The obvious guess x=412=1681x = 41^2 = 1681 is incorrect as xx cannot be a perfect square. We therefore try x=4122=4121x = 41^2 - 2 = 41^2 - 1, and x=412+1x = 41^2 + 1. The table shows the number of shells remaining on day 8, 9, and 10.

day 8day 9day 10
4122=167941^2 - 2 = 1679167940=16391679 - 40 = 1639163940=15991639 - 40 = 1599
4121=168041^2 - 1 = 1680168040=16401680 - 40 = 1640164040=16001640 - 40 = 1600
412+1=168241^2 + 1 = 1682168241=16411682 - 41 = 1641164140=16011641 - 40 = 1601

We see that the case x=1679x = 1679 is ruled out because it would imply that fewer than 402=160040^2 = 1600 shells are left on day 10. By the above observation, this also rules out the case x<1679x < 1679. The case x=1682x = 1682 is ruled out because it would imply that more than 40240^2 shells will be left on day 10. Hence, also x>1682x > 1682 is ruled out. The number of shells left on day 8 must therefore be 412141^2 - 1.

To follow the pattern back in time, we consider the case that the number of remaining shells is just shy of a perfect square. Suppose that on a given day the number of remaining shells is n2an^2 - a, where 1a<n1 \le a < n. Then the following day, the number of remaining shells is n2a(n1)n^2 - a - (n-1). Since a<na < n, we have n2a(n1)>n2n(n1)=(n1)2n^2 - a - (n-1) > n^2 - n - (n-1) = (n-1)^2. The day after that, the number of remaining shells must therefore be n2a(n1)(n1)=(n1)2(a1)n^2 - a - (n-1) - (n-1) = (n-1)^2 - (a-1).

So if Sabine originally had 452545^2 - 5 shells, then the number of remaining shells on days 2, 4, 6, and 8 are 4424,4323,422244^2 - 4, 43^2 - 3, 42^2 - 2, and 412141^2 - 1, respectively. This gives us a solution.

If Sabine originally had 452445^2 - 4 shells, then she would be left with too many shells on day 8, namely 412041^2 - 0. The original number of shells could therefore not have been 452445^2 - 4 or more.

If Sabine originally had 452645^2 - 6 shells, then she would be left with too few shells on day 8, namely 412241^2 - 2. The original number of shells could therefore not have been 452645^2 - 6 or fewer.

We conclude that the only possibility is that Sabine started with a collection of 4525=202045^2 - 5 = 2020 shells.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.