Maths Olympiad Prep

Library / /398 of 520

Combinatorics Difficulty 5.7 AIME, harder Prove it

Example 8. At the endpoints of line segment ABAB, one is marked red and the other is marked blue. Insert nn points in the middle of the line segment, and randomly mark them with red and blue. This divides the original line segment into n+1n+1 non-overlapping smaller segments, those whose endpoints have different colors are called standard segments. Prove: the number of standard segments is odd.

Solution

Proof: Let the nn points inserted in the middle of line segment ABAB be A1,A2,AnA_{1}, A_{2}, \cdots A_{n}. Suppose there are kk standard segments, and the points AiA_{i} are associated with numbers aia_{i} as follows:
ai={1, if point Ai is red 1, if point Ai is blue  \quad a_{i}=\left\{\begin{array}{l} 1, \text { if point } A_{i} \text { is red } \\ -1, \text { if point } A_{i} \text { is blue } \end{array}\right.

Then, by the problem statement, aAaB=1a_{A} \cdot a_{B}=\cdots-1, and
aAaB==aAaBa12a22an2=(aAa1)(a1a2)(a2a3)(anaB)=(1)k, \begin{array}{l} a_{A} \cdot a_{B}==a_{A} \cdot a_{B} \cdot a_{1}^{2} \cdot a_{2}^{2} \cdots a_{n}^{2} \\ =\left(a_{A} a_{1}\right)\left(a_{1} a_{2}\right)\left(a_{2} a_{3}\right) \cdots\left(a_{n} a_{B}\right) \\ =(-1)^{k}, \end{array}

Therefore, (1)A=1(-1)^{A}=-1, which means kk is odd.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.