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$.
Lời giải.
Ta lập bảng gồm $n$ cột và $10$ hàng. Gọi $A_{1},A_{2},...,A_{10}$ là các cuộc gặp mặt
1
|
2
|
3
|
…
|
n
|
|
$A_{1}$
|
0
|
1
|
|||
$A_{2}$
|
1
|
1
|
|||
$A_{3}$
|
|||||
…
|
|||||
$A_{10}$
|
Ở dòng $i$ cột $j$ ta viết số $1$ nếu $j \in A_{j}$ và viết số $0$ nếu $j \notin A_{i}$
Điều kiện $2$ người bất kỳ tham gia chung không quá $1$ cuộc họp tương ứng $\begin{vmatrix} A_{i}\cap A_{j}\end{vmatrix}\leq 1$
hay không tồn tại $4$ số $1$ là đỉnh của hình chữ nhật
Gọi $c_{i}$ là số số $1$ trên cột thứ $i$. Dễ thấy $$\sum_{i=1}^{n}c_{i}=10.20=200$$Suy ra số cặp số $1$ trên cột $i$ là $$C_{c_{i}}^{2}=\frac{c_{i}(c_{i}-1)}{2}$$Dẫn đến tổng số cặp số $1$ trên cùng $1$ cột là $$\sum_{i=1}^{n}C_{c_{i}}^{2}=\sum_{i=1}^{n}\frac{c_{i}(c_{i}-1)}{2}=\frac{1}{2}\sum_{i=1}^{n}c_{i}^{2}-100$$
Xét $2$ dòng $i,j$ bất kì. Do $\begin{vmatrix} A_{i}\cap A_{j}\end{vmatrix}\leq 1$ nên số cặp số $1$ trên cùng $1$ cột không quá $1$.
Do đó $$\sum_{i=1}^{n}C_{c_{i}}^{2} \leq C_{10}^{2}\frac{1}{2}\sum_{i=1}^{n}c_{i}^{2}-100\leq C_{10}^{2}\Leftrightarrow \sum_{i=1}^{n}c_{i}^{2}\leq 290$$
Lại có $$(c_{i}-1)(c_{i}-2)\geq 0,\;c_{i}\in Z$$$$\Rightarrow c_{i}^{2}-3c_{i}+2\geq 0\Rightarrow 290\geq \sum_{i=1}^{n}c_{i}^{2}\geq 3\sum_{i=1}^{n}c_{i}-2n=600-2n\Rightarrow n\geq 155$$
Xây dựng. Kí hiệu $i$ là người thứ $i$
$A_{1}$
|
1,2,...,20
|
$A_{2}$
|
1,21,...,39
|
$A_{3}$
|
2,21,40,...,74
|
$A_{4}$
|
3,22,40,58,...,74
|
$A_{5}$
|
4,23,41,58,75,...,90
|
$A_{6}$
|
5,24,42,59,75,91...,105
|
$A_{7}$
|
6,25,43,60,76,91,106,...,11
|
$A_{8}$
|
7,27,44,61,77,92,106,120,...,132
|
$A_{9}$
|
8,28,45,62,78,93,107,120,133,...,144
|
$A_{10}$
|
9,29,46,63,79,94,108,121,133,145,...,155
|
Một bài toán khác tương tự bài trên
Bài toán. (Chọn đội tuyển VMO Đồng Tháp 2014)
Bài toán. (Chọn đội tuyển VMO Đồng Tháp 2014)
CLB du khảo có $n$ thành viên. Năm
ngoái CLB đã tổ chức được $6$ chuyến du khảo, mỗi
chuyến có $5$ thành viên tham dự.
Một thành viên CLB nhận xét rằng hai chuyến du khảo bất
kỳ có không quá hai
thành viên chung. Hỏi CLB đó có ít nhất bao nhiêu thành viên?