grid is tiled by mosaics and (horizontal and vertical). Prove that the number of ways to choose a rectangle (horizontal and vertical) such that one of its cells is tiled by mosaic and the other cell is tiled by mosaic [horizontal and vertical] is an even number.
Problem 1482
Official solution
1. Assign Values to Unit Squares:
- Write the number in each unit square tiled by tiles.
- Write the number in each unit square tiled by tiles (both horizontal and vertical).
2. **Define the Sum :**
- For any possible rectangle (domino), sum up all the numbers on the unit squares covered by that domino.
- Add all these sums together to get the total sum .
3. Double Counting and Modulo Operation:
- Let be the number of 's on the edges of the grid, excluding the corners.
- Notice that because each rectangle contributes to based on the number of 's it covers.
4. **Claim: is Even:**
- Investigate the cases when tiles are on the edge but do not contain any corners.
- Also, consider the case when a tile contains a corner unit square.
- In each case, each tile adds exactly 's to , making the total even.
5. Conclusion:
- Since is even, must also be even.
- The sum is equal to the number of neighboring edges between tiles and tiles.
- Therefore, the number of ways to choose a rectangle such that one of its cells is tiled by a mosaic and the other cell is tiled by a mosaic is even.