Eräs noppapeli

Pelaaja saa aluksi yhden nopan. Joka kierros pelaaja heittää kaikki noppansa ja menettää ne joiden osoittamaa arvoa tuli useampi kuin yksi. Kierroksen päätteeksi pelaaja saa aina yhden uuden nopan. Tavoite on saada seitsemän noppaa (tai yleisemmin $d+1$ noppaa, kun nopassa on $d$ tahkoa). Toisin sanoen peli päättyy, kun pelaajalla on kuusi noppaa ja niillä tulee jokaisella eri arvo. Mikä on yhden pelin kierrosten määrän ( $N$ ) odotusarvo?

Ratkaisu

Peli on Markovin ketju, jossa tilat ovat noppien määrät $1, 2, \dots, d+1$ . Meidän täytyy selvittää siirtymätodennäköisyydet näiden välillä. Pienille arvoille, kuten $d = 6$ , tämä voidaan tehdä tutkimalla kaikki mahdolliset heitot ja kirjaamalla kuinka moni niistä säilyttää kuinkakin monta noppaa. Seuraava Sage-koodi tekee tämän:

from itertools import product
from collections import Counter

def getTransitionsProbsBrute1(diceAmounts, dieFaces):
    n = dieFaces+1
    ret = [0]*n
    for dice in product(range(dieFaces), repeat=diceAmounts):
        keep = sum(x for x in Counter(dice).values() if x==1)
        #we're adding 1 die after round, but 1 is the
        #first state, so keep is the correct index
        ret[keep] += 1
    tot = dieFaces**diceAmounts
    return [x/tot for x in ret]

Laskentaa voidaan hieman nopeuttaa käyttämällä kombinaatioita (takaisin panolla):

from itertools import combinations_with_replacement as cmb_rep
from collections import Counter

def getType(dice):
    return list(Counter(dice).values())

def getTransitionsProbsBrute2(diceAmount, dieFaces):
    n = dieFaces+1
    ret = [0]*n
    for dice in cmb_rep(range(dieFaces), r=diceAmount):
        keep = sum(x for x in Counter(dice).values() if x==1)
        #multinomial of the type gives the amount
        #of orderings this corresponds to when account for all
        weight = multinomial(getType(dice))
        ret[keep] += weight
    tot = dieFaces**diceAmount
    return [x/tot for x in ret]

Tässä tarvittiin tietää kombinaatiosta sen tyyppi eli siinä esiintyvien lukujen esiintymien lukumäärät (koottuna vektoriksi).

Nyt voidaan muodostaa siirtymämatriisi ja käyttää tavanomaisia keinoja $\mathbb{E}[N]$ :n selvittämiseen:

def getTransitionMatrixBrute(dieFaces):
    arr = [getTransitionsProbsBrute2(i, dieFaces)
           for i in range(1, dieFaces+2)]
    return Matrix(arr)

def getFundamentalMatrix(pMat):
    n = pMat.dimensions()[0]-1
    arr = [[(1 if i==j else 0)-pMat[i][j]
            for j in range(n)]
           for i in range(n)]
    return Matrix(arr)**-1

def getExpectedGameLen(dieFaces):
    P = getTransitionMatrixBrute(dieFaces)
    fundMat = getFundamentalMatrix(P)
    return sum(fundMat[0])


print (getExpectedGameLen(6))

Ja näin saadaan tulos

$\begin{aligned} \mathbb{E}[N] = \frac{133191861}{12500} = 10655.34888 \end{aligned}$

