Browse · MathNet
PrintXVI Silk Road Math Competition
counting and probability
Problem
Let be a square of size given on an infinite cell grid. Student wants to paint some (not necessary all!) cells with seven colors (each cell with one color), such that no two three-cell rectangles (out of 288) with centers in are colored identically. Is this possible? (Two three-cell rectangles are colored identically, if it is possible to shift and/or rotate so that each cell of a rectangle matches the same color cell of the other rectangle.)
Solution
Answer: impossible. Suppose, that there is a coloring, that satisfy above conditions. Let's count the number of different colorings of rectangle using 8 colors. Let's fix the center cell of rectangle, it can be colored in 8 ways. Other 2 cells can be colored in 8 ways, if they have the same color. If not, then its . So the number of ways to color edge cells is . Therefore, total number of different colorings of rectangle is . It means that every coloring appears exactly once. Suppose that there are white cells in . Then number of different rectangles with white center cell equals , hence or . On the one hand, let's count the number of rectangles with at least one non-center cell. If both of them are white, then the number of such rectangles equal to 8, if exactly one - number is (7 ways to color other non-center cell, 8 ways to color center). Means that there are such rectangles in total. On the other hand, we have 48 rectangles with white non-center cell, that lie outside . Also, for every white cell inside of , at least one among two vertical and at least one among two horizontal rectangles with white non-center cell is fully lie in , moreover every such rectangle can be counted no more than twice. Hence, there are at least 18 rectangles in with white non-center cell. Then total number of such rectangles at least - contradiction.
---
Alternative solution.
As in first solution, let's notice that there are 288 colorings of 3-cell rectangle with 8 colors. Therefore, every coloring appears exactly once (if it is possible). In particular, each of 7 colorings of type «red - red - not red» should appear exactly once. On the other hand, notice that each row and each column contain even number of such rectangles (every continuous block of exactly two red cells gives exactly two rectangles). Therefore, total number of such rectangles should be even, and cannot be equal to 7.
---
Alternative solution.
As in first solution, let's notice that there are 288 colorings of 3-cell rectangle with 8 colors. Therefore, every coloring appears exactly once (if it is possible). In particular, each of 7 colorings of type «red - red - not red» should appear exactly once. On the other hand, notice that each row and each column contain even number of such rectangles (every continuous block of exactly two red cells gives exactly two rectangles). Therefore, total number of such rectangles should be even, and cannot be equal to 7.
Final answer
impossible
Techniques
Counting two waysColoring schemes, extremal argumentsInvariants / monovariants