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

[linhk2]

Cho bàn cờ $4\times 4$. Chỉ được tô các ô của bàn cờ bằng 2 màu, hỏi có bao nhiêu cách tô sao cho không có ô $3\times 3$ nào được tô cùng một màu?

Bài viết đã được chỉnh sửa nội dung bởi linhk2: 22-08-2018 - 16:27

[Hr MiSu]

Có thể làm theo ng lý bù trừ như sau: xét 3x3 là màu trắng:

A: tập các hình có hcn 3x3 màu trắng có 4.2^7 cách

B: tập các hình có hcn 3x4 màu trắng có 4.2^4 cách

C: tập các hình có hcn 4x4 màu trắng có 1 cách

Vậy số cách mà có 3x3 trắng là |A|-|B|+|C|=4.2^7-2.2^4+1

Thay trắng = đen ta có số cách mà có hv 3x3 cùng màu: 2(4.2^7-2.2^4+1)

do đó số cách cần tìm là: 2^16-2(4.2^7-2.2^4+1)

[Hr MiSu]

Cho bàn cờ $4\times 4$. Chỉ được tô các ô của bàn cờ bằng 2 màu, hỏi có bao nhiêu cách tô sao cho không có ô $3\times 3$ nào được tô cùng một màu?

Mình xin đính chính lại lời giải như sau, vì lời giải trước đó của mình đã thiếu trường hợp.

Lời giải:Giả sử 2 màu là trắng và đen!

Xét 4 hình vuông $3x3$ theo thứ tự từ trên cùng bên trái, bên phải, dưới cùng bên phải, bên trái. Theo thứ tự là $1,2,3,4$

Gọi $A_i$ là tập hợp các cách tô hình vuông $i$ bằng màu đen, ta cần tính: $2(2^16-|A_1\cup A_2\cup A_3\cup A_4|)$

Ta có: $|A_i|=2^7, i=1,2,3,4$, $|A_1\cap A_2|=|A_2\cap A_3|=|A_3\cap A_4|=|A_4\cap A_1|=2^4, |A_1\cap A_3|=|A_2\cap A_4|=2^2, |A_1\cap A_2\cap A_3|= |A_2\cap A_3\cap A_4|= |A_3\cap A_4\cap A_1|= |A_4\cap A_1\cap A_2|=2^1,  |A_1\cap A_2\cap A_3\cap A_4|=2^0$,

Do đó: $|A_1\cup A_2\cup A_3\cup A_4|=4.2^7-(4.2^4+2.2^2)+4.2^1-2^0$

P/S: đây là đề AIME $2001$