Question 28
The Macedonian Mathematical Olympiad is held in two rooms labeled with the numbers $1$ and $2$. In the beginning all the contestants are in room $1$. The final schedule is obtained in the following manner: a list of names of some of the contestants is read; when a contestant's name is read, he and all of his friends change the room in which they are at the moment. So to every list of names corresponds a final schedule. Prove that the total number of possible schedules cannot be equal to $2009$. (Friendship is a symmetrical relation.)