Homework III

Due Oct. 7th


As usual, think about all problems, and come up with some ideas about how to solve them. If you want you can write them. Then choose two of the problems and write up a careful solution. Your solution should be convincing for a skeptical classmate.

 

  1. Numbers, one through twenty, are written in a row. Two players take turns putting plus and minus signs between the numbers. When all such signs have been placed, the resulting number is evaluated. The first player wins if the resulting number is odd and the second player wins otherwise. Who will win and why?
  2. The product of 22 integers is equal to 1. Can their sum be zero?
  3. Can a knight start at one corner of a standard 8x8 chessboard and end up at the opposite corner, visiting each of the remaining squares exactly once on its way? (Hint: Again think of usual coloring of the chessboard!)
  4. In how many ways we can cover a 2 by n table with dominos? (Hint: Try to describe it recursively and then see if you know the pattern. It is clear that for n=1 there is only one way and for n=2 there are two ways to do that.)
  5. A space ship is to travel between four planets A, B, C and D along the edges of the tetrahedron shown by dotted lines. Is it possible to plan the trip so as to traverse every edge exactly once?                       

                                                                                                                

  1. Is it possible to trace a path along the lines in the figure which passes through each juncture point once and only once? (Hint:  One can see that we can divide the junctures into to sets A and B such that there is no edge between two juncture in the same set. See if you can use this fact.)                                                                       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Like the problem in class, again consider the regular 8x8 chess-board. We saw that we cannot tile the board with dominos when two opposite corners of it are removed. But it is not hard to see that if we remove all the corners we can tile it with dominos. What about T-shapes? Is it possible this time to tile the board, when all its corners are removed as you see in the figure, with non overlapping T-shapes? (Hint: Again color the board in usual way, consider different colorings for a T-shape and count the number of them.)

                                    T-shape

 

                                                                         

                                                                                                                                                       The board