Kombinaatioiden (eritoteen takaisinpanon kanssa) määrä kuitenkin kasvaa melko nopeasti, kun $d$ kasvaa. Edellä jo mainittua tyyppi-ideaa voidaan jatkojalostaa: se kuinka monta noppaa heittotuloksesta menetetään riippuu vain tyypistä (kaikki, joiden arvoa yli yksi kappale menetetään). Tyypit ovat noppien lukumäärän ositukset (paitsi viimeisen tilan ositus $[1,1,\dots,1]$ ei kelpaa, sillä se tarkoittaa $d+1$ eri arvoa, mutta nopassa on vain $d$ eri arvoa. (Tästä vielä huomio-osioissa.) Nyt täytyy enää laskea kuinka moni noppien heitto vastaa kutakin ositusta. Tätä on selvitetty koodin kommenteissa:

def getFactorOfType(t, dieFaces):
    #first choose a value for each number in the type
    ret = factorial(dieFaces)/factorial(dieFaces-len(t))
    #divide away the orderings in the type
    #(we need the type's type)
    ret /= factorialProd(getType(t))
    #now we can multiply by the total number of orderings
    ret *= multinomial(t)
    return ret

def getTransitionMatrix(dieFaces):
    n = dieFaces+1
    arr = [[0]*n for i in range(n)]
    for i in range(1, n+1):
        for t in Partitions(i):
            if (len(t)>dieFaces): continue
            toState = i-sum(x for x in t if x>1)
            weight = getFactorOfType(t, dieFaces)
            arr[i-1][toState] += weight
    for i in range(n):
        tot = dieFaces**(i+1)
        for j in range(n):
            arr[i][j] /= tot
    return Matrix(arr)

Tässä vielä lopullinen tyypeillä laskeva koodi kokonaisuudessaan ja taulukko tuloksesta muutamilla $d$ :n arvoilla:

from collections import Counter

def getType(dice):
    return list(Counter(dice).values())

def factorialProd(arr):
    return reduce(lambda acc,x: acc*factorial(x), arr, 1)

def getFactorOfType(t, dieFaces):
    ret = factorial(dieFaces)/factorial(dieFaces-len(t))
    ret /= factorialProd(getType(t))
    ret *= multinomial(t)
    return ret

def getTransitionMatrix(dieFaces):
    n = dieFaces+1
    arr = [[0]*n for i in range(n)]
    for i in range(1, n+1):
        for t in Partitions(i):
            if (len(t)>dieFaces): continue
            toState = i-sum(x for x in t if x>1)
            weight = getFactorOfType(t, dieFaces)
            arr[i-1][toState] += weight
    for i in range(n):
        tot = dieFaces**(i+1)
        for j in range(n):
            arr[i][j] /= tot
    return Matrix(arr)

def getFundamentalMatrix(pMat):
    n = pMat.dimensions()[0]-1
    arr = [[(1 if i==j else 0)-pMat[i][j]
            for j in range(n)]
           for i in range(n)]
    return Matrix(arr)**-1

def getExpectedGameLen(dieFaces):
    P = getTransitionMatrix(dieFaces)
    fundMat = getFundamentalMatrix(P)
    return sum(fundMat[0])


res = [[d, float(getExpectedGameLen(Integer(d)))]
      for d in range(1, 21)]
print (res)

d	E[N]
1	1
2	4
3	15
4	80.96296
5	718.61364
6	10655.34888
7	261903.04770
8	10636087.48690
9	713183947.85983
10	7.89467e+10
11	1.44259e+13
12	4.35102e+15
13	2.16594e+18
14	1.77942e+21
15	2.41246e+24
16	5.39710e+27
17	1.99232e+31
18	1.21348e+35
19	1.21944e+39
20	2.02174e+43

Huomioita

Viimeisen tilan siirtymiä ei tarvitsisi laskea (siinä mielessä, että peli jatkuisi) vaan se asetetaan absorboivaksi eikä sitä tarvita odotusarvon laskussa ollenkaan. Itse asiassa sen laskeminen on juuri kaikista matriisin riveistä vaativin, sillä tarvittavia objekteja (permutaatioita takaisinpanolla, kombinaatioita takaisin panolla tai osituksia) on eniten.
Myös ensimmäinen tila on käytännössä turha: yhtä noppaa on turha edes heittää, koska sitä ei voi menettää; ottaa vaan suoraan toisen nopan. Mutta pidetään se mukana yksinkertaisuuden vuoksi ja lasketaan pelin pituuteen mukaan myös nämä deterministiset askeleet.

Tehtäviä

Muokkaa koodia, niin että turhia viimeisen tilan siirtymiä ei lasketa. Aseta viimeiseen tilaan itsesiirtymä todennäköisyydellä 1 tai unohda koko viimeinen tila, sillä sitä ei laskuissa tarvita.
Laske $N$ :n varianssi. Vinkki: katso Wikipedian artikkeli.
Entä jos sovitaan, että pelaaja häviää pelin, mikäli hän jollain kierroksella menettää kaikki noppansa. Mikä on häviämisen todennäköisyys?
Voidaan sopia mitä erilaisimpia sääntöjä siitä miten pelaaja saa lisänopan /-noppia tai menettää niitä riippuen hänen heitostaan. Tutki jotain tällaista muokattua peliä.

Kaksi karsinaa

Kaikkihan tietävät, että ympyrä on paras muoto kun halutaan aidata tietyn suuruinen ala käyttäen mahdollisimman vähän aitaa (ks. isoperimetrinen epäyhtälö). Mutta entäpä, jos onkin tehtävä kaksi karsinaa, jotka voivat käyttää yhteistä aitaa? Entä yleisemmin $n$ karsinaa?

Oletetaan että yhden karsinan ala on $A = 1$ ja yritetään löytää mahdollisimman pieni piirinen aitaus.

Ensimmäinen vaihtoehto, joka tulee mieleen on kaiketi ”tavallinen” suorakaiteen mallinen, jossa on yksi väliaita:

Optimoidaan piiri ja saadaan $x = \frac{\sqrt{3}}{2} = 0.866$ ja $p=2\sqrt{3} + \frac{6}{\sqrt 3} = 6.9282$ .

Mutta onko tämä paras mahdollinen? Koska ympyrä on paras ratkaisu yhdelle karsinalle, niin kokeillaanpa jakaa ympyrä kahtia:

Saadaan $r = \sqrt{\frac{2}{\pi}}$ ja $p = 2\pi r + 2r = 2(\pi+1) \sqrt{\frac{2}{\pi}} = 6.609$ . Siis parempi kuin suorakaide-ratkaisu.

Mutta entäpä jos yhdistettäisiin hieman kumpaakin: laitetaan keskelle suorakaide ja päihin puoliympyrät (ja tietenkin keskelle jakoaita) ja optimoidaan tämä muoto:

Optimiksi saadaan $r = \sqrt{\frac{2}{2+\pi}}=0.6237$ ja $p=2\sqrt{4+2\pi}=6.413$ . Löydettiin siis halkaistua ympyrääkin parempi ratkaisu.

Toinen tapa yrittää käyttää ympyrää olisi ollut tehdä kaksi täysin erillistä ympyräkarsinaa. Tällöin yhdellä on pienempi säde ( $r=\sqrt{\frac{1}{\pi}}$ ) mutta piiri on $p = 2\times 2\pi r = 4\sqrt \pi = 7.089 > 7$ ja $p=7$ saadaan jo siitä (optimoimattomasta) ratkaisusta, että laitetaan kaksi neliötä vierekkäin.

Olemme tähän asti ajatelleet, että aitauksen kuuluisi olla konveksi (~~tietenkin kummankin karsinan pitää olla konveksi~~, mutta että koko rakennelman?!?!?). Eihän sen täydykään: otetaan vain kaksi sopivan kokoista ympyrää ja läimäytetään ne yhteen. Ei keskikohdasta, vaan optimoidaan tämä kohta.

Tämä onkin niinsanottu tuplakupla ratkaisu ja myös todistetusti (tai itseasiassa 2d-versio on tämä) ongelman optimi ratkaisu, joten optimi on $p = 6.3591$ .

Huomioita

Jos karsinat eivät olisikaan samankokoiset, niin tuplakupla ratkaisussa jakoaita ei olekaan jana, vaan ympyrän kaari (ks. tuplakuplan määritelmä), joten karsinatkaan eivät välttämättä ole konvekseja. Jakokaari määräytyy siitä, että kaarien täytyy kohdata toisensa 120 asteen kulmassa eli niiden tangentit jakavat täysikulman kolmeen yhtäsuureen osaan.
Tarkka ratkaisu, joka tästä 120 asteen vaatimuksesta nähdään on $\alpha = \frac{\pi}{3}$ , $r = \frac{1}{\sqrt{\frac{2\pi}{3} + \frac{\sqrt 3}{4}}}$ ja $p=\frac{\frac{8\pi}{3} +\sqrt 3}{ \sqrt { \frac{2\pi}{3} + \frac{\sqrt 3}{4} }}$

Suorakaiteen neliöiminen

Suorakaide halutaan täyttää päälekkäinmenemättömillä neliöillä. Oletetaan, että suorakaiteen sivujen pituudet ja myös neliöiden sivut ovat positiivisia kokonaislukuja. (Jos ne ovat rationaalilukuja, niin voimme skaalata kaikkien nimittäjien pienimmällä yhteisellä jaettavalla, jolloin päästään kokonaislukutilanteeseen.)

Tämä ”neliöinti” on tietenkin helppoa, kun lähdetään vain erottamaan (esim. mahdollisimman suuria) neliöitä (lopulta voidaan aina jakaa 1×1-neliöihin). Neliöinnissä saattaa tapahtua niin, että se koostuu kahdesta osasta eli suorakaide voidaan jakaa joko pysty- tai vaakaviivalla kahteen suorakaiteeseen siten, että ei kuljeta minkään neliön läpi. Toisin sanottuna neliöiden sivut ovat jossain kohtaa kaikki ”linjassa” koko suorakaiteen matkalta. Kutsutaan tällaisia neliöintejä jaettavissa oleviksi. Jos neliöinti ei ole jaettavissa oleva, on se jaoton. Jokainen neliöinti voidaan muodostaa jaottomista neliöinneistä niitä yhdistelemällä.

Jaettavissa oleva neliöinti (vasemmalla) voidaan jakaa keltaisen viivan kohdalta. Jaottomassa neliöinnistä (oikealla) tällaista jakokohtaa ei löydy.

Toisaalta erityisen kiinnostavia olisi myös sellaiset neliöinnit, joissa jokainen käytetty neliö on erikokoinen. Näitä kutsutaan täydellisiksi. Myös täydellinen neliöinti voi olla jaettavissa oleva, mutta tällöin sen osissa käytettyjen neliöiden täytyy tietenkin olla myös erikokoisia, joten mitä tahansa kahta täydellistä neliöintiä ei voi yhdistää täydelliseksi neliöinniksi.

Entistä rajaavampi oletus neliöinnille on ns. ”yksinkertaisuus”: neliöinti ei pidä sisällään mitään aidosti pienempää neliöintiä eli toisin sanottuna neliöt eivät muodosta sisälle pienempää vähintään kaksi neliötä sisältävää suorakaidetta. Jos neliöinti ei ole yksinkertainen, sen sanotaan olevan yhdistetty. Kuvan 1 molemmat esimerkit ovat yhdistettyjä (oikean puoleisesta löytyy monta sisä-suorakaidetta vaikkei koko suorakaiteen halkaisevaa viivaa löydykään). Sen sijaan kuvan 2 (ks. alla) neliöinti on yksinkertainen.

Yhteys tasoverkkoihin

Olkoon $S$ neliöinti. Merkitään siinä olevien vaakasuorien janojen joukkoa $V$ . Verkon kaaret vastaavat neliöinnin neliöitä (neliö yhdistää janat, joille sen vastakkaiset sivut kuuluvat). Suorakaiteen ylä- ja ala-sivuja vastaavia solmuja kutsutaan verkon pohjois- ja etelä-navoiksi. Esimerkiksi:

Vastaavasti tämä konstruktio voitaisiin tehdä käyttämällä neliöinnin pystysuoria janoja (tällöin vasen ja oikea sivu ovat napoja). Tämä vastaa duaaliverkkoa. Tason duaaliverkko muodostetaan siten, että solmuiksi otetaan edellisen tahkot (sivujen rajoittamat tason alueet). Nyt tehdään kuitenkin vielä yksi lisäys: edellisen navat yhdistetään kaarella, joka jakaa ulkopuolen kahteen alueeseen ja nämä ovat duaaliverkon navat.

Huomataan, että neliöiden sivujen suuruudet liittyvät verkon virtauksiin. Asetetaan verkon sivulle sitä vastaavan neliön suuruinen virtaus. Virtauksen suunta on ilmeinen, kun katsotaan kuinka sivu suhtautuu suorakaiteeseen (jossa virtaus on alaspäin). Huomataan, että tällöin nämä virtaukset totetuttavat Kirchhoffin lait: jokaiseen solmuun saapuva virtaus on yhtä suuri kuin siitä lähtevä virtaus. Perustelu: solmu vastaa neliöinnin vaakaviivaa. Viivan yläpuolella on saapuvat neliöt (eli kaaret) ja alapuolella lähtevät. Kummatkin ovat yhteensä viivan pituus. Tämä toteutuu myös pohjois- ja etelä-navoilla, kun lisätään verkkoon vielä kaari etelä-navalta pohjois-navalle. Myös jokaisen tahkon ympäri kulkevan virtauksen summa on nolla. Tämä onkin edellistä vastaava vaatimus duaaliverkolle.

Nyt voidaankin miettiä toimisiko temppu myös toiseen suuntaan. Tehdään tasoverkolle seuraavaa. Valitaan kaksi solmua navoiksi, laitetaan pohjois-navalle saapuvaksi virta ja ratkaistaan virtaukset, siten että Kirchhoffin säännöt toteutuvat. Etelä-navalta lähtee saman suuruinen virta kuin mikä saapui pohjois-navalle ja sen arvolla voidaan ratkaisu skaalata kokonaislukuvektoriksi. Tästä ratkaisusta voidaan koota suorakaiteen neliöinti.

Katsotaan pientä esimerkkiä:

Tasoverkko, sen Kirchhoffin säännöt koodaava matriisi $K$ , sen ydinvektori (eli yhtälön $Kx = 0$ ratkaisu, huom. voidaan skaalata kokonaislukuvektoriksi, sillä ratkaisu tuottaa aina rationaalilukuja) ja siitä koottu neliöinti. Huom. napoja ja ulkotahkoja ei ole otettu mukaan.

Tässä esimerkissä huomataan eräs erikoisuus: neliöintiin tuli vierekkäin kaksi saman kokoista (4-sivuista) neliötä. Ne tulivat kaarista 0-1 ja 1-2. Mikä näissä kaarissa on vikana? Jos muodostamme duaaliverkon, huomamme että se onkin multiverkko! Vihreän kolmion 012 ja violetin nelikulmion 0123 välillä on kaksi eri sivua. Tämä verkko ei ole 3-kaari-yhtenäinen, vaan solmu 1 voidaan irroittaa verkosta leikkaamalla kaksi kaarta. Kolme-kaari-yhtenäisyys onkin hyvä vaatimus verkolle, jotta saadaan ”hyviä” neliöintejä.

Jos palataan alussa mainittuun neliöinnin jaottomuuden käsitteeseen, niin nyt huomataan, että se vastaa verkon (tai sen duaalin) 1-solmu-epä-yhtenäisyyttä: jos koko suorakaiteen läpi menevää viivaa vastaava solmu poistetaan, tulee verkosta epäyhtenäinen.

Kysymyksiä

Jos tehtävää yleistetään kolmiulotteiseksi eli täytetään laatikko $[0, a]\times[0, b]\times[0,c]$ kuutioilla, kuinka muuttuu vastaavasti muodostettu verkko, kun vaihdetaan akselia, jonka suhteen se muodostetaan? Verkon solmut ovat tasojen osia, joille kuutoiden tahkot asettuvat.

Linkkejä

Binääriblokit

Väritetään $n$ :n peräkkäisen ruudun rivistä osa mustiksi ja lasketaan millaiset putket väritettyjä tuli. Esim:

n=10, värityksestä muodostuu putket [2, 1, 3]

Yhteensä erilaisia värityksiä on $2^n$ , sillä jokainen ruutu voidaan joko värittää tai jättää tyhjäksi (vrt. binääriluvut $< 2^n$ ), mutta kysymykset koskevat värityksestä muodostuvia putkia. Sanotaan putkien pituuksista koottua vektoria putkityypiksi. Yo. esimerkissä putkityyppi on [2, 1, 3].

a) Kuinka monta erilaista putkityyppiä voidaan $n$ :n ruudun rivistä muodostaa?
b) Olkoon rivin pituus $n$ . Kuinka moni eri väritys tuottaa putkityypin [ $k_1, k_2, \dots k_m$ ]?

