USACO 2021 Gold Stone Game

How did the official solution for the Stone Game come to the conclusion that “If t>1, t−1 occurs an odd number of times in S”. Could anyone help explain? I don’t think I fully understand the explanation.

problem link:
solution link:

Thanks in advance

What the author means by this is that if t>1 (and we are talking about the floor-divved piles here), then t-1 must also occur an odd number of times. I know that’s just a repeat of the solution, so let’s have an example. Say these are the piles:
0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 3 4 4 4
If we were to remove 1 from 4, then the amount of 4’s would become even. However, that 4 doesn’t disappear into thin air- it simply becomes a 3, so we much also ensure that there’s an even amount of 3’s so that all positive piles occur an odd number of times.

1 Like

Ohhhh. Everything makes sense now.

Thanks :slight_smile:

1 Like