فرض کنید در یک کشور، اسکناس‌های $a_1$ تومانی، $a_2$ تومانی و … داریم و بخواهیم مقدار $n$ تومان را پرداخت کنیم (پرداخت یک‌طرفه است یعنی نمی‌توانیم مقداری را بپردازیم و بقیه‌‌ی پول را پس بگیریم). در صورتی که بتوان $n$ تومان را پرداخت کرد، $n$ را عددی خوب می‌گوییم. برای مثال اگر اسکناس‌های $50, 100, 200, 500$ و $1000$ تومانی داشته باشیم، ۲۹۰۰ عددی خوب است؛ اما ۲۹۵۳ عددی خوب نیست. هم‌چنین عددی مانند $n$ را عجیب گوییم، اگر بتوان $n$ تومان را پرداخت کرد؛ طوری که از هر نوع اسکناس حداکثر یک بار استفاده شود. در مثال قبل ۹۰۰ عجیب نیست.

اگر $n$ یک عدد خوب باشد، کمینه‌ی تعداد اسکناس‌ها برای پرداختش را $f(n)$ می‌نامیم. فرض کنید یک نفر الگوریتم زیر را برای پرداخت انتخاب کند:

در هر مرحله بزرگ‌ترین اسکناسی که مقدار آن از $n$ بیش‌تر نیست را انتخاب می‌کنیم. این مبلغ را پرداخت می‌کنیم و برای باقی پول همین روش را ادامه می‌دهیم تا پرداخت به طور کامل انجام شود.

عدد $n$ را زیبا گوییم، اگر تعداد اسکناس‌هایی که با الگوریتم بالا پرداخت می‌کنیم، برابر $f(n)$ شود. به یک کشور، افسانه‌ای گوییم، اگر تمام اعداد طبیعی خوب،‌ زیبا نیز باشند.

فرض کنید در یک کشور، اسکناس‌های $1, 3, 3^2, 3^3, ...$ تومانی داشته باشیم. می‌خواهیم یک نوع اسکناس‌ از بین گزینه‌های زیر به اسکناس‌های‌مان اضافه کنیم. با اضافه کردن کدام گزینه تعداد اعداد عجیب $n$ که $1 \le n \le 249$ بیش‌تر از بقیه گزینه‌ها است؟

1. ۵
2. ۲
3. ۴
4. ۶
5. ۷

فرض کنید گزینه‌های زیر اسکناس‌های ۵ کشور مختلف باشند. کدام گزینه مربوط به یک کشور افسانه‌ای نیست؟

1. $1, 2, 4, 8, ...$
2. $1!, 2!, 3!, ...$
3. $1, 2, 3, 5, 9, ...$ (۱ و ($2^n+1$)ها)
4. $1, 4, 9, 16, ...$
5. گزینه‌های ۳ و ۴

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