Đáp án Bài 18. Các bài toán về đường đi và đồ thị

Câu 1 [1137089]: Có một mạng lưới đường bộ như hình vẽ. Có bao nhiêu con đường ngắn nhất để đi từ điểm A đến điểm B?

Kí hiệu các điểm như hình vẽ.

Note: Con đường ngắn nhất chỉ gồm các bước sang phải hoặc lên trên.
Lộ trình 1:

(sang phải 3 lần + lên trên 4 lần):

cách.

(sang phải 4 lần + lên trên 4 lần):

cách.
Suy ra lộ trình 1 có

con đường thỏa mãn.
Lộ trình 2:

(không qua

(có tính cả qua

Cần sang phải 4 lần và lên trên 4 lần nên có

cách.

có

cách;

có 1 cách nên số con đường ngắn nhất đi

là

(không qua

có

cách.

(sang phải 3 lần + lên trên 4 lần):

cách.
Suy ra lộ trình 2 có

con đường thỏa mãn.
Vậy số con đường thỏa mãn là

Điền đáp án: 3675.

Câu 2 [1137090]: Có một mạng lưới đường đi được kết nối theo các hình vuông cạnh 1 đơn vị như hình vẽ. Số cách đi từ điểm A đến điểm D bằng quãng đường ngắn nhất mà không đi qua điểm B và không đi qua điểm C là bao nhiêu?

Kí hiệu các điểm như hình vẽ. Lộ trình thỏa mãn đi từ

đến

mà không đi qua

và

là

hoặc

(không đi qua

Note: Với con đường ngắn nhất chỉ được di chuyển xuống dưới hoặc sang phải.
+) Lộ trình 1:

1 cách.

(sang phải 2 lần và xuống 1 lần):

cách.

1 cách.

2 cách.
+) Lộ trình 2:

(không đi qua

bằng tổng số cách từ

trừ số cách đi

Tổng số cách

(1 lần sang phải + 4 lần xuống) là

cách.

1 cách.

(không đi qua

bằng

cách.

1 cách.

2 cách.
Vậy tổng số cách đi thỏa mãn là

Điền đáp án: 30.

Câu 3 [1137091]: Hai vật thể A và B di chuyển đồng thời và cùng tốc độ trên mặt phẳng tọa độ với toạ độ nguyên. Vật thể A bắt đầu từ vị trí

và mỗi bước của nó đều hướng sang phải hoặc lên trên với xác suất như nhau. Vật thể B bắt đầu từ vị trí

và mỗi bước của nó đều hướng sang trái hoặc xuống dưới với xác suất như nhau. Biết rằng xác suất hai vật thể gặp nhau bằng

(với

là phân số tối giản và

. Tính

Từ quy tắc di chuyển từ điểm

và

cho thấy con đường hai vật thể A và B đi là đường đi ngắn nhất. Để đi từ

đến

con đường ngắn nhất cần tổng cộng

bước.
Vì hai vật di chuyển cùng tốc độ và đồng thời nên chúng sẽ gặp nhau khi mỗi vật đã đi được đúng 6 bước.
Gọi điểm gặp nhau là

Vì

đã đi 6 bước nên

với

Suy ra tọa độ các điểm

thỏa mãn là

Vì chuyển động của

và

độc lập nên xác suất để hai vật gặp nhau tại

là

Vì mỗi bước di chuyển hai vật đều có 2 cách chọn nên số cách di chuyển của A, B sau 6 bước là

+) Với vật A: Để từ

sau 6 bước, A cần sang phải

bước và lên trên

bước: có

cách.

+) Với vật B: Để từ

đến

sau 6 bước, B cần đi sang trái

bước và xuống dưới

bước: có

cách.

Vậy với mỗi giá trị

của

thì xác suất hai vật thể A, B gặp nhau là

Vậy tổng xác suất cần tìm là

Điền đáp án: 611.

Câu 4 [1137092]: Có một mạng lưới đường hình bàn cờ, trong đó khoảng cách giữa hai điểm iền kề đều bằng 1. Mỗi lần di chuyển, robot sẽ đi được một khoảng cách là 1 dọc theo các con đường. Robot có thể di chuyển theo bất kỳ hướng nào dọc theo các con đường, nhưng không được đi qua cùng một điểm hai lần. Khi robot xuất phát từ điểm

và di chuyển 4 lần, có bao nhiêu lộ trình thoả mãn các điều kiện trên? (Biết rằng điểm xuất phát và điểm kết thúc không được phép trùng nhau.)

Như hình vẽ, khi rô-bốt xuất phát từ

và di chuyển 4 lần, các điểm có thể đến được (xét trong vùng tô đậm) tương ứng với 6 trường hợp đến các điểm

Do tính đối xứng, lấy tổng số trường hợp trong vùng tô đậm rồi nhân 4 sẽ ra đáp án.
(1) Đến

: 1 cách.
(2) Đến

:

(3) Đến

:

(4) Đến

:

(5) Đến

: có 6 cách

(6) Đến

: có 4 cách

Vậy

Câu 5 [1137093]: Trong một bản đồ trò chơi dạng lưới tọa độ nguyên, một nhân vật cần di chuyển từ điểm xuất phát

đến đích

Quy tắc di chuyển cơ bản là chỉ được đi sang phải hoặc đi lên trên theo từng đơn vị lưới. Trên bản đồ có thiết lập 3 cổng dịch chuyển tại các tọa độ:

và

Khi nhân vật di chuyển đến một tọa độ có cổng dịch chuyển, người chơi có hai lựa chọn:
• Tiếp tục di chuyển bình thường (sang phải hoặc lên trên).
• Kích hoạt dịch chuyển tức thời đến một trong hai cổng còn lại.

Sau khi thực hiện một lần dịch chuyển tức thời, hệ thống năng lượng sẽ quá tải khiến tất cả các cổng dịch chuyển biến mất, nhân vật phải hoàn thành phần còn lại của quãng đường bằng cách di chuyển bình thường.
Hỏi có tất cả bao nhiêu lộ trình khác nhau để nhân vật đi từ

đến

TH1: Lộ trình không sử dụng cổng dịch chuyển (Đi bình thường)
Số cách đi từ

đến

(sang phải 6 bước và lên trên 6 bước) là

cách.
TH2: Lộ trình có sử dụng cổng dịch chuyển
Theo quy tắc, người chơi chỉ được dịch chuyển tối đa một lần. Khi đến một cổng

người chơi dịch chuyển sang cổng

sau đó đi tiếp đến

Có 3 cổng dịch chuyển:

Nên các cặp dịch chuyển có thể là:

• Dịch chuyển từ
Lộ trình 1:

có

cách.
Lộ trình 2:

có

cách.
• Dịch chuyển từ
Lộ trình 1:

có

cách.
Lộ trình 2:

có

cách.
• Dịch chuyển từ
Lộ trình 1:

có

cách.
Lộ trình 2:

có

cách.

Tổng số cách có sử dụng dịch chuyển là

Vậy tổng số lộ trình thỏa mãn là

Điền đáp án: 1734.

Câu 6 [1104141]: Một chú kiến đang đứng ở điểm A (góc dưới bên trái) của một mạng lưới đường giao thông hình chữ nhật. Chú kiến muốn đi đến điểm B (góc trên bên phải).
Mạng lưới đường này có kích thước tổng thể là 5 ô ngang và 5 ô dọc. Tuy nhiên, có một khu vực ở trung tâm bị sụt lún hoặc bị chặn, khiến chú kiến không thể đi qua các đường giao thông nằm trong khu vực bị khuyết (như minh họa trong hình vẽ). Hỏi có bao nhiêu con đường đi ngắn nhất và khác nhau để chú kiến có thể đi được đến điểm B

Đính chính: Nhóm tác giả xin gửi lời xin lỗi chân thành đến các em học sinh. Bản in đầu tiên, không tránh khỏi có sai sót. Các em sửa lại đề bài: "6 ô ngang" thành "5 ô ngang" như trên web. Sai sót này sẽ được sửa trong lần tái bản sau. Cảm ơn các em!
Nhận xét: Để đi từ A đến B là ngắn nhất thì con kiến chỉ có thể đi tiến sang phải và tiến lên trên.
Kẻ và kí hiệu các điểm như hình.

Khi đó Số con đường ngắn nhất mà con kiến đi từ A đến B bằng tổng số con đường ngắn nhất ở 4 lộ trình

+)

Giai đoạn 1

cần bước 5 bước gồm tiến lên 3 bước và sang phải 2 bước: có

con đường.
Giai đoạn 2

cần bước 5 bước gồm tiến lên 2 bước và sang phải 3 bước: có

con đường.
Vậy lộ trình này có

con đường ngắn nhất thỏa mãn.
Thực hiện tương tự cho các lộ trình sau.
+)

có

con đường ngắn nhất thỏa mãn.
+)

