Chủ đề này có 2 trả lời

[bachhammer]

Hội toán học của một thành phố cứ mỗi năm nhóm họp 40 lần. Mỗi lần họp có đúng 10 thành viên đến tham dự, trong đó không có hai thành viên nào cùng đến dự họp với nhau quá một lần. Chứng minh rằng hội toán học của thành phố đó không thể có ít hơn 60 thành viên.

[whatever2507]

Đặt $n$ là số thành viên của hội toán học. Xét đồ thị $G=(V,E)$ với $|V|=n$ đại diện cho $n$ người, $2$ đỉnh kề nhau khi và chỉ khi  $2$ người mà $2$ đỉnh này đại diện có gặp nhau tại một buổi họp.

Ban đầu đồ thị có $0$ cạnh, sau nỗi buổi họp thì đồ thị lại tăng thêm $C^2_{10}=45$ cạnh $\Rightarrow$ sau $40$ buổi họp đồ thị có $40.45=1800$ cạnh $(1)$.

Do không có 2 nhà toán học nào gặp nhau quá một lần nên đồ thị nhận được là đồ thị đơn $\Rightarrow$ Đồ thị nhận được có nhiều cạnh nhất khi nó là đồ thị đầy đủ, và khi đó số cạnh là $C^2_n= \frac{n(n-1)}{2} (2)$.

Từ $(1)$ và $(2)$ ta suy ra $\frac{n(n-1)}{2} \geq 1800$, giải bpt này ta có đpcm.

[bachhammer]

Lặp luận bằng Graph rất hay, nhưng suy luận này không cần đến Graph lắm đâu!!!