Maths Olympiad Prep

Library / /190 of 220

Combinatorics Difficulty 6.8 National Olympiad Prove it Ukraine

The chessboard was split into domino tiles, meaning it was split into 1×21 \times 2 and 2×12 \times 1 rectangles. Each tile has a number written on it equal to the number of tiles that it has a common line segment with, without taking into account the tile itself. What is a least possible sum of all numbers that are written on the chessboard?
(Arsenii Nikolaiev)

Solution

It is clear that there are 3232 domino tiles, hence there are exactly 3232 unit intervals that are covered by domino tiles thus they are internal for tiles and therefore they cannot be common for two tiles. The rest of unit intervals that are not at the edge of the chessboard are common for two tiles. Let their number be equal to 78232=807 \cdot 8 \cdot 2 - 32 = 80.
It is obvious that 2F+N=802F + N = 80, since the common segment for them has a length of 22. Hence,
S=2F+2N=(2F+N)+N=80+N=1602F. S = 2F + 2N = (2F + N) + N = 80 + N = 160 - 2F.

A set of tiles D1,,DkD_1, \dots, D_k, where DiD_i has a tile Di+1D_{i+1} are friendly for i=1,ki=1, k, or a separate tile that has no friendly tiles, we call a chain. Each tile belongs to exactly one chain. Thus we have CC chains. Let it be k1k_1 tiles in the ll-th chain. Then it has (kl1)(k_l-1) friendly pairs in total. Then there are (k11)++(kC1)=32C=F(k_1-1)+\dots+(k_C-1)=32-C=F friendly pairs in total. Therefore S=1602F=96+2CS=160-2F=96+2C. Thus in order to minimize SS we have to minimize the number of chains CC. It is clear that there are no more than 88 tiles in the chain, hence C4C \ge 4. Hence we have that the least possible sum is S=96+2C=104S=96+2C=104.
It remains to give an example when C=4C=4. It is enough to place all the tiles in the same manner, for instance, the bigger side in all to be vertical.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.