có 1 con đường ngắn nhất.
+)

có

con đường ngắn nhất thỏa mãn.
Kết hợp các lộ trình trên, số con đường ngắn nhất thỏa mãn là

Điền đáp án: 147.

Câu 7 [695040]: Bắc đi từ nhà (điểm A) đến trường (điểm B). Biết rằng toàn bộ cung đường theo bản đồ từ trên xuống dưới, từ trái qua phải là đường một chiều vì vậy Bắc chỉ được phép đi xuống hoặc đi sang phải. Vậy Bắc có bao nhiêu cách đến trường?

Điền đáp án:

Câu 8 [1134460]: Một con xúc sắc hình lập phương có kích thước

, các mặt được đánh các số tự nhiên từ 1 đến 6, nó di chuyển trên bàn cờ kích thước

gồm các 36 ô vuông đơn vị. Bắt đầu từ ô góc dưới bên trái, con xúc sắc di chuyển bằng cách lăn quanh mặt bên (lăn sang phải hoặc lăn lên trên) cho đến khi đạt tới ô góc trên bên phải. Biết rằng lúc bắt đầu, mặt trên của con xúc sắc được ghi số 1. Hỏi có bao nhiêu lộ trình di chuyển khác nhau sao cho khi kết thúc tại đích, mặt trên của con xúc sắc vẫn ghi số 1?

