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.

1 Like

Ohhhh. Everything makes sense now.

Thanks

1 Like