V vsakdanjem življenju se velikokrat znajdemo v situaciji, ko je potrebno neko premoženje razdeliti med več ljudi, tako da se noben ne čuti prikrajšanega.Če gre za premoženje v denarju, je naloga preprosta - vsak upravičenec prejme svoj proporcionalni delež celotnega premoženja. Težava nastopi,če je oblika premoženja takšna, da posamezne dele celote različni upravičenci vrednotijo drugače.

Primer

V nadaljevanju bomo opisali, kako poiskati zadovoljivo delitev premoženja v primeru dveh ali treh upravičencev. Premoženje bomo pri tem nazorno imenovali kolač, upravičence pa igralce. Predpostavili bomo, da lahko kolač delimo v poljubno majhne dele. Pri tem dopuščamo, da vsak igralec po svoje oceni, kolikšen del celote predstavlja posamezen del kolača.

Definicija
Naj bo $\mathcal{D}$ delitev kolača med $n$ igralcev. Delitev $\mathcal{D}$ je proporcionalna, če vsak igralec meni, da je dobil vsaj $n$-ti del kolača. Delitev $\mathcal{D}$ je brez zavisti,če vsak igralec meni, da nihče ni dobil več kot on sam.

Trditev
Vsaka delitev kolača brez zavisti je tudi proporcionalna.

Dokaz

Na tem mestu se seveda postavi vprašanje, ali morda pojma "delitev brez zavisti" in "proporcionalna delitev" kar sovpadata. Če kolač delimo med dva igralca, je temu gotovo tako, saj pri proporcionalni delitvi vsak igralec meni, da je dobil vsaj pol kolača, od koder sledi, da drugi igralec ni mogel dobiti več kot on sam. Kot kaže naslednji zgled, pa pri več kot dveh igralcih temu ni več tako.

Zgled

Postopek delitve kolača med dva igralca je preprost. V prvem koraku eden od igralcev (denimo $A$) razreže kolač na dva kosa, v drugem koraku pa igralec $B$ izbere enega od kosov zase. če je igralec $A$ v prvem koraku kolač razdelil na dva, po njegovem enako velika kosa, bo ne glede na izbiro igralca $B$ po njegovem prejel polovico kolača. Zato $A$ ne zavida igralcu $B$. Seveda pa tudi igralec $B$, ki seveda izbere večjega od obeh kosov (oziroma katerega koli,če sta po njegovem enako velika), ne zavida igralcu $A$. Dobljena delitev kolača je tako brez zavisti.

Zaradi rezanja in izbiranja se zgoraj opisani postopek imenuje tudi reži in izberi.

Oglejmo si še postopek delitve kolača med tri igralce, denimo $A$, $B$ in $C$, ki vsakemu od njih, če le postopa razumno, zagotavlja, da po končani delitvi ne bo zavidal nikomur. Postopek bomo opisali v obliki korakov. Ob vsakem koraku bomo tudi navedli, kako naj posamezni igralec ravna, da na koncu ne bo zavidal nikomur.

1. Igralec $A$ naj razreže kolač na tri dele

Komentar

2. Igralec $B$ lahko bodisi ne stori nič bodisi od enega od treh kosov odreže del in ga da na stran. V slednjem primeru imenujmo zmanjšani kos $Z$, odrezani del pa $O$. Z odrezkom $O$ se do nadaljenga ne bomo ukvarjali.

Komentar

3. Igralci naj si zaporedoma izberejo po en kos (ne upoštevajoč odrezka $O$). Najprej naj svoj kos izbere igralec $C$, nato igralec $B$ in nazadnje igralec $A$.Če je igralec $B$ v prejšnjem koraku kos zmanjšal, mora zdaj izbrati zmanjšani kos $Z$, razenče ga ni pred njim izbralže igralec $C$.Če v drugem koraku igralec $B$ ni odrezal dela $O$, je s tem delitev končana. Sicer pa si naj igralci razdelijoše odrezek $O$, kot je opisano v nadaljevanju.

Komentar

4. Tisti od igralcev $B$ in $C$, ki ni prejel kosa $Z$, naj razreže odrezek $O$ na tri dele. Tega igralca bomo imenovali delilec, drugega od igralcev $B$ in $C$ pa nedelilec.

Komentar

5. Igralce izberejo vsak svoj kos odrezka v naslednjem vrstnem redu: Najprej nedelilec, nato igralec $A$ in nazadnje delilec.

Komentar

Komentarji pri posameznih korakih kažejo, da je delitev, dobljena po opisanem postopku (in pri predpostavki, da se vsi igralci odločajo razumno) brez zavisti.

