Square $600\times 600$ is divided into figures of four types, shown in figure. In the figures of the two types, shown on the left, in painted black, the cells recorded number $2^k$, where $k$ is the number of the column, where is this cell (columns numbered from left to right by numbers from $1$ to $600$). Prove that the sum of all recorded numbers are divisible by $9$. [asy][asy] // Set up the drawing area size(10cm,0); defaultpen(fontsize(10pt)); unitsize(0.8cm); // A helper function to draw a single unit square // c = coordinates of the lower-left corner // p = fill color (default is white) void drawsq(pair c, pen p=white) { fill(shift(c)*unitsquare, p); draw(shift(c)*unitsquare); } // --- Shape 1 (left) --- // 2 columns, 3 rows, black square in the middle-left drawsq((1,1), black); // middle-left black drawsq((2,0)); // bottom-right drawsq((2,1)); // middle-right drawsq((2,2)); // top-right // --- Shape 2 (next to the first) --- // 2 columns, 3 rows, black square in the middle-right drawsq((4,0)); drawsq((4,1)); drawsq((4,2)); drawsq((5,1), black); // middle-right black // --- Shape 3 (the "T" shape, 3 across the bottom + 1 in the middle top) --- drawsq((7,0)); drawsq((8,0)); drawsq((9,0)); drawsq((8,1)); // --- Shape 4 (the "T" shape, 3 across the top + 1 in the middle bottom) --- drawsq((11,1)); drawsq((12,1)); drawsq((13,1)); drawsq((12,0)); [/asy][/asy]
Problem
Source: 2020 Ukraine TST 1.1
Tags: combinatorics, Tiling
01.02.2021 20:38
From left to right call the tiles type A, B, C and D. In each cell of the table write the number 2^k where k is the column to which the cell belongs to. Observe that the sume of all the numbers on the table is divisble by 9. Also the sum of cells covered by tiles of type C and D is divisible by 9. Now denote by a the sum of all numbers in black cells and by b the sum of all numbers in white cells of type A tiles. Define c and d analogously for tiles of type B. Its easy to see that b \equiv -3a (mod 9) and d \equiv -3c (mod 9) Hence: 0 \equiv a+b+c+d \equiv -2a-2c (mod 9) so 9 \mid a+c as desired. (Note, aops thinks $ sign for latex is a picture and says "new users can not post pictures" that's why solution does not have latex, i will add latex code once i will be able to)