The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details. A final piece of advice: Start working on the problem sets early! Don't wait until the day (or few days) before they're due.
Consider a game with k piles of coins. Two players alternate turns. In each turn, they must remove some non-zero number of coins from one of the piles. The player who takes the last coin loses.An initial configuration is a sequence of values (P_1, P_2, ..., P_k) which represents that pile i has P_i coins in it. We call such a configuration winning if the first player to act can force a win (i.e., force the other player to eventually take the last coin).
Write a polynomial-time algorithm that, given an initial configuration (P_1, P_2, ..., P_k), decides if it is a winning configuration.