Merlin summons the $n$ knights of Camelot for a conference. Each day, he assigns them to the $n$ seats at the Round Table. From the second day on, any two neighbours may interchange their seats if they were not neighbours on the first day. The knights try to sit in some cyclic order which has already occurred before on an earlier day. If they succeed, then the conference comes to an end when the day is over. What is the maximum number of days for which Merlin can guarantee that the conference will last?
Problem
Source:
Tags: combinatorics unsolved, combinatorics
junioragd
08.09.2014 21:08
The answer is 2,I don't have time to write full solution. EDIT:I meant that he at day 3 the knights will have a strategy to do this.
chaotic_iak
09.09.2014 00:53
Can a knight swap seats more than one time? Does the order repeated include the direction too (and hence ABC is not the same as ACB)? Does repeating a position mean repeating a position during the conference or before the conference (the assignments) (for example, if in the second day they are assigned ABDC even if they end up sitting ACDB, in the third day they may attempt to repeat ABDC in addition to ACDB)? If the answer for the second question is yes, then clearly $2$ is not enough; the first time Merlin assigns ABC, then the second time ACB. In the second day, the knights cannot swap seats at all and hence the conference will last for another day. (On the other hand, however this third seating is assigned, this will repeat some of the previous day's, and hence the conference will last for $3$ days.)