====== سوال ۳۵======

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

این را نیز می دانیم که ماشین همه‌ی اعداد ۱ تا $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$ به صورت منحصربه‌فرد پیدا می‌شود. به عنوان مثال فرض می‌کنیم مجموع داده‌ها برابر ۱۰۰۰ و مجموع مربع داده‌ها برابر ۳۰۴۷۰ باشد در آن صورت:
<WRAP :en>

$\frac{(n-2)(n-1)}{2} \leq 1000 \leq \frac{(n-2)(n+3)}{2} \Rightarrow n=45  ,  n=46$
</WRAP>

اگر $n=45$ آن‌گاه:

<WRAP :en>
$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$
</WRAP>

در این حالت برای $x$ و $y$ جواب منحصربه‌فرد ۳۰ و ۵۰ به‌دست می‌آید.


و اما اگر $n=46$ آن‌گاه:


<WRAP :en>

$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$
</WRAP>


در این حالت برای $x$ و $y$ جواب‌های صحیحی در محدوده‌ی از ۱ تا ۴۶ به‌دست نمی‌آید. 
</پاسخ>
  * [[سوال ۳۶|سوال بعد]]
  * [[سوال ۳۴|سوال قبل]]