Bài 8 ( Liên Xô 1965 ) :
Trong cuộc hội thảo có 40 cuộc họp, mỗi cuộc họp có 10 thành viên. Cho biết hai thành viên bất kì chỉ cùng dự họp với nhau tối đa một lần. Chứng minh rằng cuộc hội thảo có nhiều hơn 60 thành viên.
Gọi số thành viên là $n.$
Ta xét bảng gồm $n$ cột và $40$ dòng. Mỗi cột tương ứng với $1$ thành viên và mỗi dòng ứng với $1$ cuộc họp.
Tại dòng $j$ cột $i$ ta viết số $1$ nếu thành viên $i$ tham gia cuộc họp $j$ và viết số $0$ nếu thành viên đó không tham gia.
Vì hai thành viên bất kì chỉ cùng dự họp với nhau tối đa một lần nên không tồn tại $4$ số $1$ trên bảng tạo thành một hình chữ nhật.
Gọi $a_i$ là số số $1$ trên cột $i.$ Vì mỗi cuộc họp có $10$ thành viên nên $\sum_{i=1}^{n}a_i=400.$
Ta đếm số cặp số $1$ trên từng cột theo hai cách.
$\cdot$ Số cặp số $1$ trên cột $i$ là $\dfrac{a_i(a_i-1)}{2}$
Do đó tổng số cặp số $1$ trên từng cột trong bảng là $\sum_{i=1}^{n} \dfrac{a_i(a_i-1)}{2}$
$\cdot$ Vì không tồn tại $4$ số $1$ trên bảng tạo thành một hình chữ nhật nên khi chiếu các cặp số $1$ xuống phương thẳng đứng sẽ không tồn tại hai cặp số $1$ trùng nhau nên số cặp số một trên từng cột trong bảng không vượt quá $C_{40}^{2}=780$
Do đó $\sum_{i=1}^{n} \dfrac{a_i(a_i-1)}{2}\leq 780 \Leftrightarrow \sum_{i=1}^{n}a_i^2 \leq 1560+\sum_{i=1}^{n}a_i=1960$
Theo bất đẳng thức $C-S,$ ta có $1960\geq \dfrac{\left ( \sum_{i=1}^{n}a_i \right )^2}{n} \Leftrightarrow n\geq \frac{400^2}{1960}>81>60.$
Bài 9 ( VMO ):
Cho tập $S=\left \{ 1,2,...,n \right \}$. Gọi $T$ là tập tất cả các tập con không rỗng của $S$. Với mỗi $X$ thuộc $T$, gọi $m(X)$ là trung bình cộng các phần tử của $X$. Tính $m=\frac{\sum m(X)}{\left | T \right |}$
Cách khác: Với mỗi tập con $X$ của $S.$ Ta xét tập con $X'=\left \{ n+1-a\ \mid a\in X \right \}.$ Suy ra $m(X)+m(X')=n+1.$
Vì mỗi tập con $X$ xác định được duy nhất tập $X'$ và $X'$ là tập con của $S$ nên $2\sum m(X)=\sum m(x)+m(X')=(n+1)\left | T \right |$
Từ đó ta có $m=\frac{n+1}{2}.$
Bài viết đã được chỉnh sửa nội dung bởi Huy Thong: 23-06-2015 - 21:38