TỔNG HỢP CÁC BÀI TOÁN TỔ HỢP 

Nhóm các bài toán về Lý thuyết đồ thị (6 bài)

Bài 1. Cho $G$ là một graph đơn, ở đây $\left |V  \right |=n;\, \left | E \right |=e$. Chứng minh rằng $$e\leq \frac{n\left ( n-1 \right )}{2}$$
Bài 2. Có $605$ người trong một dạ hội. Giả sử rằng mỗi người bắt tay với ít nhất một

người khác. Chứng minh rằng phải có một người bắt tay với ít nhất $2$ người khác.


Bài 3. (USA MO 1978)
Có $9$ nhà toán học gặp nhau tại $1$ hội nghị toán học. Với bất kì $3$ người, có ít nhất $2$ người

trong đó nói cùng $1$ ngôn ngữ. Nếu biết mỗi nhà toán học chỉ có thể nói nhiều nhất $3$ ngôn

ngữ. Chứng minh rằng có ít nhất $3$ nhà toán học có thể cùng nói $1$ ngôn ngữ.


Bài 4. Có $n$ hộp thuốc. Bất kỳ $2$ hộp thuốc có cùng $1$ loại thuốc ở bên trong

và mỗi loại thuốc được chứa trong đúng $2$ hộp thuốc. Hỏi có bao nhiêu loại thuốc tất cả $?$


Bài 5. Có $n> 3$ người. Một vài người trong đó biết nhau và các người khác không

biết nhau. Có ít nhất $1$ người không biết các người khác. Hỏi số lớn nhất các cặp biết nhau.


Bài 6. Có $18$ đội tuyển trong $1$ giải đấu. Ở mỗi vòng, nếu một đội tuyển thi đấu với

một đội tuyển khác thì nó sẽ không thi đấu với cùng đội tuyển đó ở vòng đấu khác. Hiện nay

đã thi đấu $8$ vòng. Chứng minh rằng phải có $3$ đội tuyển chưa thi đấu với nhau trong $8$ vòng

đấu đó.


Bài 7. (Chọn đội tuyển VMO Đồng Nai 2015)
Cho $n \geq 3$ là một số nguyên dương. Chứng minh với $n$ điểm phân biệt nằm trong mặt

phẳng, sao cho trong đó không có $3$ điểm nào thẳng hàng thì số tam giác có đỉnh được lấy

trong $n$ điểm đã cho và có diện tích bằng $1$ không lớn hơn $\frac{2}{3}(n^2-n)$.


Bài 8. Xét $n\in N,n\geq 2$. Ta tô tất cả các số tự nhiên bởi $2$ màu xanh hoặc đỏ thỏa mãn $2$

điều kiện sau:

   i) Mỗi số được tô bởi một màu, mỗi màu được tô vô hạn số

   ii) Tổng $n$ số cùng màu đôi một khác nhau là một số được tô cùng màu.

Hỏi có thể thực hiện được cách tô màu như trên không nếu:

  1) $n=2015$

  2) $n=2016$


Bài 9. Một nhóm học sinh có $n$ người. Họ tổ chức $10$ cuộc gặp mặt. Mỗi cuộc gặp có $20$

người tham dự. Biết rằng hai người bất kì cùng tham gia không quá $1$ cuộc gặp. Tìm giá trị

nhỏ nhất của $n$.