S podobno enostavnim postopkom lahko dosežemo proporcionalno delitev tudi v primeru poljubno velikegaštevila igralcev. Delitev brez zavisti je pri večjemštevilu igralcev precej težje doseči.

Temelj življenja v skupnosti je sposobnost sporazumnega odločanja tudi v primeru, ko imajo člani skupnosti različna mnenja. V moderni demokraciji odločanje v skupnosti navadno temelji na takšnem ali drugačnem večinskem načelu - odločitev se sprejme, če zanjo glasuje dovolj velika večina članov. Običajno odločanje poteka po načelu "en človek en glas". Obstajajo pa primeri, ko glasovi posameznih članov skupnosti niso enakomerno porazdeljeni. Primer takšne situacije je odločanje na skupščini delničarjev delniške družbe, pri kateri je število glasov posameznega delničarja sorazmerno s številom delnic, ki so v njegovi lastni. Vprašanje, s katerim se bomo ukvarjali v tem poglavju, je, ali je dejanska moč odločanja posameznika sorazmerna s številom glasov (njegovo težo), ki mu pripadajo.

Zgodovinski zgled

Zgoraj opisano neskladje med številom glasov in dejansko močjo soodločanja poskusimo pojasniti z matematičnimi sredstvi. Mislimo si, da pri odločanju sodeluje $n$ igralcev, imenujmo jih $P_1, P_2, \ldots, P_n$. Vsakemu igralcu $P_i$ priredimo njegovo utež $\alpha_i$ z intervala med $0$ in $1$ in predpostavimo, da je vsota uteži vseh igralcev enaka $1$. Poljubni podmnožici množice $\{P_1, P_2, \ldots, P_n\}$ rečemo koalicija. Teža koalicije je definirana kot vsota uteži posameznih članov koalicije. Pribijmo realno število $r$, $\frac{1}{2} < r \le 1$, in ga imenujmo prag odločanja. Za koalicijo pravimo, da je zmagovalna (glede na prag $r$), brž ko je njena teža vsaj $r$.

Član $P$ zmagovalne koalicije $\mathcal{K}$ je kritičen, če koalicija $\mathcal{K} \setminus \{P\}$ ni več zmagovalna. Ideja, ki se strinja v ozadju definicije Banzhafovega indeksa je prepričanje, da je moč soodločanja igralca tem večja, v čim več zmagovalnih koalicijah nastopa kot kritični člen.

Naj torej $N(P)$ označuje število vseh zmagovlani koalicij, v kateri je igralec $P$ kritičen. Tedaj je absolutni Banzhafov indeks igralca $P$ definiran kot

$$B(P) = \frac{N(P)}{2^{n-1}},$$

relativni Banzhafov indeks pa kot

$$B_r(P) = \frac{B(P)}{S},\> \hbox{ kjer je } \> S = B(P_1) + B(P_2) + \ldots + B(P_n).$$

Hitro se prepričamo, da je vsota relativnih Banzhofovih indeksov vseh igralcev enaka $1$:

$$B_r(P_1) + B_r(P_2) + \ldots + B_r(P_n) = \frac{B(P_1)}{S} + \frac{B(P_2)}{S} + \ldots + \frac{B(P_n)}{S} =$$ $$= \frac{B(P_1) + B(P_2) + \ldots + B(P_n)}{S} = \frac{S}{S} = 1.$$

V tem smislu lahko relativni Banzhafov indeks razumemo kot odstotek dejanske moči odločanja posameznega igralca.

Za prvi zgled izračunajmo Banzhafov indeks treh igralcev $A$, $B$ in $C$, katerih uteži so porazdeljene takole: Igralec $A$ naj nosi $47\%$ glasov, $B$ $44\%$ in $C$ $9\%$ glasov. Prag odločanja postavimo na $51\%$. Bežen pogled na razdelitev glasov pokaže, da je za sprejem sklepa potrebna podpora vsaj dveh igralcev - in to katerih koli dveh igralcev. Kljub občutni razliki v teži imajo vsi trije igralci enako moč pri sprejemanju odločitev. če naj Banzhafov indeks pravilno odraža volilne moči, bi moral biti pri vseh treh igralcih enak. Pa ga izračunajmo.

Najprej poiščemo vse možne koalicije. Teh je $2^n$, kjer je $n$ število igralcev, sistematično pa jih naštejemo tako, da navedemo vsa možna zaporedja ničel in enic dolžine $n$, pri čemer posamezno zaporedje interpretiramo kot tisto koalicijo, katere člani so natanko tisti igralci, pri katerih stoji enica. Pri vsaki koaliciji izračunamo njeno težo in glede na prag odločimo, ali je zmagovalna. Nazadnje pri vsaki zmagovalni koaliciji poiščemo še kritične člane.

