Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 46

Đáp án: 32.
Ta vẽ thêm các đường nét đứt $ AB,CE,DF $để tạo thành một đồ thị đầy đủ (giữa hai đỉnh bất kỳ luôn có một cạnh nối) như hình vẽ dưới đây.

Số chu trình Hamilton xuất phát từ $ A $ và kết thúc ở $ A $ là: $ 5! $
Ta cần loại bỏ các chu trình chứa ít nhất một cạnh nét đứt.
Gọi biến cố $ M $: “Chu trình chứa $ AB $ hoặc $ BA $”.
Biến cố $ N $: “Chu trình chứa $ CE $ hoặc $ EC $”.
Biến cố $ P $: “Chu trình chứa $ DF $ hoặc $ FD $”.
Trường hợp 1: Chu trình chứa $ AB $ hoặc $ BA $
+ Xếp $ AB $ở đầu chu trình hoặc $ BA $ ở cuối chu trình: $ 2 $ (cách)
+ Xếp 4 đỉnh ở giữa chu trình: $ 4! $ (cách)
$ \Rightarrow n\left ( { M } \right )=2.4!=48 $.
Tương tự $ n\left ( { N } \right )=n\left ( { P } \right )=48 $.
Trường hợp 2: Chu trình chứa hai trong ba cặp (giả sử $ M\cap N $).
+ Xếp $ AB $ở đầu chu trình hoặc $ BA $ ở cuối chu trình: $ 2 $ (cách)
+ Xếp $ CE $ hoặc $ EC $cạnh nhau thành một nhóm: $ 2! $ (cách)
+ Xếp 1 nhóm trên và 2 cạnh ở giữa chu trình: $ 3! $ (cách)
$ \Rightarrow n\left ( { M\cap N } \right )=2.2!.3!=24 $.
Tương tự $ n\left ( { N\cap P } \right )=n\left ( { M\cap P } \right )=24 $.
Trường hợp 2: Chu trình chứa cả ba cặp (tức là $ M\cap N\cap P $).
+ Xếp $ AB $ở đầu chu trình hoặc $ BA $ ở cuối chu trình: $ 2 $ (cách)
+ Xếp $ CE $ hoặc $ EC $cạnh nhau thành một nhóm: $ 2! $ (cách)
+ Xếp $ DF $ hoặc $ FD $cạnh nhau thành một nhóm: $ 2! $ (cách)
+ Xếp 2 nhóm trên ở giữa chu trình: $ 2! $ (cách)
$ \Rightarrow n\left ( { M\cap N\cap P } \right )=2.2!.2!.2!=16 $.
Số chu trình chứa ít nhất một cạnh nét đứt:
$ n\left ( { M\cup N\cup P } \right )=n\left ( { M } \right )+n\left ( { N } \right )+n\left ( { P } \right )-n\left ( { M\cap N } \right )-n\left ( { N\cap P } \right )-n\left ( { M\cap P } \right )+n\left ( { M\cap N\cap P } \right ) $
$ n\left ( { M\cup N\cup P } \right )=3.48-3.24+16=88 $ (cách).
Số chu trình thỏa mãn đề bài là: $ 5!-88=32 $.