Mahdolliset väritykset ja putkityypit, n = 1, 2, 3, 4

Ratkaisu

a)

Putkityyppi $[k_1, k_2, \dots, k_m]$ on mahdollinen muodostaa, mikäli se mahtuu $n$ -riviin. Jokaisen putken välissä on oltava vähintään $1$ tyhjä ruutu ja välejä on $m-1$ , joten se mahtuu tasan silloin kun

$\begin{aligned} m - 1 + \sum_{j=1}^m k_j \leq n \end{aligned}$

Määritellään lukujonot $a_n$ ja $b_n$ seuraavasti

$\begin{aligned} a_n = \#\{(k_1, k_2, \dots, k_m) \hspace{.3cm} | \hspace{.3cm} m - 1 + \sum_{j=1}^m k_j \leq n \} \\ b_n = \#\{(k_1, k_2, \dots, k_m) \hspace{.3cm} | \hspace{.3cm} m - 1 + \sum_{j=1}^m k_j = n \} \end{aligned}$

eli $b_n$ laskee sellaiset putkityypit, joita ”ei enää voi pidentää” ja $a_n$ on kysytty jono.

Huomataan, että $b_n$ itse asiassa laskee $n-$ pituisia binäärijonoja, joissa ei ole yli yhden pituisia nollaputkia ja jotka alkavat ja päättyvät ykköseen. Näiden lukumäärä voidaan laskea seuraavan graafin $n-1$ -kävelyjen solmusta A solmuun A määränä.

Solmuja voidaan ajatella tiloina seuraavasti: A=”viimeksi on tullut ykkönen”, B=”viimeksi on tullut nolla”, C=”on tullut kahden nollan putki” . Tila C on hylkäävä, siitä ei pääse enää mihinkään. (Voi myös ajatella, että C:stä on siirtymä vain itseensä; todennäköisyydellä 1, jos graafi mielletään Markovin ketjuksi.) Aloitetaan tilasta A, sillä jonon täytyy alkaa ykkösellä, joten voidaan olettaa, että yksi ykkönen on jo tullut. Kävelyn täytyy myös päättyä tilaan A, sillä viimeinen numero halutaan olevan ykkönen.

Se, että näin todella saadaan haluttu lukumäärä, nähdään esimerkiksi ajattelemalla graafia Markovin ketjuna, jossa tilojen A ja B siirtymät tapahtuvat molemmat todennäköisyydellä $\frac{1}{2}$ ja tilasta C on itsesiirtymä todennäköisyydellä $1$ . Näin saadaan todennäköisyys, että binäärijono on kysytynlainen (ks. tilojen selitykset kuvatekstissä). Tämä muutetaan lukumääräksi kertomalla kaikkien $n-1$ -pituisten binäärijonojen lukumäärällä eli $2^{n-1}$ :llä.

Lasketaan siis vierekkäisyysmatriisin $n-1$ :s potenssi diagonalisoimalla

$\begin{aligned} \left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array} \right] ^{n-1} = \left[ \begin{array}{ccc} -1 & \frac{1-\sqrt 5}{2} & \frac{1+\sqrt 5}{2} \\ * & * & * \\ * & * & * \end{array} \right] \left[ \begin{array}{ccc} 0 & & \\ & \left( \frac{1-\sqrt 5}{2} \right)^{n-1} & \\ & & \left( \frac{1+\sqrt 5}{2} \right)^{n-1} \end{array} \right] \left[ \begin{array}{ccc} 0 & * & * \\ -\frac{1}{\sqrt 5} & * & * \\ \frac{1}{\sqrt 5} & * & * \end{array} \right] \end{aligned}$

Tämän alkio paikassa (0, 0) antaa luvun $b_n$ . Saadaan

$\begin{aligned} b_n = \frac{1}{\sqrt 5} \left ( \frac{1+\sqrt 5}{2} \right)^n - \frac{1}{\sqrt 5} \left ( \frac{1-\sqrt 5}{2} \right)^n \end{aligned}$

joten $b_n$ on kuuluisa Fibonaccin lukujono $f_n =f_{n-1} + f_{n-2}, f_1=1, f_2 = 1$ .

Ratkaistaan sitten $a_n$ . Koska $n+1$ -pituiseen riviin mahtuvalle putkityypille $(k_1, k_2, \dots, k_m)$ pätee joko $m - 1 + \sum_{j=1}^m k_j \leq n$ tai $m - 1 + \sum_{j=1}^m k_j = n+1$ , niin nähdään rekursio

$\begin{aligned} a_{n+1} = a_n + b_{n+1} \end{aligned}.$

Osoitetaan nyt induktiolla, että $a_n = f_{n+2}$ . Perustapaukset $a_0 = 1$ ja $a_1 = 2$ nähdään helposti luetteloimalla. Induktioaskel saadaan suoraan edellä olleesta rekursiosta, sillä, jos oletetaan $a_n = f_{n+2}$ , niin

$\begin{aligned} a_{n+1} = a_n + b_{n+1} = f_{n+2} + f_{n+1} = f_{n+3}. \end{aligned}$

b)

Olkoon putkityyppi [ $k_1, k_2, \dots k_m$ ]. Merkitään väritettyjen ruutujen määrää $S = \sum_{j=1}^m k_j$ . Kysymys voidaan muotoilla toisin: Asetetaan $n-S$ tyhjää ruutua jonoon ja kysytään kuinka monella tavalla näiden väliköistä (ja päädyistä) voidaan valita $m$ kappaletta, joihin putkityypin putket (järjestyksessä) asetellaan. Välikköjä ja päätyjä on $n-S-1 + 2 = n-S+1$ kappaletta, joten vastaus on

$\begin{aligned} {n-S+1} \choose {m} \end{aligned}.$

Huomioita

Jonon $b_n$ voi todeta Fibonacci jonoksi myös huomaamalla rekursioyhtälön $b_n = b_{n-1} + b_{n-2}$ (joko suoraan graafista tai matriisien kertolaskusta).

Eräs korttipeli

Välineet

52 kortin pakka (4 maata, arvot 1-13)
muistiinpanovälineet pisteenlaskua varten

Pelaajia

2-5

Tavoite

Kerätä eniten pisteitä voittamalla tikkejä ja luomalla voittamistaan korteista saman arvoisten korttien ryhmiä.

Aloitus

Arvotaan kuka toimii ensimmäisenä jakana. Jokaiselle pelaajalle jaetaan 7 korttia, jakajasta seuraavasta aloittaen. Jakajasta seuraava myös aloittaa ensimmäisen tikin.

Tikin pelaaminen

Jokainen pelaaja valitsee vuorollaan kädestään tikkiin laitettavat kortit. Hän asettaa ne kuvapuoli alaspäin pöydälle siten, että toiset pelaajat näkevät vain kuinka monta korttia pelaaja laittoi. Laitettavat kortit saavat olla mitä tahansa. Kun kaikki pelaajat ovat laittaneet korttinsa tikkiin, paljastetaan kaikki tikin kortit ja pelaaja, joka laittoi parhaimman yhdistelmän, voittaa tikin itselleen ja asettaa sen omaan erilliseen tikkipakkaansa.