Rezultati postopka

Na državnozborskih volitvah leta 2008 smo državljani porazdelili poslanske sedeže med sedem političnih strank na način, kot kaže spodnja tabela. Poleg 88 sedežev, ki jih zasedajo čani strank, Ustava zagotavlja tudi dva sedeža za predstavnika italijanske in madržarske skupine. V nadaljevanju bomo na ta dva predstavnika gledali kot na samostojno poslansko skupino (tj. stranko), ki jo bomo označevali z NS (narodne skupnosti).

Porazdelitev poslanskih sedežev

Za izračun Banzhafovega indeksa moramo pregledati $2^8=256$ možnih koalicij (v resnici je potrebno obravnavati le zmagovalne koalicije, ki jih je občutno manj).

Pojasnilo

Banzhafovi indeksi

Leta 1997 smo imeli v Sloveniji predsedniške volitve, na katerih je kandidiralo osem predsedniških kandidatov: Bernik, Cerar, Kovač, Kučan, Miklavič, Peršak, Podobnik in Poljšak. V predvolilnem času je nacionalna televizija organizirala osem soočenj kandidatov, pri čemer so na vsakem soočenju sodelovali trije izmed osmih kandidatov. Ker so se na televiziji odločili za ravno toliko soočenj kot je bilo kandidatov, so lahko soočenja organizirali tako, da je vsak izmed kandidatov nastopil enako mnogokrat - tako nenazadnje veleva tudi zakon.

Kljub temu pa pozornemu gledalcu ni ušlo, da sta se Kučan in Podobnik srečala na dveh soočenjih, medtem ko se nekateri pari kandidatov sploh niso srečali. Takšno neravnovesje bi morda nekateri lahko razumeli kot favoriziranje kandidatov Kučana in Podobnika. Bi se televizija tej nerodnosti lahko izognila? Vprašanje torej je: Ali obstaja razpored osmih soočenj osmih kandidatov - po trije na vsakem soočenju - pri katerem se vsak par sreča največ enkrat?

Nalogo razporeda soočenj lahko matematično formuliramo v jeziku kombinatoričnih konfiguracij.

Definicija
Naj bo $\mathcal{V}$ poljubna neprazna končna množica in $\mathcal{B}$ poljubna družina podmnožic množice $\mathcal{V}$; elemente množice $\mathcal{V}$ imenujmo točke, elemente množice $\mathcal{B}$ pa bloki ali tudi premice. Tedaj paru $(\mathcal{V},\mathcal{B})$ rečemo kombinatorična konfiguracija, če so izpolnjeni naslednji trije aksiomi.

Aksiomi

Če z $v=|\mathcal{V}|$ označimo število točk, z $b=|\mathcal{B}|$ pa število blokov, tedaj rečemo, da je takšna konfiguracija tipa $(v_r;b_k)$. Kadar je $v=b$ in $r=k$, govorimo o simetrični konfiguraciji tipa $(v_r)$.

Vprašanje "poštenega" razporeda soočenj osmih kandidatov s predsedniških volitev leta $1997$ se torej prevede na vprašanje obstoja kombinatorične konfiguracije tipa $(8_r;8_3)$. Pri tem za množico točk vzamemo kar množico predsedniških kandidatov, vsak posamezni blok pa razumemo kot trojico kandidatov, ki so se srečali na danem soočenju.

Premislimo najprej, da lahko število $r$ (tj. število pojavitev posameznega kandidata v osmih soočenjih) določimo na podlagi ostalih podatkov. Splošneje, dokažimo, da velja naslednja trditev.

Trditev
Če obstaja kombinatorična konfiguracija tipa $(v_r;b_k)$, tedaj je $vr=bk$.

Dokaz

Od tod sledi, da je pri iskani konfiguraciji tipa $(8_r;8_3)$ parameter $r$ enak $3$. Iščemo torej simetrično konfiguracijo tipa $(8_3)$.

Izkaže se, da obstaja (do preimenovanja točk natančno) natanko ena simetrična konfiguracija tipa $(8_3)$. Imenuje se Möbius-Kantorjev konfiguracija in je definirana takole:

$\mathcal{V}$ = $\{0,1,2,3,4,5,6,7\}$,
$\mathcal{B}$ = $\{ \{0,1,3\}, \{1,2,4\}, \{2,3,5\}, \{3,4,6\}, \{4,5,7\}, \{5,6,0\}, \{6,7,1\}, \{7,0,2\}\}$.

Če števila $0,1,2,\ldots, 7$ nadomestimo z imeni osmih predsedniških kandidatov, dobimo optimalni razpored soočenj, ki bi zagotavljal, da se vsaka dva kandidata srečata natanko enkrat. Grafično si lahko konfiguracijo predočimo s pomočjo spodnje sheme.

