Maths Olympiad Prep

Library / /96 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

There are 100100 white points on a circle. Asya and Borya play the following game: they alternate, starting with Asya, coloring a white point in green or blue. Asya wants to obtain as much as possible pairs of adjacent points of distinct colors, while Borya wants these pairs to be as less as possible. What is the maximal number of such pairs Asya can guarantee to obtain, no matter how Borya plays.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. Labeling the Points:
We label the points on the circle as 1,2,,1001, 2, \ldots, 100.

2. Borya's Strategy:
- Borya pairs the points as (2i1,2i)(2i-1, 2i) for i=1,2,,50i = 1, 2, \ldots, 50.
- If Asya colors a point 2i12i-1 or 2i2i, Borya colors the other point in the pair with the same color.
- This strategy ensures that each pair (2i1,2i)(2i-1, 2i) is monochromatic, resulting in no adjacent pairs of distinct colors within each pair.
- Since there are 50 such pairs, Borya can ensure that there are at most 50 pairs of adjacent points with distinct colors.

3. Asya's Strategy:
- Asya pairs the points as (2i,2i+1)(2i, 2i+1) for i=1,2,,49i = 1, 2, \ldots, 49, and considers the pairs (1,2)(1, 2) and (99,100)(99, 100) separately.
- Asya colors point 1 with color RR (red).
- If Borya colors a point, Asya colors its pair with the opposite color.
- This strategy ensures that each pair (2i,2i+1)(2i, 2i+1) has distinct colors, resulting in 49 pairs of adjacent points with distinct colors.
- Additionally, since the circle is closed, the points 1 and 100 are also adjacent. If Borya colors point 100, Asya can color it with the opposite color of point 1, ensuring one more pair of distinct colors.
- Therefore, Asya can ensure at least 50 pairs of adjacent points with distinct colors.

4. Conclusion:
- Borya can ensure that there are at most 50 pairs of adjacent points with distinct colors.
- Asya can ensure that there are at least 50 pairs of adjacent points with distinct colors.
- Therefore, the maximal number of such pairs Asya can guarantee to obtain, no matter how Borya plays, is 50.

The final answer is 50\boxed{50}

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.