     
P 47 (2019/2020) 44
Šahovski kralj v posebnih
okoliščinah
M R
Obravnavali bomo nekatere preproste kombina-
torične probleme na šahovnici. Podobne probleme
smo sicer srečali ali že v 15. in 16. letniku Preseka.
Novo v tem prispevku pa so ovire, ki jih na raz-
lične načine postavimo na šahovnico.
Šahovskega kralja k (lahko tudi K) smo iz-
brali samo zato, ker se sme na šahovnici premikati,
če nima ovir, v osmih smereh, vedno samo za eno
polje: levo, desno, navzgor, navzdol, pa še v štirih
diagonalnih smereh. Vsak tak premik bomo imeno-
vali korak. Na šahovnici bo kralj ves čas edina figura.
Vsako polje xy je označeno s črko x iz množice
{a,b, c,d,e, f,g,h} in številko y iz množice
{1,2,3,4,5,6,7,8}. Črke označujejo vertikale, šte-
vilke pa horizontale. Polje c5 je na primer na ver-
tikali c in na horizontali 5. Namesto opisane tradi-
cionalne šahovske oznake polja xy bomo raje upo-
rabljali matematično koordinatno oznako (i, j). Pri
tem pomeni i absciso, j pa ordinato polja (i, j). Za
šahovska polja sta koordinati i, j števili iz množice
J = {0,1,2,3,4,5,6,7} (glej spodnji in levi rob ta-
bele 1). Primeri. a1 = (0,0), f7 = (5,6),h8 = (7,7).
Na začetku stoji kralj na polju (0,0). Njegov cilj
pa je prispeti na polje (7,7), pa ne kakorkoli, am-
pak tako, da je cilju po vsakem koraku bliže. To pa
pomeni, da lahko kjerkoli na šahovnici izbira samo
med tremi koraki: na desno, navzgor in diagonalno
desno-navzgor. Kralj na ta način s polja (0,0) na
polje (i, j) opravi neko pot (slika 1). Tukaj obravna-
vamo samo take poti.
1. vprašanje. Koliko je različnih poti šahovskega
kralja s polja (0,0) na polje (i, j), pri čemer se cilju
po vsakem koraku približa?
Zagotovo je možna ena sama pot s polja (0,0) na
katerokoli polje (i,0) oziroma (0, j), kjer sta i ozi-
roma j v J . Označimo z D(i, j) število poti s polja
(0,0) na polje (i, j). Na polje (i, j) lahko kralj prispe
v enem koraku na tri načine: s polja (i−1, j), s polja
(i, j − 1) ali s polja (i − 1, j − 1). To pa pomeni, da
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0ZkZ0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 Z0Z0Z0Z0
a b c d e f g h
8 0Z0Z0Z0j
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0Z0Z0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 j0Z0Z0Z0
a b c d e f g h
SLIKA 1.
Koraki in pot
šahovskega kralja
     
