Maths Olympiad Prep

Library / /1 of 4

Combinatorics Difficulty 4.8 AIME Prove it Brazil

Let SS be a set of 6n6n points in a line. Choose arbitrarily 4n4n of these points and paint them blue; the other 2n2n points are painted green. Prove that there exists a line segment that contains exactly 3n3n points from SS, 2n2n of them blue and nn of them green.

Solution

Let AiA_i be the segment with exactly 3n3n points from SS, the leftmost being the ii-th point from left to right of SS, i=1,2,,3n+1i = 1, 2, \dots, 3n + 1. Define f(i)f(i) as the number of blue points in AiA_i. We have to prove that f(i)=2nf(i) = 2n for some ii.

Notice that f(i+1)f(i)1|f(i + 1) - f(i)| \le 1 since AiA_i and Ai+1A_{i+1} have 3n13n - 1 common points and f(1)+f(3n+1)=4nf(1) + f(3n+1) = 4n because the disjoint segments A1A_1 and A3n+1A_{3n+1} cover SS.

If f(1)=2nf(1) = 2n we are done. So suppose without loss of generality that f(1)<2nf(1) < 2n. So f(3n+1)>2nf(3n + 1) > 2n and, since f(i)f(i) increases or decreases at most 1, there must exist a number kk such that f(k)=2nf(k) = 2n.

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.