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