Domino tilings- 40 points total 1. (10 pts) Consider putting down 2 x 1 dominos on...

Transcribed Image Text:

Domino tilings- 40 points total 1. (10 pts) Consider putting down 2 x 1 dominos on an 19 x 19 chess board where each domino exactly fills up two adjacent squares of the chess board. You want to have no dominos overlap and have them fill up the entire board. Is it possible to do so? Explain your answer. 2. Say you want to do the same, except you don't need to cover one corner. Can you do it? Again, explain your answer. If it is possible, say how. If it is impossible, say why in a clear and convincing way. (10 points) 3. Say you want to do the same, except you don't need to cover the second square in the first row? Can you do it? Again, explain your answer. If it is possible, say how. If it is impossible, say why in a clear and convincing way. (10 points) 4. (10 pts) When can we cover an n x m board? Give a logical expression in terms of n and m and Explain your answer carefully. (Hint: think about both the number of squares and colors of squares.) Domino tilings- 40 points total 1. (10 pts) Consider putting down 2 x 1 dominos on an 19 x 19 chess board where each domino exactly fills up two adjacent squares of the chess board. You want to have no dominos overlap and have them fill up the entire board. Is it possible to do so? Explain your answer. 2. Say you want to do the same, except you don't need to cover one corner. Can you do it? Again, explain your answer. If it is possible, say how. If it is impossible, say why in a clear and convincing way. (10 points) 3. Say you want to do the same, except you don't need to cover the second square in the first row? Can you do it? Again, explain your answer. If it is possible, say how. If it is impossible, say why in a clear and convincing way. (10 points) 4. (10 pts) When can we cover an n x m board? Give a logical expression in terms of n and m and Explain your answer carefully. (Hint: think about both the number of squares and colors of squares.)