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.
#1
Posted 29-06-2014 - 13:32
#2
Posted 30-06-2014 - 06:15
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.
- nguoivohinh98 likes this
Also tagged with one or more of these keywords: tổ hợp
Toán Trung học Cơ sở →
Toán rời rạc →
Xếp dãy 1;2;...;2003 thành dãy 2003;2002;...;1 qua một số bướcStarted by Nguyen Bao Khanh, 16-05-2024 tổ hợp |
|
|||
Toán Trung học Phổ thông và Thi Đại học →
Đại số →
Tổ hợp - Xác suất và thống kê - Số phức →
Chia $n$ kẹo cho $k$ người sao cho mỗi người nhận được ít nhất $l$ viên và nhiều nhất $h$ viênStarted by Leonguyen, 01-05-2024 tổ hợp |
|
|||
|
Toán Trung học Cơ sở →
Đại số →
Tổ hợp gây lúStarted by huucong, 30-04-2024 tổ hợp |
|
||
|
Toán Trung học Cơ sở →
Đại số →
Không biết sai ở đâuStarted by huucong, 30-04-2024 tổ hợp |
|
||
Toán Trung học Phổ thông và Thi Đại học →
Đại số →
Tổ hợp - Xác suất và thống kê - Số phức →
Không biết sai ở đâu: Chọn ngẫu nhiên 5 hs từ đội văn nghệ sao cho lớp nào cũng có học sinh được chọn, hỏi có bao nhiêu cáchStarted by huucong, 30-04-2024 tổ hợp |
|
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users