Малко задачи от стари конкурси Пътнам

[georgi111]

1. (94 година, задача B1) Да се намерят всички естествени числа $n$, за които неравенството $|n-m^2| \le 250$ е в сила за точно 15 цели неотрицателни числа $m$.
2.(94 година, задача B5) За произволно реално число $\alpha$ с $f_{\alpha}(x)$ е означена функцията $f_{\alpha}(x)$=$\lfloor{{\alpha}x}\rfloor$. Нека $n$ е естествено число. Да се докаже, че съществува такова реално число $\alpha$, че да е в сила равенството:
$f_{\alpha}^k(n^2)=n^2-k=f_{\alpha^k}(n^2)$ за всяко $1 \le k \le n$. (Тук както обикновено с $\lfloor x \rfloor$ означаваме най-голямото цяло число, не надминаващо $x$, a $f_{\alpha}^k = \underbrace{ f_{\alpha}(f_{\alpha}\cdots(f_{\alpha}) \cdots) }_{k}$ е $k$-тата итерация на $f$).

[peyo]

1. (94 година, задача B1) Да се намерят всички естествени числа $n$, за които неравенството $|n-m^2| \le 250$ е в сила за точно 15 цели неотрицателни числа $m$.

Звучи като интересна задача!

Да се опитаме да махнем модула и да представим неравенството като 2 функции на m:

Едната функция когато $n > m^2$:
$n-m^2 \le 250$

И когато <:
$-n+m^2 \le 250$

Изразяваме като функции на m:

$m_1 = \sqrt{n - 250}$
И
$m_2 = \sqrt{n + 250}$

И сега отговора който търсим е някъде около числото което се получава когато:
$m_2-m_1 = 15$

$\sqrt{n + 250} - \sqrt{n - 250} = 15$

Да го решим като вдигнем на квадрат и после пак и ще получим да решим квадратно уравнение, на което единия корен няма да е решение:

In [288]: solve(sqrt(x+250) - sqrt(x-250) - 15)
Out[288]: [12025/36]

In [289]: 12025/36
Out[289]: 334.02777777777777

Това не ни помага много, освен, че има отговори около 334. Да видим за 14 и 16:

In [290]: float(solve(sqrt(x+250) - sqrt(x-250) - 14)[0])
Out[290]: 367.8775510204082

In [291]: float(solve(sqrt(x+250) - sqrt(x-250) - 16)[0])
Out[291]: 308.140625

Значи между 308 и 367 някъде ще има стойности за които редица от точно 15 m ще отговарят на условието. Това са 59 числа. Освен да ги проверим едно по едно друг начин не виждам. Да накараме компютъра да ги провери:

Код: Избери целия код

In [284]: def ff():
     ...:     X,Y=[],[]
     ...:     for n in range(1,450):
     ...:         c = 0
     ...:         for m in range(1000):
     ...:             if abs(n-m**2)<=250:
     ...:                 c+=1
     ...:         if c==15:
     ...:             print(n,end=", ")
     ...:         X.append(n); Y.append(c)
     ...:     return X,Y

In [285]: X,Y = ff()
315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350,

Ок. Горните числа са точното решение. Да видим графиката:

In [286]: pl.plot(X,Y); pl.show()

red15_0.png (26.39 KiB) Прегледано 509 пъти

Хм. нещо странно изглежда. Да зуумнем около 15:

red15_1.png (26.11 KiB) Прегледано 509 пъти

Много интересно! Имаме прекъсване между 325 и 332, което чак сега забелязваме в горната редица.

Това решение макар и точно използва компютър. Интересно ще ми е ако някой даде решение без компютър.

[georgi111]

Решението на автора на книжката "Конкурси Пътнам" гениалния Любомир Давидов:
Ясно е, че неравенството $|n-m^2| \le 250$ е еквивалентно с : $n -250 \le m^2 \le n+250(1)$. Нека при фиксирано $n$ решенията na (1) са $m_1 \lt m_2 \lt \dots \lt m_k$. По-нататък да допуснем ,че $m_1 \ge 11$. Ако $k \ge 15$, то $m_k \ge m_1 + 14$. Тогава имаме следната верижка от равенства и неравенства : $500 = (250+n)-(n-250) \ge {m_k}^2 - {m_1}^2 \ge (m_1 +14)^2 - {m_1}^2 = 28m_1+196 \ge 28.11 + 196 > 500$, което е противоречие. Следователно ако неравенствата (1) имат точно 15 решения относно $m$, то $m_1 \le 10$ и $n \le {m_1}^2 + 250 \le 100 + 250 = 350$. Възможни са следните случаи:
(i) $1 \le n \le 250$. Тогава имаме $[0,250] \sub [n-250, n+250]$ и понеже $15^2 = 225 < 250$ и $7^2=49$, то всяко едно от числата $0,1, \dots, 15$ е решение на неравенството (1), т.е. (1) има поне 16 решения , което е противоречие.
(i) $251 \le n \le 299$. Тогава имаме $[49,500] \sub [n-250, n+250]$ и понеже $22^2 = 484 < 500$ и $7^2=49$, то всяко едно от числата $7,8, \dots, 22$ е решение на неравенството (1), т.е. (1) има поне 16 решения , което е противоречие.
(iii) $300 \le n \le 314$. Тогава имаме $[64,550] \sub [n-250, n+250]$ и понеже $23^2 = 529 < 550$ и $8^2=64$, то всяко едно от числата $8,9, \dots, 23$ е решение на неравенството (1), т.е. (1) има поне 16 решения , което е противоречие.
(iv) $315 \le n \le 325$. Сега имаме $8^2=64=314-250 \lt n - 250 \le 325-250=75 \lt 9^2 \lt 23^2=529 \lt 565=315+250 \le n+250 \le 575 \lt 24^2$.Следователно в този случай всичките решения на (1) са числата $9,10, \dots , 23$ и значи даденото неравенство има точно 15 решения.
(v) $326 \le n \le 331$. Тогава имаме $[81,576] \sub [n-250, n+250]$ и както в предните случаи се вижда, че всяко едно от числата $9,10, \dots , 24$ и значи даденото неравенство има поне 16 решения.
(vi) $332 \le n \le 350$. Последователно имаме $9^2=81 \lt 332-250 \le n-250 \le 350 - 250 =100=10^2 \lt 24^2=576=326+250 \lt n+250 \le 500 \lt 625 = 25^2$. Следователно в този случай всичките решения на (1) са числата $0,11, \dots , 24$ и значи даденото неравенство има точно 15 решения.
Окончателно търсените числа $n$ са : $n=315,316, \dots, 324, 325, 332,333, \dots, 349,350$

[georgi111]

В случая да - малко е изкуствена