Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 6.6 National olympiad Prove it Silk Road Mathematics Competition

Let QQ be a square of size 12×1212 \times 12 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 QQ 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.)

Solutions — 2

Solution 1

Answer: impossible.
Suppose, that there is a coloring, that satisfy above conditions. Let's count the number of different colorings of 1×31 \times 3 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 C82=782=28C_8^2 = \frac{7 \cdot 8}{2} = 28. So the number of ways to color edge cells is 8+28=368 + 28 = 36. Therefore, total number of different colorings of 1×31 \times 3 rectangle is 836=2888 \cdot 36 = 288. It means that every coloring appears exactly once.
Suppose that there are kk white cells in QQ. Then number of different rectangles with white center cell equals 2k2k, hence 2k=362k = 36 or k=18k = 18.
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 78=567 \cdot 8 = 56 (7 ways to color other non-center cell, 8 ways to color center). Means that there are 8+56=648 + 56 = 64 such rectangles in total. On the other hand, we have 48 rectangles with white non-center cell, that lie outside QQ. Also, for every white cell inside of QQ, at least one among two vertical and at least one among two horizontal rectangles with white non-center cell is fully lie in QQ, moreover every such rectangle can be counted no more than twice. Hence, there are at least 18 rectangles in QQ with white non-center cell. Then total number of such rectangles at least 48+18=66>6448 + 18 = 66 > 64 - contradiction.

Solution 2

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.