Yhdistelmät

Yhdistelmiä ovat (parhausjärjestyksessä):

7 kortin värisuora
6 kortin värisuora
5 kortin värisuora
4 samaa korttia
4 kortin värisuora
3 kortin värisuora
3 samaa korttia
2 kortin värisuora
pari
yksittäinen kortti

Saman tyypin yhdistelmiä verrataan vertaamalla niiden suurimman arvoista korttia. Korttien keskinäinen suuruusjärjestys taas selvitetään vertaamalla ensin arvoa ja sen ollessa sama verrataan maata. Maiden järjestys on ♤ (suurin), ♡, ♢, ♧ (pienin).

Tikin voittaminen

Pelaajan laittamista korteista katsotaan vain yksi paras mahdollinen yhdistelmä. Esimerkiksi jos pelaaja 1 laittaa tikkiin kortit 3♤ – 3♡ – 4♡ – 4♢ – 5♢, niin näistä muodostuva yhdistelmä on 4♢ – 5♢, sillä 2 kortin värisuora voittaa parin ja 5♢ > 4♡ (koska 5>4).

Tikin pelaamisen jälkeen jaetaan pelaajille pakasta kortteja (taas jakajasta seuraavasta aloittaen) kunnes jokaisella on kädessään 7 korttia tai pakka loppuu. Kortteja jaetaan kullekin yksi kerrallaan (ja pelaajat, joilla on jo 7 korttia hypätään yli), jotta kortit saataisiin jaettua mahdollisimman tasaisesti pakan loputtua. Tikin voittanut pelaaja aloittaa seuraavan tikin.

Kierros

Tikkien pelaamista jatkekaan kunnes kaikki kortit on pelattu. Jos yhdelle pelaajalle jää kortteja käteen, kun kaikkien muiden pelaajien kädet ovat tyhjät, saa tämä pelaaja omat korttinsa omaan tikkipakkaansa.

Kierroksen lopuksi, jokainen pelaaja laskee tikkipakastaan kuinka monta pistettä hän saa. Tikkipakan kortit järjestetään saman arvoisten korttien ryhmiin ja jokainen ryhmä antaa pisteitä seuraavasti:

1 kortti: 1p
2 korttia: 5p
3 korttia: 10p
4 korttia: 20p

Jakaja vaihtuu kierroksittain.

Voittaminen

Kierroksia pelataan joko ennalta sovittu määrä tai siihen asti kunnes jokin pelaaja saavuttaa jonkin ennalta sovitun pistemäärän. Voittaja on se pelaaja, jolla on viimeisen kierroksen jälkeen eniten pisteitä.

♤♡♢♧

Muunnelmia

Pakan kokoa voi vaihdella ottamalla kutakin maata kortit johonkiin arvoon asti.
Perääntymiskierros: Kun pelaajat ovat asettaneet korttinsa tikkiin, niitä ei vielä paljastetakaan, vaan käydään toinen kierros, jolla kukin pelaaja voi halutessaan ottaa laittamiaan kortteja pois. Kuitenkin jokaista pois ottamaansa korttia kohden hänen täytyy paljastaa jokin toinen laittamansa kortti ja tämän paljastetun kortin pitää jäädä pöydälle. (Tämä tarkoittaa, että korkeintaan puolet laitetuista korteista voi vetää takaisin.)

Värisuorien todennäköisyyksistä

Jos tavallisesta 52 kortin korttipakasta nostetaan satunnainen 7 kortin käsi, mikä on todennäköisyys, että käsi sisältää (ainakin) $r$ peräkkäistä saman maan korttia?

Merkitään $A_{i, j} =$ ”käsi sisältää kortit $(i, j), (i+1, j), \dots, (i+r-1, j)$ ”, arvoille $i=1,2,\dots, 13-r+1$ ja $j=$ ♠, ♥, ♣, ♦. Merkitään näiden kaikkien tapahtumien joukkoa $\cal{A}$ :lla. Kysytty todennäköisyys on tällöin

$\begin{aligned} \mathbb{P} \left( \bigcup_{A\in\cal{A}} A \right) \end{aligned} .$

Inkluusio-eksluusion periaatteen nojalla tämä voidaan laskea

$\begin{aligned} \mathbb{P} \left( \bigcup_{A\in\cal{A}} A \right) = \sum_{j=1}^{|\cal{A}|} (-1)^{j+1} \sum_{ \substack{ I\subset \cal{A} \\ |I| = j}} \mathbb{P} \left( \bigcap_{A\in I} A \right) \end{aligned}$

Merkitään tapahtumalle $A \in \cal{A}$ symbolilla $\bar {A}$ niiden korttien joukkoa, jotka siinä vaaditaan kädessä esiintymään. Huomataan, että tämä relaatio on siinä mielessä käänteinen, että kun tapahtumia $A$ leikataan, vastaa tämä joukkojen $\bar{A}$ yhdistettä. (Leikkautapahtuma tapahtuu jos ja vain jos käsi sisältää kaikki vaaditut kortit.)

Todennäköisyys $\begin{aligned} \mathbb{P} \left( \bigcap_{A\in I} A \right) \end{aligned}$ riippuu vain vaadittujen korttien unionin koosta $t = \left( \bigcup_{A\in I} \bar{A} \right)$ sillä siinä vaaditaan leikkauksen korttien esiintyvän kädessä eikä sillä ole väliä mitkä kortit ne ovat. Hypergeometrisen jakauman mukaan tämä todennäköisyys on

$p_t := \begin{aligned} \frac{ {{t} \choose {t}} {{52-t} \choose {7-t}} }{ {{52} \choose {7}} } = \frac{ {{52-t} \choose {7-t}} }{ {{52} \choose {7}} } \end{aligned}$

Täytyy siis selvittää kuinka monta $t$ :n kokoista unionia $\bigcup_{I\subset \cal{A}} \bar{A}$ tasolla $|I|=j$ on. Merkitään tätä $c_{j, t}$ .

Koska $p_t = 0$ , kun $t>7$ , niin tarvitaan vain arvot, joissa $t\leq 7$ . Lisäksi, koska tason $j$ unioni koostuu $j$ joukosta ja ensimmäinen tuo $r$ alkiota ja seuraavat jokainen ainakin yhden lisää (joukot $\bar{A}$ ovat pötköjä, jotka menevät maksimissaan $r-1$ :n verran päällekkäin), niin saadaan myös yläraja $j\leq 7-r+1$ .

Lukujen $c_{j, t}$ laskeminen voidaan tehdä brute-forcena. Tapaus $r=2$ on melko raskahko, sillä siinä täytyy laskea arvoon $j=6$ asti ja ${{4\times 12}\choose{6}} = 12 271 512$ . Tapaus $r=2$ on kuitenkin toisella tapaa yksinkertaisempi ja sen voi ratkaista tutkimalla kuinka monella tapaa neljän 13-ketjun graafista voidaan valita aligraafi, joka on kokoelma ketjuja (nämä aliketjujen pituudet vastaavat sitä tyyppiä millainen yhdiste $A$ ’ista muodostuu). Tässä joukot $A$ vastaavat graafin sivuja ja se että joukko on yhdisteessä mukana vastaa sitä, että sivu on aligraafissa mukana.

Saadaan seuraavat tulokset:

r	P(väh. r pituinen värisuora)	approks
2	686898/1194505	0.575
3	1074209/16723070	0.0642
4	151/30940	0.00488
5	407/1454180	0.000280
6	361/33446140	0.0000108
7	1/4778020	2.093e-7

Javascript-koodi:

function binCoeff(n, k) {
    if (k < 0 || k > n) return 0;
    if (k === 0 || k === n) return 1;
    let ret = 1;
    for (let i=0; i<Math.min(k, n-k); i++){
        ret = ret*(n-i)/(i+1);
    }
    return ret;
}

function* generCombinations(arr, r) {
    const result = [];
    result.length = r;
    function* makeThem(len, start) {
        if(len===0) {
            yield result.slice();
        } else {
            for (var i=start; i<=arr.length-len; i++) {
                result[result.length-len] = arr[i];
                yield* makeThem(len-1, i+1);
            }
        }
    }
    yield* makeThem(r, 0);
}

function linkBruteGeneral(j, k, m, linkLen) {
    let ret = {};
    let runStarts = [];
    for (let i=0; i<k; i++) {
        runStarts = [...runStarts,
...new Array(m-(linkLen-1)).fill(null).map((_,z)=>[z, i])];
    }
    for (let comb of generCombinations(runStarts, j)) {
        let cardSet = new Set();
        for (let card of comb) {
            for (let follow=0; follow<linkLen; follow++) {
                cardSet.add((card[0]+follow)+","+card[1]);
            }
        }
        let key = cardSet.size;
        if (!(key in ret)) ret[key] = 0;
        ret[key] += 1;
    }
    return ret;
}

function calcProb(ds) {
    const calcPart = (j) => {
        let s = 0;
        let d = ds[j];
        for (let k in d) {
            if (k>7) continue;
            s += d[k]*binCoeff(52-k, 7-k);
        }
        return s;
    };
    
    let ret = 0;
    for (let i=1; i<=ds.length; i++) {
        ret += (i%2?1:-1)*calcPart(i);
    }
    return ret;
}

