Câu hỏi 28
Olympic Toán Macedonia được tổ chức trong hai phòng đánh số $1$ và $2$. Ban đầu tất cả các thí sinh đều ở phòng $1$. Sơ đồ phòng cuối cùng được tạo ra như sau: người ta đọc một danh sách tên của một số thí sinh; khi đọc đến tên một thí sinh thì bạn ấy và tất cả bạn bè của bạn ấy đổi phòng mà họ đang ở. Như vậy mỗi danh sách tên ứng với một sơ đồ phòng cuối cùng. Chứng minh rằng tổng số sơ đồ có thể có không thể bằng $2009$. (Quan hệ bạn bè là đối xứng.)