Maths Olympiad Prep

Track / Stage 6 / 348 of 400 #1828 of 2444

Problem 1828

National Olympiad, first round
Combinatorics Difficulty 6.8 Prove it Ukrainian National Mathematical Olympiad · 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)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.