Maths Olympiad Prep

Track / Stage 6 / 224 of 400 #1704 of 2444

Problem 1704

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

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

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(1⋅212+2⋅22+2⋅24+7⋅26)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<382⋅62009 < 382 \cdot 6, it is not possible to select the required 7 pavements with the same damage out of 2009 pavements.

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