Pri tej shemi vidimo osem točk: tri oglišča trikotnika, tri razpolovišča trikotnikov in dve točki, ki ležita na presečišču težiščnice in povezovalke dveh razpolovišč stranic. Vidimo tudi osem črt: tri stranice trikotnika, dve težiščnici, dve povezovalki razpolovišč stranic in eno krivo črto. Vsaka točka leži na natanko treh črtah in vsaka črta vsebuje natanko tri točke. Vsaki dve točki ležita na največ eni črti. Obstajajo pa tudi štirje pari točk, ki ne ležijo na nobeni črti. To so pari $\{0,4 \}$, $\{1,5 \}$, $\{2,6 \}$ in $\{3,7 \}$.

V kombinatorični konfiguraciji zahtevamo, da se vsaki dve točki pojavita v natanko enem bloku. Premislimo, koliko parov točk $\{x,y\} \subseteq \mathcal{V}$, $x\not = y$, v kombinatorični komnfiguraciji tipa $(v_r;b_k)$ je takšnih, da niso vsebovani v nobenem bloku iz (za točki, ki tvorita takšen par, bomo rekli, da se ne srečata).

Dokažimo najprej naslednji pomožni rezultat.

Lema
Naj bo $A$ poljubna množica z $n$ elementi. Tedaj je število neurejenih parov $\{x,y\} \subseteq A$, $x\not = y$, množica $A$ enako

$${n \choose 2} = \frac{n(n-1)}{2}.$$

Dokaz

Iz zgornje trditve sledi, da je vseh parov $\{x,y\}$ točk iz $\mathcal{V}$ ravno $\frac{v(v-1)}{2}$, v posamičnem bloku pa se pojavi natanko $\frac{k(k-1)}{2}$ parov. Ker je blokov $b$, vsak par pa se pojavi v največ enem bloku, se torej v vseh blokih skupaj pojavi natanko $b\frac{k(k-1)}{2}$ parov. Od tod sledi naslednja trditev.

Trditev
V kombinatorični konfiguraciji tipa $(v_r;b_k)$ je natanko

$${v \choose 2} - b {k\choose 2} = \frac{v(v-1) - bk(k-1)}{2}$$

takšnih parov, ki se v konfiguraciji ne srečajo.

Če se omejimo na konfiguracije tipa $(v_3)$, dobimo naslednjo posledico zgornje trditve.

Posledica

Kot smo že ugotovili v prejšnjem razdelku, se v Möbius-Kantorjevi konfiguraciji, ki je tipa $(8_3)$, ne srečajo štirje pari.

Pričnimo poglavje z naslednjo nalogo, ki jo je daljnega leta 1850 v ameriški družabni reviji Lady's and Gentleman's Diary objavil Thomas Kirkman.
Naloga se glasi takole:
Petnajst šolark se sprehaja vsak dan v tednu v petih vrstah, po tri v vrsti. Organiziraj njihove sprehode tako, da nobeni dve ne bosta hodili v isti vrsti več kot enkrat. (V angleškem orignalu: Fifteen young ladies of a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk abreast more than once.) Ker ima teden sedem dni, v enem tednu šolarke oblikujejo $7\cdot 5 = 35$ vrst (vsak dan po $5$). Ker gre vsaka šolarka na sprehod vsak dan v tednu, pomeni, da se pojavi v natanko sedmih trojkah. Če z $\mathcal{V}$ označimo množico $15$ šolark, z $\mathcal{B}$ pa množico $35$ trojk, ki jih v sedmih dneh sprehajanja oblikujejo šolarke, nam pogoj, da se nobeni dve šolarki ne sprehajata v isti vrsti več kot enkrat, zagotovi, da je par $(\mathcal{V},\mathcal{B})$ kombinatorična konfiguracija tipa $(15_7;35_3)$. Pa vstavimo podatke $v=15$, $r=7$, $b=35$ in $k=3$ v formulo:

$$\frac{v(v-1) - bk(k-1)}{2} = \frac{15\cdot 14 - 35 \cdot 3 \cdot 2}{2} = 0.$$

To pa pomeni, da se pri takšnem razporedu sprehodov vsaki dve šolarki sprehajata v isti vrsti natanko enkrat (in ne zgolj največ enkrat) na teden. Iskana konfiguracija šolark in trojk ima torej dodatno lastnost, da se v njej prav vsak par šolark sreča natanko enkrat. Pri tem rečemo, da par $(\mathcal{V},\mathcal{B})$ tvori Steinerjev sistem trojk.

