Въпроси на преподаването
A COMBINATORIAL QUESTION RELATED TO AN EASTER TRADITION LED TO A NEW ENTRY IN OEIS
Резюме. In some regions of Bulgaria (at least) there is an Easter tradition, according to which in group of people first each one chooses a differently coloured egg, then each pair of peopleperforms a swap (or swaps) by exchanging the eggs they currently have until everyone gets the originally chosen egg. This generates a natural question: if there are \(n\) people in the group, find the least number \(E(n)\) of swaps which makes this possible. We prove that \(E(n)\) is the least even number not less than \(n(n-1) / 2\). The sequence thus generated was added to the Online Encyclopedia of Integer Sequences and linked from there to several seemingly distant combinatorial results.
Ключови думи: combinatorics; swap; inversion; invariant; paths in a lattice
Problem. Let \(n\) be a positive integer. In a group of \(n\) people, each one has a dif ferent Easter egg. W e say that a pair of people performs a swap if they exchange the eggs they currently have. Find the least possible number \(E(n)\) of swaps such that each pair of people has performed at least one swap and at the end each person has the egg he/she had at the start.
Before we solve the above problem, let us discuss what happens with \(E(n)\) for small \(n\). Denote the people by \(A, B, C, D, \ldots\) and their initial Easter eggs by the corresponding small letters. A swap is denoted by the names of the persons involved. Clearly \(E(1)=0\) and \(E(2)=2\). Let us find \(E(3)\). Assume that the persons \(A, B, C\) have chosen the eggs \(a, b, c\) respectively; we indicate this initial state by \(A a, B b, C c\). One can assume that the first swap is between persons \(A\) and \(B\), leading to the state \(A b, B a, C c\). The second swap is either by the same pair of people (which will easily seen to be not optimal) or by a different one; we will assume without loss of generality that it is between \(A\) and \(C\), thus leading to the state \(A c, B a, C b\). At least one swap is needed also between \(B\) and \(C\), but such a swap leads to the state \(A c, B b, C a\), so we need at least one more swap, and if it is between \(A\) and \(C\), the original state is restored, hence \(E(3)=4\).
Concerning \(E(4)\), four people form 6 unordered pairs, so \(E(4) \geq 6\). To see that \(E(4)=6\), we proceed as follows, starting with the initial state \(A a, B b, C c, D d\) :
– Swap \(A B\), then \(C D\); the state is now \(A b, B a, C d, D c\).
– Swap \(A C\), then \(B D\); the state is now \(A d, B c, C b, D a\).
– Swap \(A D\), then \(B C\); the state is now \(A a, B b, C c, D d\) and we are done.
Of course, the sequence so far obtained \(0,2,4,6, \ldots\) will not be followed by 8, since five people form 10 unordered pairs, yielding \(E(5) \geq 10\). To see that \(E(5)=10\), we proceed as follows, starting with the initial state \(A a, B b, C c, D d, E e\) :
– Swap \(A E\), then \(A B\), then \(B E\); the state is now \(A b, B a, C c, D d, E e\).
– Swap \(C E\), then \(C D\), then \(D E\); the state is now \(A b, B a, C d, D c, E e\).
– Swap \(A C\), then \(B D\); the state is now \(A d, B c, C b, D a, E e\).
– Swap \(A D\), then \(B C\); the state is now \(A a, B b, C c, D d, E e\) and we are done.
Now let us proceed with the solution of the originally posed general question.
Solution. There are at least \(n(n-1) / 2\) swaps, as there are that many pairs of people. We will prove that the total number of swaps must be even. Call a pair of Easter eggs “inverted”, if the egg with the former letter belongs to the person with the latter one. Let \(T\) denote the total number of inverted pairs; at the start \(T=0\). A swap performed by adjacent (by letter) people changes \(T\) by 1. Any swap is equivalent to an odd number of swaps performed by adjacent people, so it changes the parity of \(T\). Since at the end \(T=0\), the total number of swaps must be even. We will show that these two restrictions generate the answer, i.e.,
\[ E(n)=n(n-1) / 2 \text { if this number is even and } E(n)=n(n-1) / 2+1 \text { if not. } \]
We construct the required examples for even \(n\) by induction, in a way that if \(n \equiv 2(\bmod 4)\), then≡2(mod4), then the last two swaps are performed by the same pair of people (thus we keep track where the extra swap has gone). We already know that \(E(2)=2\) and \(E(4)=6\).
Assume first that \(n\) is a multiple of 4 and that the people \(P_{1}, P_{2}, \ldots, P_{n}\) can perform the task in \(n(n-1) / 2\) swaps. Take two more people, \(A\) and \(B\). For the enlarged set of \(n+2\) people we apply the same procedure as for \(n\) people with the following modifications:
– If \(k\) is odd, each swap of the type \(P_{k} P_{k+1}\) is replaced by the sequence of three swaps \(A P_{k} ; P_{k} P_{k+1} ; P_{k+1} A\), which has the same effect (in particular the Easter egg of \(A\) is returned to himself).
– If \(k\) is even, each swap of the type \(P_{k} P_{k+1}\) is replaced by the sequence of three swaps \(B P_{k} ; P_{k} P_{k+1} ; P_{k+1} B\), which has the same effect (the numbering is modulo \(n\) ).
– Each swap between non-consecutive people in the above numbering is kept unchanged.
At the end the initial state is restored (by the induction hypothesis) and each pair of people has performed exactly one swap, with the exception of \(A B\); so we perform at the end two consecutive swaps between these people and finish the construction.
Assume now that \(n=4 m+2\) and that the people \(P_{1}, P_{2}, \ldots, P_{4 m-1}, P_{4 m}, A, B\) can perform the task in \(n(n-1) / 2\) swaps, with the last two swaps being both \(A B\). Take two more people, \(C\) and \(D\). For the enlarged set of \(n+2\) people we apply the same procedure as for \(n\) people with the following modifications:
– If \(k\) is odd, each swap of the type \(P_{k} P_{k+1}\) is replaced by the sequence of three swaps \(C P_{k} ; P_{k} P_{k+1} ; P_{k} P_{k+1} D\), which has the same effect (in particular the Easter egg of \(C\) is returned to himself).
– If \(k\) is even, each swap of the type \(P_{k} P_{k+1}\) is replaced by the sequence of three swaps \(D P_{k} ; P_{k} P_{k+1} ; P_{k} P_{k+1} D\), which has the same effect (the numbering is modulo \(n\) ).
– Instead of performing the two swaps AB, at the end we perform the sequence of 6 swaps for the group of 4 people \(A, B, C, D\) as shown while discussing the case \(\mathrm{E}(4)=6\).
– Each swap between nonconsecutive people in the above numbering, as well as between one of the people \(A, B\) and one of the type \(P_{k}\), is k kept unchanged.
At the end the initial state is restored (by the induction hypothesis) and each pair of people has performed exactly one swap. This finishes the induction step for even \(n\).
Assume now that \(n\) is even and the people can perform the task in the minimum number of swaps as described above. The numbering is done in a way that the extra swap (if any) is between non-adjacent persons. Take one more person, \(A\). For the enlarged set of \(n+1\) people we apply the same procedure as for \(n\) people with the modification:
– If \(k\) is odd, each swap of the type \(P_{k} P_{k+1}\) is replaced by the sequence of three swaps \(A P_{k} ; P_{k} P_{k+1} ; P_{k+1} A\), which has the same effect (in particular the Easter egg of \(A\) is returned to himself).
– Each swap between non-consecutive people in the above numbering is kept unchanged.
At the end each person the initial state is restored (by the induction hypothesis) and each pair of people has performed exactly one swap (except for the one extra swap if \(n=4 m+2\) ). Note that for even \(n\), the n numbers \(n(n-1) / 2\) and \(n(n+1) / 2\) have the same parity. Thus for odd \(n\) we also conclude that the least number of swaps is \(n(n-1) / 2\) if this number is even and \(n(n-1) / 2+1\) if n not.
Note. The induction can be also organized via a uniform induction step from \(n\) to \(n+4\).
The sequence thus generated was new for the Online Encyclopedia of Integer Sequences; now it is added there as [2]. It is twice the sequence A054925 and is thus linked from there to several seemingly distant combinatorial re sults, like the number of edges in a median graph, walks in lattices and much more, listed in [1].
Bibliography
1. The On-Line Encyclopedia of Integer Sequences A054925 https://oeis.org/ A054925.
2. The On-Line Encyclopedia of Integer Sequences A192447 https://oeis.org/ A192447.