Maths Olympiad Prep

Library / /25 of 27

Combinatorics Difficulty 7.0 National olympiad Prove it Croatia

We say that a circular arrangement of positive integers is alternating if every number is either smaller, or larger than both of its neighbours. We call a pair of adjacent numbers good if, upon its removal, the remaining numbers form an alternating arrangement.

The numbers 11 to 300300 are placed on a circle in an alternating arrangement. Determine the least possible number of good pairs of adjacent numbers in such arrangement.

Solution

Let aa, pp, qq and bb be four consecutive numbers in an alternating arrangement. Assume p>qp > q. Then a<pa < p and q<bq < b.

The pair (p,q)(p, q) is not good if and only if a>ba > b. Therefore, we conclude that (p,q)(p, q) is not good if and only if pp is the largest, and qq the smallest number of the quadruple (a,p,q,b)(a, p, q, b).

If (p,q)(p, q) is not good, then (a,p)(a, p) is, because aa is greater than or equal to qq. Furthermore, (q,b)(q, b) is good because bb is not greater than pp.

This shows that, of any two pairs sharing an element, at least one is a good pair. We conclude that there are at least 150150 good pairs.

Assume that there is an alternating arrangement a1,,a300a_1, \dots, a_{300} in which there are exactly 150150 good pairs.

Without loss of generality, we can assume that a1>a2a_1 > a_2, and that (a1,a2)(a_1, a_2) is not a good pair. Then (a2k,a2k+1)(a_{2k}, a_{2k+1}) are both good, while the pair (a2k1,a2k)(a_{2k-1}, a_{2k}) is not, for any k=1,2,,149k = 1, 2, \dots, 149. We also notice that (a299,a300)(a_{299}, a_{300}) cannot be a good pair.

Since (a1,a2)(a_1, a_2) is not good, we conclude that a1>a3a_1 > a_3. Similarly, since (a3,a4)(a_3, a_4) is not good, we get a3>a5a_3 > a_5. Continuing this way, we get
a1>a3>a5>>a299>a1, a_1 > a_3 > a_5 > \dots > a_{299} > a_1,
thus arriving at a contradiction. This shows that it is impossible to have exactly 150150 good pairs. Therefore, there must be at least 151151 of them.

An example of an alternating arrangement containing exactly 151151 good pairs is
3,2,5,4,7,6,,299,298,300,13, 2, 5, 4, 7, 6, \ldots, 299, 298, 300, 1.

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.