Definicija
Naj bo $\mathcal{V}$ poljubna neprazna množica in $\mathcal{B}$ množica nekih trielementnih podmnožic množice $\mathcal{V}$. Če za vsak par $\{x,y\} \subseteq \mathcal{V}$, $x\not = y$, obstaja natanko ena trojka $B\in \mathcal{B}$, ki vsebuje tako $x$ in $y$, potem rečemo, da par $(\mathcal{V},\mathcal{B})$ tvori Steinerjev sistem trojk.

Ker v zgornji definiciji ne zahtevamo izrecno, da je vsaka točka vsebovana v istem številu blokov, ni povsem očitno, da je Steinerjev sistem trojk nujno tudi kombinatorična konfiguracija. Da je temu tako, bomo med drugim dokazali v naslednji trditvi.

Izrek:
Za par $(\mathcal{V},\mathcal{B})$, $|cV| = v$, $|\mathcal{B}|=b$, sta ekvivalentni naslednji trditvi:
(i) $(\mathcal{V},\mathcal{B})$ je Steinerjev sistem trojk;
(ii) $(\mathcal{V},\mathcal{B})$ je kombinatorična konfiguracija tipa $(v_r;b_k)$, kjer je $k=3$, $r=\frac{v-1}{2}$ in $b=\frac{v(v-1)}{6}$.

Dokaz

Trditev
Če obstaja Steinerjev sistem trojk z $v$ točkami, tedaj je $v$ oblike $6t+1$ ali pa oblike $6t-3$ za neko naravno število $t$.

Dokaz

V resnici velja tudi obrat zgornje trditve: Za vsako število $v$ oblike $6t-3$ ali $6t+1$, $t\in \mathbb{N}$, obstaja Steinerjev sistem trojk z $v$ točkami. To dejstva je precej težje dokazati kot zgornjo trditev.

Vrnimo se sedaj prvotni nalogi o petnajst šolarkah. Pri tej nalogi iščemo sistem trojk $(\mathcal{V},cB)$ na $v=15$ točkah z dodatno lastnostjo, da lahko množico $b=\frac{v(v-1)}{6} = \frac{15\cdot 14}{6} = 35$ trojk zabijemo v sedem skupin (dni) po pet trojk (vrste v sprehodu danega dne), tako da se v vsaki skupini vsaka točka pojavi natanko enkrat. Steinerjevim sistemom trojk, ki omogočajo takšno razbitje množice trojk pravimo tudi Kirkmanovi sistemi trojk.

Trditev
Če obstaja Kirmanov sistem trojk na $v$ točkah, je $v=6t-3$ za neko naravno število $t$.

Podobno kot pri Steinerjevih sistemih tudi tu velja obrat zgornje trditve, ki pa ga je zelo težko dokazati: Za vsako število $v$ oblike $6t-3$, $t\in \mathbb{N}$, obstaja Kirmanov sistem trojk na $v$ točkah. To nam pove, da je osnovni Kirkmanov problem s $15$ šolarkami rešljiv, saj je $15=6\cdot 3 - 3.$ Eno od možnih rešitev si lahko ogledate, denimo, na Wikipediji.

Legenda pravi, da je Katarina Velika Eulerju, ko je le-ta živel na njenem dvoru, zadala naslednjo nalogo: "Na dvoru bom sprejela predstavnike $6$ regimentov. Vsak regiment bo predstavljalo $6$ žastnikov, po en žastnik vsakega od $6$ činov. Razvrsti teh 36 častnikov v $6\times 6$ formacijo tako, da bo v vsaki vrsti in v vsaki koloni natanko en častnik iz vsakega regimenta in natanko en častnik vsakega čina."

Euler naj bi po daljšem iskanju rešitve obupal in Carici Katarini zagotovil, da takšen razpored ni možen. Da bi svojo trditev tudi ustrezno matematično podkrepil, je pričel raziskovati tako imenovane latinske kvadrate.

Latinski kvadrat velikosti $n$ je razporeditev Števil $N=\{1,2,\ldots,n\}$ (ali elementov katere koli druge $n$ elementne mnoŽice) v $n\times n$ mrežo, pri kateri se v vsaki vrstici mreže in v vsakem stolpcu mreže pojavi vsako število iz množice $N$ natanko enkrat. Zgledov latinskih kvadratov ni težko najti. Najpreprostejši način konstrukcije latinskega kvadrata velikosti $n$ je naslednji: V prvo vrstico kvadrata zapovrstjo navedemo števila $1,2, \ldots, n$. V drugo vrstico navedemo ta-ista števila v zamaknenjem vrstnem redu: $2,3,\ldots, n, 1$. Postopek nadaljujemo tako, da v vsaki naslednji vrstici števila iz prejšnje vrstice ciklično zamaknemo še za eno mesto v levo. Tako v tretji vrstici dobimo števila z vrstnim redom $3,4,\ldots, n,1,2$. Končamo z $n$-to vrstico, v kateri so števila navedena v vrstnem redu $n,1,2, \ldots, n-1$.

