Kezdőlap


Feladat:	F.1629	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Ágoston P. , Bajmóczy E. , Barbarits A. , Chikán B. , Dörfner P. , Fazekas B. , Fialovszky Alice , Frankl P. , Galántai A. , Gegesy F. , Gönczi I. , Göndőcs F. , Hadik R. , Kálmán M. , Kálmánchely G. , Kérchy L. , Kóczy L. , Komjáth P. , Lázár A. , Maróti P. , Mártonfi Gy. , Martoni V. , Máté A. , Nagy István , Pál J. , Papp Z. , Petravich G. , Sailer K. , Schűgerl Márta , Sólyom M. , Somorjai G. , Szabó Lóránt , Szalai G. , Szamosújvári S. , Terjéki J. , Várady T. , Viszkei Gy. , Zambó Péter
Füzet:	1969/október, 49 - 52. oldal		PDF \| MathML
Témakör(ök):	Azonosságok, Egészrész, törtrész függvények, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1968/november: F.1629

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. A vizsgálandó kifejezés minden előírt $n$ esetében csak véges számú, 0-tól különböző tagot tartalmaz. Ugyanis a $k + 1$ -edik $[]$ jelben álló kifejezés

\begin{matrix} \frac{1}{2} + \frac{n}{2^{k + 1}} \end{matrix}

alakban írható, és ez pozitív valódi tört minden olyan

k

esetén, melyre

\begin{matrix} \frac{n}{2^{k + 1}} < \frac{1}{2} azaz ha 2^{k} > n, \end{matrix}

tehát egész része 0. (Ha a feltétel valamely egész

k

-ra teljesül, akkor minden további egész értékre teljesül, hiszen a

2^{x}

függvény monoton nő:)
Jelöljük az összeget

S_{n}

-nel és tekintsük

n

néhány értékét.

\begin{matrix} \begin{matrix} S_{1} = [\frac{2}{2}] + [\frac{3}{4}] & = 1 + 0 = 1, \\ S_{2} = [\frac{3}{2}] + [\frac{4}{4}] + [\frac{6}{8}] & = 1 + 1 + 0 = 2, \\ S_{3} = [\frac{4}{2}] + [\frac{5}{4}] + [\frac{7}{8}] & = 2 + 1 + 0 = 3, \\ S_{4} = [\frac{5}{2}] + [\frac{6}{4}] + [\frac{8}{8}] + [\frac{12}{16}] & = 2 + 1 + 1 + 0 = 4, \\ ..... \\ S_{10} = [\frac{11}{2}] + [\frac{12}{4}] + [\frac{14}{8}] + [\frac{18}{16}] + [\frac{26}{32}] & = 5 + 3 + 1 + 1 + 0 = 10, \\ S_{11} = [\frac{12}{2}] + [\frac{13}{4}] + [\frac{15}{8}] + [\frac{19}{16}] + [\frac{27}{32}] & = 6 + 3 + 1 + 1 + 0 = 11, \\ S_{12} = [\frac{13}{2}] + [\frac{14}{4}] + [\frac{16}{8}] + [\frac{20}{16}] + [\frac{28}{32}] & = 6 + 3 + 2 + 1 + 0 = 12. \end{matrix} \end{matrix}

E példákban

n

-et

1

-gyel

- 1

-gyel növelve

S_{n}

-nek mindig egyetlen tagja nőtt 1-gyel, a többi változatlan maradt. Megmutatjuk, hogy ez minden esetben így van, ezáltal teljes indukció útján bizonyítjuk az

S_{n} = n

összefüggést. Valóban,

\begin{matrix} [\frac{n + 2^{k}}{2^{k + 1}}] = [\frac{n + 1 + 2^{k}}{2^{k + 1}}], \end{matrix}

n + 2^{k}

és

n + 1 + 2^{k}

2^{k + 1}

-nek ugyanazon két többszöröse közé esik, az alsó határt megengedve, de a fölsőt nem. Ha viszont

n + 1 + 2^{k}

eléri

2^{k + 1}

következő többszörösét, tehát valamilyen

m

-re

\begin{matrix} n + 1 + 2^{k} = (m + 1) 2^{k + 1}, azaz n + 1 = (2 m + 1) 2^{k}, \end{matrix}

akkor

