المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۱۶:سوال یک

مادربزرگ مهدی و ایلیا

مهدی و ایلیا مهمان مادربزرگشان بودند که او این سوال را مطرح کرد: $n$ عدد مثبت داریم و در هر مرحله می‌توانیم دو عدد از این اعداد را برداریم و به جای آن دو عدد مجموع یا تفاضل‌شان را قرار دهیم (تفاضل دو عدد٬ همیشه نامنفی است) تا فقط یک عدد باقی بماند. می‌خواهیم تنها عدد باقی‌مانده کمینه شود.

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

مادربزرگ به آن‌ها گفت که هیچ‌کدام از این دو روش نمی‌تواند کمینه بودن عدد آخر را تضمین کند. و در ضمن برخلاف روش‌های شما که فقط از تفاضل استفاده می‌کند٬ می‌توان فقط با یک‌ بار استفاده از تفاضل به عدد کمینه رسید.

الف. این که روش مهدی و ایلیا ممکن است به کوچک‌ترین عدد ممکن نرسد را با مثال‌هایی تایید کنید.

ب. ثابت کنید که برای رسیدن به عدد کمینه کافی است تنها یک بار از تفاضل استفاده کرد.


ابزار صفحه