Cho sơ đồ một khu hội chợ như hình dưới đây:
Hỏi có bao nhiêu cách đi, bắt đầu từ một cửa hàng (A, B, C, D, E), đi qua tất cả các cửa hàng khác và mỗi cửa hàng chỉ đi một lần?
Chú ý: Mỗi cửa hàng chỉ đi tới được cửa hàng khác nếu có đường nối (Ví dụ: A→B→C→D→E là một cách đi).
Đáp án:
Ta xét trường hợp bắt đầu đi từ điểm A, sau đó ta có thể đi tới C hoặc B hoặc D (B và D tương tự nhau).
+ Nếu đi tới C, ta có 2 cách để đi tiếp là: B.D→E→B.
+ Nếu đi tới B, ta có 4 cách để đi tiếp là:C→D→E;C→E→D;E→C→D;E→D→C.
Tương tự đi tới B cũng có 4 cách.Vậy thì xuất phát từ A có : 2 + 4 + 4 = 10 cách.
Giải thích các bước giải:
Đáp án:
Đây là bài toán suy luận không quá phức tạp, nhưng dễ dẫn đến nhầm lẫn, khiến lời giải bị sai. Vì thế, qua hai tuần nhưng OLM chỉ tìm được 3 bạn có câu trả lời đúng.
Lời giải:
Ta xét trường hợp bắt đầu đi từ điểm A, sau đó ta có thể đi tới C hoặc B hoặc D (B và D tương tự nhau).
+ Nếu đi tới C, ta có 2 cách để đi tiếp là: B→E→D hoặc D→E→B.
+ Nếu đi tới B, ta có 4 cách để đi tiếp là: C→D→E;C→E→D;E→C→D;E→D→C. Tương tự đi tới B cũng có 4 cách.
Vậy thì xuất phát từ A có : 2 + 4 + 4 = 10 cách.Các điểm A, B, D, E có vai trò tương tự nhau nên xuất phát từ mỗi điểm sẽ có 10 cách để đi.Khi xuất phát từ điểm C, ta có thể đi tới A, B, D hoặc E. Tới mỗi điểm này, ta sẽ có 2 cách để đi.
Vậy nên xuất phát từ C có 8 cách đi.Tóm lại, có tất cả: 10 x 4 + 8 = 48 cách đi thỏa mãn yêu cầu đề bài.
Giải thích các bước giải: