USAMO $1989$, Vấn đề $2$

Question

Vấn đề $2$ từ USAMO, $1989$: Các $20$ các thành viên của một câu lạc bộ quần vợt địa phương đã lên lịch chính xác $14$trò chơi hai người với nhau, với mỗi thành viên chơi trong ít nhất một trò chơi. Chứng minh rằng trong lịch trình này phải có một bộ sáu trò chơi với$12$ người chơi khác biệt.

Nỗ lực của tôi về một giải pháp: Vì có$20$ người chơi, mỗi người đã chơi ít nhất một trò chơi, số trận đấu ít nhất phải được tổ chức để chứa tất cả người chơi sẽ là $10$. Hiện nay,$4$còn lại nhiều trận đấu hơn, có thể chơi tối đa $8$ trong số này $20$người chơi. Vì vậy, ít nhất $12$ người chơi không được chơi nhiều hơn $1$phù hợp, và do đó có phải tồn tại một bộ sáu trò chơi với$12$người chơi khác biệt . Tôi tin rằng đây sẽ là nguyên tắc chỉ đạo của một bằng chứng chặt chẽ.

Tôi có những nghi ngờ sau đây bao trùm tâm trí mình:

1. Lập luận của tôi có đúng đắn, tức là, không có bất kỳ cạm bẫy nào không?
2. Nếu đúng, làm thế nào để đưa lập luận trên vào một chứng minh toán học chặt chẽ?

Chỉnh sửa: Như Ben đã chỉ ra trong phần bình luận, câu nói in nghiêng là không hợp lý. Có vẻ như tôi đã bỏ qua rất nhiều khả năng trong khi đóng khung bằng chứng này. Vì vậy, tôi muốn nhận được một số gợi ý để tiến hành chứng minh hợp lý hơn.

Answer 1

Tôi sợ có một cạm bẫy. Nếu bạn cố gắng chứng minh rằng có 6 trò chơi với 12 người chơi khác nhau trong số những người đã chơi đúng 1 trò chơi, bạn sẽ thất bại. Đây là một ví dụ:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

Trong khi có 6 trò chơi với 12 người chơi khác nhau, chỉ có 5 trò chơi là giữa những người chơi với đúng một trò chơi.

Vì vậy, đây là một gợi ý: chia người chơi thành hai nhóm, những người có một trò chơi và những người có nhiều hơn. Sau đó ghép những người chơi với một trò chơi, sau khi ghép những người chơi trong một trò chơi với những người chơi có nhiều hơn và cuối cùng là những người chơi có nhiều trò chơi hơn.

CHỈNH SỬA : Cách tiếp cận thứ hai

Nếu mọi người được coi là một đỉnh và mọi trò chơi là một cạnh, câu hỏi yêu cầu phải chứng minh rằng có sự phù hợp về kích thước ít nhất $6$. Tương tự, chúng tôi có thể chứng minh rằng kích thước của khớp tối đa$MM$ có kích thước ít nhất $6$. Lưu ý rằng kết hợp tối đa phân chia các đỉnh thành hai tập hợp, một có các cạnh trong$MM$, có kích thước $2\cdot |MM|$và một không có, có kích thước $20 - 2\cdot |MM|$cho vấn đề của chúng tôi. Vì tất cả các đỉnh đều có độ$1$, chúng tôi kết luận rằng có ít nhất $20 - 2\cdot |MM|$các cạnh giữa hai vách ngăn. Hiện nay,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$