Problem B. 5106. (May 2020)
B. 5106. The numbers \(\displaystyle n+1, n+2, \ldots, 2n\) are written on a blackboard (\(\displaystyle n\ge2\)), and the following procedure is repeated: two numbers are selected (\(\displaystyle x\) and \(\displaystyle y\)) from the board, erased, and replaced with the numbers \(\displaystyle x+y+\sqrt{x^2+y^2}\) and \(\displaystyle x+y-\sqrt{x^2+y^2}\). Prove that there will never be a number less than 1.442 written on the board.
(5 pont)
Deadline expired on June 10, 2020.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. A bizonyítás során három lemmát fogunk segítségül hívni, és bizonyítani.
Első lemma: Bármely lépés után minden táblán lévő szám pozitív.
Kezdetben az állítás nyilvánvaló.
Egy lépés után az \(\displaystyle x,y>0\) számok letörlése után az \(\displaystyle x+y+\sqrt{x^2+y^2}>0\) és \(\displaystyle x+y-\sqrt{x^2+y^2}\) számok kerülnek a táblára, ezek közül csak a második lehet nempozitív; viszont az (\(\displaystyle x,y\) pozitivitása miatt) \(\displaystyle x+y=\sqrt{x^2+2xy+y^2} > \sqrt{x^2+y^2}\), emiatt \(\displaystyle x+y-\sqrt{x^2+y^2}\) is pozitív. Ezzel igazoltuk, hogy bármelyik lépés után bármely a táblán lévő szám pozitív.
Második lemma: Bármely állapotban a táblán lévő számok reciprokösszege invariáns, azaz nem változik a lépések során.
Legyenek a táblán lévő számok egy adott állapotban \(\displaystyle a_1,a_2,...,a_{n-2},x,y\) és a soron következő lépésben az \(\displaystyle x,y\) számokat töröljük le. Ekkor azt kell igazolnunk, hogy \(\displaystyle \dfrac{1}{a_1}+...+\dfrac{1}{a_{n-2}}+\dfrac{1}{x}+\dfrac{1}{y} = \dfrac{1}{a_1}+...+\dfrac{1}{a_{n-2}} + \dfrac{1}{x+y+\sqrt{x^2+y^2}} + \dfrac{1}{x+y-\sqrt{x^2+y^2}}\). Ehhez nyilván elegendő megmutatni, hogy \(\displaystyle \dfrac{1}{x+y+\sqrt{x^2+y^2}} + \dfrac{1}{x+y-\sqrt{x^2+y^2}} = \dfrac{1}{x}+\dfrac{1}{y}\).
A gyökös nevezőjű törteknél az \(\displaystyle x+y-\sqrt{x^2+y^2}\), illetve az \(\displaystyle x+y+\sqrt{x^2+y^2}\) ,,konjugáltakkal'' bővítés után kapjuk:
\(\displaystyle \dfrac{1}{x+y+\sqrt{x^2+y^2}} + \dfrac{1}{x+y-\sqrt{x^2+y^2}} = \dfrac{x+y-\sqrt{x^2+y^2}}{(x+y)^2-(x^2+y^2)} + \dfrac{x+y+\sqrt{x^2+y^2}}{(x+y)^2-(x^2+y^2)}=\dfrac{2x+2y}{2xy}=\dfrac{x+y}{xy}= \dfrac{1}{x}+\dfrac{1}{y}\).
Azaz a táblán lévő számok reciprokösszege valóban invariáns.
Harmadik lemma: \(\displaystyle \dfrac{1}{n+1}+\dfrac{1}{n+2}+...+\dfrac{1}{2n} = \dfrac{1}{1}-\dfrac{1}{2}+\dfrac{1}{3}-\dfrac{1}{4} \pm ... - \dfrac{1}{2n}\). (Ez egy közismert állítás, de azért bebizonyítjuk.)
\(\displaystyle n\)-szerinti teljes indukcióval fogunk bizonyítani.
\(\displaystyle n=1\)-re az állítás nyilvánvaló, hiszen \(\displaystyle \dfrac{1}{2}=1 - \dfrac{1}{2}\).
T.f.h. \(\displaystyle n=k\)-ra igaz az állítás, azaz \(\displaystyle B_k=\dfrac{1}{k+1}+\dfrac{1}{k+2}+...+\dfrac{1}{2k} = \dfrac{1}{1}-\dfrac{1}{2}+\dfrac{1}{3}-\dfrac{1}{4} \pm ... - \dfrac{1}{2k}=J_k\).
Megmutatjuk, hogy igaz marad az állítás \(\displaystyle n=k+1\) esetén is.
\(\displaystyle B_{k+1}=\dfrac{1}{(k+1)+1}+\dfrac{1}{(k+1)+2}+...+\dfrac{1}{2(k+1)} = B_k - \dfrac{1}{k+1} + \dfrac{1}{2k+1}+\dfrac{1}{2k+2} = B_k - \dfrac{2}{2k+2} + \dfrac{1}{2k+1}+\dfrac{1}{2k+2} = B_k + \dfrac{1}{2k+1}-\dfrac{1}{2k+2}=J_k+\dfrac{1}{2k+1}-\dfrac{1}{2k+2}=\dfrac{1}{1}-\dfrac{1}{2}+\dfrac{1}{3}-\dfrac{1}{4} \pm ... - \dfrac{1}{2k}+\dfrac{1}{2k+1}-\dfrac{1}{2k+2}=J_{k+1}\).
Ezzel – az indukciós bizonyítási séma értelmében – beláttuk a harmadik lemmánkat is.
Felhasználva (a logaritmus Taylor-sorával kapcsolatos) összefüggést \(\displaystyle \ln 2\) értékére:
\(\displaystyle \displaystyle{\dfrac{1}{1}-\dfrac{1}{2}+\dfrac{1}{3}-\dfrac{1}{4} \pm ... - \dfrac{1}{2n} < \sum_{i=1}^{\infty} \dfrac{(-1)^{i+1}}{i}=\ln 2}\); adódik, hogy a kezdetben a táblán lévő számok reciprokösszegére igaz:
\(\displaystyle \dfrac{1}{n+1}+\dfrac{1}{n+2}+...+\dfrac{1}{2n} = \dfrac{1}{1}-\dfrac{1}{2}+\dfrac{1}{3}-\dfrac{1}{4} \pm ... - \dfrac{1}{2n} < \ln 2\), és emiatt (a táblán lévő számok pozitivitását kihasználva) a táblán bármely állapotban lévő bármely \(\displaystyle z\) számra \(\displaystyle z > \dfrac{1}{\ln 2} = \log_2 e \approx 1,442695 >1,442\).
Ezzel az állítást beláttuk.
Statistics:
13 students sent a solution. 5 points: Bán-Szabó Áron, Fekete Richárd, Füredi Erik Benjámin, Lengyel Ádám, Seres-Szabó Márton, Tiderenczl Dániel. 4 points: Beke Csongor, Mácsai Dániel, Sztranyák Gabriella. 3 points: 2 students. 2 points: 1 student. 1 point: 1 student.
Problems in Mathematics of KöMaL, May 2020