Math 310 Assignments

  1. Due Tuesday, 9 January. Meet with group members, and explore the following games: Daisy, Litton 3x3, Faux Nim, Crossed Dots. Write a 1 to 2 page report on your findings.
  2. Due Thursday, 11 January. Meet with group members, and explore the following games: Faux Nim 3xn, Litton 3x3, Adjacent Litton, variants of Dr. Nim:
    1. Misère;
    2. Replace 1, 2, 3 by 1, 2, 3, 4;
    3. Replace 1, 2, 3 by 3, 4, with the understanding that the first player who cannot make a legal move loses.
    The Three-Four Game defined on the first list of games. Come to class prepared to share your findings.
  3. Due Tuesday, 16 January.
    1. Submit by email a polished presentation of one of the first four games, with rules and some analysis. Single author.
    2. Meet with your group, choose a group name, play Bridgit, Hex, Wiggle, Faux Nim, and keep a record of which player wins. Try to construct a rigorous analysis of 3xn Faux Nim. Try to analyse 4xn Faux Nim, 5xn Faux Nim, ....
    3. Try to solve the Hex exercises that were distributed. If you don't have them, they can be downloaded here in PS or PDF. Also, here is a Bridgit position in PS and PDF. Find the winning move, and describe how play will continue.
    4. Choose a game such as Faux Nim, Litton 3x3, Adjacent Litton, variants of Dr. Nim, and compose an account of the game, including its rules and some analysis. Single author. Submit by 5pm Monday, 15 January, either by hard copy under the door at 4066 East Hall, or electronically by email. Must be word-processed.
  4. For Thursday, 18 January: Play Poison Cookie, and try to find a strategy stealing argument for one of the players. Play Nim, and record as many N and P positions as you can compute. Play Wiggle 2xn, 3x3, 3x4, 4x4, 3x5, ..., and try to determine who has the winning position. This game has a simple strategy, if you can find it! Play asymmetric Hex. Who seems to win more often? Be prepared to discuss the Bridgit and Hex exercises. What is the outcome of the Three-Four game, under optimal play?
  5. For Tuesday, 23 January: (1) Build on your understanding of Faux Nim to analyze misère Faux Nim. (2) Develop collections of N and P values for Nim and for misère Nim. (3) Play Dr. Nim when the number of stones that can be removed is a power of 2. (4) The same with powers of 3. (5) Download the three game boards with paired moves. Follow the moves. Does the strategy guarantee a win? (6) Write up something that you've figured out. Single author.
  6. For Thursday, 25 January: Homework exercises to be turned in. Groups should work together on these questions, but answes are to be written individually.
    1. Suppose you are playing generalized Dr. Nim with a finite set S. Show that the array of N and P values is eventually periodic.
    2. (a) State a relationship between the N and P values for generalized Dr. Nim and those for the misère variant. (b) Prove the relation stated in (a).
    3. (a) Describe the N and P values in Dr. Nim when S consists of all powers of 2. (b) Prove that your answer in (a) is true.
    4. (a) Describe the N and P values in Dr. Nim when S consists of all powers of 3. (b) Prove that your answer in (a) is true.

    Come to class prepared to discuss N and P values for misère Faux Nim, Nim, and misère Nim. Analyze the Three--Four game. Can Alice force a win? Can Bob force a win? Can both players force a draw?

  7. For 30 January: (1) Wiggle: Can the domino strategy be applied to an mxn rectangle when both m and n are odd? How? (2) Consider an incomplete game of Wiggle, with the curve poking into a connected region. If this region can be partitioned into n + 1/2 dominoes, with the 1/2 domino at the point of entry, then this is a safe (P) position. If no such tiling is possible, does it follow that the position is unsafe? (3) You have three boards marked with pairings. Which of these, if any, guarantees a win? (4) I need from each group a polished account of Nim, including a procedure for deciding whether an arbitrary position is N or P. (5) Work on Multinim and Nimble. The group member who writes the Nim account should be different from the group member responsible for writing up new results.
  8. For Thursday, 1 Feb. (1) Play the following games, with particular attention to who wins, and how long the games last. When possible, place an upper bound on the possible length of the game. a. Card Switching. b. Piles. c. Sprouts. d. Brussels Sprouts. (2) Using the ideas outlined in class, try to show that when a Hex board is full, someone must have won. Also, can you explain why it is impossible for both players to win? Concerning the 9x8 Hex board with paired moves, here is a hint: Suppose that Alice has made a chain of moves connecting the East and West sides of the board. Show that there must be a number k such that Alice has used both cells labeled k.
  9. For Tuesday, 6 Feb. (1) Continue with current games, such as: (a) Misère Nim; (b) Nimble; (c) Sprouts; (d) Brussels Sprouts; (e) Card Switching. (2) Work on theoretical issues, such as: (a) The proposed theory for Multi Nim---make it crystal-clear; (b) Explain why the move pairing in Hex, in which Alice starts by playing in position 0, allows Bob to win if he plays correctly; (c) Show that when a Hex board is filled with black and white pieces, then either there is a white path joining the east and west sides, or there is a black path joining the south and north sides (but not both); (d) Show that the move pairings indicated for Bridgit guarantee Alice a win. (3) Play some fun games, such as (a) Y; (b) Chameleon. (4) One member of each group should write a polished account of Piles. A different member of each group should write a polished account of asymmetric Hex.
  10. For Thursday, 8 Feb. (1) Try to use Euler's formula to show that a game of Brussels Sprouts that begins with n crosses must last exactly 5n - 2 moves. (2) Work out N and P values for Nimble with 4 stones. (3) Get to the bottom of misère nim.
  11. For Tuesday, 13 March. (1) Here's an EARLY EDITION of the QUIZ: You are playing Two Nim, there are n sticks, and you are allowed to remove up to b of them on your next turn. You compute the Zeckendorf expansion of n. How do you deduce whether the position is a P position or an N position? If it is an N position, what is your move to get to a P position? (2) Solve the Pirate riddle: DVI PS  PDF (3) Bring to class your solutions of one-peg reversal problems in Peg Solitaire. (These do not need to be word-processed. A hand-written diagram is fine.)
  12. For Thursday, 15 March: (1) Do as many one-peg reversal problems as possible. (2) Make a table of nim sums. Rows labeled 0 through 7, columns labeled 0 through 7. If you are feeling ambitious, you could make a larger table, but this should suffice. Note patterns. For example, are the nimbers in a given row a permutation of the labeling? If so, why, and compute the decomposition into disjoint cycles. The cycle decomposition has an interesting feature. Explain why. Why are the nimbers in the bottom right quarter of the board the same as in the upper left quarter? Why is there a diagonal full of 7's? Why are there two shorter diagonals of 4's?
  13. For Tuesday, 20 March. (1) Finish the remaining one-peg reversal problems in Peg Solitaire. (2) Let (a_1, ..., a_k) denote a position in Nim with k heaps whose sizes are a_1, ..., a_k. For impartial games we compute a g function for positions, by taking the mex of the g values that we can reach in a single move. Nim is an impartial game, so it has this kind of g function. I claim that the g function for Nim is nothing other than the Nim-sum of its heap sizes. When we played Nim before, we showed that if the Nim-sum of the heap sizes is non-zero, then there is a move that will make it zero. We now need to prove a slightly stronger result: If the Nim-sum of the heap sizes is s > 0, then not only is there a move that will create a nim-sum zero, but also a move that will give a nim-sum 1, 2, ..., s-1, but not s. Thus s is the mex of the nim-sums that we can reach in a single move. (3) In your list of games is a game called Grundy. Start playing it, and compute g values for positions in it. Written work should be submitted by 5pm on Monday.
  14. For Thursday, 22 March. Groups that failed to submit a report for Tuesday's class should bring (or send by email) a report of findings on some relevant topic. For the other groups, there is no writing assignment, but we have many topics to explore, so do some work and come prepared to explain what you've figured out. Topics before us:
    (1) Explain the magic trick that involves 6 cards with 32 numbers on each card.
    (2) Put 14 stones on the triangular solitaire board, and try to make jumps to reduce to a single peg, possibly where the initial hole was.
    (3) Finish the remaining one-peg reversal problems on the standard solitaire board, and try the harder reversal problem with the distinguished peg that was mentioned in class.
    (4) Compute g values for New Crossed Dots, which is defined as follows: We have several piles of cookies. A move is made as follows: Select one pile, let n denote the number of cookies in it, eat a cookie, and separate the remaining cookies into two piles whose sizes are a and b with a >= 2 and b >= 2. (a+b = n-1). If the entries become periodic, for how long must they continue to be periodic before you can be sure that they will be periodic forever?
  15. Due Monday, 26 March, at 5pm, for class on Tuesday, 27 March. (1) Analyze Poker Nim. (2) Analyze Northcott's Game. (3) Analyze Wythoff's Nim (= Queen Cornering). Start by computing N and P values. You could also compute g values. (4) We have seen that the game Piles is trivial. What are the g values for this game? (5) How many soldiers does it take to march k paces into the desert?
  16. Due Monday, 2 April, at 5pm, for class on Tuesday, 3 April. (1) Address the questions concerning Kayles on p. 9 of the document "Impartial Games". (2) Play Soft Rock, compute N/P values and Grundy values. (3) Play Rock in a Hard Place (Hard Rock), compute N/P values and Grundy values. (4) Continue playing Dots and Boxes. (5) Under the heading "Topics in Elementary Mathematics" are two new chapters. If you are not familiar with congruences, then read and digest Chapter 4. In any case, read chapter 5 (Permutations), and start addressing the questions raised. We should wrap up Permutations on Tuesday. (6) Some of you like chess. Here is a chess problem that only a mathematician would like: CHESS. Can you do it? Warning: It is sneaky.
  17. Due Monday, 9 April, at 5pm, for Tuesday, 10 April. (1) Work out problem #26 on the Permutations sheet. (2) Analyze Turning Turtles. As an impartial game, it is in some sense equivalent to Nim, but in the present case the disguise is especially thin. (3) Staircase Nim is also a disguised form of Nim, but in some ways is more reminiscent of the game we called Nimble. In Staircase Nim we start with counters on the steps of a staircase. A move consists of taking any number of counters on a particular step, and moving them to the next step down. The game ends when all counters are on the floor at the bottom of the stairs. If x_1 denotes the number of counters on the first step, and x_2 the number on the second, and so on, then a move has the effect of replacing x_j by x_j - c and x_{j-1} by x_{j-1}+c where 0 <= c <= x_j. Only steps j and j-1 are affected. (4) Figure out what you can about the SOS game.

HLM's Home