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

[dangngocthanh]

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$?

[Bui Ba Anh]

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