Competition problem — Combinatorics

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Switzerland

Problem:

In a garden, there are 2023 rose bushes planted in a row. Each bush contains either red or blue roses. Vicky is taking a walk and wants to pick some of the flowers. She starts at a bush of her choice, and picks a rose from it to add to her basket. She then continues walking down the row and picks a single flower from each bush she visits. Vicky can skip some bushes, but she cannot skip two adjacent bushes. She can leave the garden at any point. Let $r$ and $b$ be the number of red and blue roses she picked, respectively. Determine the maximal value of $|r-b|$ Vicky can achieve, irrespective of the configuration of bushes.

Solution

Solution:

507

WLOG, let there be more red than blue bushes, with $R > B$ total bushes of each colour, respectively. If $r = R$ , Vicky is only forced to stop by at most $\left\lfloor \frac{B}{2} \right\rfloor$ , which gives a total of $R - \left\lfloor \frac{B}{2} \right\rfloor \geq 507$ . This bound cannot be surpassed in the construction
$B, R, R, B, B, \ldots, B, B, R, R$
To see this, call the groups of consecutive equal bushes "pairs"; we have a singleton followed by 1011 pairs. Vicky must pass through at least one element of each pair, so if her path intersects $k$ pairs then she has a score of at most $2 \cdot \left\lceil \frac{k}{2} \right\rceil - \left\lfloor \frac{k}{2} \right\rfloor$ if she wants more reds, or $1 - \left\lceil \frac{k}{2} \right\rceil + 2 \cdot \left\lfloor \frac{k}{2} \right\rfloor$ if she wants more blues. It is easy to verify that this is an increasing function of $k$ and is maximised when $k = 1011$ and we take the first function, giving 507.

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.