
C4 In a group of $n$ people, each one had a different ball. They performed a sequence of swaps; in each swap, two people swapped the ball they had at that moment. Each pair of people performed at least one swap. In the end each person had the ball he/she had at the start. Find the least possible number of swaps, if: $a$ ) $n=5$; b) $n=6$.


## Solution

We will denote the people by $A, B, C, \ldots$ and their initial balls by the corresponding small letters. Thus the initial state is $A a, B b, C c, D d, E e(, F f)$. A swap is denoted by the (capital) letters of the people involved.

a) Five people form 10 pairs, so at least 10 swaps are necessary.

In fact, 10 swaps are sufficient:

Swap $A B$, then $B C$, then $C A$; the state is now $A a, B c, C b, D d, E e$.

Swap $A D$, then $D E$, then $E A$; the state is now $A a, B c, C b, D e, E d$.

Swap $B E$, then $C D$; the state is now $A a, B d, C e, D b, E c$.

Swap $B D$, then $C E$; the state is now $A a, B b, C c, D d, E e$.

All requirements are fulfilled now, so the answer is 10 .

b) Six people form 15 pairs, so at least 15 swaps are necessary. We will prove that the final number of swaps must be even. Call a pair formed by a ball and a person inverted if letter of the ball lies after letter of the person in the alphabet. Let $T$ be the number of inverted pairs; at the start we have $T=0$. Each swap changes $T$ by 1 , so it changes the parity of $T$. Since in the end $T=0$, the total number of swaps must be even. Hence, at least 16 swaps are necessary. In fact 16 swaps are sufficient:

Swap $A B$, then $B C$, then $C A$; the state is now $A a, B c, C b, D d, E e, F f$. Swap $A D$, then $D E$, then $E A$; the state is now $A a, B c, C b, D e, E d, F f$. Swap $F B$, then $B E$, then $E F$; the state is now $A a, B d, C b, D e, E c, F f$. Swap $F C$, then $C D$, then $D F$; the state is now $A a, B d, C e, D b, E c, F f$. Swap $B D$, then $C E$, then twice $A F$, the state is now $A a, B b, C c, D d, E e, F f$. All requirements are fulfilled now, so the answer is 16 .
