Phương pháp vết dầu loang và bài toán tô màu là hai kỹ thuật đếm quen thuộc trong Toán 10 Chương VIII. Đại số tổ hợp (sách Kết nối tri thức), thường gặp trong đề thi tốt nghiệp THPT và đánh giá năng lực ở các câu trả lời ngắn về đếm số đường đi, số cách tô màu. Tất cả bài tập đều có lời giải chi tiết ngay dưới đề.
Nguồn đề: Tài liệu Chuỗi live làm chủ xác suất – Buổi 4.2 (Vết dầu loang, tô màu) của thầy Đỗ Văn Đức, tenschool.vn.
Lời giải: Nguyễn Ngọc Sơn.
A. Đường đi trên lưới, phương pháp vết dầu loang
Ý tưởng của phương pháp
Trên lưới ô vuông đầy đủ, mỗi đường đi từ điểm $(0;0)$ đến điểm $(m;n)$ chỉ gồm các bước sang phải và đi lên là một dãy gồm $m$ bước sang phải và $n$ bước đi lên. Chọn vị trí cho $m$ bước sang phải trong $m+n$ bước, ta được $C_{m+n}^m$ đường đi.
Khi lưới có điểm bị cấm, cạnh bị cấm hoặc có thêm đường chéo thì công thức trên không dùng được nữa. Lúc đó ta dùng phương pháp vết dầu loang.
• Cách ghi số
+ Ghi số 1 tại điểm xuất phát.
+ Mỗi đường đi đến điểm P có bước cuối cùng xuất phát từ đúng một điểm đi một bước tới được P. Vì vậy số đường đi đến P bằng tổng các số đã ghi tại những điểm đó.
+ Ghi số lan dần từ điểm xuất phát ra xa, giống như vết dầu loang. Điểm bị cấm ghi số 0; cạnh bị cấm thì không cộng qua cạnh đó.
• Đếm số cách đi đúng k bước
Khi đường đi có thể quay lại điểm cũ (như kiến bò trên các cạnh của một hình), ta ghi số theo từng bước: số cách có mặt tại P sau bước thứ $t+1$ bằng tổng số cách có mặt sau bước thứ $t$ tại các vị trí đi một bước tới được P.
• Được đi ngang cả hai chiều
Nếu được đi ngang sang trái lẫn sang phải nhưng không qua điểm nào hai lần, thì trên mỗi hàng đường đi chỉ đi thẳng theo một chiều. Khi đó ta đếm theo từng hàng.
Ví dụ 3.1. Các chữ cái được xếp như hình bên; hai chữ cái ở hai hàng liên tiếp gọi là kề nhau nếu được nối bằng một đoạn thẳng. Bắt đầu từ chữ T ở hàng trên cùng, mỗi bước đi xuống một chữ cái ở hàng ngay dưới và kề với chữ cái đang đứng. Có bao nhiêu cách đi để đọc được chữ TOANHOC?
Lời giải
Ghi số 1 tại chữ T. Mỗi chữ cái ở hàng dưới được ghi tổng các số ở những chữ cái kề nó ở hàng ngay trên. Lần lượt từng hàng ta được
+ hàng O ghi 1, 1; hàng A ghi 1, 2, 1;
+ hàng N ghi $1+2=3$ và $2+1=3;$
+ hàng H ghi 3, $3+3=6,$ 3; hàng O ghi $3+6=9$ và $6+3=9;$
+ chữ C ghi $9+9=18.$
Vậy có 18 cách đọc được chữ TOANHOC.
Ví dụ 3.2. Cho lưới ô vuông $3\times3,$ trong mỗi ô vuông có thêm đường chéo nối góc dưới bên trái với góc trên bên phải như hình bên. Một con kiến đi từ A đến B dọc theo các đoạn thẳng của hình, mỗi bước sang phải một cạnh, đi lên một cạnh hoặc đi theo một đường chéo lên phía trên bên phải. Có bao nhiêu cách đi?
Lời giải
Mỗi điểm có thể được đến từ ba điểm: điểm bên trái, điểm bên dưới và điểm chéo dưới bên trái. Ghi số 1 tại A, số tại mỗi điểm bằng tổng ba số đó (điểm nào không có thì bỏ qua).
Chẳng hạn điểm $(1;1)$ ghi $1+1+1=3,$ điểm $(2;1)$ ghi $3+1+1=5.$ Số ghi tại B là $25+25+13=63.$
Vậy có 63 cách đi.
Ví dụ 3.3. Một con kiến bò trên các cạnh của hình chóp tứ giác S.ABCD (hình bên), xuất phát từ đỉnh A; mỗi bước, kiến bò dọc theo một cạnh của hình chóp sang một đỉnh khác. Có bao nhiêu cách bò 4 bước để kiến trở về đỉnh A? (Hai cách bò khác nhau nếu dãy các đỉnh kiến lần lượt đi qua khác nhau).
Lời giải
Các đỉnh kề nhau theo các cạnh của hình chóp là
+ A kề B, D, S; C kề B, D, S;
+ B kề A, C, S; D kề A, C, S;
+ S kề cả bốn đỉnh A, B, C, D.
Ghi số cách kiến có mặt tại mỗi đỉnh sau từng bước. Số ở một đỉnh sau bước tiếp theo bằng tổng các số ở những đỉnh kề nó sau bước trước.
| Bước | A | B | C | D | S |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 2 | 3 | 1 | 3 | 1 | 2 |
| 3 | 4 | 8 | 4 | 8 | 8 |
| 4 | 24 | 16 | 24 | 16 | 24 |
Chẳng hạn sau bước 3, số ở B là $3+3+2=8$ (tổng các số ở A, C, S sau bước 2). Sau bước 4, số ở A là $8+8+8=24.$
Vậy có 24 cách bò.
Ví dụ 3.4. Một khu phố có các con đường tạo thành lưới ô vuông gồm 5 cột và 3 hàng như hình bên, trong đó hai đoạn đường tô màu hồng nét đứt đang sửa chữa nên không đi qua được. Bạn An đi từ A đến B dọc theo các con đường, mỗi bước sang phải hoặc đi lên một cạnh. Có bao nhiêu cách đi?
Lời giải
Đặt A tại gốc $(0;0),$ khi đó $B(5;3),$ hai đoạn bị cấm là đoạn nối $(1;1)$ với $(2;1)$ và đoạn nối $(3;1)$ với $(3;2).$
Ghi số 1 tại A, số tại mỗi điểm bằng tổng số ở điểm bên trái và điểm bên dưới, không cộng qua đoạn bị cấm.
Chẳng hạn điểm $(2;1)$ chỉ nhận số từ điểm bên dưới nên ghi 1; điểm $(3;2)$ chỉ nhận số từ điểm bên trái nên ghi 4. Số ghi tại B là $19+11=30.$
Vậy có 30 cách đi.
Ví dụ 3.5. Cho lưới ô vuông gồm 7 cột và 4 hàng như hình bên; đặt hệ trục sao cho $A(0;0),$ $B(7;4),$ mỗi cạnh ô vuông dài 1. Một robot đi từ A đến B dọc theo các cạnh, mỗi bước sang phải hoặc đi lên một cạnh, và không đi qua ba điểm đánh dấu $(1;1),$ $(2;2),$ $(3;3).$ Có bao nhiêu cách đi?
Lời giải
Ghi số 1 tại A, ghi số 0 tại ba điểm bị cấm, số tại mỗi điểm còn lại bằng tổng số ở điểm bên trái và điểm bên dưới.
Số ghi tại B là $52+48=100.$
Vậy có 100 cách đi.
Ví dụ 3.6. Quân xe được đặt tại ô góc dưới bên trái của một bàn cờ $4\times4.$ Mỗi nước đi, quân xe sang phải hoặc đi lên một số ô tùy ý (ít nhất một ô) và không ra khỏi bàn cờ. Có bao nhiêu cách đi để quân xe đến ô góc trên bên phải? (Hai cách đi khác nhau nếu dãy các ô quân xe dừng lại khác nhau.)
Lời giải
Ở nước cuối cùng, quân xe đến một ô từ một ô bất kỳ bên trái cùng hàng hoặc một ô bất kỳ bên dưới cùng cột. Vì vậy ghi số 1 tại ô xuất phát, số tại mỗi ô bằng tổng tất cả các số ở các ô bên trái cùng hàng và các ô bên dưới cùng cột.
Chẳng hạn ô thứ hai của hàng dưới cùng ghi 1, ô thứ ba ghi $1+1=2,$ ô thứ tư ghi $1+1+2=4.$ Ô góc trên bên phải ghi $(4+12+37)+(4+12+37)=106.$
Vậy có 106 cách đi.
Ví dụ 3.7. Cho lưới ô vuông gồm 4 cột và 3 hàng như hình bên. Một con kiến đi từ A đến B dọc theo các cạnh của lưới, mỗi bước sang trái, sang phải hoặc xuống dưới một cạnh, và không đi qua điểm nút nào quá một lần (điểm nút là đỉnh của các ô vuông). Có bao nhiêu cách đi?
Lời giải
Lưới có 4 đường ngang, mỗi đường có 5 điểm nút. Kiến không đi qua điểm nút nào hai lần nên trên mỗi đường ngang, kiến chỉ đi thẳng theo một chiều rồi đi xuống.
+ Trên đường ngang trên cùng, kiến xuất phát từ A và đi xuống tại một trong 5 điểm nút, có 5 cách.
+ Tương tự, trên đường ngang thứ hai và thứ ba, mỗi đường kiến có 5 cách chọn điểm nút để đi xuống.
+ Trên đường ngang dưới cùng, kiến chỉ có một cách đi thẳng đến B.
Theo quy tắc nhân, số cách đi là $5\cdot5\cdot5=125.$
Vậy có 125 cách đi.
Ví dụ 3.8. Có 8 người đôi một khác nhau xếp hàng mua vé xem phim, giá mỗi vé là 50 nghìn đồng. Trong 8 người có 4 người chỉ mang một tờ tiền 50 nghìn đồng và 4 người chỉ mang một tờ tiền 100 nghìn đồng. Lúc mở bán, quầy vé không có tiền. Có bao nhiêu cách xếp 8 người thành một hàng sao cho khi đến lượt, người nào cũng mua được vé và được trả lại tiền thừa (nếu có) ngay?
Lời giải
Hướng giải
Mỗi người mang tờ 50 nghìn ứng với một bước sang phải, mỗi người mang tờ 100 nghìn ứng với một bước đi lên, rồi đếm số đường đi không vượt lên trên đường chéo.
• Đưa về đường đi trên lưới
Trước hết chỉ quan tâm thứ tự loại tiền của 8 người. Mỗi người mang tờ 50 nghìn ứng với một bước sang phải, mỗi người mang tờ 100 nghìn ứng với một bước đi lên. Một thứ tự xếp hàng ứng với một đường đi từ $O(0;0)$ đến $E(4;4).$
Người mang tờ 100 nghìn cần được trả lại 50 nghìn, nên tại mọi thời điểm số người mang tờ 50 nghìn đã mua vé không ít hơn số người mang tờ 100 nghìn. Điều đó có nghĩa là đường đi không bao giờ vượt lên trên đường chéo $y=x.$
• Đếm bằng vết dầu loang
Chỉ ghi số tại các điểm nằm trên hoặc dưới đường chéo.
Số ghi tại E là 14, tức là có 14 thứ tự của các loại tiền.
• Kể đến thứ tự từng người
Với mỗi thứ tự loại tiền, có $4!$ cách xếp 4 người mang tờ 50 nghìn và $4!$ cách xếp 4 người mang tờ 100 nghìn vào các vị trí tương ứng. Số cách xếp hàng là
\[14\cdot4!\cdot4!=14\cdot24\cdot24=8064.\]Vậy có 8064 cách xếp.
B. Bài toán tô màu
Cách đếm số cách tô màu
Tô lần lượt từng phần, nên bắt đầu từ phần kề với nhiều phần khác nhất. Khi có $k$ màu, số cách tô một phần bằng $k$ trừ đi số màu khác nhau đã dùng ở các phần kề với nó. Nếu số màu này còn phụ thuộc vào việc hai phần không kề nhau cùng màu hay khác màu, ta chia thành hai trường hợp.
Hai kết quả hay dùng (với $k$ màu, hai ô kề nhau phải khác màu):
+ Tô một hàng gồm $n$ ô có $k(k-1)^{n-1}$ cách (ô đầu có $k$ cách, mỗi ô sau có $k-1$ cách).
+ Tô một vòng gồm $n$ ô $(n\ge3)$ có $c_n=(k-1)^n+(-1)^n(k-1)$ cách.
Ví dụ 4.1. Một tấm biển hình chữ nhật được chia thành bốn miền A, B, C, D như hình bên. Tô mỗi miền một màu, các màu lấy từ 4 màu khác nhau, sao cho hai miền có chung một đoạn biên thì khác màu. Có bao nhiêu cách tô?
Lời giải
Miền D kề cả ba miền còn lại và miền B kề A, C, D, nên tô hai miền này trước.
+ Tô D có 4 cách, tô B (khác D) có 3 cách.
+ Tô A (khác B và D) có 2 cách, tô C (khác B và D) có 2 cách.
Số cách tô là $4\cdot3\cdot2\cdot2=48.$
Vậy có 48 cách tô.
Ví dụ 4.2. Tô màu 5 ô vuông xếp thành một hàng ngang, mỗi ô một màu, các màu lấy từ ba màu xanh, đỏ, vàng, sao cho hai ô kề nhau khác màu và có đủ cả ba màu. Có bao nhiêu cách tô?
Lời giải
+ Số cách tô sao cho hai ô kề nhau khác màu (chưa cần đủ ba màu) là $3\cdot2^4=48.$
+ Trong đó, các cách chỉ dùng đúng hai màu là: chọn 2 trong 3 màu có 3 cách, với hai màu đã chọn thì hàng phải tô xen kẽ và có 2 cách (ô đầu tô màu nào). Có $3\cdot2=6$ cách.
Số cách tô có đủ cả ba màu là $48-6=42.$
Vậy có 42 cách tô.
Ví dụ 4.3. Trong một cuộc thi, có 7 thí sinh đã được xếp ngồi cố định quanh một bàn tròn và giám thị có 3 mã đề khác nhau (mỗi mã đề có đủ số đề cần dùng). Hỏi có bao nhiêu cách phát đề thi cho các thí sinh, mỗi thí sinh 1 đề, sao cho hai thí sinh ngồi cạnh nhau thì khác mã đề?
Lời giải
Xem 7 thí sinh là một vòng gồm 7 ô và 3 mã đề là 3 màu. Áp dụng công thức tô vòng với $n=7,$ $k=3$ ta được
\[\begin{aligned}c_7&=(3-1)^7+(-1)^7(3-1)\\&=128-2=126.\end{aligned}\]Vậy có 126 cách phát đề.
Ví dụ 4.4. Tô màu một hình tròn được chia thành 5 phần O, A, B, C, D như hình bên, mỗi phần một màu, các màu lấy từ 6 màu khác nhau, sao cho hai phần có đường biên chung (đoạn thẳng hoặc cung tròn) thì không cùng màu. Chẳng hạn, O và A có chung một cung, C và D có chung một đoạn thẳng, còn A và C không có đường biên chung. Có bao nhiêu cách tô màu?
Lời giải
+ Phần O kề cả bốn phần còn lại, tô trước có 6 cách.
+ Bốn phần A, B, C, D phải khác màu O, nên chỉ dùng 5 màu còn lại, và chúng tạo thành một vòng 4 ô. Theo công thức tô vòng với $n=4,$ $k=5,$ số cách tô là $c_4=4^4+4=260.$
Số cách tô là $6\cdot260=1560.$
Vậy có 1560 cách tô màu.
Ví dụ 4.5. Một lối đi được lát bằng 8 viên gạch vuông xếp thành 2 hàng, 4 cột. Gạch có bốn màu trắng, xám, xanh, nâu; các viên gạch cùng màu giống hệt nhau và mỗi màu có đủ số gạch cần dùng. Có bao nhiêu cách lát sao cho hai viên gạch có chung cạnh thì khác màu?
Lời giải
Lát lần lượt từng cột, mỗi cột gồm viên trên và viên dưới.
+ Cột thứ nhất: viên trên có 4 cách, viên dưới (khác viên trên) có 3 cách, tức là $4\cdot3=12$ cách.
+ Mỗi cột tiếp theo: giả sử cột trước có viên trên màu $a,$ viên dưới màu $b$ $(a\ne b).$ Viên trên của cột mới khác $a,$ có 3 cách. Nếu viên trên chọn màu $b$ thì viên dưới chỉ cần khác $b,$ có 3 cách; nếu viên trên chọn một trong 2 màu khác $a$ và $b$ thì viên dưới phải khác $b$ và khác màu viên trên, có 2 cách. Mỗi cột mới có $3+2\cdot2=7$ cách.
Số cách lát là $12\cdot7^3=4116.$
Vậy có 4116 cách lát.
Ví dụ 4.6. Cho hình lăng trụ tam giác ABC.A′B′C′. Tô màu sáu đỉnh của hình lăng trụ, mỗi đỉnh một màu, các màu lấy từ 4 màu khác nhau, sao cho hai đầu mút của mỗi cạnh của hình lăng trụ có màu khác nhau. Có bao nhiêu cách tô?
Lời giải
• Tô ba đỉnh A, B, C
Ba đỉnh A, B, C đôi một kề nhau nên có $4\cdot3\cdot2=24$ cách tô. Giả sử A, B, C lần lượt có màu 1, 2, 3 và màu 4 chưa dùng.
• Tô ba đỉnh A′, B′, C′
Ba đỉnh này đôi một khác màu, đồng thời A′ khác màu 1, B′ khác màu 2, C′ khác màu 3.
+ Nếu không dùng màu 4 thì A′, B′, C′ dùng đủ ba màu 1, 2, 3 và không đỉnh nào giữ màu của đỉnh bên dưới. Có 2 cách là $(2;3;1)$ và $(3;1;2).$
+ Nếu dùng màu 4 thì có 3 cách chọn đỉnh tô màu 4. Chẳng hạn A′ màu 4, khi đó $(B';C')$ là một trong các cặp $(1;2),$ $(3;1),$ $(3;2),$ có 3 cách. Trường hợp này có $3\cdot3=9$ cách.
Như vậy có $2+9=11$ cách tô ba đỉnh A′, B′, C′. Số cách tô là $24\cdot11=264.$
Vậy có 264 cách tô.
Ví dụ 4.7. Một hình lập phương được đặt cố định. Tô màu 6 mặt của hình lập phương, mỗi mặt một màu, các màu lấy từ 4 màu khác nhau, sao cho hai mặt có chung một cạnh thì khác màu. Có bao nhiêu cách tô? (Hai cách tô khác nhau nếu có ít nhất một mặt được tô màu khác nhau.)
Lời giải
Hình lập phương có 3 cặp mặt đối diện. Hai mặt không đối diện thì luôn có chung một cạnh, nên hai mặt thuộc hai cặp khác nhau phải khác màu; chỉ hai mặt đối diện mới được cùng màu.
Nếu có hai cặp mà mỗi cặp dùng hai màu khác nhau thì cần ít nhất $2+2+1=5$ màu, không đủ. Do đó có hai trường hợp.
+ Cả 3 cặp, mỗi cặp tô cùng một màu: ba cặp có ba màu khác nhau, có $4\cdot3\cdot2=24$ cách.
+ Có đúng một cặp tô hai màu khác nhau: chọn cặp đó có 3 cách; hai cặp còn lại mỗi cặp một màu, và hai mặt của cặp được chọn tô hai màu khác, dùng đủ 4 màu, có $4!=24$ cách. Trường hợp này có $3\cdot24=72$ cách.
Số cách tô là $24+72=96.$
Vậy có 96 cách tô.
Ví dụ 4.8. Hình bên gồm một hình chữ nhật và ba đường tròn nằm trong nó, chia hình chữ nhật thành 8 miền. Tô mỗi miền một màu, các màu lấy từ 3 màu khác nhau, sao cho hai miền có chung một cung biên thì khác màu (hai miền chỉ chung nhau một điểm thì không bị ràng buộc). Có bao nhiêu cách tô?
Lời giải
Hướng giải
Tô miền giữa G trước, rồi chia trường hợp theo màu của ba miền chung của hai đường tròn (cùng màu hay không).
Đặt tên các miền như hình dưới: M là miền ngoài ba đường tròn; A, B, C là các miền chỉ thuộc một đường tròn; D, E, F là các miền chung của đúng hai đường tròn; G là miền chung của cả ba đường tròn.
Các cặp miền có chung cung biên là
+ M với A, B, C; G với D, E, F;
+ A với E, F; B với D, F; C với D, E.
Tô G trước, có 3 cách, gọi màu của G là $g.$ Ba miền D, E, F khác màu $g$ nên chỉ dùng hai màu còn lại, gọi là $p$ và $q.$
• Trường hợp D, E, F cùng màu
Có 2 cách chọn màu chung đó, giả sử là $p.$ Khi đó mỗi miền A, B, C có màu $g$ hoặc $q,$ còn M khác màu cả ba miền này.
+ Nếu A, B, C cùng màu (2 cách) thì M có 2 cách.
+ Nếu A, B, C dùng cả $g$ và $q$ $(2^3-2=6$ cách) thì M phải màu $p,$ có 1 cách.
Trường hợp này có $2\cdot(2\cdot2+6)=20$ cách.
• Trường hợp D, E, F không cùng màu
Có $2^3-2=6$ cách tô D, E, F, khi đó hai miền cùng một màu và miền còn lại màu kia. Chẳng hạn D, E màu $p,$ F màu $q.$
+ A kề E, F (màu $p,$ $q$) nên A màu $g;$ tương tự B kề D, F nên B màu $g.$
+ C kề D, E (cùng màu $p$) nên C màu $g$ hoặc $q.$ Nếu C màu $g$ thì M có 2 cách; nếu C màu $q$ thì M phải màu $p,$ có 1 cách.
Mỗi cách tô D, E, F cho $2+1=3$ cách, trường hợp này có $6\cdot3=18$ cách.
Số cách tô là $3\cdot(20+18)=114.$
Vậy có 114 cách tô.
