Đề thi chọn học sinh giỏi quốc gia THPT năm 2015 môn Toán

(Bản scan)

Bài 7 (6.0 điểm). Có m học sinh nữ và ø học sinh nam (m,n>2) tham gia một Liên hoan
Song ca. Tại Liên hoan Song ca. mỗi buổi biểu diễn một chương trình văn nghệ. Mỗi
chương trình văn nghệ bao gồm một số bài song ca nam-nữ mà trong đó mỗi đôi nam-nữ
chỉ hát với nhau không quá một bài và mỗi học sinh đều được hát ít nhất một bài. Hai
chương trình được coi là khác nhau nếu có một cặp nam-nữ hát với nhau ở chương trình
này nhưng không hát với nhau ở chương trình kia. Liên hoan Song ca chỉ kết thúc khi tất
cả các chương trình khác nhau có thể có đều được biểu diễn, mỗi chương trình được biểu
diễn đúng một lần.

a) Một chương trình được gọt là lệ thuộc vào học sinh X nếu như hủy tất cả các bài
song ca mà X tham gia thì có ít nhất một học sinh khác không được hát bài nào trong
chương trình đó. Chứng minh rằng trong tất cả các chương trình lệ thuộc vào X thì số
chương trình có số lẻ bài hát bằng số chương trình có số chẵn bài hát.

b) Chứng minh răng Ban tô chức Liên hoan có thể sắp xếp các buổi biểu diễn sao cho
số các bài hát tại hai buổi biểu diễn liên tiếp bất kỳ không cùng tính chẵn lẻ.