Maths Olympiad Prep

Library / /30 of 42

Combinatorics Difficulty 6.3 National olympiad Prove it Ireland

The commuter village of Abelia has a population of 20222022 individuals. Households vary but the average household size is 33 people. Houses are numbered consecutively.
Every inhabitant of Abelia takes a return train trip to a nearby city. There are four trains from Abelia to the city in the morning and four trains from the city to Abelia in the evening.
Show that there are two individuals who were on the same train both in the morning and in the evening, and whose house numbers differ by at most 55.

Solutions — 2

Solution 1

There are 4×4=164 \times 4 = 16 possible combinations of morning and evening trains. As 2022>2016=16×1262022 > 2016 = 16 \times 126 there must be one combination of morning and evening trains with at least 127127 Abelians on both trains. Identify these Abelians, for example by painting them purple.

Suppose for a contradiction that no two purple Abelians live in houses whose numbers differ by 55 or less. Then ordering the Abelians by their house numbers, the first purple Abelian is in house number at least 11. There can be no purple Abelians in houses 2,3,4,52, 3, 4, 5 or 66. The second purple Abelian must then be in house number at least 77, until the 127127th purple Abelian must be in house number at least 757=1+6×126757 = 1 + 6 \times 126.

As the average household size is 33, there are only 674=2022/3674 = 2022/3 houses in the village, which is a contradiction.

Solution 2

Because the average household size is 33, there are 674=2022/3674 = 2022/3 houses in the village. These houses can be grouped into 113113 groups such that the house numbers differ by at most 55 in each group, for example, for k=1,2,,112k = 1, 2, \dots, 112 the six houses 6k5,,6k6k-5, \dots, 6k form one group, and the remaining two houses 673,674673, 674 form the last group.

Because 16113=1808<202216 \cdot 113 = 1808 < 2022, there must be at least one group of houses in which at least 1717 people live. There are 4×4=164 \times 4 = 16 possible combinations of morning and evening trains, hence there are two among these 1717 Abelians who were on the same train both in the morning and in the evening.

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 and solution reproduced as published; topic and difficulty added by this site.