There are m foxes and n rabbits sitting in m+n seats around a circular table, where all animals are distinguishable. If a fox and a rabbit are sitting next to each other, they may swap positions with each other. For a fixed starting configuration, determine the number of configurations that can be reached by a sequence of swaps.
Note: Rotations and reflections of a configuration are considered distinct.
If m=0 or n=0, there is only one reachable configuration.
If m=1, there is one fox and n rabbits. The fox can occupy any of the n+1 seats. Therefore, there are n+1 reachable configurations.
Consider m=n=2.Configuration 1:We can reach Configurations 2 and 3:Configuration 2 creates three new configurations:Configuration 3 creates:Configuration 5 creates:Configuration 7 creates:Configuration 9 creates:Thus, there are 12 reachable configurations.We can choose the two seats occupied by the foxes in (24)=6 ways. The foxes and rabbits each have 2! possible permutations, giving
(24)⋅2!⋅2!=24=12.
The number of reachable configurations is
(24)⋅2=12.
Prove that
Ans≤(nm+n)mn.
By swapping foxes and rabbits, we can place the foxes in any m of the m+n seats. Hence, there are (nm+n) possible choices of seats for the foxes.Initially, the foxes f1,…,fm have a fixed clockwise cyclic order, and the rabbits r1,…,rn also have a fixed clockwise cyclic order.A swap between a fox and a rabbit does not change either cyclic order. Therefore, for each choice of occupied seats, there are at most m possible arrangements of the foxes and n possible arrangements of the rabbits.
Ans≤(nm+n)mn.
However, in Hint 4,
(24)⋅2⋅2=24=12.
Thus, not all of these configurations are necessarily reachable.
Without listing all the cases, prove that when m=n=2, exactly 12 of the (24)⋅2⋅2=24 configurations are reachable and 12 are not.By swapping, we can reach all (24)=6 choices of seats occupied by the two foxes.Cut the circle between seats 4 and 1.Starting from the cut, record the indices of the first fox and the first rabbit encountered in the clockwise direction.For example:
(f1,r1)
(f1,r2)
(f1,r2)
Assume that the starting configuration is
(f1,r1).
We can reach the following configurations:Thus, the pairs (f1,r1) and (f2,r2) are reachable.In general, write (fi,rj) for the indices of the first fox and rabbit encountered clockwise from the cut.If we swap two animals whose seats are not seats 1 and m+n, the pair (fi,rj) does not change.If we swap the animals in seats 1 and m+n, the pair changes as follows, depending on which animal crosses the cut:
(fi,rj)⟶(fi+1,rj−1)
(fi,rj)⟶(fi−1,rj+1).
Here the fox indices are taken modulo m, and the rabbit indices modulo n. We label the animals f0,…,fm−1 and r0,…,rn−1.For example, starting from
(f0,r0)⟶(f1,r−1)⟶(f0,r0).
Therefore, (f0,r1) and (f1,r0) are not reachable when m=n=2.Since all six choices of fox-occupied seats are reachable for each of the two possible index pairs,
Ans=(24)⋅2=12.
All 12 are reachable: starting from (f0,r0), we can arrange one fox and one rabbit in seats 1 and 4, swap them to obtain (f1,r1), and then rearrange the remaining fox-rabbit seat pattern without crossing the cut.
Now solve the problem for general positive integers m and n.Label the foxes f0,f1,…,fm−1 and the rabbits r0,r1,…,rn−1 according to their initial clockwise cyclic orders.The possible index pairs evolve as
(f0,r0)→(f1,r−1)→(f2,r−2)→⋯→(fk,r−k),k≥0.
Suppose the first repeated pair occurs at step t. Then
t≡i(modm),
−t≡−i(modn)⟹t≡i(modn).
Consequently,
t≡i(modlcm(m,n)).
The first repetition occurs after lcm(m,n) steps. Let
ℓ=lcm(m,n).
Thus, the sequence has period ℓ:All these index pairs are reachable by moving foxes and rabbits so that a fox and a rabbit occupy seats 1 and m+n, swapping them, and then rearranging the other seats.For each reachable index pair, we can obtain every choice of the m seats occupied by foxes. Indeed, adjacent fox-rabbit swaps that do not cross the cut allow us to move the foxes to any desired m seats while preserving the cyclic orders and the index pair.Therefore, there are (mm+n) possible seat patterns for each of the ℓ reachable index pairs.Hence, for m,n≥1,
Ans=(mm+n)ℓ
=(mm+n)lcm(m,n).
If m=0 or n=0, no swaps are possible, so the answer is 1.
