Một cầu thang có 8 bậc. Mai có thể bước lên trên 1, 2 hoặc 3 bậc mỗi lần. Hỏi có bao nhiêu cách để Mai bước hết bậc cầu thang?

Gọi số lần bước lên trên 1; 2; 3 bậc lần lượt là a, b, c (a, b, c ∈ ℕ)

Để Mai bước hết bậc cầu thang thì a + 2b + 3c = 8

Suy ra 3c ≤ 8 nên c ≤ 2 hay c ∈ {0; 1; 2}.

Trường hợp 1: c = 0

Khi đó a + 2b + 3 . 0 = 8 hay a + 2b = 8

Suy ra 2b ≤ 8 nên b ≤ 4

Khi đó b ∈{0; 1; 2; 3; 4}; a ∈{8; 6; 4; 2; 0}

Do đó (a; b; c) ∈{(8; 0; 0), (6; 1; 0), (4 ; 2; 0), (2; 3; 0), (0; 4; 0)}

Trường hợp 2: c = 1

Khi đó a + 2b + 3. 1 = 8 hay a + 2b = 5

Suy ra 2b ≤ 5 nên b ≤ 2.

Khi đó b ∈{0; 1; 2}; a ∈{5; 3; 1}

Do đó (a; b; c) ∈ {(5; 0; 1), (3; 1; 1), (1; 2; 1)}.

Trường hợp 3: c = 2

Khi đó a + 2b + 3⋅2 = 8 hay a + 2b = 2

Suy ra 2b ≤ 2 nên b ≤ 1

Khi đó b ∈{0; 1}; a ∈ {2; 0}

Do đó (a; b; c) ∈ {(2; 0; 2), (0; 1; 2)}.

Từ đó (a; b; c) ∈ {(8; 0; 0); (6; 1; 0); (4; 2; 0); (2; 3; 0); (0; 4; 0); (5; 0; 1); (3; 1; 1); (1; 2; 1); (2; 0; 2); (0;1;2)}.                   (∗)

Với mỗi bộ (a; b; c) ta có số cách bước hết bậc cầu thang là: \(C_8^a + C_{8 - a}^b\) (cách)

Như vậy số lượng cách để Mai bước hết bậc cầu thang tương ứng (∗)(∗) là:

{2; 30; 76; 48; 57; 61; 29; 29; 9}

Số cách để Mai bước hết bậc cầu thang là:

2 + 30 + 76 + 48 + 57 + 61 + 29 + 29 + 9 = 341 (bước).

Vậy có 341 cách để Mai bước hết bậc cầu thang.