$$\left[ \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 4 & 5 & 6 & 1 \\ 3 & 4 & 5 & 6 & 1 & 2 \\ 4 & 5 & 6 & 1 & 2 & 3\\ 5 & 6 & 1 & 2 & 3 & 4\\ 6 & 1 & 2 & 3 & 4 & 5 \end{matrix} \right]$$

S pomočjo latinskega kvadrata velikosti $6$ lahko Eulerjevo nalogo rešimo "na pol". Dosežemo namreč lahko, da se v vsaki vrstici in vsakem stolpcu pojavi natanko en predstavnik vsakega od šestih regimentov. To pač storimo tako, da vse častnike 1. regimenta označimo s številom $1$, častnike 2. regimetna s številom $2$ itd. Latinski kvadrat velikosti $6$ nam potem predstavlja raporeditev častnikov glede na njihovo pripadnost regimentom. Seveda nam takšna rešitv še ne zagotavlja, da se bo v vsaki vrstici in vsakem stolpcu pojavil vsak čin natanko enkrat.

Podobno bi lahko latinski kvadrat velikosti $6$ uporabili za razvrstitev, pri kateri bi se vsak posamezni čin pojavil v vsaki vrstici in vsakem stolpcu natanko enkrat - le števila med $1$ in $6$ bi morali interpretirati kot čine namesto kot regimente. Če nam uspe dva latinska kvadrata (enega, ki podaja razporeditev regimentov, in drugega, ki podaja razporeditev po činih) združiti na tak način, da vsako kombinacijo čina in regimenta podamo natanko enkrat, smo nalogo častnikov rešili.

Preden nadaljujemo z Eulerjevim problemom častnikom, si oglejmo, ali znamo latinske kvadrate velikosti $n$ konstruirati še kako drugače.

Za naravni števili $n$ in $x$ naj $x \mod n$ označuje ostanek števila $x$ pri deljenju z $n$ in naj

$$\mathbb{Z}_n = \{0,1,\ldots, n-1\}$$

označuje množico vseh možnih ostankov pri deljenju s številom $n$. Za $x,y\in \mathbb{Z}_n$ definirajmo

$$x\oplus y = x + y \mod n \quad \hbox{ in } x\odot y = xy \mod n.$$

Ni se težko prepričati, da operaciji $\oplus$ in $\odot$ zadoščata mnogim običajnim pravilom, ki veljajo za običajno seštevanje in množenje v množici celih števil. Na primer, za poljubne $x,y,z\in \mathbb{Z}_n$ velja naslednje:
1. $x \oplus y = y\oplus x$ in $x \odot y = y\odot x$ (komutativnost);
2. $(x \oplus y) \oplus z = x\oplus (y\oplus z)$ in $(x \odot y) \odot z = x\odot (y\odot z)$ (asociativnost);
3. $(x \oplus y) \odot z = (x\odot z) \oplus (y\odot z)$ (distributivnost);
4. $x\oplus 0 = x$, $x\odot 0 = 0$, $x\odot 1 = x$;
5. Za vsak $a\in \mathbb{Z}_n$ obstaja neki $b\in \mathbb{Z}_n$, za katerega je $a \oplus b = 0$ (namreč, za $b$ lahko vzamemo element $n-a$).

Če za kako število $x\in \mathbb{Z}_n$ obstaja število $y\in \mathbb{Z}_n$, za katerega velja, da je $x\odot y = 1$, potem rečemo, da je $y$ multiplikativni inverz elementa $x$ in ga označimo z $x^{-1}$, za število $x$ pa rečemo, da je obrnljivo. Množico obrnljivih števil v $\mathbb{Z}_n$ označimo z $\mathbb{Z}_n^*$.

Na primer, v $\mathbb{Z}_5$ velja $2\odot 3 = 6\mod 5 = 1$, zato je $3^{-1} = 2$ in seveda $2^{-1} = 3$. Velja tudi $1^{-1} = 1$ in $4^{-1} = 4$ (saj $4\odot 4 = 16 \mod 5 = 1$). Po drugi strani pa $0$ ni obrnljiv element, saj je $0\odot x = 0 \not = 1$ za vsak $x\in \mathbb{Z}_5$. Zato je

$$\mathbb{Z}_5^* = \{1,2,3,4\}.$$

