i
i
“1478-Mohar-0” — 2010/8/25 — 8:21 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 29 (2001/2002)
Številka 3
Strani 131–132
Bojan Mohar:
VRTNARJEVA NALOGA – nagradna naloga
Ključne besede: naloge, matematika, teorija števil, porazdelitve, pre-
dalčno načelo.
Elektronska verzija: http://www.presek.si/29/1478-Mohar.pdf
c© 2001 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
I Za vsakogar nekaj
VRTNARJEVA N AL OGA - N agradna naloga
V prvi letošnji št evi lki Preseka je bi la v prispevku Predalčno načelo Jožeta
Grassellija zastavljena naslednja naloga:
(A) Na gredo, ki ima obliko kvadrata s stranico 1 m, je vrtnar posejal
301 seme. Dokaži, da obstaja krog s po lmerom 8 cm, v katerem so
posejana vsaj št iri semena. (Seme vzamemo kot točko.)
Dokaz te trditve je napravljen z uporabo predalčnega načela. Najprej
predstavimo metrski kvadrat v ravnini , enota pa naj predstavlja 1 cm.
Potem ima naš kvadrat oglišča (0,0), (0,100), (100,100) in (100,0) . Zatem
ugotovimo, da kvadrat s stranico 100 lahko pokrijemo s stotimi krogi
po lmer a 5V2 ~ 7,07, ki imajo središča v točkah Sk ,l = (lOk - 5, 101 - 5) ,
kjer k, l E {1, . . . , lO}. Ker je v 100 krogih skupno 301 seme, morajo
po predalčnem načelu venem od krogov biti več kot tri , t orej vsaj štiri
semena.
Izurjen matematik takoj vidi, da smo pri tem dokazu napravili dokaj
grobo oceno, saj potrebujemo le kroge polmera malenkost več kot sed em
centimetrov. Naslednj i sklep prinaša precej bo ljši rezult at , saj z njim
pokažemo, da obstaja krog po lmera 8, v katerem je vsaj pet semen.
Namesto stotih vzemimo raje N = (115)2 = 13225 krogov polmera
8, ki imajo središča v točkah Pp,q = (p , q) , kjer p in q pretečeta množico
celih števil od -7 do 107.
Preštejmo sedaj vse tiste pare (K, T), kjer je K ede n izmed naših N
krogov, T pa ena od ti = 301 točk (semen) , ki leži v krogu K . Število
takih parov označimo s Q. Rec imo, da vsak krog vsebuje kvečjemu k
danih točk. Potem je
Q < Nk .
Po drugi st rani pa poljubna dana točka T leži v vseh tistih krogih,
katerih središče je od T oddaljeno za manj kot 8. Krajši račun (napravljen
s pomočjo računalnika) me je prepričal, da je vsaka točka T vsebovana
v vsaj t = 193 izmed obravnavanih krogov (najs labši primer 193 krogov
dobimo le v prime ru , ko sta koordinati točke T celoštevilski) . Torej je
Q ?: tn .
Iz obeh neenakosti za Q sledi, da je tn ::; Q ::; Nk . Od tod dobimo
k> tn = 193 ·301 = 4 39266 .. .
- N 13225 '
(1)
Za vsakogar nekaj I
Torej je k celo števi lo, večje od 4,39. Od tod sledi, da je k vsaj 5. Zato
mora obstajati krog, v katerem je vsa j 5 izmed dan ih točk.
Zdi se, da bi bilo mogoče dokazati še več . Zakaj? Če pos kušamo naj ti
n točk v kvadratu s stranico a tako, da bo v vsakem krogu polmera T
kvečjemu k točk in bo k kar se da majhen, potem morajo biti točke dokaj
enakomern o razporejene po notranjosti kvadr ata. Karkoli poizkusimo,
vidimo, da bo k večj i od 5 (in celo večji od 6) . Bralcem P reseka zato
zastavljamo dve nagradni vprašanji :
(B) Dokažit e, da v vrtnarjevi nalogi (A) vedno obstaja krog polmera
8, ki vsebuje vsa j 6 danih točk (semen) . Ali morda enako velja
tudi za 7 točk?
(O) Poiščite 301 takih točk, da bo maksimalno št evilo točk v krogu
polmera 8 čim manjše.
Najuspešnejšim reševalcem posameznih nalog obljubljamo knjižno
nagrado . S pos plošitvijo prikazanega dokaza lahko oceno (1) izbo ljšamo
do neenakosti k 2: 4,497595. Izboljšave te ocene pa se zdijo bo lj zapletene.
Zato bomo pr iznali t udi vse ideje, ki bodo (1) izbo ljša le na spodnjo mejo ,
ki bo večj a od 4,5. Obe nalogi lahko skušate rešiti tudi splošno , kjer
imamo kvadrat s st ranico dolžine a, n točk in kroge polmera T .
Nalogo (B) lahko t udi "obrn emo" :
(D) Najmanj koliko točk v kvadratu s stranico a moramo izbr ati , da
bo zagotovo obstajal krog, v katerem bo vsaj k izmed danih točk?
Vrtnarj ev na jverjet neje takšne naloge ne zanimajo. Kaj lahko pa si
zamislimo resnega znanstvenika, ki bo takšno nalogo uporabil pri svojem
delu . Recimo , da fizik s tarčo kvadr atne oblilke prestreže snop element ar-
nih delcev. Vemo, da bodo ti delci pustili sled le v pri meru , če bo v isto
tipalo na tarči (krog danega polmera) pr iletelo vsaj k delcev . Z rešitvijo
naloge (D) lah ko torej ugotovimo, koliko na jmanj delcev potrebujemo , da
jih bomo got ovo lahko zaznali, oz. največ koliko delcev je pril et elo v tarčo,
če delcev ni bilo zaznat i.
P ri nagradah bomo seveda upošteval i tudi rešit ve ali delne rešitve
naloge (D) . Rešitve poš lj it e najkasneje do 10. febru arj a na nas lov:
Presek , J adr anska c. 19, 1001 Ljubljana, p .p . 2964.
Bojan Mohar