\begin{matrix} [\frac{n + 2^{k}}{2^{k + 1}}] = [\frac{(m + 1) 2^{k + 1} - 1}{2^{k + 1}}] = m és [\frac{n + 1 + 2^{k}}{2^{k + 1}}] = [\frac{(m + 1) 2^{k + 1}}{2^{k + 1}}] = m + 1. \end{matrix}

Ilyen

k

minden egyes

n

-re csak egy van: ez az a kitevő, amire emelve 2-t, a hatvány még osztója

n + 1

-nek, de a magasabb hatványok már nem. (Ha tehát

n + 1

páratlan, akkor

k = 0

.)
Ezzel beláttuk, hogy

\begin{matrix} S_{n + 1} - S_{n} = 1, így S_{n} = S_{1} + n - 1 = n . \end{matrix}

Megjegyzés. Mivel az

[(n + 2^{k}) / 2^{k + 1}]

tag azoknál az

n

-eknél nő 1-gyel, amelyek

2^{k}

-nak páratlan többszörösei és

n = 1 \cdot 2^{k}

-nál 1 az értéke, így ez a tag az olyan,

n

-nél nem nagyobb számok számát adja, melyek oszthatók

2^{k}

-nal, de 2 magasabb hatványával nem. Ezt nem nehéz közvetlenül igazolni, ami a fenti megoldásnak egy másik változatát adja.

II. megoldás. Bebizonyítjuk alább a következő azonosságot:

\begin{matrix} [2 x] = [x] + [x + \frac{1}{2}] . \end{matrix}

(2)

Ezt ismételten alkalmazva,

n

így alakítható át:

\begin{matrix} n = [n] = [2 \cdot \frac{n}{2}] = [\frac{n}{2}] + [\frac{n}{2} + \frac{1}{2}] = \\ = [\frac{n + 1}{2}] + [\frac{n}{4}] + [\frac{n}{4} + \frac{1}{2}] = [\frac{n + 1}{2}] + [\frac{n + 2}{4}] + [\frac{n}{8}] + [\frac{n}{8} + \frac{1}{2}]; \end{matrix}

és általában

\begin{matrix} n = [\frac{n + 1}{2}] + [\frac{n + 2}{4}] + ... + [\frac{n + 2^{l}}{2^{l + 1}}] + [\frac{n}{2^{l + 1}}] . \end{matrix}

(3)

Ezt

l = 0, 1, 2

-re már láttuk és ha valamilyen

l_{0}

értékre igaz, akkor (2)-t alkalmazva az utolsó tagra

\begin{matrix} n & = [\frac{n + 1}{2}] + [\frac{n + 2}{4}] + ... + [\frac{n + 2^{l_{0}}}{2^{l_{0} + 1}}] + [\frac{n}{2^{l_{0} + 1}}] = \\ = [\frac{n + 1}{2}] + [\frac{n + 2}{4}] + ... + [\frac{n + 2^{l_{0}}}{2^{l_{0} + 1}}] + [\frac{n}{2^{l_{0} + 2}}] + [\frac{n}{2^{l_{0} + 2}} + \frac{1}{2}] = \\ = [\frac{n + 1}{2}] + [\frac{n + 2}{4}] + ... + [\frac{n + 2^{l_{0}}}{2^{l_{0} + 1}}] + [\frac{n + 2^{l_{0} + 1}}{2^{l_{0} + 2}}] + [\frac{n}{2^{l_{0} + 2}}] . \end{matrix}

(3) tehát

l = l_{0} + 1

-re is fennáll. Ha

l

-et akkorára választjuk, hogy

2^{l + 1} > n

legyen, akkor az utolsó tag értéke

0

, s így az (1) összeg értékére kapjuk, hogy az

n

.
A felhasznált (2) azonosság bizonyítását két esetre választjuk szét. Ha

\begin{matrix} [x] \leq x < [x] + \frac{1}{2}, akkor [x] < [x] + \frac{1}{2} ≦ x + \frac{1}{2} < [x] + 1, \end{matrix}

tehát

\begin{matrix} [x + \frac{1}{2}] = [x], és így [x] + [x + \frac{1}{2}] = 2 [x] \leq 2 x < 2 [x] + 1, \end{matrix}

amiből

