Kezdőlap


Feladat:	F.2808	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Bálint Péter , Farkas Zénó , Fehér András , Gárdonyi Márk , Gefferth András , Hegedűs András , Hortobágyi Viktor , Imreh Csanád , K. L. , Kerekes Gizella , Kisvölcsey Péter , Komócsi Sándor , Kotnyek Balázs , Kovács Erzsébet , Kucsera Henrik , Lente Gábor , Magó Kálmán , Monori András , Pór Attila , Ratkó Éva , Révész Ádám , Stőhr Lóránt , Szakács Réka , Virág Bálint
Füzet:	1991/május, 203 - 205. oldal		PDF \| MathML
Témakör(ök):	Partíciós problémák, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1990/szeptember: F.2808

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.

Legyenek $1 = a_{1} ≦ a_{2} ≦ ... ≦ a_{n}$ pozitív egészek. Megadunk egy szükséges és elégséges feltételt arra, hogy minden $a_{n}$ -nél nem nagyobb egész szám előállítható legyen e számok közül néhány (esetleg csak egy) összegeként. Ezután megmutatjuk, hogy a $2000$ pozitív osztóira teljesül ez a feltétel.
A feltétel a következő: minden $1 ≦ k < n$ -re $a_{k + 1} ≦ 1 + a_{1} + a_{2} + ... + a_{k}$ . Ez a feltétel szükséges, mert ha $a_{k + 1} > 1 + a_{1} + a_{2} + ... + a_{k}$ , akkor nem tudjuk előállítani $(1 + a_{1} + a_{2} + ... + a_{k})$ -t $a_{i} - k$ összegeként, hiszen $a_{k + 1}$ , $...$ , $a_{n}$ ennél a számnál nagyobb, így nem szerepelhetnek a tagok között, viszont a legnagyobb szám, amit a többi $a_{i}$ -vel ‐ $a_{1}$ , $a_{2}$ , $...$ , $a_{k}$ -val ‐ elő lehet állítani, kisebb $(1 + a_{1} + ... + a_{k})$ -nál.
Ezután $n$ szerinti teljes indukcióval bebizonyítjuk, hogy ha a feltétel teljesül, akkor minden $(a_{1} + a_{2} + ... + a_{n})$ -nél nem nagyobb pozitív egész előállítható néhány $a_{i}$ összegeként. Ez $n = 1$ -re igaz: az egyetlen, $a_{1}$ -nél nem nagyobb pozitív egész az $1$ , és $a_{1} = 1$ .
Tegyük fel, hogy $n ≧ 2$ , és minden $(a_{1} + a_{2} + ... + a_{n - 1})$ -nél nem nagyobb pozitív egész szám előáll $a_{1}, ..., a_{n - 1}$ közül néhánynak az összegeként. Megmutatjuk, hogy ekkor $a_{n}$ -et is felhasználva az $(a_{1} + ... + a_{n - 1}) + 1$ és $(a_{1} + ... + a_{n})$ közötti számok is előállíthatók ilyen módon. Legyen ( $a_{1} + ... + a_{n - 1}) + 1 ≦ b ≦ a_{1} + ... + a_{n}$ . Azt akarjuk belátni, hogy $b$ előállítható $a_{n}$ és néhány $a_{i}$ $(1 ≦ i ≦ n - 1)$ összegeként. Ha $b = a_{n}$ , akkor ez nyilvánvaló, így feltehető, hogy $b \neq a_{n}$ , Az $a_{n} ≦ a_{1} + ... + a_{n - 1} + 1 ≦ b$ a feltétel szerint, tehát $b > a_{n}$ . Az indukciós feltevés értelmében $b - a_{n} (> 0)$ előállítható néhány $a_{i}$ $(1 ≦ i ≦ n - 1)$ összegeként. Ehhez az összeghez $a_{n}$ -et hozzáadva éppen $b$ előállításához jutunk. Ezzel a feltétel elégségességét is igazoltuk.
Mutatunk most egy erősebb (elégséges, de nem szükséges) feltételt és ezt fogjuk alkalmazni $2000$ osztóira.
Tegyük fel, hogy minden $1 ≦ k < n$ -re $a_{k + 1} ≦ 2 a_{k}$ , azaz számaink mindegyike legfeljebb az előző kétszerese.Ekkor teljesül a fönt bizonyított feltétel is, tehát hogy minden $1 ≦ k < n$ -re $a_{k + 1} ≦ 1 + a_{1} + ... + a_{k}$ .
Állításunkat ismét indukcióval bizonyítjuk.

\begin{matrix} k = 1 -re a_{2} ≦ 2 a_{1} = a_{1} + 1. \end{matrix}

Tegyük fel, hogy

a_{k + 1} ≦ (a_{1} + ... + a_{k}) + 1

. Ekkor

\begin{matrix} a_{k + 2} ≦ 2 a_{k + 1} = a_{k + 1} + a_{k + 1} ≦ a_{k + 1} + (a_{1} + a_{2} + ... + a_{k} + 1) = (a_{1} + a_{2} + ... + a_{k + 1}) + 1. \end{matrix}

Végül a

2000

osztói nagyság szerint:

\begin{matrix} 1,2,4,5,8,10,16,20,25,40,50,80,100,125,200,250,400,500,1000,2000, \end{matrix}

és ezekre láthatóan teljesül, hogy mindegyikük legfeljebb az előző kétszerese.

Lente Gábor(Eger, Gárdonyi G. Gimn., III. o. t.) dolgozata alapján

Megjegyzés. A közölt bizonyítás segítségével általában az is belátható, hogy ha az

n

természetes szám

2^{a} \cdot 5^{b}

alakú, ahol

a ≧ 2

, akkor minden, az

n

-nél nem nagyobb pozitív egész előállítható az

n

néhány osztójának összegeként. Ehhez elegendő, hogy az

n

szám

1 = d_{1} < d_{2} < ... < d_{s} = n

osztóira

d_{i + 1} ≦ 2 d_{i}

teljesüljön

(i = 1,2, ..., s - 1)

. Tekintsünk evégből egy

d_{i}

osztót

(d_{i} < n)

. Ha

2 d_{i} | n

, akkor

d_{i + 1} ≦ 2 d_{i}

. Ha

2 d_{i}

nem osztója

n

-nek, akkor

d_{i} = 2^{a} \cdot 5^{v}

, ahol

v < b

; ekkor viszont

d' = 2^{a - 2} \cdot 5^{v + 1}

osztja

n

-et, és

d_{i} < \frac{5}{4} d_{i} = d'

miatt

d_{i + 1} ≦ \frac{5}{4} d_{i} < 2 d_{i}