It is not possible to cover a chessboard with dominoes that each cover exactly two squares if the squares in the two diagonally opposite corners have been removed. Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same. The reverse of our assumption must be true: This is clearly impossible, so we have our desired contradiction. By the pigeon-hole principle, two of the black squares must be covered by the same domino. These 31 dominoes will be our "pigeon-holes". With 62 places to be covered, 31 dominoes will be needed. We first show that if we have a collection of containers, cs, where every. Each domino, no matter how it is placed on the board to cover exactly two squares will always cover exactly one black square and exactly one white square. ( This module presents a proof of the pigeon hole principle, which states that if you place n things into m containers, and n > m, then one or more of the containers have more than one thing in it. These 32 black spaces will play the role of our "pigeons". Consequently, there are only 30 white squares left from the original 32 on a complete board, while the number of black squares remains unchanged at 32. Without loss of generality, let's suppose the two corners removed were both white. Note that the diagonally opposite corners of a complete chessboard are of the same color. We argue indirectly, using the pigeon-hole principle.Īssume it is possible. However, if the two diagonally opposite corners are removed, this changes.
It is certainly possible to cover a chessboard with dominoes that each cover exactly two squares.
0 kommentar(er)
