P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 20 (1992/1993) Številka 1 Strani 38-40
Borut Zalar:
PRINCIP NAJMANJŠEGA IN NAJVEČJEGA ELEMENTA V PODMNOŽICAH NARAVNIH ŠTEVIL
Ključne besede: matematika, naravna števila, teorija števil, minimum, maksimum.
Elektronska verzija: http://www.presek.si/20/1115-Zalar.pdf
© 1992 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
FIRTETIRTIKR
PRINCIP NAJMANJŠEGA IN NAJVEČJEGA ELEMENTA V PODMNOŽICAH NARAVNIH ŠTEVIL
1.	Uvod
Ogledali si bomo dve lastnosti, ki ju imajo naravna števila, ostala števila pa največkrat ne.
Lastnost minimuma. V vsaki podmnožici naravnih Števil obstaja najmanjši element.
Že racionalna števila te lastnosti nimajo več. Celo če je neka podmnozica racionalnih števil omejena navzdol, ni nujno, da ima najmanjši element, te vzamemo množico vseh pozitivnih racionalnih števil, potem ta množica nima najmanjšega elementa, ker je ulomek vedno manjši od ulomka Podobno ne obstaja najmanjše pozitivno realno število. Poleg tega imajo naravna števila Še naslednjo lastnost:
Lastnost maksimuma. V vsaki podmnožici naravnih števil, kije omejena navzgor, obstaja največji element.
Racionalna števila tudi te lastnosti nimajo. Podmnozica tistih racionalnih števil, ki so manjša od 1, je namreč navzgor omejena (kar s številom 1), nima pa največjega elementa. 0 tem se lahko prepričamo na naslednji način:
Naj bo 0 < ~ < 1 poljuben ulomek. Tedaj je seveda n < m. Če primerjamo ulomka ^ in ^jt^. vidimo, da je ^ <	< 1. torej vedno
obstaja ulomek, ki je večji od ulomka ^ in še vedno manjši od 1.
Obe omenjeni lastnosti je mogoče koristno uporabiti pri reševanju problemov iz teorije števil in kombinatorike. Pokažimo dva osnovna primera.
2.	Primer uporabe lastnosti minimuma
Naj bo n neko naravno število in naj bo
Vn = { n, 2/1, 3n,... }
množica njegovih večkratnikov. Ta podmnožica naravnih števil ima naslednji lastnosti:
Lastnost A. če je m poljubno naravno Število in p poljubno Število iz množice Vn, potem je število p ■ m tudi v množici Vn.
Lastnost B. Če sta pi in P2 dve števili iz množice Vn in je p\ > P2, potem je tudi število p\ — p2 v množici Vn-
Teh lastnosti ni težko preveriti. Naj bo torej p iz množice Vn. Tedaj je p večkratnik števila n. To pomeni, da obstaja tako naravno število r, da je p = r ■ n. Če je m poljubno nadaljnje naravno število, je m- p = (m-rjntudi večkratnik števila n in zato m ■ p spada v množico Vn večkratnikov števila n. Povsem podobno preverimo tudi lastnost B.
Zdaj se nam zastavi vprašanje, ali obstajajo še kakšne druge podmnožice naravnih števil z lastnostma A in B:
Problem. Naj bo V neka podmnožica naravnih števil, ki ima lastnosti A in B. Ali obstaja tako naravno število n, da je množica V kar enaka množici večkratnikov tega Števila (oziroma ali je V = Vn za neki n)?
Problem bomo rešili z uporabo lastnosti minimuma in pokazali, da je odgovor na zastavljeno vprašanje pritrdilen.
Ker je V podmnožica naravnih števil, ima po lastnosti minimuma najmanjši element. Označimo ga s črko n. Naj bo p poljubno število iz množice V. različno od n. Ker je n najmanjši element množice V, je očitno p > n. Število p razcepimo na vsoto p = q ■ n + o, kjer je q > 1 kvocient, o pa ostanek pri deljenju števila p s Številom n. Gotovo vam je dobro znano, da je ostanek vedno večji ali enak 0 in manjši ali enak n — 1, zato je o < n.
Zaradi lastnosti A je najprej število q ■ n v množici V, saj je po predpostavki število n v množici V. Denimo, da je ostanek o različen od nič. Tedaj je p > q ■ n, zato je po lastnosti B tudi število o = p — q ■ n v množici V. To pa ni mogoče, ker je število n najmanjše v množici V.
To pomeni, da je p = q ■ n, oziroma število p je večkratnik števila n. Dokazali smo, da je vsako število iz množice V večkratnik števila n, kar pomeni, da je množica V podmnožica množice Vn. Zaradi lastnosti A sta ti množici kar enaki, ker z množenjem števila n z vsemi možnimi naravnimi števili dobimo vse večkratnike.
3. Uporaba principa maksimuma
Rešili bomo naslednji
Problem. Na matematičnem kongresu sta dva prijatelja, ki sta šla po predavanjih skupaj na kosilo, ugotovila naslednjo zanimivost:
Če sta imela dva matematika na kongresu enako število znancev, potem nista imela skupnih znancev.
Dokaži, da je obstajal na kongresu tudi tak matematik, ki je imel samo enega znanca.
Ta problem bomo rešili z uporabo principa maksimuma. Označimo udeležence kongresa s številkami 1, 2 , .,, , n. Pri vsakem matematiku označimo še število njegovih znancev (brez njega samega) s števili Z( 1), Z(2),
Očitno je nemogoče, da bi veljalo Z( 1) = Z(2) = .., — Z(n) = 0. To bi namreč pomenilo, da nihče na pozna nikogar, zato se pri kosilu ne bi mogla srečati dva prijatelja.
Ker nihče ne more poznati več oseb, kot je prisotnih, je vedno 0 < Z(/) <
<	n — 1, kjer je i eno izmed števil 1,2, ..., n. To pomeni, da je množica { Z(l), Z(2),..., Z(n) } navzgor omejena in ima po lastnosti maksimuma največji element. Naj bo p ta največji element, ki je zaradi razmisleka v prejšnjem odstavku vsaj enak 1. Brez škode za sploŠnost lahko privzamemo, da je kar Z(l) = p. To pomeni, da ima matematik 1 natanko p znancev
¡1, ¡2.....ip■ Seveda ni nujno, da je matematik 1 edini udeleženec kongresa
s p znanci.
Zdaj si oglejmo števila Z(/"i), Z(f2). ■ ■ ■, Z(ip). Očitno je. da velja Z(ii), ..Z(ip) < p. Ker vsi ti poznajo matematika lr je tudi 1 <
<	Z(i1), ... , Z (ip). Torej imamo med 1 in p natanko p naravnih števil.
Ali sta lahko dve med njimi enaki? Če bi veljalo Z(li) — Z(/2)r bi imela ta matematika enako število znancev, zato po predpostavki ne bi smela imeti skupnih znancev. Toda matematik 1 je njun skupni znanec, zato je Z(/"i) ^
^ Z(/2). Na podoben način vidimo, da so vsa števila Z(/'i), .....Z(/p)
med seboj različna.
Če imamo p različnih naravnih števil, ki so vsa med 1 in p, pa ne gre drugače, kot da je eno med njimi enako 1, eno med njimi enako 2 in tako naprej do p. To pomeni, da mora biti nekdo, ki ima na kongresu samo enega znanca.
Borut Zalar