function makeTheFormula(ds) {
    const makePart = (j) => {
        let f = "(";
        let d = ds[j];
        let isFirst = true;
        for (let k in d) {
            if (k>7) continue;
            if (isFirst) {
                isFirst = false;
            } else {
                f += "+";
            }
            f += d[k]+`*binomial(${52-k}, ${7-k})`;
        }
        return f+")";
    };
    
    let ret = "";
    for (let i=1; i<=ds.length; i++) {
        ret += (i===1?'':(i%2?'+':'-')) + makePart(i);
    }
    return ret;
}

let testK = 4;
let testM = 13;
let testR = 3;

let maxNeedJ = 7-testR+1;

let ds = [];
for (let j=0; j<=maxNeedJ; j++) {
    ds.push(linkBruteGeneral(j, testK, testM, testR));
}

console.log(calcProb(ds));
console.log(makeTheFormula(ds));

Koodi toiselle tavalle tapauksessa r=2:

/** list of partitions of n to at most maxPartsN parts that are at most maxSize */
function getPartitions(n, maxPartsN, maxSize) {
    if (n===0) return [[]];
    let canMakeMax = maxPartsN*maxSize;
    if (n>canMakeMax) return [];
    if (n===canMakeMax) return [new Array(maxPartsN).fill(maxSize)];
    let ret = [];
    for (let x=Math.min(n, maxSize); x>=0; x--) {
        let toConcat = getPartitions(n-x, maxPartsN-1, x).map(p=>[x].concat(p));
        ret = ret.concat(toConcat);
    }
    return ret
}

function factorial(n) {
    let ret = 1;
    for (let i=2; i<=n; i++) ret *= i;
    return ret;
}

function binCoeff(n, k) {
    if (k < 0 || k > n) return 0;
    if (k === 0 || k === n) return 1;
    let ret = 1;
    for (let i=0; i<Math.min(k, n-k); i++){
        ret = ret*(n-i)/(i+1);
    }
    return ret;
}

/** In how many ways  can subchains be fitted into chains.
* Chain length is the number of edges in it.
*/
const linkageMemo = {};
function countLinkages(chains, subchains) {
    //debugger;
    let memoKey = chains.join(",")+";"+subchains.join(",");
    if (memoKey in linkageMemo) return linkageMemo[memoKey];
    if (subchains.length===0) return 1;
    let s = 0;
    let currSub = subchains[0];
    let restSubs = subchains.slice(1);
    for (let cI=0; cI<chains.length; cI++) {
        let cLen = chains[cI];
        let maxInd = cLen-currSub;
        for (let ind=0; ind<=maxInd; ind++) {
            let restChains = chains.slice(0, cI).concat(chains.slice(cI+1));
            if (ind>1) restChains.push(ind-1);
            if (ind<maxInd-1) restChains.push(maxInd-ind-1);
            restChains.sort((a,b)=>b-a);
            s += countLinkages(restChains, restSubs);
        }
    }
    linkageMemo[memoKey] = s;
    return s;
}


function permuFactor(arr) {
    let counts = {};
    for (let x of arr) {
        if (!(x in counts)) counts[x] = 0;
        counts[x] += 1;
    }
    let ret = 1;
    for (let val of Object.values(counts)) ret *= factorial(val);
    return ret;
}

function countAllLinkages(j, k, m) {
    let chains = new Array(k).fill(m-1);
    let linksN = k*(m-1);
    let partis = getPartitions(j, linksN, linksN);
    let ret = {};
    for (let parti of partis) {
        let key = parti.reduce((a,b)=>a+b+1,0);
        if (!(key in ret)) ret[key] = 0;
        ret[key] += countLinkages(chains, parti)/permuFactor(parti);
    }
    return ret;
}


/* Given the amounts of linkages calculate the numerator of probability of having a 2-run
* ds = [
    {
      "0": 1
     },
     {
      "2": 48
     },
     {
      "3": 44,
      "4": 1084
     },
     {
      "4": 40,
      "5": 1944,
      "6": 15312
     }, ...
]
*/
function calcProb(ds) {
    const calcPart = (j) => {
        let s = 0;
        let d = ds[j];
        for (let k in d) {
            if (k>7) continue;
            s += d[k]*binCoeff(52-k, 7-k);
        }
        return s;
    };
    
    let ret = 0;
    for (let i=1; i<=6; i++) {
        ret += (i%2?1:-1)*calcPart(i);
    }
    return ret;
}

function makeTheFormula(ds) {
    const makePart = (j) => {
        let f = "(";
        let d = ds[j];
        let isFirst = true;
        for (let k in d) {
            if (k>7) continue;
            if (isFirst) {
                isFirst = false;
            } else {
                f += "+";
            }
            f += d[k]+`*binomial(${52-k}, ${7-k})`;
        }
        return f+")";
    };
    
    let ret = "";
    for (let i=1; i<=6; i++) {
        ret += (i===1?'':(i%2?'+':'-')) + makePart(i);
    }
    return ret;
}


let testK = 4;
let testM = 13;
let ds = [];
for (let j=0; j<=6; j++) {
    ds.push((countAllLinkages(j, testK, testM)));
}

console.log(makeTheFormula(ds));
console.log(calcProb(ds));

$\begin{aligned} \end{aligned}$

Ympyrät tasossa

Kysymys

Olkoon tasossa $n$ toisiaan leikkaamatonta $1$ -säteistä ympyrää. (Ympyrällä tarkoitetaan sen kaarta.) Mikä on todennäköisyys, että kun valitaan näiltä piste satunnaisesti, tästä pisteestä ei näy muita ympyröitä?

Ympyrän 2 pisteestä $A$ näkyy kaikki muut ympyrät. Pisteestä $B$ taas ei näy mikään toinen ympyrä, sillä ne ovat kaikki $B$ :hen piirretyn tangenttisuoran ”väärällä” puolella.

Kokeile:

https://Invisible-Circles–minkkilaukku2.repl.co

Ratkaisu

Vastaus on $\begin{aligned} \frac{1}{n} \end{aligned}$ .

Ja tämä siis aivan riippumatta ympyröiden sijainneista (paitsi eivät saa leikata toisiaan, kuten sovittiin).

Todistuksen runko

Ympyröiden konveksiverho $C$ . Kaariosuudet keltaisella ja janaosuudet ruskealla. Vihreät pisteet ympyröillä ovat niiden välisten tangenttijanojen päätepisteitä, ”kaikkein uloimmaiset” tangenttijanat ovat mukana $C$ :ssä.

Olkoon $C_0$ ympyröiden yhdisteen konveksiverho.
Joukon $C_0$ reuna $C$ on janoista ja ympyränkaarista koostuva derivoituva Jordanin käyrä.
Ympyrän piste $P$ kuuluu $C$ :hen täsmälleen silloin, kun se on sellainen piste, josta ei näy mikään muu ympyrä. (Pois lukien äärellisen monta pistettä, jotka ovat $C$ :n janojen päätepisteitä: janat ovat ympyröiden välisiä tangentteja, joten niiden päätepisteet leikkaavat kahta ympyrää, joten niistä on näköyhteys. Näiden joukko on kuitenkin äärellisenä nollamittainen eikä vaikuta todennäköisyyteen.)
Käyrän $C$ kokonaiskaarevuus on $\begin{aligned} \int_{a}^b \kappa (s) ds = 2\pi \end{aligned}$ , sillä kierrosluku on $1$ .
Toisaalta $\begin{aligned} \int_{a}^b \kappa (s) ds \end{aligned}$ on käyrällä $C$ olevien ympyränkaarien yhteenlaskettu mitta, sillä janaosuudella kaarevuus $\kappa = 0$ ja kaariosuudella $\kappa = \frac{1}{1} = 1$ , sillä jokaisen ympyrän säde on $1$ (ks. kaarevuudesta Wikipediassa).
Siis suotuisan osan mitta on $2\pi$ . Kaikkien ympyröiden mitta on $2\pi n$ , joten väite seuraa.

Huomioita

Yleistyy kolmiulotteiseksi: pallot 3D-avaruudessa. Gauss-Bonnet:n lause.
Jos ympyröiden säteet ovat eri suuruisia, ympyröiden paikat vaikuttavat tulokseen. Tämä johtuu siitä, yo. integraalissa kaarevuus ei ole joka ympyrällä vakio vaan tulos riippuu siitä millaisia ympyröitä ulkokaaressa on mukana minkäkin verran. Ks. esimerkkikuva alla.

Erisäteisille ympyröille voi käydä näin. Selvästi jälkimmäisessä tapauksessa suotuisaa mittaa on vähemmän kuin ensimmäisessä.

Hedetniemen matriisisumma

Kaikkihan tietätävät että graafin solmujen välillä olevien $q$ -kävelyjen lukumäärät saadaan korottamalla graafin vierekkäisyysmatriisi potenssiin $q$ . Mutta entä jos matriisissa käytetään kaarien painotuksia ja matriisitulossa rivin ja sarakkeen pistetulon paikalla alkioiden summien minimiä? Tämä on Hedetniemen matriisisumma.

Määritelmä

