Introduction to Mathematical Thinking 2003

Introduction to Mathematical Thinking Fall 2003 Assignment 2 Due Thursday, September 25 1. 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 1 . ........... .......... .. ............. .... . . . . . .. . . ...... .... .... ...... ........ .... ...... . ...... . ... .... . . . . . . .. ..... ... ...... ..... . . . ... . . . . . . .. . . . . . . ... . . . ... .... ... ... ... ... ... ... ... ... ... ... ....... ... ..... ... ..... ........ ..... .... ..... ... ..... ..... ... ..... ... ..... ... ..... .. . n ... ...... ... ..... . . . ... ... ... ... ... ... ... . . ... . . . ... . . . ... .. . . . 1 ... ...... ... ..... . . . ... ... ... ... ... ... ... . . ... . . . . ... . . ... .. . . . n 0n−1n 1n 0n 1n −1 n 0n −1 2. 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 1n 0n−1n 1n 0n −1 n ..... ... ... ... ..... . . . ... ... ... ... ... ... ... . . . ... . . . ... . . ... ... 1 ..... ... ... ... .... . . ... . ... ... ... ... ... ... . . ... . . . ... . . . ... ... . n−1n −1 −1 Assignment 2 2 3. Draw the complete tree below the node corresponding to the tic-tac-toe position shown (a total of 16 nodes); it is X’s turn to move. Then determine the natural outcome of this “subgame”. Label each node with a picture of the game position, that is, start by filling in the next row down, then continue from there. O X X X O O ..................... ............... .... .............................. ................ ............... ... ................ ................ . . . . . . . . . ... . . . . . ................ .......... ... ................ ............... . . . . . . . ................ . . . . . . . . . ...... ... . . ................ . . . . . . . . . . . . ................ ...... . . . . . . . . . . . . . . . . ................ . ..... . . . . . . . . . . . .............. . . . . . . . ......... O X O X X O O X X X O O X O X X O O 4. In some tic-tac-toe positions it is not necessary to analyze all possible moves to determine the outcome. Explain why the position below (O to move) is a natural draw, without considering the tree structure (that is, without considering multiple move possibilities). O X X