Olympiad Maths Prep

Library / /12 of 19

Combinatorics Difficulty 6.5 National olympiad Prove it Mongolia

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)

Solution

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)(1\ 2\ 3\ 4\ 5\ 6); (7 8 9 10 11 12)(7\ 8\ 9\ 10\ 11\ 12); (1 3 5)(2 4 6)(7 9 11)(8 10 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\ 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\ 5\ 3)(2\ 6\ 4)(7\ 11\ 9)(8\ 12\ 10); (1 6 5 4 3 2)(7 12 11 10 9 8)(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)(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(1212+222+224+726)t = \frac{1}{12}(1 \cdot 2^{12} + 2 \cdot 2^2 + 2 \cdot 2^4 + 7 \cdot 2^6) where tt is the number of orbits. In other words, the total number of pavements that are damaged in a different manner equals 4584/12=3824584/12 = 382. Thus, since 2009<38262009 < 382 \cdot 6, it is not possible to select the required 7 pavements with the same damage out of 2009 pavements.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.