Browse · MathNet
PrintFinal Round
Netherlands counting and probability
Problem
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?
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 . The next day, she therefore gives shells to her sister and is left with 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 be the first day that Sabine is left with a number of shells that is a perfect square, say shells. Then days are the second to tenth day that the remaining number of shells is a perfect square (namely shells). We conclude that , and hence .
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 . As , we see that , and hence . We find that day 10 is the first day that the number of remaining shells is a perfect square, and that this number is .
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 shells, say . After giving away shells, she will be left with shells. If she had started with shells instead of , she would have been left with or shells.
Let be the number of shells remaining on day 8. The obvious guess is incorrect as cannot be a perfect square. We therefore try , and . The table shows the number of shells remaining on day 8, 9, and 10.
We see that the case is ruled out because it would imply that fewer than shells are left on day 10. By the above observation, this also rules out the case . The case is ruled out because it would imply that more than shells will be left on day 10. Hence, also is ruled out. The number of shells left on day 8 must therefore be .
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 , where . Then the following day, the number of remaining shells is . Since , we have . The day after that, the number of remaining shells must therefore be .
So if Sabine originally had shells, then the number of remaining shells on days 2, 4, 6, and 8 are , and , respectively. This gives us a solution.
If Sabine originally had shells, then she would be left with too many shells on day 8, namely . The original number of shells could therefore not have been or more.
If Sabine originally had shells, then she would be left with too few shells on day 8, namely . The original number of shells could therefore not have been or fewer.
We conclude that the only possibility is that Sabine started with a collection of shells.
Let be the first day that Sabine is left with a number of shells that is a perfect square, say shells. Then days are the second to tenth day that the remaining number of shells is a perfect square (namely shells). We conclude that , and hence .
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 . As , we see that , and hence . We find that day 10 is the first day that the number of remaining shells is a perfect square, and that this number is .
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 shells, say . After giving away shells, she will be left with shells. If she had started with shells instead of , she would have been left with or shells.
Let be the number of shells remaining on day 8. The obvious guess is incorrect as cannot be a perfect square. We therefore try , and . The table shows the number of shells remaining on day 8, 9, and 10.
| day 8 | day 9 | day 10 |
|---|---|---|
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 , where . Then the following day, the number of remaining shells is . Since , we have . The day after that, the number of remaining shells must therefore be .
So if Sabine originally had shells, then the number of remaining shells on days 2, 4, 6, and 8 are , and , respectively. This gives us a solution.
If Sabine originally had shells, then she would be left with too many shells on day 8, namely . The original number of shells could therefore not have been or more.
If Sabine originally had shells, then she would be left with too few shells on day 8, namely . The original number of shells could therefore not have been or fewer.
We conclude that the only possibility is that Sabine started with a collection of shells.
Final answer
2020
Techniques
Invariants / monovariantsRecurrence relationsFloors and ceilings