Introduction to Mathematical Thinking 2010

Introduction to Mathematical Thinking Spring 2010 Assignment 2 Due Thursday, February 4 Answer questions 3 and 4 on this paper, and attach your answers to 1 and 2 on a separate sheet. 1. In most cases, the same player who can win Nim under last stone wins rules also wins under last stone loses, and using almost the same strategy. a. Suppose whichever player, say A, can win under last stone wins plays that strategy under last stone loses. At some point there will be exactly one pile left with more than 1 stone (assuming, of course, that the game started with at least one pile with more than 1 stone). At this point, it must be A’s turn. Explain why. b. Explain how A can win the game under last stone loses. 2. A Nim position is shown below. The player about to move can win, and has 3 winning moves. Find all three and explain your answer.                   3. Assume that White plays first at the top of the tree. Find the natural outcome by filling in the values for all the empty circles and squares. . ................... ...... .. ..... ......... ...... .... .......... ................... ...... ..... .......... . . ... . . . . ..... .......... . ... ..... .......... ...... ..... ...... .......... ... ..... ...... .......... . . . . . . ..... ... .......... ... . . . . . . . .......... ..... . ... . . . . .......... . . . . . ..... ... ... . .......... . . . . . .... . .... ..... n Ln ........ ............ ..... .. .... .... .... ........ . . . ..... ... .... ..... .... .... ..... ..... .. ..... .... . . . ..... . ... . . . . ..... . . .. . . . ..... . . .. . .... n .. ...... ... ... ... .... . . ... . ... ... ... ... ... ... . . ... . . . ... .. . .. .. W . ........... .......... .. ...... .... .. ...... ....... .... . . . . . . .. ... ...... ........ ... ...... ... ... ...... .... ...... . . . . ... . . . . . . ... . . . . ... . . . . . .. ... . . . . . ... . . . .... ...... ... ... ... ... ... ... ... ... ... ... ....... ... ..... ... ....... ... ..... ..... ... ..... ... ..... .. ..... ... ..... ... ..... ... ..... Ln Dn Ln Wn Dn Wn n .. ...... ... ... ... .... . . ... . ... ... ... ... ... ... . . ... . . . ... .. . .. .. L .. ...... ... ... ... .... . . ... . ... ... ... ... ... ... . . ... . . . ... .. . .. .. Ln Dn W 2 4. Assume that White plays first at the top of the tree. Find the natural outcome by filling in the values for all the empty circles and squares, using the “mini-max” procedure. ... .................... ...... .... ............................. ...... . ..... . ... . . . . ..... ................... ...... ... ..... .......... ...... ..... .......... ... ...... . . . .......... . . . ..... . . ... .......... ... . . . . . . . . . ..... .......... . ... . . . . . . .......... . . ..... ... ... . . .......... . . . . . ..... ... . . .......... . . . . . . . . .. .. ... n n 1 ........ ........... .... ... ........ . . . . .... .... ........ ..... ... .... .... ..... . ... . . ..... ... ... ..... .... . . . . .. ..... .. . . . . ..... .. .. . . . . ... . ... n ... ...... ... ..... . . . ... ... ... ... ... ... ... . . . ... . . . ... . . ... .. . . . 1 . ......... .......... .. ............. .... . . . . . .. . ...... .... ..... ...... ....... .... ...... .... ...... . . ... . . . . . . . .. ... ..... .... ...... . . . . ... . . . . . . ... . . . . ... . . . . . .... ... ... ... ... ... ... ... ... ... ... ... ....... ... ..... ... ..... ........ ..... .... ..... ... ..... ..... .. ..... ... ..... ... ..... .. . n 1 1 1n 0n n 1n 0n n ... ...... ... ..... . . . ... ... ... ... ... ... ... . . . ... . . . ... . . ... .. . . . 1 ... ...... ... ..... . . . ... ... ... ... ... ... ... . . . ... . . . ... . . ... .. . . . n n 1 1 1