## Task A-1.5.

Let $n$ be a natural number. Two identical sets of $n$ cards, each labeled from 1 to $n$, are given. On the table, all the cards from the first set are arranged in some order from left to right, followed by all the cards from the second set in the same order. We say that such an arrangement of cards is good if it is possible to select and remove some $n$ cards so that the remaining $n$ cards are arranged in increasing order from left to right, with the numbers from 1 to $n$. How many good arrangements of cards are there?
## Solution.

Notice that $1,2, \ldots, n-1, n, 1,2, \ldots, n-1, n$ is one good arrangement. For this arrangement, we can remove $n$ cards in $n+1$ ways so that the remaining numbers are 1 to $n$ from left to right (by removing any $n$ consecutive cards). For any other good arrangement, some cards must remain from the first set and some from the second.

Consider one such good arrangement of cards. Let $k$ be the largest number that remains on the table from the first set, i.e., the cards from the first set that remain have labels from 1 to $k$, and from the second set, from $k+1$ to $n$. The number $k$ can be any natural number such that $k < n$.

Since both sets were originally arranged in the same order, the cards from $k+1$ to $n$ in the first set must also have been in increasing order from left to right. Therefore, the order of the cards in the first set (and thus in the second set) consists of two increasing sequences - one from 1 to $k$, and the other from $k+1$ to $n$.

Imagine that the cards labeled from 1 to $k$ are red, and the remaining cards are blue. The number $k$ and the arrangement of the cards are uniquely determined once we choose which cards in the first set are red and which are blue. All color arrangements are allowed, except for the cases where all cards are the same color or all red cards are in front of all blue cards, as this would result in the arrangement $1,2, \ldots, n-1, n, 1,2, \ldots, n$.

It remains to count the number of ways to color the cards in allowed ways. There are $2^n$ possible colorings since for each card, we can choose one of two colors, but exactly $n+1$ colorings are not allowed - those in which there are $k$ red and $n-k$ blue cards for $k=0,1,2, \ldots, n$.

When we include the good arrangement $1,2, \ldots, n-1, n, 1,2, \ldots, n$, we conclude that the number of good arrangements is $2^n - n$.

## NATIONAL MATHEMATICS COMPETITION

## 2nd grade - high school - A variant

## April 25, 2023.