申論題

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.

(b) [7 points] Show a tight upper bound on the worst -case number of moves in a Sprouts game that starts with n dots, and prove your answer.