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

[Ispectorgadget]

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?

 

Đồng Tháp -2013

 

[hoangtrong2305]

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?

 

Đồng Tháp -2013

Bài này mình ví dụ như sau

 

Chuyến du khảo $1: 5$ người $A, B, C, D, E$

Chuyến du khảo $2: 5$ người $A, F,G,I,J$

Chuyến du khảo $3: 5$ người $F, B, K, L, M$

Chuyến du khảo $4: 5$ người $G, C,K,N,O$

Chuyến du khảo $5: 5$ người $E,J,M,O,P$

 

Vậy tối thiểu $15$ bạn

 

Thuật toán bài này là chuyến du khảo thứ $n$ sẽ có $n-1$ bạn đã đi rồi, nhiệm vụ ta sắp sao cho không phạm luật thôi

Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 27-10-2013 - 23:40

[chanhquocnghiem]

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?

 

Đồng Tháp -2013

CLB đó có ít nhất $12$ thành viên.

Ví dụ :

Chuyến đầu tiên : $A,B,C,D,E$

Chuyến thứ $2$ : $A,B,F,G,H$

Chuyến thứ $3$ : $A,C,F,I,J$

Chuyến thứ $4$ : $A,D,G,I,K$

Chuyến thứ $5$ : $A,E,H,J,K$

Chuyến thứ $6$ : $B,C,F,K,L$

[LNH]

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?

 

Đồng Tháp -2013

 

Gọi $x_i$ là số chuyến tham gia của thành viên thứ $i$

Suy ra $x_1+x_2+...+x_n=30$

Ta sẽ đếm số bộ (thành viên, chuyến, chuyến) bằng $2$ cách

Cách 1: Với mỗi thành viên có $C_{x_i}^2$ cách chọn $2$ nhóm tham gia

Vậy số bộ cần đếm là $\sum_{i=1}^{n}C_{x_i}^{2}$

Cách 2: Có $C_6^2$ cách chọn $2$ trong $6$ nhóm trên

Mà với $2$ nhóm bất kì có không quá $2$ thành viên chung nên số bộ cần đếm không quá $C_{6}^{2}.2=30$

Từ $2$ cách đếm trên suy ra $\sum_{i=1}^{n}C_{x_i}^{2}$\leq 30$

$\sum_{i=1}^{n}C_{x_i}^{2}=\frac{\sum_{i=1}^{n}x_i^2}{2}-15$

Không mất tính tổng quát, giả sử $x_1\geq x_2\geq ...\geq x_n$

Theo bất đẳng thức Chebychev, $\frac{\sum_{i=1}^{n}x_i^2}{2}\geq \frac{\left ( \sum x_i \right )^2}{2n}=\frac{450}{n}$

Suy ra $\frac{450}{n}-15\leq 30$

Hay $n\geq 10$

Vậy GTNN của $n$ là $10$

 

[chanhquocnghiem]

 

Bạn LNH có thể nêu ra 1 ví dụ cho thấy CLB đó có thể có đúng $10$ thành viên (và danh sách các thành viên của $6$ chuyến đi) có được không ?