Matriisien $A$ (kokoa $m\times n$ ) ja $B$ (kokoa $n\times p$ ) Hedetniemen summa $A \ddagger B$ on $m \times p$ -matriisi $C$ , jonka $(i, j)$ -alkio on

$\begin{aligned} c_{ij} = \min_{ k \in \{1, \dots, n\} } a_{ik}+b_{kj} \end{aligned}$

Huom. Sallimme matriisin alkioksi myös plus äärettömän $\infty$ . Määrittelemme $\infty + x = x + \infty = \infty$ ja $\min(\infty, x) = x$ kaikille luvuille $x$ ja myös tapauksessa $x = \infty$ .

Esimerkki

Hedetniemen summan alkion $(3, 4)$ muodostuminen korostettuna. Matriisi $A$ on alla esiintyvän graafin kaarien painomatriisi.

Hedetniemen summan alkion $(3, 4)$ muodostuminen korostettuna. Matriisi $A$ on alla esiintyvän graafin kaarien painomatriisi.

Mihin tätä summaa sitten käytetään? Sen avulla voidaan selvittää lyhyimmät reitit kaikkien solmuparien välillä graafissa, jonka kaarille on annettu ei-negatiiviset painokertoimet (etäisyydet). Muodostetaan graafille $G=(\{v_1, v_2 \dots, v_n\}, E)$ kaarien painomatriisi $A$ , jossa alkio $a_{ij}$ , $i \neq j$ on $v_i$ :n ja $v_j$ :n välisen kaaren paino tai $\infty$ , jos solmujen välillä ei ole kaarta. Diagonaalialkiot $a_{ii}$ asetetaan nollaksi, sillä solmusta itseensä on nollan askeleen reitti, jonka pituus (=sen käyttämien kaarien painojen summa) on nolla. Oletamme että graafi on yksinkertainen eli sillä ei ole kaaria solmusta itseensä eikä useampia kaaria kahden solmun välillä. Tämä on luonnollinen oletus kun haluamme selvittää lyhyimpiä reittejä, sillä luuppia solmusta itseensä ei kannata reitissä ikinä käyttää ja useammasta kaaresta solmujen välillä kannattaa aina valita se, jolla on pienin paino.

Kaaret ajatellaan suunnaatuiksi, mutta suuntaamattomassa tapauksessa ajatellaan, että kaari on kumpaankin suuntaan olemassa (samalla painolla). Suuntaamattomassa tapauksessa matriisi $A$ on siis symmetrinen.

Suuntaamaton graafi ja sen kaarien painomatriisi $A$ . Ensimmäinen rivi ja sarake ovat indeksejä.

Lasketaan matriisin $A$ iteroituja Hedetniemen summia $A, A^2, A^3, \dots$ . Merkitsemme siis $A^2 = A \ddagger A$ (tämä ei sotkeutune tavalliseen matriisituloon, jota ei tässä postauksessa esiinny). Iteraation $A^{t}$ alkio $a_{ij}^t$ kertoo lyhyimmän $t-1$ :n askeleen reitin pituuden solmusta $v_i$ solmuun $v_j$ . Koska graafi on äärellinen, käy jostakin $t$ :n arvosta $t_1$ lähtien niin, että $A^{t_1} = A^{t_1+1} = A^{t_1+2} = \dots$ eli jono stabiloituu. Ylläolevalle esimerkille

Hedetniemen matriisisumma-iteraatiot edellä olleen graafin kaarien painomatriisille. Jono stabiloituu arvosta $t_1 = 7$ lähtien. Kuten voidaan todeta, eniten askelia vievä lyhyin reitti (solmujen $2$ ja $5$ välillä) on 6 askelta: 2-0-1-3-4-6-5 ja sen pituus on $9 (=2+1+2+1+2+1)$ . Se käykin kaikki graafin solmut läpi, joten tämä on maksimitapaus.

Hedetniemen matriisisumma-iteraatiot edellä olleen graafin kaarien painomatriisille. Jono stabiloituu arvosta $t_1 = 7$ lähtien. Kuten voidaan todeta, eniten askelia vievä lyhyin reitti (solmujen $2$ ja $5$ välillä) on 6 askelta: 2-0-1-3-4-6-5 ja sen pituus on $9 (=2+1+2+1+2+1)$ . Se käykin kaikki graafin solmut läpi, joten tämä on maksimitapaus.

Reitin selvitys

Lyhyimmän reitin pituus on luettavissa matriisin $A^{t_1}$ alkiosta, mutta kuinka saamme tiedon mikä tuo reitti on? Se voidaan selvittää solmu kerrallaan lähtemällä päätepisteestä ja ratkaisemalla mikä sitä täytyy reitillä edeltää. Otetaan esimerkiksi edellä olleen graafin solmut $0$ ja $6$ . Matriisista $A^7$ nähdään, että lyhyimmän reitin pituus on $a_{60}^7 = 6$ . Tutkitaan nyt päätepisteen eli solmun $6$ naapureita ( $k= 4, \text{ ja } 5$ ). Se kummasta kutoseen on tultu, täytyy toteuttaa yhtälö, että lyhyin reitti nollasta siihen on $6 - a_{k6}$ . Koska solmusta $4$ tulee 2:n painoinen kaari ja lyhyin reitti nollasta solmuun $4$ on $A^7$ :n mukaan pituudeltaan 4, niin valitaan solmu $4$ . Jatketaan nyt solmusta $4$ ja etsitään sen edeltäjä. Näin jatketaan kunnes päästään alkupisteeseen ja reitti on selvitetty.

Reitin selvityksen kaksi ensimmäistä askelta. Loput menevät vastaavasti.

Huomioita

Jos matriisin jää äärettömyyksiä jonon stabiloiduttua, tarkoittaa se että graafi on epäyhtenäinen: jostain solmusta ei ole mitään reittiä johonkin toiseen solmuun.
Stabiloituminen vie korkeintaan $|V|-1$ askelta, sillä lyhyin reitti ei vieraile missään solmussa kuin korkeintaan kerran.
Pienempiä (ennen stabiloitumista) iterantteja voi käyttää askelten määrän ollessa rajoitettu, sillä ne tosiaan kertovat sen hetkisen lyhyimmän etäisyyden kun käytetään korkeintaan $t$ askelta. (Jos haluaisi käyttää tasan $t$ askelta sen voisi varmaan toteuttaa asettamalla diagonaalialkiot äärettömiksi, jolloin solmussa ei ole luvallista pysyä. ???)
Algoritmin kehittäjä on Stephen Hedetniemi. Lisätietoa historiasta Seuran artikkelissa. Hedetniemen nimissä on myös graafien tensoritulon väritykseen liittyvä konjektuuri, joka ratkesi aivan tässä viime aikoina kielteisesti eli siihen löytyi vastaesimerkki: Yaroslav Shitov, Counterexamples to Hedetniemi’s conjecture.

Ohjelmakoodit (Python)

INFTY = 2**56 #number larger than any other occuring one

def hedetniemiMatrixSum(a, b):
    m = len(a)
    n = len(b)
    p = len(b[0])
    return [[min(a[i][k] + b[k][j] for k in range(n))
             for j in range(p)]
            for i in range(m)]


def findStableHedetniemiSum(a):
    n = len(a)
    prev = a
    b = a
    counter = 0
    while counter<n:
        b = hedetniemiMatrixSum(b, a)
        if b == prev: break
        prev = b
    return b
    

def findPath(start, end, minDMat, a):
    """
       start: index of the start node
       end: index of the target node
       minDMat: the stabilized matrix
                containing the minimum paths lenghts
       a: the weighted adjacency matrix
    """
    n = len(a)
    path = [end]
    dist = minDMat[start][end]
    if dist>=INFTY: return None #no path exists
    curr = end
    def findPrev():
        for i in range(n):
            if i==curr: continue
            if dist-a[i][curr] == minDMat[start][i]: return i
    counter = 0
    while curr != start and counter<n:
        prev = findPrev()
        dist -= a[prev][curr]
        curr = prev
        path.append(curr)
    return path[::-1]

#the example matrix
a = [
    [0,1,2,INFTY,INFTY,8,INFTY],
    [1,0,4,2,INFTY,INFTY,INFTY],
    [2,4,0,INFTY,7,INFTY,INFTY],
    [INFTY,2,INFTY,0,1,INFTY,INFTY],
    [INFTY,INFTY,7,1,0,INFTY,2],
    [8,INFTY,INFTY,INFTY,INFTY,0,1],
    [INFTY,INFTY,INFTY,INFTY,2,1,0]
]
b = findStableHedetniemiSum(a)
print b
print findPath(0, 6, b, a)

Rauhalliset ratsut

Kysymys:

Kuinka monella tavalla voidaan $n\times n$ -laudalle asettaa 4 ratsua, siten että mikään ei uhkaa toista? Kaikki ratsut ovat identtisiä ja vihollisia keskenään.

Ratkaisu:

Merkitään $V = [1..n]^2$ eli kaikkien laudan ruutujen joukko. Kaikki mahdolliset neljän ratsun asettelut ovat nyt joukko

$\begin{aligned} S=\{(v_1, v_2, v_3, v_4) \in V^4 \text{ } | \text{ } v_i \neq v_j \text{, kun } i \neq j \} \end{aligned}.$

