Cho bảng $8\times 6$,các ô của bảng được tô bởi $n$ màu sao cho mỗi cặp 2 màu chỉ xuất hiện cùng nhau không quá một hàng. Tìm giá trị nhỏ nhất có thể của $n$?
Tìm giá trị nhỏ nhất có thể của $n$?
#2
Đã gửi 11-07-2016 - 20:15
Cho bảng $8\times 6$,các ô của bảng được tô bởi $n$ màu sao cho mỗi cặp 2 màu chỉ xuất hiện cùng nhau không quá một hàng. Tìm giá trị nhỏ nhất có thể của $n$?
Đề bài khá lỏng lẻo vì nếu vậy thì ta cứ tô các ô hết một màu, đến hàng cuối cùng tô một màu nữa là xong nếu $n>1$
Nếu thêm điều kiện không có $2$ hàng nào mà tất cả các ô chung một màu:xét bài toán tổng quát là tô màu cho bảng $m.x$
Thay việc tô màu bằng việc đánh các số vào ô vuông
Giả sử ta dùng $k$ số từ $1$ đến $k$ để điền vào ô vuông thỏa mãn đề bài
Với $k$ hàng đầu tiên, với hàng $i$ ta đánh hết các số trong hàng là $i$.
Còn lại $m-k$ hàng
Với mỗi hàng như vậy, ta chọn một cặp bất kì $2$ số từ $k$ số đầu điền vào, các số còn lại trong hàng, ta đánh hết chúng là một trong hai số từ cặp đã chọn.
Như vậy để thuật toán này đúng thì $C^2_k \geq m-k$ hay $k \geq \dfrac{-1+\sqrt{1+8m}}{2}$ với k nguyên
Phần lập luận chứng minh k nhỏ nhất tương tự như lập luận tìm k này
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh