Question 24
The Macedonian Mathematical Olympiad is held in two rooms numbered $1$ and $2$. At the beginning all contestants enter room no. $1$. A final arrangement of the contestants among the rooms is obtained in the following way: a list with the names of some of the contestants is read aloud; when a name is read, that contestant and all his acquaintances among the other contestants change the room in which they currently are. Thus to each list of names there corresponds one final arrangement of the contestants among the rooms. Show that the total number of possible final arrangements is not equal to $2009$. (Acquaintance between contestants is a symmetric relation.)