Nekoliko drugačna je situacija v množici $\mathbb{Z}_6$. Tam sta ponovno obrnljiva elementa $1$ in $5$, saj je $1^{-1} = 1$ in $5^{-1} = 5$, med tem ko elementi $0,2,3$ in $4$ niso obrnljivi. Denimo, če bi $2$ bil obrnljiv element in bi bil $x$ njegov inverz, bi veljalo

$$3 = 1\odot 3 = (x\odot 2) \odot 3 = x \odot (2\odot 3) = x \odot 0 = 0,$$

kar je očitno protislovje. Podobno poteka premislek za števila $0,3$ in $4$. Zato velja

$$\mathbb{Z}_6^{*} = \{1,5\}.$$

V splošnem velja naslednja trditev, ki pa je ne bomo dokazali.

Trditev
V množici $\mathbb{Z}_n$ so obrnljiva natanko tista neničelna števila, ki so tuja številu $n$. Če je $n$ praštevilo, so v $\mathbb{Z}_n$ torej obrnljivi vsi neničelni elementi.

Operaciji $\oplus$ in $\odot$ lahko uporabimo za konstrukcijo latinskih kvadratov na naslednji način. Izberimo obrnljiv element $a\in\mathbb{Z}_n^*$ in konstruirajmo matriko $L_a(n)$ velikosti $n\times n$, katere vrstice in stolpce oštevilčimo z elementi $0,1,\ldots, n-1\in \mathbb{Z}_n$. Na presečišče vrstice $x\in \mathbb{Z}_n$ in stolpca $y\in \mathbb{Z}_n$ v $L_a(n)$ vstavimo element $a\odot x + y$. Predem dokažemo, da smo tako res dobili latinski kvadrat, si oglejmo konkretni zgled. Naj bo $n=5$ in $a=2$. Tedaj je

$$L_2(5) = \begin{array}{cc} \begin{array}{c} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left[ \begin{array}{ccccc} 0 & 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 0 & 1 \\ 4 & 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 & 0 \\ 3 & 4 & 0 & 1 & 2 \end{array} \right] \\ & \\ & \begin{array}{ccccc} 0 & 1 & 2 & 3 & 4 \end{array} \end{array}$$

Trditev
Če je $a$ obrnljiv element množice $\mathbb{Z}_n$, tedaj je $L_a(n)$ latinski kvadrat.

Dokaz

Naj bosta $A$ in $B$ dva latinska kvadrata velikosti $n$ zapolnjena s števili $N=\{1,2,\ldots, n\}$. Element, ki stoji na presečišču $i$-te vrstice in $j$-tega stolpca matrike $A$ označimo z $a_{ij}$, enako ležeči element v matriki $B$ pa z $b_{ij}$. Za latinska kvadrata $A$ in $B$ pravimo, da sta ortogonalna, če za vsak urejeni par $(x,y) \in N\times N$ obstaja natanko en par indeksov $i,j\in \{1,\ldots,n\}$, tako da je $a_{ij} = x$ in $b_{ij} = y$. Z drugimi besedami, $A$ in $B$ sta ortogonalna, če pari $(a_{ij}, b_{ij})$ enako ležečih elementov iz $A$ in $B$ opišejo celotno množico urejenih parov iz $N\times N$.

Za zgled si oglejmo naslednje tri latinske kvadrate velikosti $4$.

$$A = \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \end{array} \right], \quad B = \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3\\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{array} \right], \quad C=\left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2\\ 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \end{array} \right].$$

Kvadrata $A$ in $B$ nista ortogonalna, saj se denimo par $(1,1)$ pojavi na dveh mestih (skrajno levo zgoraj in na tretjem mestu glavne diagonale), par $(1,2)$ pa se sploh ne pojavi. Po drugi strani pa kvadrata $A$ in $C$ sta pravokotna, v kar se najlažje prepričamo, če sestavimo kvadrat parov in preverimo, da se v njem res pojavijo vsi pari števil med $1$ in $4$ (vsak natanko enkrat).

$$(B,C) = \left[ \begin{array}{cccc} (1,1) & (2,2) & (3,3) & (4,4) \\ (2,3) & (1,4) & (4,1) & (3,2) \\ (3,4) & (4,3) & (1,2) & (2,1) \\ (4,2) & (3,1) & (2,4) & (1,3) \end{array} \right]$$

Par ortogonalnih latinskih kvadratov velikosti $n$ lahko uporabimo za rešitev različice Eulerjeve naloge z $n$ častniki iz $n$ regimentov. Na primer, če regimente označimo z $a,b,c$ in $d$, čine pa z gen, pol, maj in por, tedaj iz zgornjega para kvadratov dobimo zahtevano razporeditev častnikov, če prve komponente parov zamenjamo po pravili $1\mapsto$ gen, $2\mapsto$ pol, $3\mapsto$ maj in $4\mapsto$ por, druge komponente pa po pravilu $1\mapsto a$ , $2\mapsto b$, $3\mapsto c$ in $4\mapsto d$. Tako dobimo naslednjo razporeditev:

