مرحله اول المپیاد ریاضی 1404: سالنی به تعدادی لامپ
مرحله اول المپیاد ریاضی 1404: سالنی به تعدادی لامپ که می‌دانیم حداکثر 40 تا هستند مجهز شده است. برای تنظیم روشنایی این سالن یک دستگاه خودکار و دارای حس‌گر نور قرار داده شده است. این دستگاه صبح‌ها که به تدریج نور بیشتر می‌شود شروع به خاموش کردن برخی از لامپ‌های روشن می‌کند. روش آن بدین صورت است که در هر مرحله اگر n لامپ روشن باشد و d بزرگ‌ترین مقسوم‌علیه n باشد که d < n دستگاه d لامپ را خاموش می‌کند. در این صورت حداکثر چند مرحله تا رسیدن به یک لامپ روشن طول می‌کشد؟
توجه کنید که اگر با n چراغ روشن شروع کنیم و p کوچک‌ترین عدد اولی باشد که n را می‌شمارد و n = p^k در این صورت در مرحله بعد (p-1)k چراغ روشن خواهیم داشت. اگر در مرحله‌ای تعداد زوجی چراغ روشن باشیم، در مرحله بعدی تعدادشان نصف می‌شود. همچنین اگر n = 2k+1 باشد پس از دو مرحله حداکثر k چراغ روشن خواهد بود. بنابراین با شروع از تعداد زوجی چراغ روشن، پس از 5 مرحله حداکثر یک‌چهارم چراغ‌ها روشن خواهد بود و در نتیجه کمتر از 5 چراغ روشن خواهیم داشت. ( اگر با 40 چراغ شروع کنیم بعد از 4 مرحله کمتر از 5 چراغ داریم) و این تعداد نیز حداکثر پس از دو مرحله به 1 می‌رسد. در نتیجه ثابت کردیم اگر تعداد اولیه زوج باشد با حداکثر 7 مرحله کار تمام می‌شود. اگر تعداد چراغ‌های روشن فرد و 3k باشد در مرحله بعد 2k و در مرحله بعد k می‌شود. بنابراین پس از 2 مرحله حداکثر 13 عدد می‌شود که پس از دو مرحله دیگر حداکثر 6 خواهیم بود که همین اعداد بعد از 3 مرحله به 1 عدد می‌رسند. پس مشابه اعداد زوج، برای اعداد مضرب 3 هم ثابت کردیم حداکثر هفت مرحله خواهیم داشت. همچنین اگر 5k چراغ روشن باشد و این تعداد بر 2 و 3 بخش‌پذیر نباشد، در مراحل بعد به ترتیب به 4k، 2k و k تبدیل می‌شود. پس بعد از 5 مرحله، حداکثر 4 تا خواهد بود که با دو مرحله دیگر به پایان می‌رسد. در نتیجه اگر با تعداد فرد و مرکب چراغ روشن، شروع کنیم چون کوچک‌ترین عامل اول آن 3 یا 5 است، پس از حداکثر 7 مرحله کار تمام می‌شود. در مورد اعداد اول نیز برای آن‌هایی که کمتر از 24 هستند چون پس از 6 مرحله کمتر از 3 تا خواهند بود مجدداً ثابت می‌شود 7 مرحله کافی است. تنها اعدادی که بررسی نشده‌اند 29، 31 و 37 هستند که می‌توانیم ببینیم به بیش از 7 مرحله نیاز ندارند. در نتیجه چون 39 به 7 مرحله نیاز دارد جواب 7 خواهد بود.