Primož Potočnik
Zapiski predavanj iž
Matematike v Praksi
Ljubljana, marec 2011
Naslov: Zapiski predavanj iz Matematike v praksi Avtor: PrimoZ Potočnik 1. izdaja
Dostopno na spletnem naslovu www.fmf.uni-lj.si/~potocnik
CIP - KataloZni zapis o publikaciji Narodna in univerzitetna knjiZnica, Ljubljana
51-7(0.034.2) 51-8(0.034.2)
POTOČNIK, Primoz, 1971 -
Zapiski predavanj iz Matematike v praksi [Elektronski vir] Primoz Potočnik. - 1. izd. - El. knjiga. - Ljubljana : samozal., 2011
Način dostopa (URL):
http://www.fmf.uni-lj.si/~potocnik/Ucbeniki/MaPra-zapiski.pdf
ISBN 978-961-93056-0-7 255518976
Izdano v samozalozbi marca 2011. Avtor si pridrzuje vse pravice.
Kazalo
1	V banki............................................................5
1.1	Varčevanje za eno leto....................................5
1.2	Krajše kapitalizacijske dobe..............................7
1.3	Krediti in anuitete........................................9
2	Pravična delitev kolača............................................11
2.1	Proporcionalna delitev in delitev brez zavisti..........11
2.2	Delitev za dva igralca: rezi in izberi....................12
2.3	Delitev brez zavisti za tri igralce........................12
3	Volilna moc........................................................15
3.1	Banzhafov indeks volilne moci............................15
3.2	Zgledi......................................................16
3.3	zdruzevanje igralcev......................................18
3.4	Volilna moc strank v Drzavnem zboru..................20
4	Posteni razporedi soocenj ........................................22
4.1	Kombinatorcne konfiguracije ............................22
4.2	Mobius-Kantorjeva konfiguracija........................23
4.3	Pari, ki se ne srecajo......................................24
5	Steinerjevi sistemi trojk..........................................27
5.1 Kirkmanovi sistemi trojk ................................29
6	Eulerjev problem 36 castnikov....................................30
6.1	Latinski kvadrati..........................................30
6.2	Modularna aritmetika....................................31
6.3	Konstrukcija latinskih kvadratov........................32
6.4	Pari ortogonalnih latinskih kvadratov ..................33
6.5 Resljivost Eulerjeve naloge ..............................34
7	Igra nim............................................................35
7.1	Nim vsota..................................................35
7.2	Zmagovalna strategija....................................36
8	Zapornikova dilema................................................38
8.1	Nashevo ravnovesje........................................39
8.2	Dominantne akcije........................................41
9	Simpsonov paradoks ..............................................42
9.1	Vpisi na podiplomski studij na univerzi Berkley ....	42
9.2	Uspesnost zdravljenja....................................43
1 V banki
Ce želimo denar, ki ga imamo v žepu danes, shraniti za nakup nečesa v prihodnosti, ga navadno nesemo v banko. Banka nam v zameno za pravico upravljati z nasim denarjem v vmesnem obdobju plača določen znesek, ki je odvisen od količine denarja, ki ji ga zaupamo, in seveda časa lezanja denarja na bančnem računu.
1.1 Varčevanje za eno leto
Denimo, da banka za sredstva na vpogled (sredstva, ki jih lahko kadar koli dvignemo z računa) obljublja o-odstotne obresti. To pomeni, da če na začetku leta na bančni račun polozimo znesek a, nam bo banka ob konču leta poleg zneska a na račun pripisala se obresti v visini o odstotkov od zneska a. Ob konču leta bomo imeli tako na računu
ao	o
a +--= a(1 +--).
100 v 100;
Na primer, če so obresti 2%, na začetku leta pa vlozimo 200 EUR, bomo ob konču leta imeli na računu
2
200(1 + = 204
evrov. Faktor
r = 1 + — = 1 + — = 1,02, 100 100
s katerim pomnozimo začetni znesek (glavnico), da dobimo znesek ob konču prvega leta obrestovanja, imenujemo faktor obrestovanja. Ce znesek ar, ki ga imamo na računu po prvem letu, pustimo obrestovati se eno leto, bomo po drugem letu tako imeli (ar)r = ar2. Ce z varčevanjem nadaljujemo, bomo ob konču n-tega leta imeli na računu
an = ar
Zgled. Koliko let moramo pustiti denar na računu, da se nam bo pri 10% obrestni meri glavnica vsaj podvojila?
Ker je obrestna mera 10%, je obrestovalni faktor enak r = 1 + = 1,1. Ce na začetku na račun polozimo znesek a, bomo po n letih imeli na računu arn. Ce naj bo to vsaj 2a, mora torej veljati
arn 2a.
Iščemo torej najmanjši n, pri katerem je rn > 2. Ce neenakost logaritmi-ramo, dobimo
log(rn) > 2.
Ker je log(rn) = n log(r) in ker je pri r > 1 logaritem log(r) pozitiven, je zgornji pogoj ekvivalenten
^ log(2) 0,69
n > -—H- &-& 6,9.
log(r) 0,10
Od tod sledi, da se nam začetni znesek podvoji ob koncu sedmega leta. ■
Zgornji zgled je pokazal na zanimivo lastnost obrestnega računa: Ce pri obrestni meri o odstotkov varčujemo n let, skupna obrestna mera ob koncu n let ni no odstotkov začetnega zneska (kot bi morda kdo pričakoval), temveč nekoliko več. Koliko več? Za lazje računanje označimo
o
0 = 100.
Na primer, če je obrestna mera 2%, je o = 2, in zato 0 = 0,02. Videli smo, da je ob začetnem vlozku a ob konču leta n skupni znesek na računu enak arn. Ker je bil a nas vlozek, je pridobljenih obresti v n letih torej arn — a = a(rn — 1), kar je ravno
o0n = rn - 1
začetnega vlozka. Ce izrazimo r z obrestno mero o, dobimo
0n = (1 + 0)n — 1 = 1+ n0+ 02 +(n) 03 ... + 0n — 1.
Razlika med naivno pričakovano obrestno mero po n letih varčevanja no in dejansko obrestno mero on je torej
n 2	n 3	n
no — o,n = ( 2J 02 + ^ |03 ... + 0"
Ce obrestna mera znasa le nekaj odstotkov (tj. če je 0 blizu 0 in če stevilo let varčevanja majhno), razlika ni zelo velika. V časih hiperinflačije, ko se obrestne mere povzpnejo na 100 in več odstotkov, pa postane zgornja razlika ogromna. Na primer, če je obrestna mera o = 100%, je 0 = 1 in zato
no — 0n = ( ^ + (n ) ... + 1 = 2n — n — 1
23
Kar zelo hitro raste s stevilom let n.
1.2 KrajSe kapitalizacijske dobe
V prejsnjem razdelku smo si ogledali preprost primer, pri katerem smo denar na racunu pustili polno leto, obresti pa so se pripisale glavnici ob izteku leta. Časovnemu obdobju, po katerem se dogovorjene obresti pripisejo glavnici (so dejansko izplacane) recemo kapitalizacijska doba. Poglejmo si, v kaksne zagate nas lahko pripelje enoletna kapitalizacijska doba.
V primeru enoletne kapitalizacijske dobe, banka obresti pripise glavnici ob koncu koledarskega leta. Če je denar lezal na bancnem racunu od 1. januarja do 31. decembra, ta nacin obrestovanja ne povzroca vecjih tezav Kaj pa naj banka naredi, ce sredstva na racunu ne lezijo polno leto, temvec, na primer, le n-ti del leta, po izteku tega obdobja pa varcevalec zahteva zaprtje racuna z izplacilom glavnice in vseh natecenih obresti?
Se pred nekaj desetletji so banke pri nas v tem primeru izplacale poleg glavnice a se ao/n obresti, skupaj torej a(1 + o/n). Ce je varcevalec nato dobljeni znesek ponovno polozil na nov racun in postopek ponovil, se je po drugem obdobju vlozeni znesek povecal na a(1 + o/n)2. Ce je postopek ponovil n-krat, se je ob koncu koledarskega leta vlozek povecal na
a(1 + -)n. n
Varcevalcev dejanski obrestovalni faktor je na letnem nivoju tako znasal
(1 + -)n n
in ne o, kot je bil prvotni namen banke. Ce je bil varcevalec pri tem zelo hiter, si lahko mislimo, da je stevilo n postalo poljubno veliko in se je s tem varcevalcev dejanski obrestovalni faktor poljubno priblizal limiti
lim (1 + -)n = eo. ra^TO n
Varcevalec je pri taksnem nacinu obrestovanja od banke "izsilil" obrestno mero blizu eo — 1, namesto obrestne mere o. Spomnimo Taylorjeve vrste za eksponento funkcijo:
2	3
ex = 1+ x + + + ...
Razlika med njegovo dejansko letno obrestno mero in obrestno mero, ki jo je nacrtovala banka, je tako znasala priblizno
o	o2 o3
e°— 1 — o = 2! + +...
Ce obrestna mera o znasa nekaj odstotkov do, recimo, 50% (in je zato o nekje
_2
med 0,01 in 0,5), so cleni, ki v zgornji vrsti sledijo clenu °2r, zanemarljivi in je tako zgornja razlika v obrestnih merah priblizno enaka
o! 2!'
Dokler je obrestna mera 0 relativno majhna (nekje med 0 in 5%), zgornja razlika ne preseze bistveno vrednosti 1,052/2 = 0,00125 = 0,125%, kar za banko ni prehud zalogaj. Ko pa so v casih hiperinflacije letne obrestne mere presegle 100%, je razlika med tako izsiljeno obrestno mero in s strani banke predvideno obrestno mero presegla mejo eo — 1 — o = e — 1 — 1 « 0,72 = 72%, kar pa je znesek, ki lahko banko pripelje v tezak polozaj. Zato so banke v casih visoke inflacije prisiljene preiti na krajsa kapitalizacijska obdobja v dolzini enega meseca ali celo dneva.
Denimo, daje tako kapitalizacijska doba enaka n leta. S kaksim obresto-valnim faktorjem naj banka po eni kapitalizacijski dobi pomnozi glavnico, da bo v primeru, da varcevalec drzi celotno glavnico, skupaj z vsemi pri-posanimi obrestmi, na racunu polno leto, koncni obrestovalni faktor enak
r?
Oznacimo iskani obrestovalni faktor z rn. Tedaj bo po prvi kapitalizacijski dobi prvotni vlozek a skupaj z obrestmi narasel na arn. Po drugi kapitalizacijski dobi bo znesek na racunu enak ar2n, po n kapitalizacijskih dobah (se pravi, po enem letu) pa arn. Ker zelimo, da je ta znesek enak znesku, ki bi ga varcevalec dobil, ce bi prvotno glavnico a obrestovali s faktorjem r in letno kapitalizacijsko dobo, mora veljati arnn = ar, od koder sledi:
rn = //T '
Zgornja formula torej podaja zvezo med letnim faktorjem obrestovanja r in faktorjem obrestovanja vloge, ki lezi na racunu n-ti del leta s pripisom obresti ob izteku te dobe.
Zgled. Na banki vezemo 1.000 EUR za dobo 1 meseca z letno obrestno mero 5%. Koliko obresti bomo dobili ob izteku te dobe?
Letni faktor obrestovanja znasa r = 1 + ^ = 1,05. Ker sredstva lezijo na racunu i! leta, obresti pa se pripisejo takoj po izteku te dobe, je kapitalizacijska doba enaka i! leta, ustrezni obrestovalni faktor pa je enak
ri2 = V105 « 1,00407.
Ce znesek 1.000 EUR pomnozimo s faktorjem n2, dobimo 1004,07 EUR. Banka nam je torej izplačala 4,07 EUR obresti.	■
V časih hiperinflačije, in pri nekaterih bankah tudi se danes, je kapital-izačijska doba enaka enemu dnevu. Ustrezni dnevni faktor obrestovanja je tedaj enak
ru = 3fW,
Kjer je r letna obrestna mera. Ce v taksnih razmerah začetni znek a drzimo na računu m dni, bomo ob konču tega obdobja na računu imeli
m	365^m	m
arm = a y r = ar 365 . 1.3 Krediti in anuitete
Ce zelijo banke poslovati z dobičkom, morajo denar, ki so jim ga zaupali varčevalči, smotrno posoditi tistim strankam, ki potrebujejo posojilo. Obresti, ki jih pri tem zaračunajo posojilojemalčem, morajo seveda biti nekoliko visje od tistih, ki jih za bančne vloge ponujajo varčevalčem. Pri posojilih banka stranki na začetku posojilne dobe izplača dogovorjeni znesek kredita, označimo ga z a. Posojilojemaleč nato preko čelotne posojilne dobe mesečno vrača fiksni znesek b, ki mu pravimo tudi anuiteta. Ob konču posojilne dobe morajo vplačane anuitete znasati čeloten znesek posojila a skupaj s pripadajočimi obrestmi.
Koliko naj bo anuiteta b, če posojilna doba znasa n mesečev, obrestna mera pa je enaka 0? Letni faktor obrestovanja znasa r^ = 1 + 0, mesečni pa zato
r = VTT0.
Po izteku prvega meseča banka h glavniči a pripise obresti 0a in odsteje anuiteto b, ki jo je posojilojemaleč v tem meseču vrnil banki. Glavniča po prvem meseču tako znasa
ai = ar — b.
Po enakem razmisleku, je stanje glavniče (po pripisu obresti in upostevanju vrnjene anuitete) enaka
a2 = a1r — b = (ar — b)r — b = ar2 — br — b.
Splosneje, če z ak označimo stanje glavniče po izteku k mesečev, je ak+1 = akr — b. S pomočje te formule in z uporabo matematične indukčije brz dokazemo, da velja
ak = ark — brk-i — brk-2 — ... — br — b.
Ker mora po m mesecih glavnica pasti na 0, od tod spledi enakost
b(rm-1 + rm-2 + ... + r + 1) = arm.
Ce na levi strani prepoznamo vsoto geometrijske vrste, vidimo, da od tod sledi
rm(r — 1)
rm
b = a-
rm1
2 PraviCna delitev kolaCa
V vsakdanjem zivljenju se velikokrat znajdemo v situaciji, ko je potrebno neko premozenje razdeliti med vec ljudi, tako da se noben ne cuti prikraj-sanega. Ce gre za premozenje v denarju, je naloga preprosta - vsak up-ravicenec prejme svoj proporcionalni delez celotnega premozenja. Tezava nastopi, ce je oblika premozenja taksna, da posamezne dele celote razlicni upravicenci vrednotijo drugace. Na primer, ce je potrebno deliti zapuscino, ki obsega nekaj neprimicnin, avto, zbirko starih starih kovancev in morda nekaj denarja, ni nujno, da vsi dedici posamezni del zapuscine cenijo enako. Mozna resitev problema bi bila, da premozenje najprej prodajo na trgu (in s tem vrednotenje delov premozenja prepustijo trgu), in si iztrzek v enakih delih razdelijo med seboj. Kaj pa, ce tega nocejo storiti - denimo zato, ker trenutne razmere na trgu niso ugodne za prodajo?
V nadaljevanju bomo opisali, kako poiskati zadovoljivo delitev premozenja v primeru dveh ali treh upravicencev. Premozenje bomo pri tem nazorno imenovali kolač, upravicence pa igralce. Predpostavili bomo, da lahko kolac delimo v poljubno majhne dele. Pri tem dopuscamo, da vsak igralec po svoje oceni, koliksen del celote predstavlja posamezen del kolaca.
2.1 Proporcionalna delitev in delitev brez zavisti
Definicija 2.1 Naj bo D delitev kolaca med n igralcev. Delitev D je proporcionalna, ce vsak igralec meni, da je dobil vsaj n-ti del kolaca. Delitev D je brez zavisti, ce vsak igralec meni, da nihce ni dobil vec kot on sam.
Trditev 2.2 Vsaka delitev kolaca brez zavisti je tudi proporcionalna.
Dokaz: Denimo, da trditev ne drzi. Tedaj obstaja delitev kolaca D med n igralcev, ki je brez zavisti, ni pa proporcionalna. Po definiciji proporcionalnosti to pomeni, da obstaja igralec, denimo A, ki meni, da je dobil strogo manj kot n kolaca. Ker pa je delitev proporcionalna, A hkrati meni, da nihce drug ni dobil vec kot on. Igralec A torej meni, da je vsak od n igralcev dobil strogo manj kot n kolaca, in zato vsi skupaj strogo manj kot n n kolaca. To pa je seveda nemogoce, saj je bil med igralce razdeljen celoten kolac. To protislovje kaze, da je bila nasa zacetna predpostavka (da trditev ne drzi) napacna.	I
Na tem mestu se seveda postavi vprasanje, ali morda pojma "delitev brez zavisti" in "proporcionalna delitev" kar sovpadata. Ce kolac delimo
med dva igralca, je temu gotovo tako, saj pri proporcionalni delitvi vsak igralec meni, da je dobil vsaj pol kolaca, od koder sledi, da drugi igralec ni mogel dobiti vec kot on sam. Kot kaze naslednji zgled, pa pri vec kot dveh igralcih temu ni vec tako.
Zgled. Poišči proporcionalno delitev kolača med tri igralce, ki ni brez zavisti.
Denimo, da kolac razrezemo na tri kose, X, Y in Z, in da trije igralci, A, B in C, vrednotijo kose kolaca kot prikazuje spodnja tabela.
	X	Y	Z
A	1 3	4 9	2 9
B	1 3	1 3	1 3
C	1 3	1 3	1 3
Oglejmo si delitev D, pri kateri A dobi kos X, B dobi kos Y in C dobi kos Z. Delitev D je proporcionalna, saj vsak igralec meni, da je prejel natanko 3 kolaca. Ni pa brez zavisti, saj igralec A zavida igralcu B, ker meni, daje B prejel 4 kolaca, on sam pa le 1.	■
2.2	Delitev za dva igralca: reži in izberi
Postopek delitve kolaca med dva igralca je preprost. V prvem koraku eden od igralcev (denimo A) razreze kolac na dva kosa, v drugem koraku pa igralec B izbere enega od kosov zase. Ce je igralec A v prvem koraku kolac razdelil na dva, po njegovem enako velika kosa, bo ne glede na izbiro igralca B po njegovem prejel polovico kolaca. Zato A ne zavida igralcu B. Seveda pa tudi igralec B, ki seveda izbere vecjega od obeh kosov (oziroma katerega koli, ce sta po njegovem enako velika), ne zavida igralcu A. Dobljena delitev kolaca je tako brez zavisti.
Zaradi rezanja in izbiranja se zgoraj opisani postopek imenuje tudi rečzi in izberi.
2.3	Delitev brez zavisti za tri igralce
Oglejmo si se postopek delitve kolaca med tri igralce, denimo A, B in C, ki vsakemu od njih, ce le postopa razumno, zagotavlja, da po koncani 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.	Igraleč A naj razreze kolač na tri dele.
Komentar: Igraleč A ravna razumno, če jih razdeli na tri zanj enake dele.
2.	Igraleč B lahko bodisi ne stori nič bodisi od enega od treh kosov odreze del in ga da na stran. V slednjem primeru imenujmo zmanjsani kos Z, odrezani del pa O. Z odrezkom O se do nadaljenga ne bomo ukvarjali. Komentar: Igraleč B ravna razumno, če z rezanjem doseza, da sta največja dva kosa enako velika, tretji pa manjši od njiju. Pri tem naj ne stori nič, če sta ze na začetku bila največja kosa enako velika.
3.	Igralči naj si zaporedoma izberejo po en kos (ne upostevajoč odrezka O). Najprej naj svoj kos izbere igraleč C, nato igraleč B in nazadnje igraleč A. (Ce je igraleč B v prejsnjem koraku kos zmanjsal, mora zdaj izbrati zmanjsani kos Z, razen če ga ni pred njim izbral ze igraleč C. Ce v drugem koraku igraleč B ni odrezal dela O, je s tem delitev končana. Sičer pa si naj igralči razdelijo se odrezek O, kot je opisano v nadaljevanju.
Komentar: V tem trenutku vsak igraleč, če je le ravnal razumno, meni, da je njegov kos vsaj tako velik kot kosa drugih dveh igralčev. Res, igraleč C gotovo tako misli, saj je izbiral prvi. Igraleč B je poskrbel, da sta bila pred izbiranjem največja kosa enako velika (eden od teh je bil ravno kos Z), tako da lahko tudi, ko je C ze izbral svoj kos, se vedno izbere enega od največjih kosov. Nazadnje izbira B. Vendar, ker je na začetku kolač razrezal na tri enake dele, zmanjsani kos Z pa je moral izbrati B (če ga ni izbral ze C ), je tudi on s preostalim kosom zadovoljen.
4.	Tisti od igralčev B in C, ki ni prejel kosa Z, naj razreze odrezek O na tri dele. Tega igralča bomo imenovali delilec, drugega od igralčev B in C pa nedelilec.
Komentar: Delileč ravna razumno, če odrezek razdeli na tri zanj enake dele.
5.	Igralče izberejo vsak svoj kos odrezka v naslednjem vrstnem redu: Najprej nedelileč, nato igraleč A in nazadnje delileč.
Komentar: Igralči ravnajo razumno, če izberejo po njihovo največji kos, ki je se na razpolago. Premislimo, da po tej delitvi vsak meni, da je prejel vsaj tako velik kos kolača, kot ostala dva igralča. Nedelileč gotovo misli tako, saj je izbiral prvi. Igraleč A ni zavisten nedelilču, saj je nedelileč v prvem krogu delitve prejel zmanjsani kos Z, ki je po mnenju igralča A tudi skupaj s čelotnim odrezkom O se vedno manjsi enak kosu, ki ga je sam prejel v prvem
krogu. Seveda A ne zavida niti delilču, saj je izbiral pred njim. Delileč pa tudi ne zavida ostalima dvema, saj je odrezek razrezal v tri zanj enake dele.
Komentarji pri posameznih korakih kazejo, da je delitev, dobljena po opisanem postopku (in pri predpostavki, da se vsi igralči odločajo razumno) brez zavisti.
S podobno enostavnim postopkom lahko dosezemo proporčionalno delitev tudi v primeru poljubno velikega stevila igralčev. Delitev brez zavisti je pri večjem stevilu igralčev prečej tezje doseči. Algoritma za proporcionalno delitev in delitev brez zavisti sta opisana, na primer, v članku [1].
3 Volilna moč
Temelj zivljenja v skupnosti je sposobnost sporazumnega odločanja tudi v primeru, ko imajo člani skupnosti različna mnenja. V moderni demokračiji odločanje v skupnosti navadno temelji na taksnem 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 taksne situačije je odločanje na skupsčini delničarjev delniske druzbe, pri kateri je stevilo glasov posameznega delničarja sorazmerno s stevilom delnič, ki so v njegovi lastni. Vprasanje, s katerim se bomo ukvarjali v tem poglavju, je, ali je dejanska moč odločanja posameznika sorazmerna s stevilom glasov (njegovo tezo), ki mu pripadajo.
Oglejmo si naslednji zgodovinski zgled. Evropska skupnost je med leti 1958 in 1973 obsegala sest članič: Nemčijo, Frančijo, Italijo, Belgijo, Nizozemsko in Luksemburg. V tem obdobju so odločitve v Svetu Evropske skupnosti praviloma sprejemali z 12 od 17 moznih glasov, ki so bili med članiče razporejeni takole: Nemčija, Frančija in Italija po 4 glasovi, Belgija in Nizozemska po 2 in Luksemburg 1 glas. Glasovi v Svetu so bili tako razporejeni priblizno v skladu z velikostjo drzave, kar se morda zdi smiselno in posteno -pri tem je tudi daleč najmanjsa članiča, Luksemburg, imela svoj glas. Vendar pa so članiče kmalu ugotovile, da je glas Luksemburga pri glasovanju o konkretni odločitvah popolnoma irelevanten: Ce so za nek sklep skupaj z Luksemburgom zbrali vsaj 12 glasov, bi jih vsaj 12 zbrali tudi brez Luksem-burga. Luksemburg je imel tako enako moč soodločanja v Svetu Skupnosti, kot bi jo imel, če bi bil brez glasu.
3.1 Banzhafov indeks volilne moči
Zgoraj opisano neskladje med stevilom 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^ P2,..., Pn. Vsakemu igralču Pj priredimo njegovo utež aj z intervala med 0 in 1 in predpostavimo, da je vsota utezi vseh igralčev enaka 1. Poljubni podmnoziči mnoziče {P1, P2,..., Pn} rečemo koalicija. Teža koalicije je definirana kot vsota utezi posameznih članov koaličije. Pribijmo realno stevilo r, 2 < r < 1, in ga imenujmo prag odločanja,. Za koaličijo pravimo, daje zmagovalna (glede na prag r), brz ko je njena teza vsaj r.
Clan P zmagovalne koaličije K je kritičen, če koaličija K \ {P} ni več
zmagovalna. Ideja, ki se strinja v ozadju definicije Banzhafovega indeksa je prepričanje, da je moC soodloCanja igralca tem veCja, v Cim veC zmagovalnih koalicijah nastopa kot kritiCni Clen. Naj torej N (P) oznaCuje stevilo vseh zmagovlani koaliCij, v kateri je igraleC P kritiCen. Tedaj je absolutni Banzhafov indeks igralCa P definiran kot
B(P) = N^,
v ' 2™
relativni Banzhafov indeks pa kot
Br(P) = BP"' kjer je S = B(Pi) + B(P2) + ... + B(Pra).
Hitro se prepriCamo, da je vsota relativnih Banzhofovih indeksov vseh igralCev enaka 1:
Br (Pl) + Br (P2) + ... + Br (P„) = ^ + ^ + ... + ^
= B(Pi) + B(P2) + ... + B(Pn) = S = .
S	S .
V tem smislu lahko relativni Banzhafov indeks razumemo kot odstotek dejanske moCi odloCanja posameznega igralCa.
Relativni Banzhafov indeks lahko izraCunamo tudi neposredno iz vrednosti N(Pi), ne da bi prej izraCunali absolutne Banzhafove indekse:
N (P)
Br (P )=	'
B(P)	_	šn-r
B(P1) + B(P2) + ... + B(Pn) N(Pl)+N(2pa2+-+N(P") ' in zato:
Br (P) =	N (P>
N(Pi) + N(P2) + ... + N(Pra)"
3.2 Zgledi
Za prvi zgled izraCunajmo Banzhafov indeks treh igralCev A, B in C, katerih utezi so porazdeljene takole: IgraleC A naj nosi 47% glasov, B 44% in C 9% glasov. Prag odloCanja postavimo na 51%. Bezen pogled na razdelitev glasov pokaze, da je za sprejem sklepa potrebna podpora vsaj dveh igralCev - in to katerih koli dveh igralCev. Kljub obCutni razliki v tezi imajo vsi trije igralCi enako moC pri sprejemanju odloCitev. Ce naj Banzhafov indeks
pravilno odraža volilne moči, bi moral biti pri vseh treh igralcih enak. Pa ga izračunajmo.
Najprej poiSčemo vse možne koalicije. Teh je 2n, kjer je n Število igralcev, sistematično pa jih naštejemo tako, da navedemo vsa možna zaporedja ničel in enič dolžine n, pri čemer posamezno zaporedje interpretiramo kot tisto koaličijo, katere člani so natanko tisti igralči, pri katerih stoji eniča. Pri vsaki koaličiji izračunamo njeno tezo in glede na prag odločimo, ali je zmagovalna. Nazadnje pri vsaki zmagovalni koaličiji poisčemo se kritične člane. Rezultate tega postopka so predstavljene v tabeli spodaj:
ABC	koaličija	teza	zmagovalna?	kritični
0 0 0	0	0%	NE	
0 0 1	{C }	9%	NE	
0 1 0	{B}	44%	NE	
0 1 1	{B, C }	53%	DA	B, C
1 0 0	{A}	47%	NE	
1 0 1	{A, C }	56%	DA	A, C
1 1 0	{A, B}	91%	DA	A, B
1 1 1	{A, B, C}	100%	DA	
Iz tabele je razvidno, da je vsak od igralčev kritičen v natanko dveh koaličijah. Ker je stevilo igralčev n enako 3, je absolutni Banzhafov indeks vseh treh enak
B(A) = B(B) = B (C) = = 1,
relativni indeks pa
i i
Br (A) = Br (B) = Br (C) = .j, = 1,
2 + 2 + 2 3
tako kot smo pričakovali.
Za drugi zgled vzemimo situačijo s stirimi igralči, katerih utezi so porazdeljene takole:
A : 27%, B : 26%, C : 25%, D : 22%.
Prag odločanja naj bo ponovno enak 51%. Iskanje zmagovalnih koaličij izvedemo podobno kot pri prejsnjem zgledu:
A B C D	koalicija	teza	zmagovalna?	kriticni
0 0 0 0	0	0%	NE	
0 0 0 1	{D}	22%	NE	
0 0 10	{C }	25%	NE	
0 0 11	{C, D}	47%	NE	
0 10 0	{B}	26%	NE	
0 10 1	{B,D}	48%	NE	
0 110	{B, C }	51%	DA	B, C
0 111	{B,C,D}	73%	DA	B, C
10 0 0	{A}	27%	NE	
10 0 1	{A, D}	49%	NE	
10 10	{A, C }	52%	DA	A, C
10 11	{A, C, D}	74%	DA	A, C
110 0	{A, B}	53%	DA	A, B
110 1	{A, B, D}	75%	DA	A, B
1110	{A, B, C}	78%	DA	
1111	{A, B, C, D}	100%	DA	
Izračun Banzhafovega indeksa organizirajmo v obliki spodnje tabe:
P	N (P)	B(P)	Br (P)
A	4	1 2	1 3
B	4	1 2	1 3
C	4	1 2	1 3
D	0	0	0
S	12	3 2	1
Kot vidimo, je v tem primeru volilna moč enakomerno porazdeljena med prve tri igralce, medtem ko igralec D nima nobene moči, saj je vsaka zmagovalna koalicija, v kateri sodeluje, zmagovalna tudi brez njega. Do taksnega neravnovesja volilne moči je prislo kljub temu, da so utezi posameznih igralcev relativno blizu skupaj.
Premisli, kako na volilno moc posameznih igralcev iz zgledov prejsnjega razdelka vpliva dviganje praga odlocanja. Ali taksno dviganje vedno koristi najmanjsi clanici, in to ne glede na velikost dviga praga odlocanja?
3.3 Združevanje igralcev
Denimo, da se dva igralca zdruzita v novega, zdruzenega igralca, pri cemer utez zdruzenega igralca dolocimo kot vsoto utezi igralcev, ki sta se zdruzila.
Ali bo relativni Banzhafov indeks zdruzenega igralča enak vsoti Banzhafovih indeksov igralčev, ki sta se zdruzila? Bo morda večji, ali manjsi? Na to vprasanje odgovorimo z naslednjimi zgledi.
Denimo, da se igralča A in B v zadnjem primeru iz prejsnjega razdelka zdruzita. Spomnimo se: imeli smo stiri igralče z naslednjimi utezmi: A : 27%, B : 26%, C : 25, D : 22%. Po zdruzitvi dobimo tri igralče: A + B, C in D z naslednjim utezmi:
A + B : 53%, C : 25%, D : 22%.
Ker je prag odločanja enak 51%, vidimo, da so zmagovalne koaličije natanko tiste, pri katerih sodeluje zdruzeni igraleč A + B. Taksne so 4. V vseh teh koaličijah je A + B edini kritični član. Tedaj Banzhafov indeks izračunamo s pomočjo spodnje tabele:
P	N (P)	Br (P)
A + B	4	4 = 4
C	0	0
D	0	0
S	4	1
Igralča A in B sta si torej z zdruzitvijo povečala Banzhafov indeks preko vsote njunih starih indeksov. Zdruzitev se jima je torej obrestovala.
Poglejmo si sedaj naslednji zgled s petimi igralči in njihovimi utezmi razporejenimi takole:
A : 30%, B : 6%, C : 49%, D : 5%, 10%.
Pri upostevanju 51% praga odločanja dobimo naslednje relativne Banzhafove indekse:
P	Br (P )
A	1 11
B	1 11
C	7 11
D	1 11
E	1 11
Po zdruzitvi igralčev A in B pa se Banzhafovi indeksi spremenijo v:
P	Br (P)
A + B	1 6
C	1 2
D	1 6
E	1 6
Ker je Br (A) + Br (B) = ii + ii = 2 strogo več kot Br (A + B) = 6, se zdruzevanje igralčema A in B v tem primeru ni izplačalo.
3.4 Volilna moč strank v Državnem zboru
Na drzavnozborskih volitvah leta 2008 smo drzavljani porazdelili poslanske sedeze med sedem političnih strank na način, kot kaze spodnja tabela. Poleg 88 sedezev, ki jih zasedajo čani strank, Ustava zagotavlja tudi dva sedeza za predstavnika italijanske in madrzarske 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).
stranka	sedezi
SD	29
SDS	28
ZARES	9
DeSUS	7
SNS	5
SLS	5
LDS	5
NS	28
S	90
Za izračun Banzhafovega indeksa moramo pregledati 28 = 256 moznih koaličij (v resniči je potrebno obravnavati le zmagovalne koaličije, ki jih je občutno manj). Ker je to kar veliko stevilo, se ga najbrz sami (če ravno nimamo viska časa) ne bomo lotili sami na roke. Lahko pa si pomagamo z računalniskim programom (če ga znamo sestaviti) ali pa tako, da na pomoč pokličemo prijatelje. V skupini 16 ljudi lahko delo organiziramo tako, da vsak od njih pregleda vse koaličije, ki imajo članstvo prvih stirih strank predpisano. Na primer, prvi pregleda vse koaličije, ki vključujejo SD, SDS, Zares in DeSUS; drugi vse koaličije s SD, SDS, ZARES in brez DeSUS; tretji vse koaličije s SD, SDS, brez ZARES in z DeSUS itd.
V spodnji tabeli so navedeni Banzhafovi indeksi pri dveh pragih odločanja (običajne večinskem, ki zahteva 46 glasov, in dvotretjinskim s 60 glasovi).
stranka	sedezi	r = 46/90	r = 60/90
SD	29	28%	42%
SDS	28	24%	41%
ZARES	9	13%	3%
DeSUS	7	11%	3%
SNS	5	7%	3%
SLS	5	7%	3%
LDS	5	7%	3%
NS	28	2%	1%
4 Pošteni razporedi soočenj
Leta 1997 smo imeli v Sloveniji predsedniske volitve, na katerih je kandidiralo osem predsedniskih kandidatov: Bernik, Cerar, KovaC, KuCan, MiklaviC, Persak, Podobnik in Poljsak. V predvolilnem Casu je naCionalna televizija organizirala osem sooCenj kandidatov, pri Cemer so na vsakem sooCenju sodelovali trije izmed osmih kandidatov. Ker so se na televiziji odloCili za ravno toliko sooCenj kot je bilo kandidatov, so lahko sooCenja organizirali tako, da je vsak izmed kandidatov nastopil enako mnogokrat - tako nenazadnje veleva tudi zakon.
Kljub temu pa pozornemu gledalCu ni uslo, da sta se KuCan in Podobnik sreCala na dveh sooCenjih, medtem ko se nekateri pari kandidatov sploh niso sreCali. Taksno neravnovesje bi morda nekateri lahko razumeli kot favoriziranje kandidatov KuCana in Podobnika. Bi se televizija tej nerodnosti lahko izognila? Vprasanje torej je: Ali obstaja razpored osmih sooCenj osmih kandidatov - po trije na vsakem sooCenju - pri katerem se vsak par sreCa najveC enkrat?
4.1 Kombinatorčne konfiguracije
Nalogo razporeda sooCenj lahko matematiCno formuliramo v jeziku kombi-natoričnih konfiguracij.
Definicija 4.1 Naj bo V poljubna neprazna konCna mnoziCa in B poljubna druzina podmnoziC mnoziCe V; elemente mnoziCe V imenujmo točke, elemente mnoziCe B pa bloki ali tudi premice. Tedaj paru (V, B) reCemo kom-binatoričcna konfiguracija, Ce so izpolnjeni naslednji trije aksiomi.
A1. Obstaja taksno naravno stevilo r, da je vsaka toCka iz V vsebovana v natanko r blokih iz B.
A2. Obstaja taksno naravno stevilo k, da vsak blok iz B vsebuje natanko k toCk iz V.
A3. Vsak par toCk iz V je hkrati vsebovan v najveC enem bloku iz B.
Ce z v = |V| oznaCimo stevilo toCk, z b = |B| pa stevilo blokov, tedaj reCemo, da je taksna konfiguraCija tipa (vr; bk). Kadar je v = b in r = k, govorimo o simetrični konfiguraciji tipa (vr).
Vprasanje "postenega" razporeda sooCenj osmih kandidatov s predsedniskih volitev leta 1997 se torej prevede na vprasanje obstoja kombinatoriCne
konfiguračije tipa (8r; 83). Pri tem za mnozičo točk vzamemo kar mnozičo predsedniskih kandidatov, vsak posamezni blok pa razumemo kot trojičo kandidatov, ki so se srečali na danem soočenju.
Premislimo najprej, da lahko stevilo r (tj. stevilo pojavitev posameznega kandidata v osmih soočenjih) določimo na podlagi ostalih podatkov. Splosneje, dokazimo, da velja naslednja trditev.
Trditev 4.2 Ce obstaja kombinatoricna konfiguracija tipa (vr; bk), tedaj je vr = bk.
Dokaž: Dokaz izpeljimo s pomočjo "računovodskega pravila". Defini-rajmo mnozičo
M = {(x,t) : x G V,t GB,x G t}
in prestejmo njene elemente na dva različna načina. Najprej opazimo, da se vsak x G V pojavi kot prva komponenta v parih iz M natanko r-krat - z vsakim blokom, v katerem je vsebovan, enkrat. Ker je točk v V ravno v, je torej parov v M natanko vr.
Po drugi strani pa vsak t G B nastopi kot druga komponenta v parih iz M natanko k-krat - z vsako točko, ki jo vsebuje, po enkrat. Zato je |M| = |B|k = bk. Ker morata oba načina stetja elementov mnoziče M dati enak rezultat, dobimo enakost vr = bk.	I
Od tod sledi, daje pri iskani konfiguračiji tipa (8r ;83) parameter r enak 3. Isčemo torej simetrično konfiguračijo tipa (83).
4.2 Mobius-Kantorjeva konfiguracija
Izkaze se, da obstaja (do preimenovanja točk natančno) natanko ena simetrična konfiguračija tipa (83). Imenuje se Mobius-Kantorjev konfiguracija in je definirana takole:
V = {0,1, 2, 3, 4, 5, 6, 7},
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}}.
Ce stevila 0,1,2,..., 7 nadomestimo z imeni osmih predsedniskih kandidatov, dobimo optimalni razpored soočenj, ki bi zagotavljal, da se vsaka dva kandidata srečata natanko enkrat. Grafično si lahko konfiguračijo predočimo s pomočjo spodnje sheme.
Mobius-Kantorjeva konfiguracija (83).
Pri tej shemi vidimo osem toCk: tri ogliSCa trikotnika, tri razpoloviSCa trikotnikov in dve toCki, ki leZita na preseCiSCu teZiSCnice in povezovalke dveh razpolovi sC straniC. Vidimo tudi osem Crt: tri straniCe trikotnika, dve teZi sCniCi, dve povezovalki razpolovi sC straniC in eno krivo Crto. Vsaka toCka lezi na natanko treh Crtah in vsaka Crta vsebuje natanko tri toCke. Vsaki dve toCki lezita na najveC eni Crti. Obstajajo pa tudi stirje pari toCk, ki ne lezijo na nobeni Crti. To so pari {0, 4}, {1, 5}, {2, 6} in {3, 7}.
4.3 Pari, ki se ne srečajo
V kombinatoriCni konfiguraCiji zahtevamo, da se vsaki dve toCki pojavita v najveC enem skupnem bloku. Premislimo, koliko parov toCk {x, y} C V, x = y, v kombinatoriCni komnfiguraCiji tipa (vr; bk) je taks nih, da niso vsebovani v nobenem bloku (za toCki, ki tvorita taksen par, bomo rekli, da se ne srečata).
Dokazimo najprej naslednji pomozni rezultat.
Lema 4.3 Naj bo A poljubna množica z n elementi. Tedaj je število neurejenih parov {x, y} C A, x = y, mnoZica A enako
Dokaz: V to se najlazje prepriCamo, Ce elemente mnoziCe A uredimo,
n(n — 1)
2
A = {ai, 02,..., a„},
in sestavimo kvadratno tabelo
X |a2,ai}
|a3,ai}
{01,^2}
X {03,02}
{01,03 } {02,03 } X
{0„,0i} {0n,02} {0n,03}
{01, 0n}
{02, 0n} {03, 0n}
X
V tej tabeli vsak par {o»,0j}, i = j}, nastopa natanko dvakrat: enkrat na presečišču i-tega stolpca in j-te vrstice, drugič na presečisču j-tega stolpca in i-te vrstiče. Ker je parov v tabeli n2 — n (saj n izmed možnih n2 pozičij zasedajo simboli X) in ker se vsak par pojavi natanko dvakrat, je parov ravno 1 (n2 — n) = n(n2-1).	I
Iz zgornje trditve sledi, da je vseh parov {x, y} točk iz V ravno 1), v posamičnem bloku pa se pojavi natanko fc(fc2-1) parov. Ker je blokov b, vsak par pa se pojavi v največ enem bloku, se torej v vseh blokih skupaj pojavi natanko bfc(fc—1) parov. Od tod sledi naslednja trditev.
Trditev 4.4 V kombinatoriCni konfiguraciji tipa (vr; b^) je natanko
v) ~ v(v — !) — bfc(fc — !)
taksnih parov, ki se v konfiguraciji ne srečajo.
Ce se omejimo na konfiguračije tipa (v3), dobimo naslednjo posledičo zgornje trditve.
Posledica 4.5 V simetrični konfiguraciji tipa (v3) je natanko
v (v — 7)
takčsnih parov, ki se v konfiguraciji ne srečcajo.
Kot smo ze ugotovili v prej snjem razdelku, se v Mobius-Kantorjevi kon-figuračiji, ki je tipa (83), ne srečajo stirje pari.
Nadalje, iz zgornje poslediče sledi, da ima vsaka kombinatorična kon-figuračija vsaj 7 točk, morebitna kombinatorična konfiguračija z natanko sedmimi točkami pa ima dodatno lastnost, da se v njej vsak par točk pojavi v natanko enem bloku. Taks na konfiguračija tipa (73) res obstaja in se imenuje Fanova ravnina (glej sliko)
Fanova ravnina - simetrična konfiguračija tipa (73).
Navedimo na tem mestu se tri konfiguračije tipa (93). Prvi od treh rečemo tudi Pappusova konfiguracija. Za vse slike v tem razdelku se zahvaljujem Marku Bobnu.
5 Steinerjevi sistemi trojk
PriCnimo poglavje z naslednjo nalogo, ki jo je daljnega leta 1850 v ameriski druzabni 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 solarke oblikujejo 7 ■ 5 = 35 vrst (vsak dan po 5). Ker gre vsaka s olarka na sprehod vsak dan v tednu, pomeni, da se pojavi v natanko sedmih trojkah. C e z V oznaCimo mnoziCo 15 solark, z B pa mnoziCo 35 trojk, ki jih v sedmih dneh sprehajanja oblikujejo solarke, nam pogoj, da se nobeni dve solarki ne sprehajata v isti vrsti veC kot enkrat, zagotovi, daje par (V, B) kombinatoriCna konfiguraCija tipa (157;353).
Pa vstavimo podatke v = 15, r = 7, b = 35 in k = 3 v formulo iz trditve 4.4:
To pa pomeni, da se pri taksnem razporedu sprehodov vsaki dve solarki sprehajata v isti vrsti natanko enkrat (in ne zgolj najveC enkrat) na teden. Iskana konfiguraCija solark in trojk ima torej dodatno lastnost, da se v njej prav vsak par solark sreCa natanko enkrat. Pri tem reCemo, da par (V, B) tvori Steinerjev sistem trojk.
Definicija 5.1 Naj bo V poljubna neprazna mnoziCa in B mnoziCa nekih trielementnih podmnoziC mnoziCe V. Ce za vsak par {x, y} C V, x = y, obstaja natanko ena trojka B G B, ki vsebuje tako x kot y, potem reCemo, da par (V, B) tvori Steinerjev sistem trojk.
Ker v zgornji definiCiji ne zahtevamo izreCno, da je vsaka toCka vsebovana v istem stevilu blokov, ni povsem oCitno, da je Steinerjev sistem trojk nujno tudi kombinatoriCna konfiguraCija. Da je temu tako, bomo med drugim dokazali v naslednji trditvi.
Izrek 5.2 Za par (V, B), |V| = v, |B| = b, sta ekvivalentni naslednji trditvi:
v(v — 1) — bk(k — 1) 15 ■ 14 — 35 ■ 3 ■ 2
0.
2
2
(i) (V, B) je Steinerjev sistem trojk;
(ii) (V, B) je kombinatorična konfiguracija tipa (vr; bk), kjer je k = 3,
v— 1 • z, v(v— 1)
r = "T-1 in b = v 6 .
Dokaž: Predpostavimo najprej, da velja (i). Dokazimo najprej, da je (V, B) kombinatorična konfiguračija. Ce primerjamo definičiji sistema Steinerjevih trojk in kombinatorične konfiguračije, vidimo, da moramo le se dokazati, da obstaja taksno naravno stevilo r, da se vsaka točka iz V pojavi v natanko r blokih iz B. Se več, radi bi videli, da je taksen r enak . V ta namen vzemimo x G V in si oglejmo mnozičo vseh trojič
{x,y1,Z1}, {x,y2,Z2}, {x,y3,Z3},...
iz B, v katerih nastopa točka x. Ker x z vsakim elementom mnoziče V \ {x} nastopi v trojiči natanko enkrat (to nam zagotavlja definičija Stein-erjevega sistema trojk), se vsak element iz mnoziče V \ {x} med elementi y1, z1,y2, z2, y3, z3,... pojavi natanko enkrat. Od tod sledi, da je zgoraj nastetih trojk natanko 1, oziroma z drugimi besedami, točka x se pojavi
v natanko trojkah iz B. S tem smo dokazali, daje (V, B) kombinatorična konfiguračija tipa (vr; bk), pri čemer je r = "T . Ker je k = 3 po definičiji, se lahko v pravilnost formule za b prerpičamo s pomočjo enakosti vr = bk, ki velja pri poljubni kombanitorični konfiguračiji.
Predpostavimo sedaj, da velja (ii). Ce zelimo dokazati, da je v tem primeru par (V, B) Steinerjev sistem trojk, moramo dokazati, da se vsak par točk v konfiguračiji sreča. To pa sledi iz trditve 4.4, saj je
v(v - " - bk(k - ^ = 1(v(v - 1) - vfe-H • 6) = 0.
2 2V v ! 6 !
Od to sledi naslednji pogoj na obstoj Steinerjevega sistema trojk z v točkami.
Trditev 5.3 Ce obstaja Steinerjev sistem trojk z v točkami, tedaj je v oblike 6t + 1 ali pa oblike 6t — 3 za neko naravno čtevilo t.
Dokaž: Naj bo (V, B) Steinerjev sistem trojk z v točkami. Tedaj se, po prejsnji trditivi, vsaka točka pojavi v r = "T trojkah, od koder sledi, da je r naravno stevilo, in zato v liho stevilo. Od tod sledi, da lahko v zapi semo v obliki v = 2s — 1 za neko naravno stevilo s. Po drugi strani je stevilo trojk v B enako
_ v(v — 1) _ (2s — 1)(2s — 2) _ (2s — 1)(s — 1)
Ker je tudi b naravno stevilo, od tod sledi, da 3 deli 2s — 1 ali pa s — 1. V prvem primeru je 2s — 1 = 3m za neko naravno stevilo m. Ker je v = 2s — 1 liho stevilo, mora biti tudi stevilo m liho, in zato
v = 2s — 1 = 3(2t — 1) = 6t — 3
za neko naravno stevilo t.
C e pa 3 deli s — 1, je s — 1 = 3t za neko naravno s tevilo t, in zato
v = 2s — 1 = 2(3m + 1) — 1 = 6t + 1.
Trditev je s tem dokazana.	I
V resniči velja tudi obrat zgornje trditve: Za vsako stevilo v oblike 6t — 3 ali 6t + 1, t G N, obstaja Steinerjev sistem trojk z v točkami. To dejstva je prečej tezje dokazati kot zgornjo trditev.
5.1 Kirkmanovi sistemi trojk
Vrnimo se sedaj prvotni nalogi o petnajst solarkah. Pri tej nalogi isčemo sistem trojk (V, B) na v = 15 točkah z dodatno lastnostjo, da lahko mnozičo b = 1) = i5_M = 35 trojk razbijemo 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 taks no razbitje mnoziče trojk, pravimo tudi Kirkmanovi sistemi trojk.
Trditev 5.4 Ce 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 gaje zelo tezko dokazati: Za vsako stevilo v oblike 6t—3, t G N, obstaja Kirmanov sistem trojk na v točkah. To nam pove, da je osnovni Kirkmanov problem s 15 solarkami resljiv, saj je 15 = 6 ■ 3 — 3. Eno od moznih resitev si lahko ogledate, denimo, na Wikipediji.
6 Eulerjev problem 36 Častnikov
Legenda pravi, da je Katarina Velika Eulerju, ko je le-ta zivel na njenem dvoru, zadala naslednjo nalogo: "Na dvoru bom sprejela predstavnike 6 regimentov. Vsak regiment bo predstavljalo 6 castnikov, po en castnik vsakega od 6 cinov. Razvrsti teh 36 castnikov v 6 x 6 formacijo tako, da bo v vsaki vrsti in v vsaki koloni natanko en castnik iz vsakega regimenta in natanko en castnik vsakega cina."
Euler naj bi po daljsem iskanju resitve obupal in Carici Katarini zagotovil, da taksen razpored ni mozen. Da bi svojo trditev tudi ustrezno matematicno podkrepil, je pricel raziskovati tako imenovane latinske kvadrate.
6.1 Latinski kvadrati
Latinski kvadrat velikosti n je razporeditev stevil N = {1, 2,... ,n} (ali elementov katere koli druge n elementne mnozice) v n x n mrezo, pri kateri se v vsaki vrstici mreze in v vsakem stolpcu mreze pojavi vsako stevilo iz mnozice N natanko enkrat. Zgledov latinskih kvadratov ni tezko najti. Na-jpreprostejsi nacin konstrukcije latinskega kvadrata velikosti n je naslednji: V prvo vrstico kvadrata zapovrstjo navedemo stevila 1,2,... ,n. V drugo vrstico navedemo ta-ista stevila v zamaknenjem vrstnem redu: 2,3,..., n, 1. Postopek nadaljujemo tako, da v vsaki naslednji vrstici stevila iz prejsnje vrstice ciklicno zamaknemo se za eno mesto v levo. Tako v tretji vrstici dobimo stevila z vrstnim redom 3,4,..., n, 1,2. Koncamo z n-to vrstico, v kateri so stevila navedena v vrstnem redu n, 1,2,...,n — 1.
" 1 2 3 4 5 6 " 234561 345612
4	5 6 1 2 3
5	6 1 2 3 4 612345
S pomocjo latinskega kvadrata velikosti 6 lahko Eulerjevo nalogo resimo "na pol". Dosezemo namrec lahko, da se v vsaki vrstici in vsakem stolpcu pojavi natanko en predstavnik vsakega od sestih regimentov. To pac storimo tako, da vse castnike 1. regimenta oznacimo s stevilom 1, castnike 2. regimetna s stevilom 2 itd. Latinski kvadrat velikosti 6 nam potem predstavlja rapored-itev castnikov glede na njihovo pripadnost regimentom. Seveda nam tak sna resitv se ne zagotavlja, da se bo v vsaki vrstici in vsakem stolpcu pojavil vsak cin natanko enkrat.
Podobno bi lahko latinski kvadrat velikosti 6 uporabili za razvrstitev, pri kateri bi se vsak posamezni Cin pojavil v vsaki vrstiCi in vsakem stolpCu natanko enkrat - le stevila med 1 in 6 bi morali interpretirati kot Cine namesto kot regimente. Ce nam uspe dva latinska kvadrata (enega, ki podaja razporeditev regimentov, in drugega, ki podaja razporeditev po Cinih) zdruziti na tak naCin, da vsako kombinaCijo Cina in regimenta podamo natanko enkrat, smo nalogo Castnikov res ili.
Preden nadaljujemo z Eulerjevim problemom Castnikom, si oglejmo, ali znamo latinske kvadrate velikosti n konstruirati se kako drugaCe.
6.2 Modularna aritmetika
Za naravni stevili n in x naj x mod n oznaCuje ostanek stevila x pri deljenju z n in naj
Zn = {0,1,..., n — 1}
oznaCuje mnoziCo vseh moznih ostankov pri deljenju s stevilom n. Za x, y G Zn definirajmo
x © y = x + y mod n in x 0 y = xy mod n.
Ni se tezko prepriCati, da operaCiji © in 0 zadosCata mnogim obiCajnim pravilom, ki veljajo za obiCajno sestevanje in mnozenje v mnoziCi Celih stevil. Na primer, za poljubne x, y, z G Zn velja naslednje:
1.	x © y = y © x in x 0 y = y 0 x (komutativnost);
2.	(x © y) © z = x © (y © z) in (x 0 y) 0 z = x 0 (y 0 z) (asoCiativnost);
3.	(x © y) 0 z = (x 0 z) © (y 0 z) (distributivnost);
4.	x © 0 = x, x 0 0 = 0, x 0 1 = x;
5.	Za vsak a G Zn obstaja neki b G Zn, za katerega je a © b = 0 (namreC, za b lahko vzamemo element n — a).
C e za kako stevilo x G Zn obstaja stevilo y G Zn, za katerega velja, da je x 0 y = 1, potem reCemo, da je y multiplikativni inverz elementa x in ga oznaCimo z x-1, za stevilo x pa reCemo, daje obrnljivo. MnoziCo obrnljivih stevil v Zn oznaCimo z Zn.
Na primer, v Z5 velja 2 0 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 04 = 16mod5 = 1). Po drugi strani pa 0 ni obrnljiv element, saj je 0 0 x = 0 = 1 za vsak x G Z5. Zato je
Z5 = {1, 2, 3, 4}.
Nekoliko drugačna je situačija v mnoziči 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 0 3 = (x 0 2) 0 3 = x 0 (2 0 3)= x 0 0 = 0,
kar je očitno protislovje. Podobno poteka premislek za stevila 0, 3 in 4. Zato velja
Z_ = {1, 5}.
V splo snem velja naslednja trditev, ki pa je ne bomo dokazali.
Trditev 6.1 V mnošici Zn so obrnljiva natanko tista nenišelna števila, ki so tuja številu n. Ce je n praštevilo, so v Zn torej obrnljivi vsi nenicelni elementi.
6.3 Konstrukcija latinskih kvadratov
Operačiji © in 0 lahko uporabimo za konstrukčijo latinskih kvadratov na naslednji način. Izberimo obrnljiv element o G z*n in konstruirajmo matriko La(n) velikosti n x n, katere vrstiče in stolpče ostevilčimo z elementi 0,1,...,n — 1 G Zn. Na preseči sče vrstiče x G Zn in stolpča y G Zn v La(n) vstavimo element o0x + y. Predem dokazemo, da smo tako res dobili
latinski kvadrat, si oglejmo konkretni zgled. Naj bo n = 5 in 0 = 2. Tedaj je
L2(5) =
4 1 3 0 2
01234
Trditev 6.2 Ce je o obrnljiv element množice Zn, tedaj je La(n) latinski kvadrat.
Dokaz: Dokazati moramo, da v nobeni vrstiči in v nobenem stolpču ne dobimo dveh enakih stevil. Pa denimo, da bi v vrstiči x G Zn dobili enaki stevili v stolpčih y1 = y2. Tedaj bi veljalo
o 0 x © y1 = o 0 x © y2.
Ce na levi in desni strani pristejemo stevilo n — a0x, dobimo 0©y1 = 0©y2, in zato y1 = y2, kar je v protislovju z na so predpostavko.
C e pa bi se ujemala elementa v stolpču y, in sičer v vrstičah x1 in x2, bi pa dobili
a 0 x1 © y = a 0 x2 © y,
od koder najprej sledi a 0 x1 = a 0 x2 (pristejemo n — y na levi in desni strani), nato pa se x1 = x2 (pomnozimo levo in desno stran z a-1, kar smemo, saj je a G Z£). To pa je ponovno protislovje.	I
6.4 Pari ortogonalnih latinskih kvadratov
Naj bosta A in B dva latinska kvadrata velikosti n zapolnjena s stevili N = {1,2,...,n}. Element, ki stoji na preseči sču i-te vrstiče in j-tega stolpča matrike A označimo z aij, enako lezeči element v matriki B pa z bj. Za latinska kvadrata A in B pravimo, da sta ortogonalna, če za vsak urejeni par (x,y) G N x N obstaja natanko en par indeksov i, j G {1,... ,n}, tako daje aj = x in bj = y. Z drugimi besedami, A in B sta ortogonalna, če pari (aij, bij) enako lezečih elementov iz A in B opisejo čelotno mnozičo urejenih parov iz N x N.
Za zgled si oglejmo naslednje tri latinske kvadrate velikosti 4.
A=
1234 2341 3412 4123
B=
1234 2143 3412 4321
C=
1234 3412 4321 2143
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 najlazje prepričamo, če sestavimo kvadrat parov in preverimo, da se v njem res pojavijo vsi pari stevil med 1 in 4 (vsak natanko enkrat).
(1,1) (2,2) (3,3) (4,4)
(2.3)	(1,4) (4,1) (3,2)
(3.4)	(4,3) (1,2) (2,1) L (4, 2) (3,1) (2, 4) (1, 3)
Par ortogonalnih latinskih kvadratov velikosti n lahko uporabimo za resitev različiče Eulerjeve naloge z n častniki iz n regimentov. Na primer,
(B, C) =
ce regimente oznacimo z a, b, c in d, cine pa z gen, pol, maj in por, tedaj iz zgornjega para kvadratov dobimo zahtevano razporeditev castnikov, ce prve komponente parov zamenjamo po pravili 1 ^ gen, 2 ^ pol, 3 ^ maj in
4 ^ por, druge komponente pa po pravilu 1 ^ a ,2 ^ b, 3 ^ c in 4 ^ d. Tako dobimo naslednjo razporeditev:
(gen, a)	(pol, b)	(maj, c)	(por, d)
(pol, c)	(gen, d)	(por, a)	(maj, b)
(maj, d)	(por, c)	(gen,b)	(pol, a)
(por, b)	(maj, a) (pol, d)	(gen, c)
Poglejmo si sedaj kako poiskati par ortogonalnih latinskih kvadratov velikosti n za vsako liho stevilo n.
Izrek 6.3 Naj bo n, n > 3, naravno število in naj bosta a in b obrnljiva elementa mnozice Zn, za kateri je tudi razlika |b — a| obrnljiva v Zn. Tedaj sta La(n) in Lb(n) ortogonalna latinska kvadrata velikosti n.
Dokaz: To, da sta La(n) in Lb(n) latinska kvadrata, ze vemo. Dokazimo se, da sta ortogonalna. Zaradi enostavnosti bomo operaciji © in 0 v Zn pisali kar kot obicajno sestevanje in mnozenje. Ce kvadrata La(n) in Lb(n) nista ortogonalna, tedaj obstajata dva para indeksov (x,y) G Zn x Zn in (s,t) G Z n x Z n, za katera velja (ax + y, bx + y) — (as + t, bs + t). Od tod sledi a(x — s) — y — t in b(x — s) — y — t. Ce ti dve enakosti od stejemo med seboj, dobimo (a — b)(x — s) — 0. Ker pa je element a — b obrnljiv v Zn, od tod sledi x — s. Ce to vstavimo v enakost a(x — s) — y — t, dobimo se y — t, kar je v protislovju s predpostavko, da sta para (x, y) in (s, t) razlicna. I
Posledica 6.4 Za vsako liho število n obstaja par ortogonalnih latinskih kvadratov velikosti n.
Dokaz: Ker je n liho stevilo, je za a — 1 in b — n—1 stevila b—a — n—2 tuje stevilu n. Zato sta latinska kvadrata L1(n) in Ln-1(n) ortogonalna. I
6.5 Resljivost Eulerjeve naloge
V prej s njem razdelku smo videli, kako Eulerjevo resimo nalogo za liho stevilo regimentov. Kaj pa, ce je regimentov sodo mnogo, kot je to primer v originalni Eulerjevi nalogi (n — 6). Izkaze se, daje naloga re s ljiva prav za vse n, razen za n — 2 in 6. Resitev za stevila n, ki so deljiva s 4 je dokaj enostavno poiskati (pomagamo si z re s itvijo za n — 4, ki smo jo navedli zgoraj), za stevila, ki pa dajo ostanek 2 pri deljenju s 4 pa je konstrukcija mnogo tezja.
7 Igra nim
Igra nim je igra za dva igralCa, ki izmeniCno jemljeta vzigaliCe s treh kupCkov, pri Cemer sme igraleC na potezi vzeti s poljubnega (vendar le enega) kupCka poljubno stevilo vzigaliC (vsaj eno, lahko pa tudi vse). Zmaga igraleC, ki vzame zadnjo vzigaliCo. Koliko vzigaliC naj bo na kupih, da bo igra dobljena za igralCa na potezi (ob njegovi pravilni igri, seveda) in koliko, da bo dobljena za igralCa, ki ni na potezi?
7.1 Nim vsota
Kot bomo videli v naslednjem razdelku, je odgovor na zgornje vpra sanje zelo enaostaven, Ce vpeljemo nekoliko nenavaden naCin se stevanja naravnih stevil, ki gaimenujemo nim vsota.
Vzemimo naravni stevili a in b (v tem poglavju bomo med naravna stevila pristevali tudi stevilo 0) ter ju zapi simo dvoji sko (po potrebi manj semu od stevil dodajmo na zaCetek nekaj niCel, da bosta obe stevili imeli enako dolg zapis):
a = ao + a1 ■ 2 + a2 ■ 22 + ... + an ■ 2n = anan-1... ao(2) ; G {0,1} b = bo + b1 ■ 2 + b2 ■ 22 + ... + bn ■ 2n = bnbn-1... bo(2) ; bi g {0,1}
Nim-vsoto stevil a in b definirajmo na obiCajen naCin, le da pri sestevanju v kupčku ne prenasamo viska v naslednji stolpeC. Da ne bo prihajalo do zmede, bomo nim-sestevanje oznaCevali s ©, navadno pa s +. Velja torej
c = a © b , kjer c = cncn-1... c0(2) , ck = ak + bk mod 2 .
Oglejmo si zgled. Vzemimo a = 5 = 101(2) in b = 3 = 11(2)
101 011 110
Ko smo v skrajno desnem stolpCu sesteli 1 + 1, smo dobili 2 kar je po modulu 2 enako 0. Dobljeni rezultat ponovno interpretiramo kot stevilo v dvojiskem zapisu in dobimo
5 © 3 = 110(2) =6.
Ni tezko videti, da je nim vsota komutativna (tj. a © b = b © a) in asociativna (tj. a © (b © c) = (a © b) © c). Vlogo niCle, tako kot pri obiCajnem
sestevanju, igra stevilo 0. Poleg tega pa za vsako naravno stevilo 0 velja nekoliko nenavadna enakost
o © o = 0. 7.2 Zmagovalna strategija
Poglejmo, kako si z nim vsoto lahko pomagamo pri igranju igre nim. Prepričajmo se, da velja naslednje:
Izrek 7.1 Igra nim je v poziciji (x, y, z) dobljena za igralca na potezi, ce in samo ce je nim vosta x © y © z nenicelna. Zmagovalna poteza je tista, ki prevede igro v pozicijo z nim-vsoto enako 0.
Dokaz: Izrek lahko dokazemo z indukčijo na skupno stevilo vzigalič. C e je to stevilo enako 0, potem igra izgubljena za igralča na potezi (saj je zadnjo vzigaličo v prejsnji potezi vzel njegov nasprotnik). Denimo, sedaj, da je na mizi vsaj ena vzigaliča in da izrek velja za vse pozičija s strogo manj vzigaličami.
Za začetek predpostavimo, da je nim vsota neničelna. Dokazati moramo, da je tedaj igra dobljena za igralča na potezi. Zaradi indukčijske predpostavke je dovolj dokazati, da obstaja poteza, ki prevede igro v ničelno nim vsoto. Do taksne poteze pridemo tako, da stevila vzigalič v posmaeznik kupčih zapi semo v dvoji skem sistemu, jih podpisemo in po stolpčih sestejemo v njihovo nim vsoto. Ker je le-ta neničlena, lahko v vsoti najdemo vsaj eno eničo. Vzemimo prvo eničo z desne in si oglejmo njen stolpeč (imenujmo ha stolpeč X. Ker je vsota stolpča X enaka 1, je v njem liho mnogo enič, in zato obstaja vrstiča (imenujmo jo vrstiča Y), ki ima v stolpču X eničo. Vrstičo Y spremenimo tako, da v vseh tistih stolpčih, kjer ima vsota eniče, spremenimo vrednost vrstiče Y (iz 1 na 0 ter iz 0 v 1). Dobljeno vrstičo imenujmo Y'. Ce vrstičo Y nadomestimo z vrstičo Y', se nim vsota vrstič spremeni v 0 (tako smo namreč zgradili vrstičo Y'). Po drugi strani pa je stevilo, ki ga predstavlja vrstiča Y', manj se od stevila , ki ga predstavlja vrstiča Y, saj smo v vrstiči Y sreminjali le stolpče desno od stolpča X, pri stolpču X pa smo 1 spremenili v 0. Označimo razliko teh dveh stevil z 0. To pomeni, da lahko igraleč na potezi z odstranjevanjem 0 vzigalič iz kupa vzigalič, ki ustreza stolpču Y, spremeni nim vsoto v 0 in s tem (po indukčijski predpostavki) postavi nasprotnika v izgubljen polozaj.
Obratno, če je nim vsota dane pozičije enaka nič, potem bo igraleč na potezi, ne glede na to, kaj odigra, nim vsoto spremenil (premislek!) in tako nasprotnika postavil v pozičijo z neničelno nim vsoto. Po indukčijski
predpostavki pa je taksna poziCija dobljena za igralCa, ki bo takrat na potezi - torej za nasprotnika. PoziCija z niCelna nim vsoto je zato izgubljena za igralCa na potezi.	I
Zgled. Na treh kupcih imamo zaporedoma 6, 13 in 14 vžigalic. Ali je igra dobljena za igralca na potezi ali za igralca, ki ni na potezi?
Zapi s imo stevila 6, 13 in 14 v dvoji s kem zapisu in jim poisCimo nim vsoto.
6:	0110
13 :	1101
14 :	1110
©:	0101
Nim vsota je neniCelna, kar pomeni, da je igra dobljena za igralCa na potezi. Postavimo se v njegovo vlogo in razmislimo, kaj moramo odigrati, da bo igra ostala dobljena za nas.
Gledano z leve proti desni se prva eniCa v vsoti pojavi v drugem stolpCu. Izberimo vrstiCo, ki ima v tem stolpCu eniCo. Na izbiro imamo kar vse tri vrstiCe - odloCimo se, na primer, za drugo (1101). Ker se v vsoti eniCa pojavi se v zadnjem stolpCu, popravimo drugo vrstiCo na drugem in zadnjem stolpCu - dobimo 1000, kar v dvoji s kem zapisu pomeni stevilo 8. To pomeni, da moramo z drugega kupCka vzeti toliko vzigaliC, da jih bo ostalo 8. Ker je na zaCetku tam 13 vzigaliC, jih moramo torej vzeti 5. S tem bomo igro prevedli v situaCijo
6:	0110
8:	1000
14 :	1110
©:	0000
z niCelno vsoto, ki je izgubljena za na sega nasprotnika, ki se v tej situaCiji znajde na potezi.	■
8 Zapornikova dilema
Denimo, da poličija zasači pri nečednih poslih dva nepridiprava, zaradi pomanjkljivih dokazov pa ni prepričana, da bo na sodisču dosegla obsodilne sodbe brez priznanja sodelujočih. Zato si izmisli naslednji postopek:
Osumljenča zapre v ločeni sobi in vsakemu od njiju pozove, da dejanje prizna in hkrati obtozi tudi svojega pajdasa. Hkrati poličija (v sodelovanju s tozilstvom, seveda) obljubi, da bo v primeru, če en prizna, drugi pa ne, tistega, ki je priznal, izpustila, za drugega pa zahtevala 10 let zapora. Ce priznata oba, gresta tudi v zapor oba, vsak za 7 let, če pa ne prizna nihče od njiju, bodo ze nasli kaj, za kar ju bodo zaprli - vsakega za 1 leto.
Nepridiprava sta se tako zna s la v klasični zapronikovi dilemi. Kako bosta dilemo razresila račionalna osebka? Prvi nepridiprav razmi slja takole:
Ce drugi ne prizna, je zame gotovo bolje, da priznam, saj bom tako prost, sicer pa bi odsedel 1 leto. Ce pa drugi prizna, pa je spet bolje, da tudi sam priznam, saj bom tako dobil le 7 let namesto 10. V vsakem primeru je torej bolje, da priznam.
Račionalna zapornika se bosta torej oba odločila za priznanje, kar ju bo na konču popeljalo vsakega za 7 let v zapor. S tem seveda zapravita odlično priloznost, da ob hkratnem vztrajanju pri nedolznosti odsluzite le vsak po 1 leto. Poskusimo zgornjo situačijo posplos iti in jo izraziti v matematičnem jeziku.
Imejmo dva igralca (v zgornjem primeru zapornika): P1 in P2. Vsak od njiju ima na voljo mnozičo akcij, ki jih lahko izvede - mnozičo akčij igralča Pi označimo z Ai (v zgonjem primeru je A1 = A2 = {P, NP}). Igra, ki jo igralča igrata je preprosta: vsak od njiju izbere eno od akčij iz svoje mnoziče moznih akčij. To storita istočasno, tako da noben od njiju ne ve, katero akčijo je izbral drugi. Paru akčij (a1,a2), ai G Ai, ki jih igralča izbereta, rečemo profil. Mnoziča vseh moznih profilov je torej enaka A1 x A2. V primeru zgoraj opisane zapornikove dileme imamo torej stiri mozne profile: (P, P), (P, NP), (NP, P) in (NP, NP).
Ko oba igralča izbereta svojo akčijo in tako določita nek profil (a1, a2) G A1 x A2, dobita nagrado, ki jo izrazimo kot realno stevilo. Pri tem si mislimo, da si vsak igraleč zeli čim večje stevilo za nagrado. Nagrado igralča Pi pri profilu (a1,a2) označimo z ui(a1,a2). V primeru zapornikov je za nagrade smiselno vzeti negativno stevilo let prisojenega zapora, saj gre v resniči za kazen in ne nagrado v pravem pomenu besede - tako dobimo:
U1(P,P) = —7, U1(P,NP) =0, U1(NP,P) = —10, U1(NP,NP) = —1,
U2(P,P) = —7, U2(P,NP) = —10, U2(NP,P) = 0, U2(NP,NP) = —1.
Funkčijama u1: A1 x A2 ^ R in u2: A1 x A2 ^ R rečemo funkciji preferenc igralčev P1 in P2.
Igra postane preglednejsa, če nagrade zlozimo v bimatriko, katere vrstiče so ostevilčene z elementi iz mnoziče A1, stolpči iz mnoziče A2, na presečisču vrstiče o1 G A1 in stolpča o2 G A2 pa stoji par u1(o1 ,o2),u2(o1 ,o2). V primeru zapornikove dileme je taka bimatrika torej enaka
P NP P / —7, —7 0, —10 ) NP —10, 0 —1, —1 .
Ko imamo bimatriko dano, lahko pozabimo na originalno igro in si mislimo, da igralča igrata igro kar na bimatriki: Prvi igraleč izbere vrstičo, drugi stolpeč, nagrado pa prečitata na preseči sču izbrane vrstiče in stolpča - prvo stevilo na preseči sču je nagrada prvega igralča, drugi stevilo pa nagrada drugega igralča. Taksno igro v literaturi poznamo pod pojmom strateška igra s funkcijo preferenc za dva igralca.
8.1 Nashevo ravnovesje
Oglejmo si ponovno bimatriko, ki ustreza zapornikovi dilemi. Pojasnili smo ze, kaksno (sičer povsem račionalno) razmisljanje napelje zapornika, da izbereta profil (P,P), ki je očitno za oba neugodnejsi od profila (NP,NP).
Srz problema tiči v tem, da ima med vsemi moznimi profili le profil (P,P) naslednjo lastnost: Ce je kateremu koli od obeh igralčev dana moznost, da svojo akčijo spremeni (drugemu pa ne), igraleč nima nobene motivačije, da bi to storil. Premislimo, da je temu res tako: Ce je moznost spremembe akčije dana prvemu igralču, se zanjo ne bo odločil, saj bi to privedlo do profila (NP,P), ki je zanj se slab si kot profil (P,P). Podobno, če je moznost spremembe akčije dana drugemu igralču, se zanjo ne bo odločil, saj je zanj profil (P,NP) slabsi kot profil (P,P).
Profilom, ki imajo zgoraj opisano lastnost, rečemo Nasheva ravnovesja. Zapi simo definičijo Nashevega ravnovesja se matematično korektno: Profil (o1,o2) je Nashevo ravnovesje strateske igre s funkčijama preferenč u1 in u2, če velja naslednje:
Vo1 G A1 \ {o1} : u1(o1, o2) < u1 (o1, o2),
V02 G A2 \ {o2} : u2(o1 ,02) < U2(o1,o2).
Ce v zgornjih dveh neenakostih nadomestimo sibko neenakost < s strogo neenakosjo <, potem govorimo o strogem Nashevem ravnovesju.
Nekatere igre imajo lahko veC Nashevih ravnovesij, nekatere natanko eno, nekatere pa nobenega. Primer z natanko enim Nashevim ravnovesjem smo ze videli (zapornikova dilema). Oglejmo is se primera z veC in z nobenim Nashevim ravnovesjem.
Bitka spolov
Fant in punCa se odpravljata v kino, kjer v dveh dvoranah igrata: akCijski film in romantiCna komedija. Vsak zase se morata odloCiti, katerega od filmov si bosta ogledala. Fantu bi bilo najbolj vseC, da gresta oba gledat akCijski film (to opCijo oCeni z oCeno 10), Ce to ne gre, bi se zadovoljil tudi s skupnim ogledom romantiCne komedije (to opCijo oCeni s 5), najmanj zadovoljen pa bi bil, Ce si film ogleda sam - v tem primeru mu je Celo vseeno kaj gleda (ti dve opCiji oCeni z 0). SituaCija pri punCi je simetriCna. Najraje bi gledala romantiCno komedijo skupaj s fantom (oCena 10), Ce to ne gre, potem akCijski film skupaj s fantom (oCena 5), siCer pa bo nezadovoljna (oCena 0). Njuno dilemo lahko opisemo z bimatriko
AF RK AF / 10, 5 0, 0 \ RK 0, 0 5, 10 .
Hitro se prepriCamo, da ima ta igra dve Nashevi ravnovesji (obe strogi), namreC (AF,AF) in (RK,RK). Kako se bo igra v resniCi razpletla, je tezko napovedati. Ce v pogovoru eden od obeh ne bo popustil, se jima prav lahko primeri, da bosta sla gledat vsak svoj film, kar je za oba najmanj ugoden razplet. Njuna dilema se v literaturi imenuje bitka spolov.
Par nepar
Dva igralCa istoCasno pokazeta en ali dva prsta. Ce je skupno stevilo pokazanih prstov sodo, tedaj prvi igraleC drugemu plaCa en evro, siCer pa drugi igraleC plaCa prvemu en evro. PripadajoCa bimatrika je taksnale:
1 prst 2 prsta
1	prst / —1,1 1, —1 \
2	prsta y 1, —1 —1,1 J.
Ta igra, ki jo imenujemo tudi par nepar (ali tudi matching coins v anlge sCini) nima Nashevega ravnovesja. Omenimo se, da ima ta igro to lasntost, da je
vsota preferenčnih funkčij u1 (a1, a2)+u2(a1, a2) pri vsakem profilu (a1, a2) G A1 x A2 anaka 0. Taksnim igram rečemo tudi igre z ničelno vsoto in jih lahko enolično opi semo z eno samo matriko, namreč z matriko vrednosti u1(a1 ,a2). Vrednosti, ki pripadajo drugemu igralču dobimo tako, da vrednosti preferenčne funkčije drugega igralča pomnozimo z —1. V konkretnem primeru tako dobimo matriko
8.2 Dominantne akcije
Pri strateski igri se včasih primeri, daje kaka od akčij taksna, daje račionalni igraleč ne bo v nobenem primeru izbral. Na primer, če obstajata akčiji a1, a1 G A1, za kateri pri vsakem a2 G A2 velja:
potem račionalni prvi igraleč ne bo izbral akčije a1, saj je ne glede na izbiro drugega igralča zanj bolje (ali pa vsaj ne slab s e) izbrati akčijo a1. V tem primeru rečemo, da akčija a1 dominira akčijo a1, oziroma, da je akčija a1 dominirana z akčijo a1. Na analogen način lahko definiramo tudi pojem dominačije med akčijami drugega igralča.
Ob predpostavki račionalnosti igralčev lahko torej dominirane akčije kar izbri semo iz mnoziče akčij in tako zmanjsamo velikost igre. V zelo posebnih primerih lahko s postopkom brisanja dominiranih akčij igro prevedemo do le ene mozne akčije za vsakega igralča. V taksnem primeru lahko rezultat igre (ob predpostavki račionalnosti igralčev) natančno napovemo. Profil akčij, ki ga pri tem dobimo, je hkrati tudi edino Nashevo ravnovesje igre.
U1(a1,a2) < U2(a1,a2),
9 Simpsonov paradoks
Zamislimo si naslednjo hipoteticno situacijo. Na dveh kosarkarskih tekmah ekpie Zmajckov igralca Joze in Lojze meceta proste mete z naslednjim izkoristkom:
	1. tekma	2. tekma
Joze	50%	75%
Lojze	25%	70%
Zvesti navijaci Zmajckov iz tega brz sklepajo, da je Joze bolj si izvajalec prostih metov kot Lojze. Pa si poglejmo se, koliko prostih metov sta Joze in Lojze na vsaki od tekem vrgla in koliko zadela.
	1. tekma	2. tekma
Joze	8 : 16	3 : 4
Lojze	1 : 4	7 : 10
Na obeh tekmah skupaj je torej Joze zadel 11 metov od 20, kar pomeni, da je bil 55% uspe sen. Lojze pa je zadel 8 metov od 14, kar znese dobrih 57%. Gledano na obeh tekmah skupaj, je bil torej Lojze boljsi od Jozeta (pa ceprav je bil na vsaki tekmi slabsi).
Kratek premislek nam pove, da je do taksne presenetljive situacije pri slo zato, ker je Lojze na 2. tekmi (kjer je bil izkoristek metov obeh igralcev precej vecji kot izkoristek na 1. tekmi) vrgel precej vec prostih metov kot Joze, na 1. tekmi (ko sta oba metala slabo), pa je veckrat metal Joze. Zato ima v skupnem Lojzetovem rezultatu poglavitno vlogo 2. tekma, v Jozetovem pa 1. tekma.
Zgoraj opisani nenavadni pojav se v literature pojavlja pod imenov Simpsonov paradoks, poimenovan po britanskem statistiku Edwardu Simpsonu. Ta navidezni paradoks se v najrazlicnejsih preoblekah pogosto pojavlja v vsakdanjem zivljenju. Oglejmo si nekaj primerov.
9.1 Vpisi na podiplomski študij na univerzi Berkley
Leta 1973 se je na podiplomski studij na univerzo v Berkleyju poskusalo vpisati 12.763 kandidatov, od tega 8.442 moskih in 4.321 zensk. Na studij je bilo sprejetih 3.738 moskih in 1.494 zensk. Ce izracunamo uspesnost po spolih, dobimo naslednjo tabelo:
	prijavljeni	sprejeti	delez
mos ki	8.442	3.738	44%
zenske	4.321	1.494	35%
skupaj	12.763	5.232	41%
Tako velika razlika med uspe snostjo mo skih in zensk je sprozila namigovanja, da dajejo vpisne komisije prednost mo skim (hote ali nehote), kar bi ob predpostavki, da je usposobljenost kandidatov enakomerno porazdeljena med moske in zenske, pomenilo spolno diskriminačijo. Ker poteka izbirni pročes na vsakem oddelku univerze ločeno, so nato pogledali, kateri izmed oddelkov kazejo najhuj so sliko. Rezultat te podrobne analize pa je pokazal presenetljivo sliko: Na veliki večini oddelkov je bila uspesnost zenskih kandidatk visja od uspesnost mos kih kandidatov, na tistih, kjer pa so bili moski uspesnejsi, pa je bila razlika tako majhna, da jo je bilo moč pripisati naključju. Ugotovili so torej, da sprejemni postopki na nobenem od oddelkov niso diskriminatorni v skodo zensk. Od kod torej navidezna diskriminatorna slika na nivoju čelotne univerze?
Odgovor se skriva v dejstvu, da porazdelitve kandidatk po oddelkih in kandidatov po oddelkih nista bili enaki: zenske so se v večini vpisovale na popularnej se oddelke, kjer je bilo razmerje med prijavljenimi in sprejetimi zelo veliko (in zato uspesnost pri sprejemu nizka), mo ski pa so se v večji meri kot zenske odločali za manj popularne studije, kjer je bilo prijavljenih glede na stevilo vpisnih mest relativno malo in zato uspe snost pri sprejemu visoka. Zato je na nivoju čelotne univerze uspesnost mos kih blizje povprečni uspe snosti na teh, manj popularnih oddelkih, uspesnost zensk pa blizje povprečni uspesnosti na popularnih oddelkih. Na videz diskrimina-torne stevilke so torej poslediča neenakih preferenč zensk in mos kih in ne diskriminačije vpisnih komisij.
9.2 Uspesnost zdravljenja
Primer v tem razdelku je sičer hipotetičen, sloni pa na konkretni studiji o zdravljenju ledvičnih kamnov, ki sojo izvajali v Angliji med leti 1972 in 1985. Zaradi enostavnosti smo sičer kompleksno studijo nekoliko poenostavili.
Mislimo si, da zdravimo 100 bolnikov z boleznijo X. Na razpolago imamo dva načina zdravljenja: A in B. Bolezen X lahko nastopi v dveh oblikah X1 in X2. Glede na tip bolezni in na način zdravljenja, za katerega smo se odločili, bolnike razdelimo v stiri skupine. V naslednji tabeli podajmo stevilo bolnikov v pozamezni skupini in stevilo bolnikov, pri katerih je bilo zdravljenje uspesno. Dodajmo se odstotek uspe snih zdravljenj.
	tip X1	tip X2	skupaj
zdravljenje A	30 : 60 (50%)	7 : 10 (70%)	37 : 70 (53%)
zdravljenje B	2 : 5 (40%)	15 : 25 (60%)	17 : 30 (57%)
Zgornja tabela nas po eni strani napeljuje na zakljuCek, da je naCin zdravljenja A pri obeh tipih bolezni uspesnej si od tipa zdravljenja B. Po drugi strani pa je zdravljenje B uspes nejse na skupini vseh bolnikov z boleznijo X. Do tega, na videz protislovnega zakljuCka smo prisli zaradi neenakomerne porazdelitve zdravljenj A in B znotraj posameznih tipov bolezni.
Literatura
[1]	S. J. Brams, A. D. Taylor: An Envy-Free Cake Division Protocol, The AmeriCan MathematiCal Monthly 102 (1995), 9-18.
[2]	D. Maru s iC, T. Pisanski Mobius-Kantorjeva konfiguracija v politiki, Presek 28 (2000-2001), 264-268.
[3]	S. Cabello, M. Juvan Strateške igre s funkcijami preferenc, rokopis.