Câu 9 [1137178]: Trong không gian tọa độ

cho một vùng giới hạn là khối bát diện đều với các mặt bên thoả mãn

Một con kiến xuất phát từ gốc toạ độ và di chuyển theo các hướng song song với các trục toạ độ, mỗi bước di chuyển có độ dài 1 đơn vị và không có lựa chọn dừng lại. Có bao nhiêu lộ trình di chuyển khác nhau để sau đúng 5 lần di chuyển, con kiến có thể đi đến các mặt của khối bát diện?

Vì vị trí ban đầu là

và các mặt thỏa mãn

nên để sau đúng 5 bước con kiến đến được các mặt thì mỗi bước đi đều phải làm tăng tổng trị tuyệt đối của các tọa độ. Điều này đồng nghĩa với việc con kiến không được phép đi lùi (không có hai bước nào ngược hướng nhau triệt tiêu nhau). Tại mỗi bước, kiến chỉ được chọn hướng làm tăng khoảng cách từ gốc tọa độ.
Khối bát diện đều có 8 mặt tương ứng với các tổ hợp dấu của tọa độ

trong không gian. Ta xét trường hợp con kiến đi đến một mặt cụ thể, ví dụ mặt

(nơi

Lựa chọn hướng đi: Để tiến đến mặt

tại mỗi bước di chuyển, con kiến có 3 lựa chọn hướng đi là

Suy ra số lộ trình đi đến 1 mặt: Sau 5 bước di chuyển (mỗi bước có 3 lựa chọn) nên số cách đi là

Do tính đối xứng, 8 mặt của khối bát diện có số lộ trình đi tới là như nhau. Vậy tổng số lộ trình di chuyển khác nhau để con kiến đến được các mặt là

Điền đáp án: 1944.

Câu 10 [1137183]: Một con ếch đang ở gốc tọa độ

Trong ao có 4 tảng đá nằm tại các vị trí:

Con ếch chỉ có thể nhảy qua lại giữa 4 tảng đá này, mỗi bước, con ếch nhảy một quãng đường dài đúng 1 đơn vị để đến một tảng đá khác với quy tắc nhảy như sau: tại mỗi vị trí,
• Con ếch có hai lựa chọn để nhảy.
• Các bước nhảy cùng hướng ra xa gốc toạ độ hoặc cùng hướng về gốc toạ độ có xác suất như nhau.
• Do hướng gió nên với các bước nhảy hướng ra xa gốc toạ độ có xác suất gấp hai lần các bước nhảy hướng về gốc toạ độ.

Gọi

là xác suất để sau 4 lần nhảy con ếch đứng ở tảng đá có toạ độ

Tính giá trị của

Vì “Nhảy ra xa gốc tọa độ có xác suất gấp 2 lần nhảy về gốc tọa độ” nên

(xác suất nhảy ra xa gốc tọa độ) và

(xác suất nhảy hướng về gốc tọa độ).
Tại gốc

cả hai hướng đều là "ra xa" nên xác suất mỗi hướng là

Điều kiện: Sau 4 bước phải đứng tại

Gọi

là số bước theo trục

Vì tổng số bước là 4 nên

Để dừng tại tọa độ lẻ

số bước mỗi trục phải là số lẻ

Vậy

hoặc

Do tính đối xứng, ta tính 1 trường hợp rồi nhân 2.
Xét trường hợp

(1 bước sang Phải) và

(2 bước Lên, 1 bước Xuống):
Ký hiệu các hướng: P (Phải), T (Trái), L (Lên), X (Xuống).
Các lộ trình khả thi để không ra khỏi 4 tảng đá và kết thúc tại

là
Lộ trình 1: P - L - X - L

: ra xa,

: về gốc,

(vì cả 2 hướng từ đây đều là về gốc)

: ra xa,

Lộ trình 2: L - X - L - P

Lộ trình 3: L - P - X - L

Lộ trình 4: L - X - P - L

Tổng xác suất cho TH (

) là

Do tính đối xứng giữa

và

nên xác suất cần tìm là

Điền đáp án: 22,5.

Câu 11 [1134278]: Cho một lưới tam giác có cạnh bằng 4, bao gồm 15 điểm chốt. Bạn Dũng muốn đặt các sợi dây thun bao quanh các điểm chốt của lưới tam giác sao cho mọi cạnh của lưới đều được bao phủ bởi đúng một sợi dây thun và không có sợi dây thun nào đi qua cùng một cạnh hai lần.
Hai cách đặt dây được coi là khác nhau nếu tập hợp các cạnh được bao phủ bởi các sợi dây thun là khác nhau, hoặc nếu có bất kỳ sợi dây thun nào đi qua các cạnh của nó theo một thứ tự khác nhau. Thứ tự đè lên nhau (trên/dưới) của các sợi dây không quan trọng. Gọi N là tổng số cách để bao phủ lưới tam giác trên bằng một số lượng dây thun bất kỳ. Số dư của phép chia N cho 1000 bằng bao nhiêu?

Nhận xét:
+) Mỗi sợi dây thun tạo thành một vòng khép kín (chu trình).
+) Khi một sợi dây thun đi qua một đỉnh, nó phải đi vào bằng một cạnh và đi ra bằng một cạnh khác. Vì vậy, tại mỗi đỉnh, các cạnh kết nối với đỉnh đó phải được bắt cặp với nhau (một cạnh vào, một cạnh ra) để đảm bảo sợi dây không bị đứt đoạn hoặc thừa cạnh.
Note: Trong lý thuyết đồ thị và hình học mạng lưới, bậc của một đỉnh được hiểu đơn giản là số lượng cạnh kết nối trực tiếp với đỉnh đó.
Lưới tam giác cạnh bằng 4 có tổng cộng 15 đỉnh (chốt) với các bậc như sau:
• 3 đỉnh ở góc: Mỗi đỉnh có bậc 2.
• 9 đỉnh nằm trên cạnh (không tính góc): Mỗi đỉnh có bậc 4.
• 3 đỉnh nằm bên trong lưới: Mỗi đỉnh có bậc 6.

