## Task A-1.5.

For natural numbers arranged in a circle, we say they are in a zig-zag order if each number is either greater or smaller than both of its neighbors. A pair of adjacent numbers is called good if, after their removal, the remaining numbers are still in a zig-zag order.

Numbers from 1 to 300 are arranged in a zig-zag order. What is the smallest possible number of good pairs of adjacent numbers?
## Solution.

Let $a, p, q, b$ be four consecutive numbers in a zigzag order. Assume that $p > q$. Then $ab$. Therefore, we conclude that the pair $(p, q)$ is not good if and only if $p$ is the largest and $q$ is the smallest number in the quartet $(a, p, q, b)$.

If the pair $(p, q)$ is not good, then the pair $(a, p)$ is good because $a$ is not less than $q$. Similarly, the pair $(q, b)$ is good because $b$ is not greater than $p$.

Thus, we have shown that for any two pairs that share a common element, at least one of these two pairs is good. Therefore, there are at least 150 good pairs.

Suppose there exists a zigzag order $a_{1}, \ldots, a_{300}$ in which there are exactly 150 good pairs.

Without loss of generality, we can assume that $a_{1} > a_{2}$ and that the pair $\left(a_{1}, a_{2}\right)$ is not good. Then the pairs $\left(a_{2 k}, a_{2 k+1}\right)$ are good, and the pairs $(a_{2 k-1}, a_{2 k})$ are not good for all $k=1,2, \ldots, 149$. Also, the pair $\left(a_{299}, a_{300}\right)$ is not a good pair.

Since the pair $(a_{1}, a_{2})$ is not good according to the given criterion, we conclude that $a_{1} > a_{3}$. Also, since $(a_{3}, a_{4})$ is not a good pair, we conclude that $a_{3} > a_{5}$. Similarly, we conclude

$$
a_{1} > a_{3} > a_{5} > \cdots > a_{299} > a_{1}.
$$

This leads to a contradiction, so it is not possible for a zigzag order to have exactly 150 good pairs. Therefore, there are at least 151 good pairs.

An example of an order with exactly 151 good pairs is

$$
3,2,5,4,7,6, \ldots, 299,298,300,1
$$

In this order, the pair $(300,1)$ and all pairs $(2 k, 2 k+3)$ for $k=1, \ldots, 148$ are not good, while all other pairs are good.

## NATIONAL MATHEMATICS COMPETITION

## 2nd grade - high school - A variant Poreč, April 13, 2018.