Määritellään kaarijoukko $E$ kuvastamaan sitä mihin ruutuun kustakin ruudusta ratsu voi liikkua, eli mitä kaikkia ruutuja se uhkaa. (Huom. ratsuissa on se mukava juttu, että ne eivät välitä laudan muista nappuloista vaan voivat hypätä näiden yli.) Näin saadaan $n\times n$ –ratsun graaf i.

Ratsun liikkumismahdollisuudet ovat 1 ruutu vaakasuunnassa ja 2 ruutua pystysuunnassa, tai kääntäen.

Tehdään tässä välissä sellainen huomio, että ratsun graafilla ei ole kolmioita: mitkään kolme eri ratsua (kun ovat laudalla eri ruuduissa) eivät voi uhata kaikki toisiaan. Tämä johtuu siitä, että ratsu vaihtaa aina liikkuessaan väriä: se liikkuu yhteensä kolme askelta mustalta valkealle / valkealta mustalle. Kolmesta ratsusta vähintään kaksi on samalla värillä, joten ne eivät voi uhata toisiaan. Ratsun graafi on juuri tämän värin vaihtamisen takia kaksijakoinen (valkeat ja mustat ruudut).

Määritellään joukot $\begin{aligned} A_{ij} = \{ (v_1, v_2, v_3, v_4) \in S \text{ } | \text{ } v_i \text{ ja } v_j \text{ uhkaavat toisiaan} \} \end{aligned}$ . Tarvitsemme joukkoja $A_{12}, A_{13}, A_{14}, A_{23}, A_{24}$ ja $A_{34}$ , sillä kysytty lukumäärä on joukon $S \setminus \cup_{ij\in I} A_{ij}$ koko. Indeksijoukko $I := \{ 12, 13, 14, 23, 24, 34\}$ (huom. merkinnät 12,… eivät aiheuta sekaannusta, sillä luvut pysyvät alle kymmenen). Voimme laskea inkluusio-eksluusiolla:

$\begin{aligned} \left |S\setminus \bigcup_{ij\in I} A_{ij} \right | = \sum_{J\subset I} (-1)^{|J|} \left|\bigcap_{ij \in J} A_{ij} \right| \end{aligned},$

missä leikkaus tyhjän joukon yli tarkoittaa koko joukkoa $S$ . Tehtävän ratkaisemiseksi meidän on siis laskettava kaikkien erilaisten leikkausten $\cap_{J} A_{ij}$ koot. Monet näistä ovat symmetrian nojalla samoja ja osa graafin kolmio-vapauden takia mahdottomia. Ne jakautuvat seuraaviin luokkiin:

Erilaiset leikkaustyypit. Solmut ovat indeksejä $i$ ja $j$ , kaari näiden välillä tarkoittaa että $A_{ij}$ on leikkauksessa mukana. Viereen merkitty kuinka monta kutakin leikkaustyyppiä on (symmetria, kuvassa on aina vain esimerkki numerointi solmuille). Taso, eli kuinka monta joukkoa leikkauksessa on, merkitty alle. Huomaa että tason $t$ kaikkinainen lukumäärä on ${{6}\choose{t}}$ : leikkaukseen valitaan $t$ joukkoa kaikista kuudesta. Kolmion sisältävät ovat mahdottomia eli niitä vastaavat leikkaukset ovat tyhjiä.

Merkitään

$\begin{aligned} a_1 =& |A_{12}| = |A_{13}| = \dots = |A_{34}| \\ a_{21} =& |A_{12} \cap A_{13}| = |A_{13} \cap A_{14}| = \dots = |A_{14} \cap A_{24}| \\ a_{22} =& |A_{12} \cap A_{34}| = |A_{13} \cap A_{24}| = |A_{14} \cap A_{23}| \\ a_{31} =& |A_{12} \cap A_{13} \cap A_{14} | = \dots = |A_{14} \cap A_{24} \cap A_{34} | \\ a_{32} =& |A_{12} \cap A_{23} \cap A_{34} | = \dots \\ a_{4} =& |A_{12} \cap A_{23} \cap A_{34} \cap A_{14} | = \dots \end{aligned}$

Siis $a_1 =$ kaaret (ja kaksi muuta saa olla mitä vain muita solmuja), $a_{21} =$ 2-ketjut (ja viimeinen saa olla mikä vain muu solmu), $a_{22} =$ erilliset kaaret, $a_{31} =$ kaikki yhden naapureita, $a_{32} =$ 4-ketjut ja $a_{4} =$ 4-syklit.

Tällöin kysytty lukumäärä on

$\begin{aligned} \frac{1}{24}(n^2(n^2-1)(n^2-2)(n^2-3) - 4a_1 + 12a_{21} + 3a_{22} - 4a_{31} - 12a_{32} + 3a_{4}) \end{aligned}$

Tässä on sijoitettu $|S| = n^2(n^2-1)(n^2-2)(n^2-3)$ ja jakaja $24=4!$ tulee siitä, että ratsujen järjestyksellä ei ole kysymyksessä väliä, mutta me laskimme järjestettyjä nelikoita.

Tällaisten konfiguraatioiden laskemista graafilla käsittelimme viime kertojen postauksissa: Erillisten kaariparien laskeminen ja Graafin naapuruus-polynomeja. Meillä oli apuna graafin naapuruus-polynomit. Koitetaan siis selvittää ne ratsun $n\times n$ -graafille. Laskeminen eri arvoille paljastaa melko nopeasti säännönmukaisuuden, jonka voi sitten kuvaa katsomalla perustella. Polynomi $p_1$ on helppo: nurkilla on jokaisella 2 naapuria, näiden viereisillä ( $8$ :lla) reunaruuduilla 3, muilla ( $4(n-4)$ ):lla reunaruuduilla 4. Toisella rinkulalla käy näin: nurkat: 4, muut reunat ( $4(n-4)$ ): 6. Sitä sisemmillä on kaikilla täydet 8 naapuria. Saamme siis, kun $n\geq 5$

$\begin{aligned} p_1(x) = 4x^2 + 8x^3 + 4(n-3)x^4 + 4(n-4)x^6 + (n-4)^2x^8 \end{aligned}$

Pienemmille $n$ :n arvoille tämä ei toimi, mutta niille koko ongelma voidaan laskea brute-forcena.

Sitten polynomi $p_2$ . Tämä vaatii hieman enemmän pähkäilyä, mutta tapaus $8 \times 8$ oli meillä jo edellisessä postauksessa esimerkkinä. Itse asiassa tuo tapaus on juuri viimeinen, jossa yleinen kaava ei tule vielä käytäntöön. Arvoille $n\geq 9$ pätee

$p_2(y_2, y_3, y_4, y_6, y_8) =\\ 4y_6^2 \text{ } + \text{ } 8y_4y_6y_8 \text{ } + \text{ } 8y_3y_6^2y_8 \text{ } + \text{ } 8y_4y_6y_8^2 \text{ } + \text{ } 4(n-8)y_6^2y_8^2 \text{ } + \text{ } 4y_4^2y_8^2 \text{ } + \text{ } 8y_2y_4^2y_6y_8^2 \text{ } + \text{ } 8y_3y_4y_6y_8^3 \text{ } + \text{ } 4(n-8)y_4^2y_8^4 \text{ } + \text{ } 4y_3^2y_4^2y_6^2y_8^2 \text{ } + \text{ } 8y_4^3y_6^2y_8^3 \text{ } + \text{ } 4(n-8)y_4^2y_6^2y_8^4 \text{ } + \text{ } 4y_6^4y_8^4 \text{ } + \text{ } 4(n-8)y_6^2y_8^6 \text{ } + \text{ } (n-8)^2y_8^8$

Lisäksi tarvitsimme vielä polynomin $p_E$ . Se saadaan, mikäli $n \geq 7$ , kaavalla

$\begin{aligned} p_E(x) = 8 x^6 + 16 x^7 + 8 x^8 + 8(n-5)x^9 + 8x^{10} + 8(n-3)x^{11} + (16(n-6)+8)x^{13} + 4(n-5)(n-6)x^{15} \end{aligned}$

Ainoa tapaus, jota emme $a$ ’itten laskemisesta vielä käsitelleet aimmissa postauksissa on 4-syklit eli $a_4$ . Mutta näiden lukumäärälle löytyy kaava mathworldista: Jos $n\geq 4$ , niin $a_4 = 16(n^2-18n+26)$ , muuten $0$ . (Meidän täytyy kertoa mathworldin kaava $8$ :lla, sillä tutkimme järjestettyjä nelikoita.)

Huomataan, että, kun $n \geq 9$ , laskenta-algoritmit tuottavat $n$ :stä riippuvan, astetta $8$ olevan polynomin, joten sen kertoimet voidaan selvittää laskemalla interpolaatio-polynomi tarpeeksi monelle pisteelle. Saadaan

$\begin{aligned} \frac{1}{24}(n^8 - 54n^6 + 144n^5 + 1019n^4 - 5232n^3 - 2022n^2+51120n - 77184) \end{aligned}$

Huomataan, että tämä kaava toimii itse asiassa, kun $n \geq 6$ . Pienemmät arvot $1 \leq n \leq 5$ eivät noudata tätä kaavaa, mutta niille voidaan keksiä kaava

