i
i
“Razpet-grafika” — 2010/6/14 — 9:52 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 16 (1988/1989)
Številka 3
Strani 130–131, IX
Marko Razpet:
ŠAHOVSKI KRALJ IZBIRA VZOREC
Ključne besede: matematika, računalništvo, deljivost števil, računal-
niška grafika.
Elektronska verzija: http://www.presek.si/16/930-Razpet.pdf
c© 1988 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.
, , ', . . ,,'.')'" , .
, . .~. '. . .
--;/.. rlRTErlRTIKR
SAHOVSKI KRALJ IZBIRA VZOREC
V šesti številki lanskega Preseka smo govorili o šahovskem kralju z omejeno
svobodo gibanja. Kraljevo sprehajanje po šahovnici z osnovnico, ki šteje n kva-
dratov, je kar dvakrat omejeno: kralj ima na razpolago le polja pod diagonalo in
na njej (slika 1), če se more, pa se lahko premakne le v treh dovoljenih smereh:
(x, y) -+ (x + 1, yI, (x, y) -+ (x, y+ 1), (x, y) -+ (x + 1, y+ 1)
Spraševali smo se po številu q(x, y) različnih poti, po katerih lahko pride
kralj s polja (O, O) na polje (x, y). Pri tem je O~ y ~ x. Če je y> x, je seveda
q(x, y) = O. Posebej vzemimo q(O, O) = 1. Potem je očitno q(x, O) = 1 za vsak
x ~ O. S preprostim premislekom smo ugotovili, da lahko števila q(x, yI izra-
čunamo samo s seštevanjem po formuli: .
q(x, yI = q(x - 1, yI + q(x, y - 11+ q(x - 1, y - 11, 1 ~ y ~ x (1I
Po tej formuli dobimo najprej števila q(x, 1I za x ~ 1, nato q(x, 21 za x ~2 in
tako naprej. Na ta način lahko tvorimo poljubno velik trikotnik števil q(x, yI.
Na vsako polje (x, yI napišemo ustrezno število q(x, y). Tvorba števil je jasna:
v spodnjo vrsto vpišemo same enice, nato pa seštevamo z leve proti desni po
tri, kakor je označeno na sliki 1. Na prvi pogled opazimo, da števila q( x,yl
y=o
-
y =4 9O
y=3 22 68
..-.-:..
y=2 6 1'9 30
y=1 2 4 Hi& \§
I 1 1 1 1 1
x=o x t: 1 x=2 x=3 x=4
y=o
ro---
y=4 O
y=3 1 2
y=2 O 1 O
y=1 2 1 O 2
I 1 1 1 1 1
x=O x=1 x=2 x=3 x=4
Slika 1 Slika 2
hitro naraščajo, če povečujemo števili x in y. Razen v začetni vrstici imamo
povsod drugje sama soda števila. Zato se je smiselno vprašati, kje so števila
130
q(x, yI. ki so deljiva s kakšn im številom p, p ~ 3. Najzan imivejši so primeri , ko
je IJ praštev ilo.
Pretežko bi bilo odgovoriti na vprašanje, ali je na pr imer štev ilo
q (3535 , 2525) deljivo s številom p = 17. Pač pa lahko sesta vimo tabelo ostan-
kov pri de ljenju šte vil q ix, y) s štev ilom p. Tako kot smo sestavili prejšnjo tabe-
lo, naredimo novo po formuli (1), čim pa vsota preseže p, odštejemo od nje
to likokrat p , da dobimo rezultat med O in p - 1. Za p =3 pa dob imo sliko
2 . Če je na mestu (x , y ) število O, potem je število q(x, y) deljivo sp.
Na prvi pogled to ni nič posebnega, to pa zato, ker je številski trikotnik na
sliki 2 premajhen. Toda z računalnikom si lahko privoščimo precej večji tri-
kotn ik. Napisati je treba program, ki nariše točko (x, yI. če je število q(x, y)
deljivo s p , sicer pa naj ne nariše ničesar. Na ta način dobimo zanimive vzorce .
Za p = 3, O ~ x ~ 250, O~ y ~ x dobimo na primer (temnim področjem
ust rezajo števila q (x, y), ki so del jiva s 3) :
Slika 3
Podobno lahko sestavimo sliko deljivosti števil q(x, y) tud i za druga števila.
Prav tako bi lahko raziskovali Pascalov in Stirlingov, pa morda še kakšen števil-
ski trikotnik. Prva dva sta obširno obdelana v članku Marte Sved: Divisibility-
With Visibility. Objavljen je v reviji The Mathematical Intelligencer, letnik 10
(1988) , številka 2.
Naš šahovski kralj je bil celo tako prijazen, da je sodeloval pri izbiri naslov-
ne strani ovitka . Za p = 7 smo dobili spodnji, za p =5 pa zgornji trikotnik. Pri
tem je spodnji rob osnovnica spodnjega, zgornji rob pa osnovnica zgornjega
trikotnika, tako da je najbolje, da pri gledanju zgornjega Presek obrnete.
Marko Razpet
131