A finite grid is covered with cards in such a way that the edges of the cards match with the lines of the grid, no card lies over the edge of the grid, and every square is covered by exactly two cards. Prove that one can remove some of the cards in such a way that every square will be covered by exactly one card.
Solution
Choose any square covered by two cards, and choose one of these cards. Move that card to a neighbouring square, and choose the other card that is covering that square. From there we move to the next square, etc., until we return to the first square. We cannot return to any other square visited previously, since in all squares except the first one, both cards have been chosen already. If we color the rectangular grid like a chessboard, then after an odd number of moves, we reach a square with the opposite color, and after an even number of moves, we reach a square with the same color. Therefore, the number of chosen cards is even. So, we can remove every second chosen card. All of the remaining squares we passed through will be covered by exactly one card. If after this, there are still squares that are covered by two cards, we repeat the process with a new randomly chosen square which is covered by two cards. We can never move from a square covered by two cards to a square covered by exactly one card, since all the squares covered by exactly one card were previously connected to squares now covered by exactly one card. So, after a finite number of steps we can find a new cycle, from which we can remove every second card. We repeat, until all squares are covered by exactly one card.