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
Đã gửi 29-06-2014 - 13:32
#2
Đã gửi 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 yêu thích
Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: 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ênBắt đầu bởi Leonguyen, Hôm nay, 13:59 tổ hợp |
|
|||
|
Toán Trung học Cơ sở →
Đại số →
Tổ hợp gây lúBắt đầu bởi huucong, Hôm qua, 21:21 tổ hợp |
|
||
|
Toán Trung học Cơ sở →
Đại số →
Không biết sai ở đâuBắt đầu bởi huucong, Hôm qua, 20:50 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áchBắt đầu bởi huucong, Hôm qua, 20:44 tổ hợp |
|
|||
Toán thi Học sinh giỏi và Olympic →
Tổ hợp và rời rạc →
Có bao nhiêu cách viết số nguyên dương n thành tổng các số nguyên dương?Bắt đầu bởi Explorer, 24-04-2024 tổ hợp, đếm, nguyên dương và . |
|
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh