سوال سوم (۱۸ نمره)

تعدادی عدد متمایز دور یک دایره داریم که در ابتدا همه‌ی آن‌ها سفید هستند. یک عدد را دره می‌گوییم، اگر از هر دو عدد مجاورش کوچک‌تر باشد. هم‌چنین یک عدد را قله می‌نامیم، اگر از هر دو عدد مجاورش بزرگ‌تر باشد.

روی اعداد به ترتیب از کوچک به بزرگ، عملیات زیر را انجام می‌دهیم:

• اگر دره است، آن را سیاه می‌کنیم.
• اگر قله است، از این عدد به دو جهت حرکت می‌کنیم تا به اولین دره‌ی سیاه برسیم و از میان این دو دره‌ی سیاه عدد بزرگ‌تر را انتخاب کرده و با قله‌ی مذکور جفت می‌کنیم و دره‌ای که جفت شده را قرمز می‌کنیم. (اگر از دو جهت به یک دره‌ی سیاه یکسان رسیدیم، همان را انتخاب می‌کنیم.)
• در غیر این صورت، کاری انجام نمی‌دهیم.

به این ترتیب، در نهایت دره‌ها و قله‌ها به جفت‌هایی افراز می‌شوند. در شکل زیر، افراز حاصل از اجرای الگوریتم در یک نمونه آمده است.

حال، هر عدد را با قرینه‌اش جایگزین کرده و الگوریتم گفته شده را با اعداد جدید اجرا می‌کنیم. ثابت کنید دو عدد در اجرای دوم الگوریتم جفت می‌شوند، اگر و تنها اگر اعداد متناظرشان (قرینه‌هایشان) در اجرای اول الگوریتم جفت شده باشند.

• سوال قبل
• سوال بعد