P 47 (2019/2020) 4 5
za i, j ≥ 1 velja relacija
D(i, j) = D(i− 1, j)+D(i, j − 1)+D(i− 1, j − 1).
Ker veljata pogoja D(i,0) = 1 in D(0, j) = 1, lahko
števila D(i, j) izračunamo samo s seštevanjem. V ta
namen zapišemo rezultate v tabelo. Pri tem, da hi-
treje izpopolnimo tabelo, upoštevamo simetričnost:
D(i, j) = D(j, i).
Primer. Število 681 = D(5,4) je vsota uokvirjenih
števil 321 = D(4,4), 231 = D(5,3) in 129 = D(4,3).
Število poti s polja (0,0) na polje (7,7) je torej
D(7,7) = 48639. To število je kar veliko. Če bi vsako
sekundo narisali eno pot, bi potrebovali 13 ur, 30
minut in 39 sekund, da bi dobili vse. Potrebovali pa
bi več tisoč listov papirja formata A4, da bi nanje
narisali vse poti, čeprav bi jih na vsak list na vsaki
strani narisali 20.
Števila D(i, j) so Delannoyjeva števila, ki jih je
prvi obravnaval francoski amaterski matematik in
častnik Henri Auguste Delannoy (1833–1915).
Za Delannoyjeva števila obstajajo tudi eksplicitne
formule, ki pa niso preproste in se izražajo s konč-
nimi vrstami, ki vsebujejo binomske koeficiente. Več
o tem lahko preberemo npr. v [1, 2].
Tabelo Delannoyjevih števil lahko seveda razširi-
mo do poljubne velikosti. Uporabimo pa jo lahko
tudi za izračun števila poti s polja (i, j) na polje
(u,v). Poti ni, če je i > u ali j > v . V nasprotnem
primeru pa je število poti enakoD(u−i, v−j). Tedaj
je polje (u,v) s polja (i, j) dosegljivo.
2. vprašanje. Koliko je različnih poti šahovskega
kralja s polja (0,0) na polje (7,7), pri čemer se cilju
po vsakem koraku približa, na šahovnici pa je polje
(p, q), na katerega kralj zaradi ovire ne more stopiti?
Na sliki 2 levo je ovirano polje d5 oziroma (3,4).
Lahko si tudi mislimo, da tega polja preprosto ni.
Število poti s polja (0,0) na ovirano polje je 0.
Poti bo zdaj seveda manj kot D(7,7), in sicer za
število poti P(p, q) s polja (0,0) čez ovirano polje
(p, q) do ciljnega polja (7,7). Po osnovnem izreku
kombinatorike je P(p, q) enako produktu števila poti
s polja (0,0) na polje (p, q) s številom poti s polja
(p, q) na polje (7,7), torej P(p, q) = D(p,q) ·D(7−
p,7−q). Število dovoljenih poti označimo z N(p,q).
Tako smo našli:
N(p,q) = D(7,7)−D(p,q) ·D(7− p,7− q).
V posebnih primerih jeN(0,0) = 0 inN(7,7) = 0, saj
kralj v prvem primeru na start niti ne more stopiti,
na cilj pa ne dospeti. Poti potemtakem sploh ni.
V primeru oviranega polja (3,4) je
N(3,4) = D(7,7)−D(3,4) ·D(4,3)
= 48639− 1292 = 31998.
V tem primeru je torej število poti nekoliko manjše
kot brez ovire: 31998. Do rezultata lahko pridemo
tudi s tabelo, v katero postavimo črn kvadratek v ce-
lico (3,4), in zanjo ničesar ne računamo, za preo-
stale celice pa računamo tako kot v tabeli 1,
3. vprašanje. Koliko je različnih poti šahovskega
kralja s polja (0,0) na polje (7,7), pri čemer se cilju
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
i 0 1 2 3 4 5 6 7
j a b c d e f g h
0 1 1 1 1 1 1 1 1 1
1 2 1 3 5 7 9 11 13 15
2 3 1 5 13 25 41 61 85 113
3 4 1 7 25 63 129 231 377 575
4 5 1 9 41 129 321 681 1289 2241
5 6 1 11 61 231 681 1683 3653 7183
6 7 1 13 85 377 1289 3653 8989 19825
7 8 1 15 113 575 2241 7183 19825 48639
TABELA 1.
Delannoyjeva števila. Število poti.
     
