CSC236 Tutorial #1
1. Aaron and Bianca play the following game: they place on a table two piles containing an equal number
of matches. They take turns removing some (non-zero) number of matches from one of the piles; the
player whose turn it is can choose which pile. The player removing the last match from the table wins.
Use induction to show that if Aaron goes first, Bianca has a winning strategy. That is, she can win no
matter how Aaron plays.
Solution: As the first step, we define the predicate which we want to prove:
P(n) : starting from two piles of nmatches each, and given the rules of the game, if Aaron moves first,
Bianca can win.
The goal is to prove for all n∈N, n ≥1, P(n).
Base Case: Let k= 1.
Then P(k) is true since the only move possible for Aaron is to take the only match from one of the
two piles. Bianca removes the 1 match in the other pile and wins.
Induction Step: Let k∈N. Suppose for all j∈N, 1 ≤j < k,P(j) is true. [IH]
WTP: P(k) holds.
Starting from two piles of kmatches, Aaron will have to choose a pile and remove imatches from it
where 1 ≤i≤k. There are two possibilities:
