Câu hỏi 133
Có những người lính $n \ge 3$ trong đội của đội trưởng Petrenko và không ai trong số họ có chiều cao giống nhau. Thuyền trưởng đã xếp tất cả vào một bậc duy nhất (không nhất thiết phải sắp xếp theo chiều cao). Chúng tôi gọi là "làn sóng" bất kỳ dãy quân lính nào trong cấp bậc này (họ không được đứng cạnh nhau) sao cho người lính đầu tiên (ngoài cùng bên trái) trong làn sóng cao hơn người lính thứ hai trong đó, nhưng người lính thứ hai trong đó thấp hơn người thứ ba, người này lần lượt cao hơn người thứ tư, v.v. (Ví dụ: nếu $n=9$, các binh sĩ được liệt kê theo thứ tự tăng dần theo chiều cao và đội trưởng sắp xếp chúng thành 9-3-5-7-1-2-6-4-8 thì một trong những đợt dài nhất cho cấp bậc này là 9-3-7-1-6-4-8. Tuy nhiên, nếu đội trưởng sắp xếp chúng thành 1-2-3-4-5-6-7-8-9 thì mỗi đợt dài nhất sẽ chỉ có một người lính, ai có thể là bất kỳ ai.) Với mỗi $n$, hãy xem xét số cấp có thể có các sóng dài nhất có độ dài chẵn và số cấp có thể có các sóng dài nhất có độ dài lẻ. Số nào trong số này lớn hơn?