Kezdőlap


Feladat:	2013. évi Nemzetközi Matematika Diákolimpia 11. feladata	Korcsoport: -	Nehézségi fok: -
Megoldó(k):	Havasi Márton
Füzet:	2013/október, 386 - 387. oldal		PDF \| MathML
Hivatkozás(ok):	Feladatok: 2013/szeptember: 2013. évi Nemzetközi Matematika Diákolimpia 11. feladata

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.

Havasi Márton megoldása.¹ Az állítást $k$ -ra vonatkoztatott indukcióval bizonyítjuk. A következőt fogjuk belátni:
$k = 1$ -re, az $m_{1} = n$ triviálisan megoldás.
Feltesszük, hogy az állítás igaz egy pozitív egész $k$ -ra. Azt akarjuk belátni, hogy minden $n$ egészhez léteznek $m_{1}, ..., m_{k + 1}$ egészek, amelyek kielégítik az

\begin{matrix} 1 + \frac{2^{k + 1} - 1}{n} = (1 + \frac{1}{m_{1}}) \dots (1 + \frac{1}{m_{k + 1}}) \end{matrix}

egyenletet. Két esetet különböztetünk meg

n

paritásától függően.
1. eset:

n

páratlan. Ekkor

\frac{n + 1}{2}

biztosan egész és a feltételből adódóan léteznek olyan

m_{1}, ..., m_{k}

egészek, amelyekre teljesül

\begin{matrix} 1 + \frac{2^{k} - 1}{\frac{n + 1}{2}} = (1 + \frac{1}{m_{1}}) \dots (1 + \frac{1}{m_{k}}) . \end{matrix}

Legyen

m_{k + 1} = n

. Ekkor:

\begin{matrix} (1 + \frac{1}{m_{1}}) \dots (1 + \frac{1}{m_{k + 1}}) = (1 + \frac{2^{k} - 1}{\frac{n + 1}{2}}) \cdot (1 + \frac{1}{n}) = \\ = (1 + \frac{2^{k + 1} - 2}{n + 1}) \cdot \frac{n + 1}{n} = \frac{n + 1 + 2^{k + 1} - 2}{n} = 1 + \frac{2^{k + 1} - 1}{n} . \end{matrix}

2. eset:

n

páros. Ekkor

\frac{n}{2}

biztosan egész és a feltételből adódóan léteznek olyan

m_{1}, ..., m_{k}

egészek, amelyekre teljesül

\begin{matrix} 1 + \frac{2^{k} - 1}{\frac{n}{2}} = (1 + \frac{1}{m_{1}}) \dots (1 + \frac{1}{m_{k}}) . \end{matrix}

Legyen

m_{k + 1} = 2^{k + 1} + n - 2

. Ekkor:

\begin{matrix} (1 + \frac{1}{m_{1}}) \dots (1 + \frac{1}{m_{k + 1}}) = (1 + \frac{2^{k} - 1}{\frac{n}{2}}) \cdot (1 + \frac{1}{2^{k + 1} + n - 2}) = \\ = (1 + \frac{2^{k + 1} - 2}{n}) \cdot (1 + \frac{1}{2^{k + 1} + n - 2}) = \frac{2^{k + 1} + n - 2}{n} \cdot \frac{2^{k + 1} + n - 2 + 1}{2^{k + 1} + n - 2} = \\ = 1 + \frac{2^{k + 1} - 1}{n} . \end{matrix}

¹Forrás: imomath.com.