Đáp án bài toán 'xếp người thành hàng dọc'

Đề bài:

Một nhóm người xếp thành một hàng dọc được gọi là xếp theo chuẩn thứ tự nếu điều kiện sau được thỏa mãn: Nếu A đứng bên trái B trong hàng (A, B không nhất thiết kề nhau) thì A cao hơn B không quá 8 cm.

Ví dụ, 5 người có chiều cao là 160, 165, 170, 175, và 180 cm tương ứng có thể xếp theo chuẩn thứ tự (từ trái qua phải) như sau 160, 170, 165, 180, 175 cm.

Hỏi có bao nhiêu cách xếp 10 người có chiều cao tương ứng là 140, 145, 150, 155, 160, 165, 170, 175, 180, và 185 cm theo chuẩn thứ tự?

Ta đưa ra 2 lời giải, 1 lời giải "bình dân" ở mức suy luận và dự đoán trực quan và một lời giải toán học, chặt chẽ in băng rôn gía rẻ hơn.

Lời giải 1:

Ta thấy người cao nhất (185 cm) chỉ có thể đứng ở bên trái của người cao nhì. Do đó người cao nhất chỉ có xếp ở cuối hàng hoặc kế người cuối hàng. Trong trường hợp người cao nhất xếp cuối hàng thì ta standee x lại có 9 người cao 140, 145, …, 180 xếp theo chuẩn thứ tự, ta đưa bài toán về 9 người.

Nếu người cao nhất xếp kế cuối hàng thì người cuối hàng phải là người cao nhì (180 cm). Bỏ đi hai người này, ta thấy 8 người đầu xếp theo chuẩn thứ tự. Cứ như vậy, nếu đi từ dưới lên, ta có 1 người (140 cm) có 1 cách xếp, 2 người (140, 145) có 2 cách xếp, 3 người (140, 145, 150) có 3 cách xếp (là (140, 145, 150), (145, 140, 150) và (140, 150, 145). Với 4 người, ta có 5 cách xếp thu được bằng cách

            a) Thêm người 155 vào cuối 3 cách xếp của 3 người: (140, 145, 150, 155), (145, 140, 150, 155) và (140, 150, 145, 155).

            b) Thêm cặp (155, 150) (theo thứ tự đó) vào cuối 2 cách xếp của 2 người

                        (140, 145, 155, 150), (145, 140, 155, 150)

Cứ như vậy, với 5 người ta có 5 + 3 = 8 cách xếp, 6 người có 8 + 5 = 13 cách xếp … và 10 người có 55 + 34 = 89 cách xếp.

Lời giá chữ x giải 2:

Trần Nam DũngĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM