題組內容

6. I want to play a game! (13 points) Now we want to play a famous game called ""Sprouts", which is a two-player game and can be played with paper and pencil. First, several dots are drawn on the paper. Afterward, the players take turns, each doing the following process.
ㆍ Drawing a line that connects two dots or conn nnects a dot to itself but does not touch or cross any other line.
ㆍPutting a new dot on this new line, thus separating it into two lines.
 If no dot can have more than three lines attached to it, the last player that can make a legal move wins.

(a) [6 points] Prove that any Sprouts game consists of a finite number of moves before someone loses. In other words, the game will terminate eventually.