فهرست مندرجات
سوالات ۱۴ و ۱۵
فرض کنید در یک کشور، اسکناس‌های $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$ بیشتر از بقیه گزینه‌ها است؟
- ۵
- ۲
- ۴
- ۶
- ۷
پاسخ
گزینه (۱) درست است.
در صورتی که یک سکه مثل $a$ اضافه شود به ازای هر عدد مثل $i$ که قبلا تولید می‌شد می‌توان یک عدد تولید کرد به صورت $a+i$ مگر اینکه این عدد خود قابل تولید توسط اعداد قبلی باشد. هرچه تعداد این اعداد مشترک کمتر باشد اعداد عجیب بیشتری خواهیم داشت. حال به ازای هر $a$ باید ببینیم در چند حالت $i$ و $+a$ هر دو عجیب هستند.
اگر اعداد را در مبنای 3 بنویسیم اعدادی عجیب هستند که تنها از ارقام 0 و 1 تشکیل شده باشند. حال با این ویژگی اگر $a=2$ باشد تنها زمانی $i$ و $i+2$ عجیب هستند که دو رقم سمت راست $i$ برابر 01 باشد. به همین ترتیب برای $a=4$ باید دو رقم آخر $00$، برای $a=5$ باید سه رقم آخر $011$، برای $a=6$ باید سه رقم آخر $011$ یا $010$ و برای $a=7$ $\quad\quad\quad\quad\quad$ باید سه رقم آخر $010$ باشد.
با این توضیحات به ازای $a=5$ و $a=7$ تعداد اعداد بصورت $i$ و $i+a$ که هر دو عجیب باشند کمتر است و در نتیجه در مجموع اعداد عجیب بیشتری تولید می‌کنند. ولی از این میان یکی از اعداد به شکل $i+7$ خارج از محدوده‌ی مسئله (یعنی کمتر مساوی 249) می‌شود که $243+7=250$ است. در نتیجه در مجموع تعداد اعداد عجیب ساخته شده به ازای $a=5$ بیشتر از بقیهی گزینه‌ها است.
سوال ۱۵
فرض کنید گزینه‌های زیر اسکناس‌های ۵ کشور مختلف باشند. کدام گزینه مربوط به یک کشور افسانه‌ای نیست؟
- $1, 2, 4, 8, ...$
- $1!, 2!, 3!, ...$
- $1, 2, 3, 5, 9, ...$ (۱ و ($2^n+1$)ها)
- $1, 4, 9, 16, ...$
- گزینه‌های ۳ و ۴
پاسخ
گزینه (۴) درست است.
در صورتی که در یک کشور هر سکه از مجموع سکه‌های کوچکتر از آن بزرگتر باشد الگوریتم یاد شده درست است (چرا؟). در نتیجه گزینه‌های اول و دوم هر دو افسانه‌ای هستند. برای گزینه‌ی چهارم به ازای $n=18$ الگوریتم بهینه نیست و در نتیجه کشور افسانه‌ای نخواهد بود.
ولی گزینه‌ی سوم هم کشوری افسانه‌ای است. فرض کنید چنین نباشد، در این صورت به ازای $n$ای روش ما تعداد سکه‌ی بیشتری انتخاب می‌کند. فرض کنید در انتخاب بهینه بزرگترین عدد انتخاب نشود. در این صورت باید از یکی از اعداد دیگر چند بار انتخاب شود. ولی می‌دانیم بجای انتخاب دو عدد یکسان، می‌توان سکه‌ی بزرگترش را به همراه عدد 1 انتخاب کرد. در نتیجه با انتخاب بزرگترین عدد نیز می‌توان با همان تعداد سکه به جواب بهینه رسید. پس این گزینه هم کشوری افسانه‌ای است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
