سوال ۳۵
ماشینی داریم که با فشار دادن دکمه‌ی «نمایش» آن، همه‌ی اعدادی که در خود دارد را یک‌به‌یک و بدون ترتیب خاصی به ما نشان می‌دهد و این کار را اگر بخواهیم تکرار می‌کند، ولی ممکن است همان ترتیب قبلی نباشد. ما فقط یک ماشین‌حساب معمولی (با امکان ضرب، تقسیم، جمع و تفریق و نیز تعداد ۱۰ تا حافظه‌ی کمکی) در دست داریم و اجازه نداریم عددی که ماشین نشان می‌دهد را بر روی برگی یادداشت کنیم یا به خاطر بسپاریم.
این را نیز می دانیم که ماشین همه‌ی اعداد ۱ تا $n$ را نشان می‌دهد، به‌جز دو عدد $x$ و $y$. ما از قبل مقدار $x$٬ $y$ و $n$ را نمی‌دانیم.
با چند بار فشار دادن دکمه‌ی «نمایش»، می‌توانیم مقدارهای $x$ و $y$ را پیدا کنیم. فرض کنید که $n \le 10000$ و ماشین‌حساب تا اعداد $10^{10}$ را می‌تواند در خود ذخیره کند و بر روی آن‌ها عملیات ساده‌ی حسابی گفته شده را انجام دهد.
- ۱
- ۲
- $n-2$
- $n-1$
- $n$
پاسخ
گزینه (۲) درست است.
ابتدا با یک بار فشار دادن دکمه‌ی نمایش٬ اعداد نشان داده شده را وارد ماشین حساب کرده و آن‌ها را با هم جمع می‌کنیم٬ معلوم است که حاصل این جمع برابر $\frac{n(n+1)}{2}-(x+y)$ خواهد بود. از آن‌جا که مقدار $x+y$ حداقل برابر ۳ و حداکثر برابر $2n-1$ می‌باشد. بنابراین حاصل عدد به‌دست آمده بین$\frac{(n-2)(n-1)}{2}$ و $\frac{(n-2)(n+3)}{2}$ خواهد شد. فرض می‌کنیم آن حاصل جمع برابر $\alpha$ باشد. در این صورت در نابرابری $\frac{(n-2)(n-1)}{2} \leq \alpha \leq \frac{(n-2)(n+3)}{2}$ برای $n$ بیش از دو جواب به‌دست نخواهد آمد.
بار دیگر با فشار دادن دکمه نمایش٬ هر یک از اعداد نشان داده شده را به توان ۲ رسانده و با هم جمع می‌کنیم. می‌دانیم مجموع مربع اعداد از ۱ تا $n$ برابر $\frac{n(n+1)(2n+1)}{6}$ می‌باشد٬ بنابراین باتوجه به محدودیت به‌دست آمده برای $n$ در حالت قبلی٬ برای $x^2+y^2$ دو مقدار یافت می‌شود که با تشکیل یک دستگاه دو معادله و دو مجهول٬ مقادیر $x$ و $y$ به صورت منحصربه‌فرد پیدا می‌شود. به عنوان مثال فرض می‌کنیم مجموع داده‌ها برابر ۱۰۰۰ و مجموع مربع داده‌ها برابر ۳۰۴۷۰ باشد در آن صورت:
$\frac{(n-2)(n-1)}{2} \leq 1000 \leq \frac{(n-2)(n+3)}{2} \Rightarrow n=45 , n=46$
اگر $n=45$ آن‌گاه:
$1+2+3+...+45=\frac{45 \times 46}{2}=1035 \Rightarrow x+y=35$
$1^2+2^2+3^2+...+45^2=\frac{45 \times 46 \times 91}{6}=31395 \Rightarrow x^2+y^2=925$
در این حالت برای $x$ و $y$ جواب منحصربه‌فرد ۳۰ و ۵۰ به‌دست می‌آید.
و اما اگر $n=46$ آن‌گاه:
$1+2+3+...+46=\frac{46 \times 47}{2}=1081 \Rightarrow x+y=81$
$1^2+2^2+3^2+...+46^2=\frac{45 \times 47 \times 93}{6}=33511 \Rightarrow x^2+y^2=3041$
در این حالت برای $x$ و $y$ جواب‌های صحیحی در محدوده‌ی از ۱ تا ۴۶ به‌دست نمی‌آید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
