سعی کنید سوالات را با کمترین راهنمایی حل کنید.

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

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

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

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

نمونه اجرای الگوریتم

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

راهنمایی

استقرا!

راهنمایی

سعی کنید به نحوی یک قله و یک دره ی کنار هم را حذف کنید.

راهنمایی

به کوچکترین قله فکر کنید.