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 (123456); (789101112); (135)(246)(7911)(81012); (14)(36)(25)(36)(710)(810)(912); (153)(264)(7119)(81210); (165432)(712111098); and (18)(27)(312)(411)(510)(69) 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=121(1⋅212+2⋅22+2⋅24+7⋅26) 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 pavements.
Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.