P 47 (2019/2020) 46
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0Z0Z0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 j0Z0Z0Z0
a b c d e f g h
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0Z0Z0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 j0Z0Z0Z0
a b c d e f g h
SLIKA 2.
Šahovnici s prepo-
vedanimi polji
po vsakem koraku približa, na šahovnici pa sta polji
(p, q) in (r , s), na kateri kralj zaradi ovir ne more
stopiti?
Tedaj je pomembno, če je eno od njiju v normal-
nih okoliščinah dosegljivo iz preostalega. V tem pri-
meru je npr. p ≤ r in q ≤ s. Med potmi, ki gredo
posebej čez (p, q) in posebej čez (r , s), so tudi tiste,
ki gredo hkrati čez (p, q) in (r , s). Zato je število
prepovedanih poti
P(p, q; r , s) = D(p,q) ·D(7− p,7− q)+
D(r , s) ·D(7− r ,7− s)−
−D(p,q) ·D(r − p, s − q) ·D(7− r ,7− s).
V primeru nedosegljivosti prepovedanih polj tudi ve-
lja zgornja formula, če postavimo D(x,y) = 0, če je
vsaj eno od števil x in y negativno. Potem je šte-
vilo vseh poti pri danih prepovedanih poljih (p, q)
in (r , s) enako
N(p,q; r , s) = D(7,7)− P(p, q; r , s).
Na sliki 2 desno sta prepovedani polji (3,4) in (5,5).
V tem primeru je
N(3,4; 5,5) = D(7,7)−D(3,4) ·D(4,3)−
−D(5,5) ·D(2,2)+D(3,4) ·D(2,1) ·D(2,2) =
= 48639−1292 −1683 · 13+ 129 · 5 · 13=18504.
Kljub omejitvam je število poti s polja (0,0) na polje
(7,7) še vedno veliko: kar 18504. Rezultat lahko
preverimo tudi s tabelo.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
i 0 1 2 3 4 5 6 7
j a b c d e f g h
0 1 1 1 1 1 1 1 1 1
1 2 1 3 5 7 9 11 13 15
2 3 1 5 13 25 41 61 85 113
3 4 1 7 25 63 129 231 377 575
4 5 1 9 41 192 522 1160 2112
5 6 1 11 61 102 294 1038 2750 6022
6 7 1 13 85 248 644 1976 5764 14536
7 8 1 15 113 446 1338 3958 11698 31998
TABELA 2.
Število poti z oviranim poljem (3,4)
     
P 47 (2019/2020) 4 7
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0Z0Z0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 j0Z0Z0Z0
a b c d e f g h
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0Z0Z0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 j0Z0Z0Z0
a b c d e f g h
SLIKA 3.
Šahovnici z več
prepovedanimi
polji
Prav tako lahko oviramo kralja, da bi stopil na
tri, štiri ali več polj. Pri treh preštejemo prehode
prek enega oviranega polja, preko dveh, kjer je več
možnosti, in preko vseh treh. V bistvu uporabimo
v kombinatoriki znano načelo vključitve-izključitve.
Da se izognemo zapletenim računom, je najenostav-
neje, da naredimo tabelo. Vanjo v celice, ki ustrezajo
oviram, vpišemo črne kvadratke in postopamo tako
kot v tabeli 2. Navajamo primer za ovirana polja, ki
so označena na sliki 3 levo. Število poti s polja (0,0)
na polje (7,7) se je pri postavljenih ovirah drastično
zmanjšalo na 220. Tabeli, ki ustrezata slikama 2 in
3 desno, pa naj na tak način sestavijo bralci. Še eno
vprašanje. Koliko je poti, če postavimo ovire na vsa
polja razen na vertikali a in h ter horizontali 1 in 8?
Literatura
[1] M. Razpet, Poravnava nizov in Delannoyjeva šte-
vila, Obzornik mat. fiz. 58 (2011), št. 4, str. 133–
145.
[2] R. A. Sulanke, Objects counted by the Delannoy
numbers, Journal of Integer Sequences 6 (2013),
članek 03.1.5, 1–19.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
i 0 1 2 3 4 5 6 7
j a b c d e f g h
0 1 1 1 1 1 1 1 1 1
1 2 1 2
2 3 1 2 2 22 2 0 2
3 4 1 4 8 12 2 2 4
4 5 1 6 18 12 14 18 24
5 6 1 8 18 30 56 88 130
6 7 1 218
7 8 1 2 2 2 2 2 2 220
TABELA 3.
Število poti s prepovedjo prehoda
preko več polj (slika 3 levo)
×××