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

[cutkit]

Mình có một bài toán rất khó và đang cần giải gấp. Nhưng vẫn không nghĩ ra câu trả lời. Vậy mong các bạn giải giúp:

Cu Tí vẽ bốn mươi tranh

Mười màu mỗi bức rành rành chẳng sai

Xem tranh mới thấy Tí tài

Hai tranh không có đến hai màu cùng

Bây giờ bạn tính ung dung :

Số màu ít nhất Tí dùng bao nhiêu ?

Mình đã tính và chỉ biết rằng nó sẽ nhỏ hơn 214. Mong các bạn giúp cho.

[lehoan]

Số màu ít nhất cần dùng là 9.40+1=361 màu

[mathhọcvẹt]

Cu Tí vẽ bốn mươi tranh

Mười màu mỗi bức rành rành chẳng sai

Xem tranh mới thấy Tí tài

Hai tranh không có đến hai màu cùng

Bây giờ bạn tính ung dung :

Số màu ít nhất Tí dùng bao nhiêu ?

---------------------------------------------------

Mình có cách này không biết có sai xót gì ko :

chia 40 tranh làm 4 tập hợp A ,B,C,D, mỗi tập có 10 tranh.
tô màu cho 10 tranh trong A như sau.
tranh thứ nhất tô = 10 màu ai # nhau , i=1..10.
tranh thứ 2 tô =9 màu bi ,i=2..10 (bi#aj) và dùng lại 1 màu a1.
tranh 3 tô = 8 màu ci ,i=3..10 (ci#aj , ci#bj) và dùng lại 2 màu a2,b2.
tranh 4 tô =7 màu di , i=4..10 (di# tất cả ca'c màu đã dùng) và dùng lại 3 màu
a3,b3,c3.
.......................
tranh 10 tô =1 màu k (k # tất cả các màu đã dùng)và dùng lại 9 màu :
a9,b9,c9,...i9. (a,b,c,d,e,f,g,h,i,k).

Với cách tô như vậy :
+Mỗi tranh tô = 10 màu # nhau và 2 tranh bất kỳ có chung đúng 1 màu.
=> Đây là cách tô màu tiết kiệm nhất thỏa mãn yêu cầu bài tóan.
Số màu cần dùng la`: 10+9+8+...+1=55 màu.
Trong đó có 10 màu :a10,b10,c10,...,i10,k mới dùng 1 lần, đặt là tập M.
(còn lại đều đã dùng đúng 2 lần) .

Tương tự cho tập B => cần 55 màu
và cũng có 10 màu dùng 1 lần , ta thay 10 màu này = 10 màu trong tập M.

=> trong B dùng 55-10=45 màu # nhau và # 55 màu của tranh trong A
Như vậy tất cả 55+45=100 màu được tô cho tranh trong A và B ,
và mỗi màu dùng đúng 2 lần (số lần tối đa được tô).
(Vì nếu dùng >2 lần => có hơn 2 tranh cùng 1 màu , ko thỏa ycbt).

Tương tự choC,D => dùng 100 màu.

KQ : 200 màu.