Note: Tại mỗi đỉnh bậc

số cách ghép đôi các cạnh để tạo thành lộ trình cho dây thun là

• Đỉnh bậc 2: Có

cách.
• Đỉnh bậc 4: Có

cách.
• Đỉnh bậc 6: Có

cách.
Vì lựa chọn tại mỗi đỉnh là độc lập nên tổng số cách

là tích số cách ghép đôi tại tất cả các đỉnh là

Vậy số dư của phép chia N cho 1000 bằng 125.
Điền đáp án: 125.

Câu 12 [1134288]: Một quốc gia có

thành phố được sắp xếp tại các đỉnh của một hình bát giác đều. Quốc gia này dự định xây dựng

con đường thẳng nối giữa các cặp thành phố sao cho:
• Mọi thành phố đều có thể đi đến tất cả các thành phố khác thông qua một hệ thống đường nhất định (đồ thị liên thông).
• Các con đường không được cắt nhau tại các điểm không phải là thành phố.
• Mỗi thành phố có không quá hai con đường xuất phát từ nó.
Hãy tìm số cách xây dựng hệ thống các con đường thỏa mãn các điều kiện trên?

Minh họa 8 quốc gia tương ứng với 8 đỉnh 1, 2, 3,…,8 của một hình bát giác đều như hình.
Chọn 1 đỉnh xuất phát: 8 cách. Giả sử đỉnh 1.
Tại đỉnh 1: Có 2 cách nối: 1-2 hoặc 1-8. Giả sử nối 1-2.
Tại đỉnh 2: Có 2 cách nối: 2-3 hoặc 2-8.
…
Như vậy, ta thấy với mỗi đỉnh (trong 6 đỉnh nối đầu tiên) có 2 cách chọn. Đỉnh thứ 7 sẽ chỉ có 1 cách chọn (là nối với đỉnh thứ 8 còn lại).
Suy ra tổng số cách nối là

