سوال ۲۸
۸۲ کارت به ترتیب بر روی هم قرار دارند. برروی این کارت‌ها اعداد دل‌خواه ولی متمایزی نوشته شده‌اند. یک نفر دنباله‌ای از دستورهای $(i,j)$ را به ترتیب بر روی این کارت‌ها اجرا می‌کند. دستور $(i,j)$ یعنی این که اگر عدد نوشته شده بر روی کارت $i$ام (از بالا) از عدد نوشته شده بر روی کارت $j$ام بیش‌تر باشد٬ این دو کارت جا‌به‌جا شوند.
توجه کنید که این کار تغییری در ترتیب کارت‌های دیگر ایجاد نمی‌کند. دستورهای زیر را یک بار از ابتدا تا انتها به ترتیب بر روی کارت‌های ورودی اجرا کنیم. کدام‌یک از گزینه‌های زیر بهترین جواب برای وضعیت نهایی کارت‌هاست؟
- کارت‌ها بر حسب عددشان از بالا به پایین به صورت صعودی مرتب می‌شوند.
- کارت با بزرگ‌ترین عدد٬ پایین‌ترین کارت خواهد شد.
- کارت با بزرگ‌ترین عدد در پایین و کارت با دومین بزرگ‌ترین عدد درست بالای آن خواهد بود.
- کارت با کوچک‌ترین عدد اولین کارت خواهد شد.
- کارت با کوچک‌ترین عدد اولین کارت و کارت با دومین کوچک‌ترین عدد کارت دوم خواهد بود.
پاسخ
گزینه (؟) درست است.
اعداد موجود در کارت $i$ام را $a_i$ می‌نامیم. بعد از دستور اول نابرابری $a_1 < a_2$ برقرار است. بقیه دستورها را از بالا به پایین دوبه‌دو یک زوج می‌نامیم. زوج $k$ام به شکل $[(k+1,k+2),(k,k+1)]$ خواهد بود. بنابراین ۸۰ زوج به‌دست می‌آید که برایند آن عملکرد زوج $k$ام آن است که اعداد موجود در سه کارت $k+1,k$ و $k+2$ به صورت صعودی مرتب می‌شود. معلوم است که اعداد بزرگ به سمت پایین منتقل می‌شوند ولی اعداد موجود در آن کارت‌ها حداکثر دو پله به سمت بالا منتقل شود٬ بنابراین اگر کوچک‌ترین عدد در کارت ۴ و یا پایین‌تر باشد هرگز آن عدد به کارت ۱ منتقل نخواهد شد ولی بزرگ‌ترین عدد به پایین‌ترین کارت و دومین عدد بزرگ به دومین کارت از پایین منتقل خواهند شد.