Kezdőlap


Feladat:	F.1901	Korcsoport: 16-17	Nehézségi fok: -
Megoldó(k):	Horváth Eszter , Somogyi Antal
Füzet:	1974/szeptember, 9 - 10. oldal		PDF \| MathML
Témakör(ök):	Halmazok számossága, Indirekt bizonyítási mód, Kombinatorikai leszámolási problémák, Kombinatorika, Feladat
Hivatkozás(ok):	Feladatok: 1973/november: F.1901

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. Az állítást indirekt úton bizonyítjuk be. Tételezzük fel, hogy csak véges sok számot karikáztunk be. A bekarikázott számok halmaza nem üres: az első számot mindenképpen be kell karikáznunk. Ekkor a bekarikázott számok között van legnagyobb, legyen ez $N$ . Tekintsük a ,,valamilyen sorrendben'' leírt természetes számok közül az első $(N + 1)$ darabot. Mivel minden számot egyszer írtunk le, azért ez az $(N + 1)$ szám mind különböző természetes szám.

Megmutatjuk, hogy ezen

(N + 1)

szám egyike sem nagyobb

N

-nél.

a) A bekarikázottak nem lehetnek nagyobbak

N

választása miatt.
b) A be nem karikázott számok a feladat feltétele szerint kisebbek, mint ahányadik helyen állnak. Így az első

(N + 1)

helyen álló be nem karikázott számok közül sem lehet

N

-nél nagyobb.
Így arra jutottunk, hogy

(N + 1)

különböző természetes számunk van, amelyek közül egyik sem nagyobb

N

-nél. Ezzel ellentmondásra jutottunk, vagyis az eredeti állítás igaz.

Horváth Eszter (Budapest, Ságvári E. Gyak. Gimn. IV. o. t.)

II. megoldás. A ,,valamilyen sorrendben'' leírt természetes számok közül az

i

-edik helyen álló legyen

a

. Tekintsük a sorozat első

k

elemét. Ezek összegét nem növeljük, ha helyette a

\sum_{i = 1}^{k} i

összeget vesszük, vagyis

\begin{matrix} \sum_{i = 1}^{k} (a_{i} - i) \geq 0 (k \geq 1) . \end{matrix}

(1)

A bizonyítást ismét indirekt úton végezzük. Tegyük fel, hogy az

a_{i}

, számok közül csak véges sokat karikáztunk be, azaz csak véges sok számra teljesül, hogy

(a_{i} - i) \geq 0

. Legyen a bekarikázott számok közül az utolsónak a sorszáma

m

(

m \geq 1

, hiszen az első számot feltétlenül bekarikázzuk). Legyen

\begin{matrix} \sum_{i = 1}^{m} (a_{i} - i) = s . \end{matrix}

(2)

(m + 1)

-edik elemtől kezdve az indirekt feltevés következtében egy elem sincs bekarikázva, így

(a_{i} - i) < 0

, ha

i \geq m + 1

. Mivel

a_{i}

és

i

természetes számok,

a_{i} - i \leq - 1 (i \geq m + 1)

, és ezért

\begin{matrix} \sum_{i = m + 1}^{m + s + 1} (a_{i} - i) \leq (- 1) (s + 1) = - s - 1. \end{matrix}

(3)

Összeadva (2)-t és (3)-t

\begin{matrix} \sum_{i = 1}^{m + s + 1} (a_{i} - i) \leq - 1. \end{matrix}

Ez azonban (1) miatt lehetetlen. Ellentmondásra jutottunk: indirekt feltevésünk hibás volt, vagyis végtelen sok számot kellett bekarikáznunk.

Somogyi Antal (Budapest, Móricz Zs. Gimn. IV. o. t.)