\begin{matrix} [2 x] = 2 [x] = [x] + [x + \frac{1}{2}] . \end{matrix}

Ha pedig

\begin{matrix} [x] + \frac{1}{2} \leq x < [x] + 1, akkor [x] + 1 \leq x + \frac{1}{2} < [x] + \frac{3}{2} [x] + 2, \end{matrix}

tehát

\begin{matrix} [x + \frac{1}{2}] = [x] + 1, és így [x] + [x + \frac{1}{2}] = 2 [x] + 1 \leq 2 x < 2 [x] + 2, \end{matrix}

amiből ismét

\begin{matrix} [2 x] = 2 [x] + 1 = [x] + [x + \frac{1}{2}] . \end{matrix}

Megjegyzések. 1. A bizonyítás (3)-at valamivel általánosabban, tetszőleges pozitív

n

-re adja, ha a bal oldalon

n

helyére

[n]

-ét írunk, s így az (1) összeg is tetszőleges pozitív

n

-re

[n]

-ét adja.
2. A (2) azonosságnak és a látott megoldás alapján (1)-nek konkrét tartalmát látjuk a következő probléma megválaszolásában.
Játsszék bizonyos számú versenyző ‐ pl. pingpongozó ‐ a szokásos módon kieséses versenyt, vagyis kettesével játszanak egymás ellen, minden párból a nyertes jut a második fordulóba, továbbá játék nélkül a pár nélkül maradt versenyző ‐ amennyiben ilyen van, ti. ha az indulók száma páratlan; ugyanígy alakul ki a 3., a 4.,

...

forduló mezőnye, végül az nyeri a bajnoki érmet, aki veretlenül marad. Tegyük még fel, hogy minden vesztes vigaszdíjként megkapja a mérkőzésén használt pingponglabdát. ‐ Kérdés: hány mérkőzés folyik le, más szóval hány labda kerül kiadásra az egyes fordulókban ?
Bármelyik forduló indulóinak számát

v

-vel jelölve a fordulóban

[\frac{v}{2}]

mérkőzés folyik le. Ennyi a továbbjutók száma is, ha

v

páros ; ha pedig pártatlan, akkor 1-gyel több. Számuk

v

párosságától függetlenül

[\frac{v}{2} + \frac{1}{2}] = [\frac{v + 1}{2}]

alakban írható, eszerint a (2)-nek megfelelő

\begin{matrix} v = [\frac{v}{2}] + [\frac{v + 1}{2}] \end{matrix}

azonosság azt fejezi ki, hogy minden versenyző vagy kiesik, vagy továbbjut. Másrészt az egész verseny folyamán 1-gyel kevesebb labdát adnak ki, mint az indulók száma, hiszen a bajnok kivételével mindenki kiesik előbb-utóbb. A kiadandó labdák számát

n

-nel jelölve az első forduló indulóinak, kiesőinek és továbbjutóinak száma rendre

\begin{matrix} n + 1, [\frac{n + 1}{2}], [\frac{n + 2}{2}], \end{matrix}

a másodikban kiesők, ill. a továbbjutók) száma

\begin{matrix} [\frac{[\frac{n + 2}{2}]}{2}] = [\frac{n + 2}{2^{2}}], ill. [\frac{[\frac{n + 2}{2} + 1]}{2}] = [\frac{n + 2}{2^{2}}], \end{matrix}

könnyű ugyanis belátni, hogy ha

a

b

c

természetes számok, akkor

\begin{matrix} [\frac{[\frac{a}{b}]}{c}] = [\frac{a}{b c}] és [\frac{a}{b}] + c = [\frac{a}{b} + c] . \end{matrix}

Általában a

k

-adik fordulóból továbbjutott

[\frac{n + 2^{k}}{2^{k}}]

versenyző közül labdát kap, ill. továbbjut

\begin{matrix} [\frac{[\frac{n + 2^{k}}{2^{k}}]}{2}] = [\frac{n + 2^{k}}{2^{k + 1}}], ill. [\frac{[\frac{n + 2^{k}}{2^{k}} + 1]}{2}] = [\frac{n + 2^{k + 1}}{2^{k + 1}}], \end{matrix}

tehát (1) tagjai az egymás utáni fordulókban kiadott labdák számát adják, összegük pedig

n

-et, az összes labdák számát.