Competition problem — Combinatorics

Library / /41 of 86

Combinatorics Difficulty 6.5 National Olympiad Prove it United States

Problem:

Two infinite rows of evenly-spaced dots are aligned as in the figure below. Arrows point from every dot in the top row to some dot in the lower row in such a way that:
- No two arrows point at the same dot.
- No arrow can extend right or left by more than $1006$ positions.
Show that at most $2012$ dots in the lower row could have no arrow pointing to them.

Solution

Solution:

Call dots in the lower line that lie at the endpoints of arrows "target dots" and those that are not, "missed dots". If an arrangement has $2013$ or more missed dots, pick a contiguous set $S$ of dots in the lower line that includes exactly $2013$ missed dots and $t$ target dots.

Consider the set of $t+2013$ dots directly above the dots in $S$ from which $t+2013$ arrows must initiate. At most $t$ of them can terminate in $S$ , so at least $2013$ of them terminate outside $S$ . But since arrows can only extend to dots $1006$ outside of $S$ on either side, there are only $1006+1006=2012$ possible targets for those $2013$ or more arrows, which is impossible.

Therefore it is impossible to have $2013$ or more missed dots in a valid configuration.

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.