سوال ۱۳

یک جایگشت از ۱، ۲، $\ldots$، $n$ داده شده است ($n \ge 32$). یک زیردنباله از آن تعدادی از عناصر این جایگشت‌اند که لزوماً پشت‌سر هم قرار ندارند. یک زیر دنباله را خوب می‌نامیم، اگر دو خاصیت داشته باشد:

• طولش حداقل به اندازه $\lg n$ باشد.
• اختلاف هر دو نفر متوالی در آن ۱ باشد.
• صعودی باشد. (از چپ به راست اعضای این دنباله به ترتیب صعودی مرتب شده باشند)

ثابت کنید بیشی از نیمی از جای‌گشت‌ها اصلاً زیر دنباله خوب ندارند.