Tuy nhiên, khi thay đổi điểm xuất phát và điểm bắt đầu thì với mỗi một lộ trình bị đếm lặp 1 lần. Ví dụ:

và

Do đó số lộ trình thực sự là

Điền đáp án: 256.

Câu 13 [1134287]: Có mười thị trấn được đánh số từ

đến 10 và mỗi cặp thị trấn đều được nối với nhau bởi một con đường. Định nghĩa một "bước đi lùi" là đi từ thị trấn

đến thị trấn

sao cho

, và một "bước đi tiến" là đi từ thị trấn

đến thị trấn

sao cho

Nam muốn đi từ thị trấn

đến 10 thỏa mãn các điều kiện sau:
• Nam thực hiện đúng một bước đi lùi, các bước còn lại đều là bước đi tiến.
• Thị trấn 10 chỉ được ghé thăm vào lúc kết thúc lộ trình.
Ví dụ về một lộ trình hợp lệ:

Có bao nhiêu lộ trình phù hợp với mong muốn của Nam?

Lộ trình có dạng:

Với
• GĐ1:

(giai đoạn tiến)
• GĐ2:

(giai đoạn lùi, nên

• GĐ3:

(giai đoạn tiến)
Điều kiện:

,

Giai đoạn 1:

Các thị trấn trung gian thuộc tập

(có

phẩn tử).
Mỗi tập con của

cho một cách đi tăng dần tương ứng.
⇒ Số cách chọn là

Giai đoạn 2: bước lùi

Chọn

sao cho

Giai đoạn 3:

Các thị trấn trung gian thuộc

(có

phần tử).
Tương tự giai đoạn 1, có số cách chọn là

Với mỗi giá trị của

, tổng số cách ở GĐ2 và GĐ3 là

Vậy tổng số lộ trình với một giá trị của

là

+)

Số lộ trình là

+)

Số lộ trình là

+)

Số lộ trình là 1792.
+)

Số lộ trình là 3840.
+)

Số lộ trình là 7936.
+)

Số lộ trình là 16128.
+)

Số lộ trình là 32512.
+)

Số lộ trình là 65280.
Vậy tổng số lộ trình là

Điền đáp án: 128512.

Câu 14 [1137184]: Mỗi mặt của một hình bát diện đều được tô ngẫu nhiên bằng một trong hai màu: xanh hoặc đỏ. Một con sâu đang ở một đỉnh của hình bát diện và muốn di chuyển đến đỉnh đối diện bằng cách đi dọc theo các cạnh của hình bát diện đều. Con sâu chỉ có thể di chuyển trên những cạnh là cạnh chung của hai mặt khác màu nhau. Biết rằng xác suất để con sâu di chuyển được đến đích là một phân số tối giản có dạng

Giá trị của

bằng bao nhiêu?

Điền đáp án: 3.
Mỗi mặt có 2 cách tô màu nên số phần tử của không gian mẫu là

Chia khối chóp thành 2 phần, mỗi phần có 4 mặt
B1: Tô màu 4 mặt ở phần 1 có

cách
B2: Tô màu ở phần 2 luôn có 8 cách tô màu ở mỗi trường hợp của P1
Xác suất cần tìm là

Câu 15 [1168816]: Trong một trò chơi thám hiểm, anh Sơn phải vượt qua một mê cung gồm các phòng thông nhau như sơ đồ dưới đây. Tại mỗi phòng, anh Sơn sẽ chọn ngẫu nhiên một trong các cửa thông với phòng hiện tại (với xác suất như nhau) để đi tiếp. Quá trình di chuyển diễn ra liên tục và trò chơi sẽ kết thúc ngay khi anh bước vào phòng chứa Kho báu hoặc phòng có Bẫy. Biết anh Sơn bắt đầu từ Phòng 1, tính xác suất để anh tìm được kho báu. (Kết quả làm tròn đến hàng phần trăm).

Gọi

là xác suất tìm thấy kho báu nếu anh Sơn đang đứng ở phòng

(

).

Yêu cầu bài toán: Tính

Ta có:
Xác suất tìm thấy kho báu khi anh Sơn đứng ở phòng Kho báu là

Xác suất tìm thấy kho báu khi anh Sơn đứng ở phòng Bẫy là

Dựa vào sơ đồ, ta thiết lập hệ phương trình dựa trên các kết nối giữa các phòng:
Phòng 1: Thông với Kho báu, Phòng 2, Phòng 3 (3 cửa với xác suất chọn mỗi cửa bằng nhau và bằng