Đây là một bài toán hay, liên quan đến balanced incomplete block design (BIBD).

Gọi 12k người là người 1, người 2,..., người 12k. Gọi \(A_1, A_2, ..., A_{12k}\) là tập các người bắt bắt tay với người 1,2,...,12k. Thế thì \(|A_1|=|A_2|=...=|A_{12k}|=3k+6.\)

Cũng theo đề bài, với mọi i,j ; \(1 \leq i < j \leq 12k\) thì \(|A_i \cap A_j|= m \leq 3k+6\) 

Gọi \(d_i\) trong số tập trong \(A_1, A_2, ..., A_{12k}\) mà chứa người i.

Ta lại dùng 2 công thức (rất hữu ích) ở bài toán 7 ta được: 

Công thức 1: \(d_1+d_2+...+d_{12k}=|A_1|+|A_2|+...+|A_{12k}|=(3k+6)(12.k)\)

Công thức 2: \(C_{d_1}^2+C_{d_2}^2+...+C_{d_{12k}}^2= \sum\limits_{1\leq i<j \leq 12k} |A_i \cap A_j| = C_{12k}^2.m\)

Vì mỗi người bắt tay với đúng 3k+6 người khác nên ta cũng suy ra: \(d_1=d_2=...=d_{12k}=3k+6\)

Do đó từ công thức 2 ta suy ra:\(\dfrac{12k(12k-1)}{2} \cdot m= \dfrac{12k(3k+6)(3k-5)}2 => m\cdot (12k-1) = 3(k+2)(3k+5)\) 

Đến đây ta suy ra: 3.(k+2)(3k+5) chia hết cho (12k-1) với k là số nguyên nên k = 3. Đáp đó:  36 người.

Lời giải anh hangtuan hay quá, em cảm ơn Anh ạ. Anh ơi, Anh cho em xin fb để kết bạn học hỏi thêm được không Anh

Đưa facebook lên đây không tiện em ạ, có gì muốn trao đổi em liên hệ với anh Khương nhé =))).

Dạ Anh.

Dạ bài toán 11 ạ.

Bài 11.

Lời giải:

Giả sử hàng i có \(x_i\) người nữ. Ta có:\(\sum_{i=1}^{20}x_i=n \)

Ta đếm T là số bộ \((C_1,C_2,H)\): Hàng H giao với hai cột \(C_1,C_2\) tại hai người cùng giới.

Đếm theo cột: Theo GT hai cột bất kỳ có không quá 13 hàng giao với chúng tại hai người cùng giới cho nên: $$T\leq C_{101}^{2}.13 \quad (1)$$

Đếm theo hàng: Hàng i có  \(x_i\) người nữ và \(101-x_1\) người nam nên:

$$T=\sum_{i=1}^{20}(C_{x_1}^{2} + C_{101-x_1}^{2})=\sum_{i=1}^{20}\frac{1}{2}(x_i^2-x_i+(101-x_i)^2-101+x_i)=\sum_{i=1}^{20}(x_i^2-101x_i+101.50)$$

$$\Rightarrow T \ge \frac{1}{20}(\sum_{i=1}^{20}x_i)^2 - 101\sum_{i=1}^{20}x_i+ 20.50.101$$

$$\Rightarrow T \ge \frac{1}{20}n^2-101n+1000.101  \quad (2)$$

Kết hợp (1) và (2) ta có: \(13C_{101}^2 \geq \frac{1}{20}n^2-101n+1000.101\).

Giải bất phương trình kết hợp n số nguyên dương ta được: \(451 \leq n \leq 1569\). Vậy giá trị nhỏ nhất của n là 451.