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: http://www.usaco.org/index.php?page=viewproblem2&cpid=1113
solution link:http://www.usaco.org/current/data/sol_prob1_gold_feb21.html
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.
Ohhhh. Everything makes sense now.
Thanks 