Phương pháp tô màu trong bài toán Tổ hợp - Trần Ngọc Thắn

PHƯƠNG PHÁP TÔ MÀU TRẦN NGỌC THẮNG - THPT CHUYÊN VĨNH PHÚC Phương pháp tô màu thường được dùng để giải các bài tập liên quan đến bảng ô vuông (bài toán phủ, cắt, ghép…), tùy theo giả thiết và yêu cầu của từng bài toán mà ta chọn bao nhiêu màu và tô màu theo những cách phù hợp nhất để chứng minh bài toán. Việc tô màu theo cách như thế nào là bước rất quan trọng để giải các bài toán theo phương pháp tô màu và để có thể trang bị phần nào đó cho học sinh trong qua trình học chuyên đề này chúng tôi chọn lọc một số bài tập liên quan đến phương pháp tô màu. 1. Cho bảng 8×8 bị mất hai ô ở hai góc đối diện. Hỏi có thể lát phần còn lại của bảng bởi các quân a) 2×1 (cùng với các hình tạo bởi bằng cách quay đi một góc tùy ý) b) Hình chữ L dưới đây (cùng với các hình tạo bởi bằng cách quay đi một góc tùy ý) c) 2×1 và các quân hình chữ Hình chữ L dưới đây (cùng với các hình tạo bởi bằng cách quay đi một góc tùy ý) Lời giải. Tô màu bảng 8×8 như hình vẽ. 1 a) Khi đó mỗi quân 2×1 sẽ chiếm một ô đen và một ô trắng. Do đó nếu phần còn lại của bảng được phủ bởi các quân này thì số ô đen bằng số ô trắng vô lí vì số ô đen là 32, số ô trắng là 30. b) Khi đó mỗi quân hình chữ L sẽ chiếm một 2 ô đen và 2 ô trắng. Do đó nếu phần còn lại của bảng được phủ bởi các quân này thì số ô đen bằng số ô trắng vô lí vì số ô đen là 32, số ô trắng là 30. c) Mỗi quân 2×1 hoặc quân hình chữ L sẽ có số ô trắng bằng số ô đên. Do đó nếu phần còn lại của bảng được phủ bởi các quân này thì số ô đen bằng số ô trắng vô lí vì số ô đen là 32, số ô trắng là 30. 2. Xét bàn cờ vua 8×8 . Chứng minh rằng nếu xuất phát từ một ô góc, con mã không thể đi qua tất cả các ô của bàn cờ, mỗi ô một lần và kết thúc ở ô góc đối diện với ô góc nó xuất phát. Lời giải. Xét bàn cờ vua 8×8 như hình vẽ. Mỗi nước đi của quân mã sẽ chuyển đến ô khác màu với ô nó đứng trước đó. Do đó nếu xuất phát từ ô góc và đi qua tất cả các ô còn lại và đến ô góc đối diện thì con mã sẽ thực hiện 63 nước đi. Do đó con mã sẽ đến ô khác màu với ô xuất phát vô lí vì ô đối diện với ô xuất phát là cùng màu. Vậy bài toán được chứng minh. 3. Một hình tròn được chia thành 2014 hình quạt. Trong mỗi hình quạt có một viên bi. Thực hiện trò chơi sau: mỗi lần cho phép lấy ra hai viên bi trong hai hình quạt nào đó và chuyển sang các ô bên cạnh nhưng theo hai chiều ngược nhau. Hỏi sau một số lần có thể chuyển hết các viên bi vào một hình quạt được không? Lời giải. 2 Ta tô màu các hình quạt như hình vẽ, sao cho hai hình quạt cạnh nhau thì khác màu. Gọi S ( n) , T ( n) lần lượt là tổng số bi ở bước thứ n của các các hình quạt màu đen, hình quạt màu trắng. Do S ( 0) = T ( 0) = 1005 và S ( n) , T ( n) bất biến theo mod 2 nên không thể xảy ra trường hợp S ( n) = 0 hoặc T ( n) = 0 . Vậy bài toán được chứng minh. Nhận xét. Bài toàn có thể tổng quát nhứ sau: Cho n ∈ * , một hình tròn được chia thành n hình quạt. Trong mỗi hình quạt có một viên bi. Thực hiện trò chơi sau: mỗi lần cho phép lấy ra hai viên bi trong hai hình quạt nào đó và chuyển sang các ô bên cạnh nhưng theo hai chiều ngược nhau. Tìm tất cả các số nguyên dương n sao cho sau một số lần có thể chuyển hết các viên bi vào một hình quạt. 4. (Romania TST 2000) Tìm tất cả các cặp số nguyên dương ( m, n) sao cho bảng m×n có thể lát được bởi các quân hình chữ L dưới đây (cùng với các hình tạo bởi bằng cách quay đi một góc tùy ý) Lời giải. Phân tích: Giả sử bảng được lát bởi một vài giá trị của a . Giả sử m ≤ n . Nếu a = 1 dễ thấy không thỏa mãn. x quân hình chữ L suy ra mn = 4a , ta sẽ thử Nếu a = 3 ta có mn = 12 ta có các khả năng ( m, n) = ( 2,6) , ( 3,4) cả hai bảng này không thể lát bởi các quân hình chữ L . 3 Nếu a = 2 ta có mn = 8 ta có các khả năng ( m, n ) = ( 2, 4) bảng này có thể lát bởi các quân hình chữ L như hình vẽ Như vậy ta dự đoán để lát được bảng m×n thì a phải là số chẵn. Trở lại bài toán: Ta sẽ chứng minh a chẵn và chỉ ra cách lát trong trường hợp đó. Ta tô bảng m×n theo cách sau: Với cách tô như vậy thì mỗi quân hình chữ L sẽ chiếm 3 ô đen và 1 ô trắng hoặc 3 ô trắng 1 ô đen. Giả sử trong a quân hình chữ L có u quân gồm 3 ô đen và 1 ô trắng, v quân gồm 1 ô đen và 3 ô trắng. Khi đó ta có: u + v = a u = v ⇔  3u + v = 3v + u a = 2u Suy ra a  2  mn  8 . Ta sẽ chứng minh với mn 8 thì luôn lát được bảng m×n bởi các quân hình chữ L . Ta xét các trường hợp sau: TH1. Nếu cả hai số m, n đều chẵn: do mn  8  một trong hai số phải chia hết cho 4 , giả sử n 4 .Khi đó ta chia bảng được như hình vẽ m×n thành các bảng 2×4 và các bảng con này lát 4 TH2. Nếu trong hai số m, n có một số lẻ, giả sử m lẻ. Khi đó ta viết m = 2 k + 3, n = 8 l suy ra m × n = ( 2k + 3) × ( 8l ) = 2lk ( 2 × 4) + l ( 3× 8) . Ta nhận thấy các bảng con 2×4 lát được bởi các quân hình chữ L , ta chỉ ra cách lát cho bảng 3×8 là xong. Thật vậy ta lát như hình vẽ: Vậy các số nguyên dương m, n thỏa mãn mn chia hết cho 8 . Bài toán đề xuất. Tìm tất cả các cặp số nguyên dương ( m, n) sao cho bảng m× n có thể lát được bởi các quân hình chữ L dưới đây (cùng với các hình tạo bởi bằng cách quay đi một góc tùy ý) 5. (VMO 2006) Xét bảng ô vuông m× n ( m, n là các số nguyên dương lớn hơn 3). Thực hiện trò chơi sau: mỗi lần đặt 4 viên bi vào 4 ô của bảng (mỗi ô 1 viên bi) mà 4 ô đó tạo thành một trong các hình dưới đây Hỏi sau một số lần ta có thể nhận được bảng mà số bi trong các ô bằng nhau được không nếu a) m = 2004 và n = 2006 ? b) m = 2005 và n = 2006 ? Lời giải. a) Bảng ô vuông 4× 2 được ghép bởi hai quân 5 Do đó với bảng 2004×2006 ta chia nó thành các bảng 4× 2 . Khi đó với cách đặt bi như yêu cầu ta sẽ đặt được mỗi ô vuông đơn vị của bảng 4× 2 một viên bi. Do vậy bảng 2004×2006 sẽ được đặt mỗi ô vuông đơn vị một viên bi. b) Giả sử ta có thể nhận được bảng mà số bi các ô bằng nhau và mỗi ô có q viên bi. Khi đó bảng 2005×2006 sẽ được lát bởi các quân Ta tô màu bảng 2005×2006 như hình vẽ (các ô vuông đơn vị trên cùng hàng thì cùng màu và hai hàng cạnh nhau thì khác màu) Gọi D( n) ,T ( n) lần lượt là tổng số bi trong các ô đen, ô trắng ở bước cuối cùng. Do 2005×2006 gồm 2005 hàng và 2006 cột nên D( n) = 2006.1003q,T ( n) = 2006.1002q  D( n) −T ( n) = 2006q . Mỗi quân được lát đều bảng chiếm 2 ô đen và 2 ô trắng nên D( n) −T ( n) = D( 0) −T ( 0) = 0 vô lý ( D( 0) ,T ( 0) là tổng số bi ở các ô đen, ô trắng lúc ban đầu). Vậy với m = 2005 và n = 2006 không thỏa mãn yêu cầu bài toán. 6 Nhận xét. Với cách làm của phần b thì ta có thể chứng minh được: nếu bảng m× n ( m, n > 3)thỏa mãn yêu cầu bài toán thì m, n đều là số chẵn. Khi một trong hai số m, n chia hết cho 4 thì bảng này sẽ thỏa mãn yêu cầu. Khi m, n đều chẵn và không chia hết cho 4 thì bảng có thỏa mãn không? 6. Cho k, n là các số nguyên dương. Xét một bảng ô vuông vô hạn, đặt 3k.n quân cờ trong hình chữ nhật 3k × n . Thực hiện trò chơi sau: mỗi quân cờ sẽ nhảy ngang hoặc dọc qua một ô kề với nó và có chứa quân cờ, để đến ô kề với ô này (ô mà quân cờ nhảy đến phải là ô trống). Sau khi làm như trên ta loại bỏ quân cờ ở ô bị nhảy qua ra khỏi bàn cờ. Chứng minh rằng, với cách chơi đó trên bảng ô vuông sẽ không bao giờ còn lại đúng một quân cờ. Lời giải. Ta tô bảng ô vuông vô hạn bởi ba màu 1, 2, 3 và được tô như hình vẽ. Gọi Sn ( i) là tổng số quân cờ trong ô vuông đơn vị có màu i ( i =1,2,3) ở bước chơi thứ n , trong đó n = 0 chỉ lúc ban đầu. Ta có S0 (1) = S0 ( 2) = S0 ( 3) = kn . Trong mỗi lần chơi thì tổng số bi của mỗi màu đều tăng hoặc giảm đúng một đơn vị nên tính chẵn lẻ của tổng số bi trong mỗi màu không đổi. Do đó không có trạng thái mà trên bảng còn lại đúng một quân cờ. 1 2 3 1 2 3 2 3 1 2 3 1 3 1 2 3 1 1 2 3 1 2 3 1 3 1 1 1 7. Xét bảng ô vuông n×n ( n là số nguyên dương lớn hơn 4) và xóa bỏ 4 ô vuông đơn vị ở bốn góc của bảng. Tìm tất cả các giá trị có thể có của n sao cho bảng trên được lát bởi các quân hình chữ L như hình dưới đây (cùng với các hình tạo bởi bằng cách quay đi một góc tùy ý) 7 Lời giải. Giả sử bảng n×n và xóa bỏ đi bốn ô vuông đơn vị ở bốn góc của bảng được lát bởi các quân hình chữ L và giả sử cần a quân hình chữ L . Khi đó ta có: n2 −4 = 4a Từ đẳng thức này ta suy ra n phải là số chẵn. Khi đó ta tô màu bảng n×n như hình vẽ dưới đây: Khi đó mỗi quân hình chữ L sẽ phủ 1 ô đen và 3 ô trắng hoặc 1 ô trắng và 3 ô đen. Giả sử trong a quân hình chữ L có u quân gồm 3 ô đen và 1 ô trắng, v quân gồm 1 ô đen và 3 ô trắng. Khi đó ta có: u + v = a u = v ⇔  3u + v = 3v + u a = 2u Suy ra a  2  n 2 − 4  8  n ≡ 2 ( mod 4 ) . Với n ≡ 2 ( mod 4 ) ta có thể chỉ ra cách lát theo cách giống như bài 4. 8. Một bảng 7×7 được phủ kín bởi 16 quân 3×1 và 1 quân 1×1. Hỏi quân 1×1 phải được đặt ở vị trí nào? Lời giải. Đầu tiên ta dự đoán vị trí của quân 1×1 ta được vị trí tại bốn góc của bảng, tâm của bảng và tại trung điểm của dòng 1, 7 và các cột 1, 7 . Ta sẽ chỉ ra 3 cách giải cho bài toán này. Cách 1. Ta tô màu mỗi ô vuông đơn vị bằng 1 trong 3 màu 0,1,2 như hình A dưới đây: 8 0 1 1 0 1 1 0 1 2 2 1 2 2 1 1 2 2 1 2 2 1 0 1 1 0 1 1 0 1 2 2 1 2 2 1 1 2 2 1 2 2 1 0 1 1 0 1 1 0 Hình A Nếu quân 1×1 không được phủ bởi màu 0 thì ô chứa màu 0 phải được phủ bởi quân 3×1. Do mỗi quân 3×1 gồm hai loại: loại 1 là quân chứa một ô màu 0 và hai ô màu 1, loại 2 là quân chứa 1 ô màu 1 và hai ô màu 2. Do có tất cả 9 ô có màu 0 nên có 9 quân 3×1 loại 1 và 7 quân 3×1 loại 2. Do đó 16 quân 3×1 sẽ phủ được 9×2 + 7 = 25 ô vuông có màu 1 và 7×2 =14 ô vuông có màu 2. Với cách tô màu bảng như trên thì có 16 ô vuông được tô màu 2 và 24 ô vuông có màu 1 vô lí. Vậy quân 1×1 phải được đặt ở ô vuông tô màu 0. Ta nêu ra cách phủ trong các trường hợp đặt quân 1×1 như sau: Đặt quân 1×1 vào ô tô màu đen. Khi đó ta phủ các quân 3×1 như hình B dưới đây: Hình B Các trường hợp đặt quân 1×1 được làm tương tự. Cách 2. Đầu tiên ta tô màu mỗi ô vuông đơn vị bằng 1 trong 3 màu 0,1,2 như hình C dưới đây: 9 0 1 2 0 1 2 0 2 0 1 2 0 1 2 1 2 0 1 2 0 1 0 1 2 0 1 2 0 2 0 1 2 0 1 2 1 2 0 1 2 0 1 0 1 2 0 1 2 0 Hình C Theo cách tô màu này thì có 17 ô vuông đơn vị được tô màu 0, 16 ô vuông đơn vị được tô màu 1 và 16 ô vuông đơn vị được tô màu 2. Mặt khác mỗi quân 3×1 sẽ chiếm 3 ô vuông đơn vị có màu 0,1,2 suy ra quân 1×1 phải được đặt ở ô vuông đơn vị có màu 0. Tiếp theo ta tô màu mỗi ô vuông đơn vị bằng 1 trong 3 màu 0,1,2 theo hình D dưới đây 0 2 1 0 1 2 0 2 1 0 1 2 0 1 1 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 Hình D Theo cách tô màu này thì có 17 ô vuông đơn vị được tô màu 0, 16 ô vuông đơn vị được tô màu 1 và 16 ô vuông đơn vị được tô màu 2. Mặt khác mỗi quân 3×1 sẽ chiếm 3 ô vuông đơn vị có màu 0,1,2 suy ra quân 1×1 phải được đặt ở ô vuông đơn vị có màu 0. Do đó để quân 1×1 giữ nguyên vị trí theo hai cách tô hình C và hình D thì nó phải nằm ở ô vuông đơn vị có màu 0 tại tâm của bảng, tại 4 góc của bảng và tại trung điểm mỗi cạnh của bảng. Tương tự như cách 1 ta sẽ phủ được bảng khi đặt quân 1×1 vào các vị trí đó. 10