The chessboard was split into domino tiles, meaning it was split into and 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 domino tiles, hence there are exactly 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 .
It is obvious that , since the common segment for them has a length of . Hence,
A set of tiles , where has a tile are friendly for , or a separate tile that has no friendly tiles, we call a chain. Each tile belongs to exactly one chain. Thus we have chains. Let it be tiles in the -th chain. Then it has friendly pairs in total. Then there are friendly pairs in total. Therefore . Thus in order to minimize we have to minimize the number of chains . It is clear that there are no more than tiles in the chain, hence . Hence we have that the least possible sum is .
It remains to give an example when . It is enough to place all the tiles in the same manner, for instance, the bigger side in all to be vertical.