Saudi Arabian IMO Booklet

We will call a woman unusual if she sits closer to her husband than her brother. Our goal is to find the smallest possible number of unusual women. Let us call this number $k$. We note that going from each man to his sister and from each woman to her husband we obtain an oriented graph which breaks up into oriented cycles of even length. We also note that within an oriented cycle the sequence of lengths between consecutive members increases unless we encounter an unusual woman. Thus, each cycle must have at least one unusual woman. We also note that since the maximum length between two seats is $6n+3$, this is also the maximum distance within a cycle we can go without encountering an unusual woman. Thus, we can have neither $k=0$ nor $k=1$, since by the first requirement we would have only one cycle, but this cycle would then have to have more than $6n+3$ people. We will show that $k=2$ is also impossible. The only options for $k=2$ are to have either one cycle with lengths $1,2,\dots ,6n+3,1,2,\dots ,6n+3$ or two cycles with lengths $1,2,\dots ,6n+3$. We note that the second option does not work because the cycles have odd length, while the first option does not work because the two locations where the unusual women are supposed to be are at an odd distance from each other along the cycle and therefore those positions cannot be occupied by two people of the same gender.

We now give an example for $k=3$. Arrange the three unusual women in an equilateral triangle and place their brothers diametrically opposite of them. Each unusual woman is part of a cycle of length $4n+2$. If we label the members of one of these cycles in order as $$W_1,M_1,W_2,M_2,\dots ,W_{2n+1},M_{2n+1},$$ where $W_1$ is the unusual woman, then if we place $W_1$ at position 0, we can place each $M_k$, $k=1,\dots ,2n$ at position $k$ and each $W_k$ at position $k=1,\dots ,2n+1$ at position $-k+1$. Finally, we place $M_{2n+1}$, the brother of $W_1$, at position $6n+3$.

The other two unusual women are placed symmetrically at positions $4n+2$ and $-(4n+2)$. We note that all the conditions of the problem are satisfied for this arrangement. Thus, the maximum possible number of women seated closer to their brother than their husband is $6n+3-3=6n$. $\square$