Toán 9 Sau khi lựa chọn các học sinh cho lớp CLB Toán 9

[Edgarnguyen248]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Sau khi lựa chọn các học sinh cho lớp CLB Toán 9, giáo viên nhận thấy rằng:
i) Trong CLB có ít nhất hai bạn quen nhau
ii) Nếu hai bạn có cùng số lượng người quen thì không có người quen chung
Chứng minh rằng có một học sinh của lớp chỉ quen đúng một người.

 

[7 1 2 5]

Nhận thấy ta không cần xét các học sinh không quen bất kỳ ai nên xem như tất cả học sinh đều quen ít nhất [imath]1[/imath] người.
Gọi [imath]A_1,A_2,...,A_n[/imath] là các học sinh trong CLB, và [imath]a_1,a_2,...,a_n[/imath] là số người quen tương ứng.
Giả sử điều phải chứng minh sai, tức [imath]a_1,a_2,...,a_n \geq 2[/imath].
Khi đó không mất tính tổng quát giả sử [imath]a_n =\max \lbrace a_1,a_2,...,a_n \rbrace = k[/imath].
Ta có [imath]A_n[/imath] sẽ quen với [imath]A_{i_1},A_{i_2},...,A_{i_k}[/imath], suy ra [imath]a_{i_1},a_{i_2},...,a_{i_k}[/imath] đôi một khác nhau.
Thật vậy, nếu có [imath]2[/imath] số [imath]r,s \in \lbrace i_1,i_2,...,i_k \rbrace[/imath] sao chô [imath]a_r=a_s[/imath] thì [imath]A_r,A_r[/imath] sẽ không có người quen chung (mâu thuẫn với [imath]A_n[/imath] cùng quen [imath]2[/imath] người)
Mà [imath]2 \leq a_{i_1},a_{i_2},...,a_{i_k} \leq k[/imath] nên [imath]k[/imath] số đó chỉ nhận tối đa [imath]k-1[/imath] giá trị khác nhau, tức tồn tại [imath]2[/imath] số bằng nhau (mâu thuẫn với điều trên)
Vậy điều ta giả sử sai hay ta có điều phải chứng minh.

Nếu còn thắc mắc chỗ nào bạn hãy trả lời dưới topic này để được hỗ trợ nhé ^^ Chúc bạn học tốt ^^
Ngoài ra, bạn tham khảo kiến thức tại đây nhé
[Lý thuyết] Chuyên đề HSG: Toán rời rạc