سوال ۳۵

ماشینی داریم که با فشار دادن دکمه‌ی «نمایش» آن، همه‌ی اعدادی که در خود دارد را یک‌به‌یک و بدون ترتیب خاصی به ما نشان می‌دهد و این کار را اگر بخواهیم تکرار می‌کند، ولی ممکن است همان ترتیب قبلی نباشد. ما فقط یک ماشین‌حساب معمولی (با امکان ضرب، تقسیم، جمع و تفریق و نیز تعداد ۱۰ تا حافظه‌ی کمکی) در دست داریم و اجازه نداریم عددی که ماشین نشان می‌دهد را بر روی برگی یادداشت کنیم یا به خاطر بسپاریم.

این را نیز می دانیم که ماشین همه‌ی اعداد ۱ تا $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$ جواب‌های صحیحی در محدوده‌ی از ۱ تا ۴۶ به‌دست نمی‌آید.

المپدیا

ابزار کاربر

ابزار سایت

سوال ۳۵

ابزار صفحه