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

[nguoivohinh98]

Bài 3.Trong một hội nghị khoa học có 5000 đại biểu tham dự, mỗi một đại biểu biết ít nhất một thứ tiếng. Một uỷ ban gồm một số đại biểu được gọi là uỷ ban làm việc nếu tất cả thành viên trong uỷ ban đều biết chung một thứ tiếng và được gọi là uỷ ban thách thức nếu không có hai thành viên nào của uỷ ban biết chung một thứ tiếng (uỷ ban có thể gồm 1 thành viên; uỷ ban này gọi là làm việc cũng được, thách thức cũng được). Chứng minh rằng có thể chia các đại biểu thành đúng 100 uỷ ban rời nhau (mỗi đại biểu thuộc đúng một uỷ ban) sao cho các uỷ ban này hoặc là uỷ ban làm việc hoặc là uỷ ban thách thức.

[Karl Heinrich Marx]

Những bài thế này thường ta khảo sát cỡ 3-4 giá trị đầu xem số tối ưu là bao nhiêu và mình tìm ra số tối ưu nhất là $\frac{(n+1)(n+2)}{2}-1$ người có thể chia được vào $n$ nhóm còn lớn hơn thì không được.

Tìm được rồi thì ta quy nạp thôi.

Bây giờ với một số $k \le \frac{(n+2)(n+3)}{2}-1$ người ta sẽ chỉ ra cách phân vào $n+1$ nhóm sau khi đã quy nạp đến $n$.

Cho $k$ nguời này xếp hàng, những người nói được cùng 1 thứ tiếng cho đứng chung 1 cột, vậy mỗi cột là một thứ tiếng và mỗi hàng là một nhóm những người ko cùng thứ tiếng. Nếu có 1 hàng hay 1 cột nào đó mà có nhiều hơn $n+1$ người thì ta tách cái đó thành 1 nhóm và phần còn lại sẽ có không quá $k-n-2 \le \frac{(n+1)(n+2)}{2}-1$ người và phân được vào $n$ nhóm theo quy nạp. Suy ra đpcm

Nếu mà mỗi hàng không quá $n+1$ người thì ta lấy mỗi cột là 1 nhóm suy ra phân được thành số nhóm không quá $n+1$, muốn đủ thành $n+1$ thì chọn một số người còn thiếu ở các nhóm kia cho mỗi người 1 nhóm là xong.