Maths Olympiad Prep

Library / /358 of 426

Combinatorics Difficulty 6.7 National Olympiad Prove it Saudi Arabia

A set of nn points in space is given, no three of which are collinear and no four of which are co-planar (on a single plane), and each pair of points is connected by a line segment. Initially, all the line segments are colorless. A positive integer bb is given and Alice and Bob play the following game. In each turn Alice colors one segment red and then Bob colors up to bb segments blue. This is repeated until there are no more colorless segments left. If Alice colors a red triangle, Alice wins. If there are no more colorless segments and Alice hasn't succeeded in coloring a red triangle, Bob wins. Neither player is allowed to color over an already colored line segment.
1. Prove that if b<2n232b < \sqrt{2n-2} - \frac{3}{2}, then Alice has a winning strategy.
2. Prove that if b2nb \ge 2\sqrt{n}, then Bob has a winning strategy.

Solution

1. We will call a threat an uncolored segment whose coloring of red would produce a triangle. We will show that Alice can use the following strategy to win: Alice will keep coloring segments whose one end-point is AA unless she can complete a triangle. We will call the other endpoints opposite ends. Let us assume that Bob can stop this strategy. Bob's optimal strategy to counter Alice's is first eliminating all threats in his move and then using his remaining moves to color segments coming out of AA. Note that after the kk-th red line is drawn, Bob must color k1k - 1 threats blue, which are the lines connecting the new opposite end with all the previous opposite ends. Thus in the kk-th pair of moves of Alice and Bob, the number of colored edges coming out of AA has increased by b+1(k1)=bk+2b + 1 - (k - 1) = b - k + 2. Assume there exists a ll such that after ll moves all segments out of AA have been colored before Alice could draw a triangle. Then we have
(b+2)ll(l+1)2n1l2+2l(b+32)+2n20, (b + 2)l - \frac{l(l + 1)}{2} \geq n - 1 \Rightarrow l^2 + 2l\left(b + \frac{3}{2}\right) + 2n - 2 \leq 0,
therefore the discriminant of the quadratic equation is non-negative, i.e. 4(b+32)24(2n2)04\left(b + \frac{3}{2}\right)^2 - 4(2n - 2) \geq 0 and therefore b2n232b \geq \sqrt{2n - 2} - \frac{3}{2}. Since this inequality is violated, it follows that Alice's winning strategy works.

2. We will show that Bob can use the following strategy to win: Whenever Alice colors a line ABAB, Bob will color b/2\lfloor b/2 \rfloor edges out of AA blue and b/2\lfloor b/2 \rfloor edges out of BB. This ensures at most n/b/2+1n/\lfloor b/2 \rfloor + 1 red edges out of any point, which is not larger than b/2+1\lfloor b/2 \rfloor + 1 for b2nb \ge 2\sqrt{n}. Assuming Alice completes a triangle ABCABC and WLOG moves ABAB, ACAC and BCBC in sequence, it follows that before placing BCBC there were at least b/2+1\lfloor b/2 \rfloor + 1 threats out of CC. However this means, since placing ACAC created these threats, that, not counting ACAC, there were at least b/2+1\lfloor b/2 \rfloor + 1 red lines out of AA and thus the total number of red lines coming out of AA is larger than b/2+1\lfloor b/2 \rfloor + 1, a contradiction.

\Box

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.