$\begin{aligned} \frac{1}{6} (723 n^4 - 6869 n^3 + 23187 n^2 - 32317 n + 15276) \end{aligned}.$

ja näin on ratkaisu saatu kahdessa palassa määrättyä.

Huomoita

Yleinen ongelma, josta tämä on esimerkki on graafin riippumattomien joukkojen numerointi.
Tämä kyseinen jono löytyy OEIS:sta. Jonon $n$ :s termi on ratsun $n\times n$ -graafin riippumattomuus polynomin neljännen asteen kerroin.

Tehtäviä

Ratkaise vastaava tehtävä, kun laudalle asetetaan 2 valkeaa ja 2 mustaa ratsua. Nyt sallittuja tilanteita ovat ne, joissa eriväriset eivät uhkaa toisiaan. (Vinkki: valitse tietyt joukot $A_{ij}$ .)
Yleistyksiä: $m\times n$ -laudalle, $k$ :lle ratsulle, $(k_1, k_2,\dots)$ eri väriselle ratsulle. Myös eri nappuloille (huom. rajoituksen että nappi ei voi mennä toisen yli voi unohtaa. Uhkaamattomassa tilanteessa sillä ei ole väliä, koska muiden nappuloiden liikkeet ovat lineaariset ja ne uhkaavat jo edessä olevaa nappulaa, jos joutuisivat kulkemaan sen läpi uhatakseen toista).
Perustele 4-syklien kaava.

Graafin naapuruus-polynomeja

Olkoon $G=(V, E)$ yksinkertainen, suuntaamaton, äärellinen graafi.

Määritellään $G$ :n ensimmäinen naapuruus-polynomi

$\begin{aligned} p_1(x) = \sum_{v\in V} x^{\deg(v)} \end{aligned}.$

Termin $x^k$ kerroin kertoo kuinka monta $k$ -asteista solmua graafissa on eli kuinka monella on (tasan) $k$ naapuria. Esimerkki:

Polynomista $p_1(x) = \sum_{k=0}^{m} a_k x^k$ voidaan laskea graafin kaarien määrä laskemalla $\frac{1}{2} p_1 '(1)$

$\frac{1}{2} \begin{aligned} \sum_{k=1}^m k a_k\end{aligned}$

Tämähän on tuttu kaava, että solmujen asteiden summa on kaksi kertaa kaarien määrä. Polynomi kuitenkin ryhmittelee solmut asteen mukaan, joten se on kätevä laskuissa. Esimerkin graafissa lasku on $(4 + 3\times 3 + 2 \times 3 + 1)/2 = 10.$

Mielenkiintoisempi ja enemmän graafista tietoa antava polynomi on toinen naapuruus-polynomi $p_2(y_1, y_2, \dots)$ . Muuttujia $y_j$ on mielivaltaisen monta, mutta kuitenkin tietyssä polynomissa aina vain äärellisen monta. Se määritellään seuraavasti.

Tutkitaan jokaiselle solmulle $v$ sen naapureita $w_1, w_2, \dots , w_t$ ja muodostetaan termi $\begin{aligned} \prod_{j=1}^{t} y_{\deg(w_j)} \end{aligned}$ . Nämä summataan yhteen. Esimerkki:

Keltaisella korostetut solmut tuottavat saman termin. Niillä sattuu tässä esimerkissä olemaan täysin samat naapurit, mutta samanlaiset termit voi syntyä muutenkin, riittää että naapuruston ”tyyppi” eli asteiden suurusjärjestykseen järjestetty vektori on sama.

Polynomin $p_2$ avulla voidaan laskea esimerkiksi kolmio-vapaan (ei sisällä 3-sykliä) graafin 4-ketjujen lukumäärä seuraavasti: Olkoon 4-ketju $(x_1, x_2, x_3, x_4)$ . Kiinnitetään $x_2$ . Nyt $x_1$ ja $x_3$ ovat jotkin sen naapurit. Annetaan siis niiden juosta kaikkien naapuri-kaksikkojen $(a_1, a_2)$ , $a_1 \neq a_2$ läpi. Lopuksi $x_4$ täytyy olla jokin $x_3$ :n naapuri. Tässä graafin kolmio-vapaus tulee tarpeeseen: meidän täytyy tietää vain se kuinka monta naapuria $x_3$ :lla on $x_1$ :n lisäksi. Solmu $x_1$ ei voi olla $x_3$ :n naapuri sillä muuten muodostuisi kolmio. Seuraava JavaScript funktio suorittaa tämän laskun, kun sille antaa polynomin $p_2$ objektina, johon termin $\prod_{j=1}^t y_{i_j}$ kerroin on koodattu avaimen ” $i_1, i_2, \dots , i_t$ ” arvoksi (huom. jokainen $i_j$ on siis avaimessa niin monta kertaa kuin se termissä esiintyy eli ”potenssit kirjoitetaan tuloina”).

/** @param p: The second neighbor polynomial of the graph */
function count4PathsInTriangleFreeGraph(p) {
    let s = 0;
    for (let key in p) {
        let a = key.split(",").map(x=>+x);
        for (let k1=0; k1<a.length; k1++) {
            for (let k2=0; k2<a.length; k2++) {
                if (k2===k1) continue;
                //x4 can be any nbr of x3 except x2 (hence -1)
                //x1 can't be a neighbor of x3, since no triangles
                s += p[key]*(a[k2]-1);
            }
        }
    }
    return s;
}

Edellisen esimerkin graafi on kolmio-vapaa, joten funktiota voi käyttää. Parametriksi annettava objekti on:

{"4":1, "2,3,4":2, "3,3":1, "2,3,3":1, "2,3":1, "2,4":1, "1,2,3,3":1}

Koodi antaa tulokseksi 60. Näin pienessä esimerkissä tämän funktion hyödyllisyys ei ehkä tule ilmi; voisimmehan käydä kaikki solmu-nelikot läpi ja tarkastaa kuinka moni niistä on 4-ketju. Sen hyödyt nähdään suuremmille graafeille, joille polynomi $p_2$ on laskettavissa helposti ja sen termien lukumäärä säilyy pienenä (eli niissä on jokin sellainen säännönmukaisuus joka helpottaa laskemista). Esimerkki:

Ratsun graafi 8×8-laudalla. Säännönmukaisuuksia merkitty väreillä. Tässä esimerkissä sitä ei vielä itse asiassa näe, mutta kun laudan koko kasvaa yli 8, keskelle syntyy neliö, jonka kaikki solmut ovat $p_2$ :n mielessä samanlaisia: niillä on 8 naapuria, joilla jokaisella on 8 naapuria. Suurilla n termi $y_8^8$ tulee siis hallitsevaksi: sen kerroin on $(n-8)^2$ .

Ratsun graafi 8×8-laudalla. Säännönmukaisuuksia merkitty väreillä. Tässä esimerkissä sitä ei vielä itse asiassa näe, mutta kun laudan koko kasvaa yli 8, keskelle syntyy neliö, jonka kaikki solmut ovat $p_2$ :n mielessä samanlaisia: niillä on 8 naapuria, joilla jokaisella on 8 naapuria. Suurilla n termi $y_8^8$ tulee siis hallitsevaksi: sen kerroin on $(n-8)^2$ .

Huomioita

Jos polynomissa $p_2$ asettaa $y_j = x$ kaikilla $j$ , niin saadaan polynomi $p_1$ . Tämä johtuu siitä, että $p_2$ jaottelee solmut tarkemmin niiden naapureiden asteiden mukaan, kun $p_1$ vain solmun oman asteen mukaan. Jokainen solmu $v$ tuo $p_2$ :een astetta $\deg(v)$ oleven $y$ -termin, joten asetettassa $y_j = x, \forall j$ , tämä redusoituu $x^{\deg(v)}$ :ksi, kuten $p_1$ :ssä.
Kun edellä puhuttiin 4-ketjuista, tarkoitettiin vain solmu-nelikkoja, joiden välillä on kaaret ensimmäisestä toiseen, toisesta kolmanteen ja kolmannesta neljänteen. Muista kaarista ei välitetä (esim. vaikka neljännestä olisi takaisin ensimmäiseen). Ei siis puhuta indusoiduista ketjuista.
Kolmio-vapaus on oleellinen vaatimus 4-ketjulaskelmassa. Esimerkiksi 3-solmuiselle täydelle graafille $K_3$ , joka on itse kolmio, saadaan $p_2(y) = 3y_2^2$ , joka antaisi tulokseksi 4. Mutta tietenkään siellä ei voi olla yhtään 4-ketjua, kun solmuja on vain 3.
Funktiota count4PathsInTriangleFreeGraph voi yksinkertaistaa jättämällä k1:n iteraation pois ja vain kertomalla sisimmässä silmukassa lisättävän lukumäärän (a.length-1):llä.

Tehtäviä

Laske graafista sellaisten solmu-kolmikkojen $(v_1, v_2, v_3)$ lukumäärä, joille $v_1$ ja $v_2$ ovat rinnakkaiset (eli niitä yhdistää kaari) sekä $v_1$ ja $v_3$ ovat rinnakkaiset.
Entäpä vastaavasti nelikot, jossa kaikki $v_j, j>1$ ovat rinnakkaisia $v_1$ :lle?