45th Mongolian Mathematical Olympiad

Question

A certain factory produces asphalt pavements in the shape of right hexagons with unit edges and unit width. During transportation some corners of the pavement may incur some degree of damages. Then can 7 pavements with the same degree damage be found at all times from 2009 pavements? (proposed by B. Bayasgalan)

Accepted Answer

There are 12 permutations of this object that transform it onto itself that are unit and in the form of (1 2 3 4 5 6); (7 8 9 10 11 12); (1 3 5)(2 4 6)(7 9 11)(8 10 12); (1 4)(3 6)(2 5)(3 6)(7 10)(8 10)(9 12); (1 5 3)(2 6 4)(7 11 9)(8 12 10); (1 6 5 4 3 2)(7 12 11 10 9 8); and (1 8)(2 7)(3 12)(4 11)(5 10)(6 9) etc. Exactly one of them has 12, 2 of them have 2, 2 of them have 4 disjoint cycles, and lastly 7 of them are a product of 6 disjoint cycles. Therefore, according to the orbit counting lemma, t = 112(1 2^12 + 2 2^2 + 2 2^4 + 7 2^6) where t is the number of orbits. In other words, the total number of pavements that are damaged in a different manner equals 4584/12 = 382. Thus, since 2009 < 382 6, it is not possible to select the required 7 pavements with the same damage out of 2009 pa…