Problem

Source: 2020 Ukraine TST 1.1

Tags: combinatorics, Tiling



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]