Boy and Girls!

For discussing Olympiad Level Combinatorics problems
User avatar
Kazi_Zareer
Posts:86
Joined:Thu Aug 20, 2015 7:11 pm
Location:Malibagh,Dhaka-1217
Boy and Girls!

Unread post by Kazi_Zareer » Tue Dec 20, 2016 2:47 pm

There are $n$ boys and $n+1$ girls standing in a straight line in some order (from left to right). A group of girls is a sequence of at least two neighboring girls with no girl immediately to the left and no girl immediately to the right of it. In a move, we take the leftmost group of girls and make the leftmost girl in it switch places with her left neighbour (if she has one) and the rightmost girl in it switch places with her right neighbour (if she has one). Prove that after finitely many moves, there will be at least one boy between every two girls.
We cannot solve our problems with the same thinking we used when we create them.

Post Reply