I've got this problem on my Graph algorithms exam and I still can't solve it! Here is the problem:
At first there are 100 people sitting at a round table and neither one is enemies with their neighbor. Than first night comes and each person becomes an enemy with one of his neighbors. How many nights have to pass until there are no more ways that the group can be seated so no one sits beside his enemy?
After each night, every person will become enemies with exactly one other person. This gives us 50 pairs of enemies after the first night. (This is because if persons 1 and 2 become enemies, person 3 must become enemies with person 4, and so on around the circle.) An easy way to seat them the second night would be to have each person sit directly across from their enemy. The third night, each person could sit with their enemies 25 seats away in either direction. You can continue halving the distance between pairs of enemies until they are right next to each other. The sequence of distances would then be $100,50,25,13,6,3,2,$and finally $1$; where someone would be forced to sit next to their enemy. Therefore, you could successfully seat the guests at least 7 nights without making enemies sit next to each other.
Edit: Thanks to commenter @Jaap Scherphius, I have been introduced to an even better solution. Given seat numbers of $0-99$, label each person by the number of the seat they sat in on day 1. For any value $0<c<100$ that is coprime to 100 ($c$ and 100 have a GCD of 1), you can arrange each person $p$ to seat $s$ where $s=(p*c)\ mod\ 100$. Coprime values above 50 produce mirror images of other values, so for the 20 numbers below 50 that are coprime to 100, you can successfully place all the people. This allows for a new maximum of $20$ days of happily seated people.