افراد با شمارههای ۱ تا ۶ به ترتیب دور میز دایرهای شکل و در جهت ساعتگرد نشستهاند و هریک ورقهای دارند که بر روی آن یک عدد نوشته شده است (عدد فرد شمارهي i را A[i] مینامیم). الگوریتم زیر را ۱۳۸۸ مرحله تکرار میکنیم:
۱) هر فرد با شمارهی فرد ورقهاش را با نفر کناریاش (در جهت ساعتگرد) مقایسه میکند. خود عدد کوچکتر و نفر کناریاش عدد بزرگتر را برمیدارد.
۲) هر فرد با شمارهی زوج ورقهاش را با نفر کناریاش (در جهت ساعتگرد) مقایسه میکند. خود عدد کوچکتر و نفر کناریاش عدد بزرگتر را برمیدارد.
اگر A[1..6]=⟨2,4,5,6,8,9⟩ باشد٬ بعد از اجرای ۱ مرحله A[1..6]=⟨9,5,4,8,6,2⟩ خواهد بود. بعد از اجرای ۱۳۸۸ مرحله ورقهای که عدد ۲ روی آن نوشته شده است در دست کدام فرد خواهد بود؟
پاسخ
گزینه (۳) درست است.
میدانیم عدد ۲ کوچکترین عدد در بین اعداد است، در نتیجه همواره عنصر کوچکتر است. بدین ترتیب از مرحلهی اول به بعد همواره در جایگاههای زوج باقی خواهد ماند و همواره دو خانه نسبت به قبل عقبتر خواهد رفت. در مرحلهی اول در خانهی ششم قرار دارد و باتوجه به اینکه ۱۳۸۸ باقیماندهاش بر ۳ برابر با ۲ است در آخرین مرحله در خانهی چهارم قرار میگیرد (هر سه مرحله به جایگاه قبلیش برمیگردد).