$$\left[ \begin{array}{cccc} (\hbox{gen},a) & (\hbox{pol},b) & (\hbox{maj},c) & (\hbox{por},d) \\ (\hbox{pol},c) & (\hbox{gen},d) & (\hbox{por},a) & (\hbox{maj},b) \\ (\hbox{maj},d) & (\hbox{por},c) & (\hbox{gen},b) & (\hbox{pol},a) \\ (\hbox{por},b) & (\hbox{maj},a) & (\hbox{pol},d) & (\hbox{gen},c) \end{array} \right]$$

Poglejmo si sedaj kako poiskati par ortogonalnih latinskih kvadratov velikosti $n$ za vsako liho število $n$.

Izrek
Naj bo $n$, $n\ge 3$, naravno število in naj bosta $a$ in $b$ obrnljiva elementa množice $\mathbb{Z}_n$, za kateri je tudi razlika $|b-a|$ obrnljiva v $\mathbb{Z}_n$. Tedaj sta $L_a(n)$ in $L_b(n)$ ortogonalna latinska kvadrata velikosti $n$.

Dokaz

Posledica

Dokaz

V prejšnjem razdelku smo videli, kako Eulerjevo rešimo nalogo za liho število regimentov. Kaj pa, če je regimentov sodo mnogo, kot je to primer v originalni Eulerjevi nalogi ($n=6$). Izkaže se, da je naloga rešljiva prav za vse $n$, razen za $n=2$ in $6$. Ršitev za števila $n$, ki so deljiva s $4$ je dokaj enostavno poiskati (pomagamo si z rešitvijo za $n=4$, ki smo jo navedli zgoraj), za števila, ki pa dajo ostanek $2$ pri deljenju s $4$ pa je konstrukcija mnogo težja.

Igra nim je igra za dva igralca, ki izmenično jemljeta vžigalice s treh kupčkov, pri čemer sme igralec na potezi vzeti s poljubnega (vendar le enega) kupčka poljubno število vžigalic (vsaj eno, lahko pa tudi vse). Zmaga igralec, ki vzame zadnjo vžigalico. Koliko vžigalic naj bo na kupih, da bo igra dobljena za igralca na potezi (ob njegvi pravilni igri, seveda) in koliko, da bo dobljena za igralca, ki ni na potezi?

Vzemimo naravni števili $a$ in $b$ ter ju zapišimo dvojiško (po potrebi manjšemu od števil dodajmo na začetek nekaj ničel, da bosta obe števili imeli enako dolg zapis):

$$a={a_0\; + \; a_1 \cdot 2\; + \; a_2 \cdot 2^2 \; + \ldots + \; a_n \cdot 2^n \; = \; a_n a_{n-1} \ldots a_0}_{(2)} \> ; \quad a_i \in \{0,1 \}$$ $$b={b_0\; + \; b_1 \cdot 2\; + \; b_2 \cdot 2^2 \; + \ldots + \; b_n \cdot 2^n \; = \; b_n b_{n-1} \ldots b_0}_{(2)} \> ; \quad b_i \in \{0,1 \}$$

Nim-vsoto števil $a$ in $b$ definirajmo na običajen način, le da pri seštevanju v kupčku ne prenašamo viška v naslednji stolpec. Da ne bo prihajalo do zmede, bomo nim-seštevanje označevali s $\oplus$, navadno pa s $+$. Velja torej

$$c=a\oplus b\> , \quad \hbox {kjer} \quad c={c_n c_{n-1} \ldots c_o}_{(2)} \> , \quad c_k=a_k + b_k \mod 2 \> .$$

Oglejmo si zgled. Vzemimo $a=5=101_{(2)}$ in $b=3=11_{(2)}$

$$\begin{array}{r} 101 \\ 011 \\ \hline 110 \end{array}$$

Ko smo v skrajno desnem stolpcu sešteli $1+1$, smo dobili $2$ kar je po modulu $2$ enako $0$. Dobljeni rezultat ponovno interpretiramo kot število v dvojiškem zapisu in dobimo

$$5\oplus 3 = 110_{(2)} = 6.$$

Izrek
Igra nim je v poziciji $(x,y,z)$ dobljena za igralca na potezi, če in samo če je nim vosta $x\oplus y \oplus z$ neničelna. Zmagovalna poteza je tista, ki prevede igro v pozicijo z nim-vsoto enako $0$.