Kruunaneliöt

Pöydällä on $n\times n$ -neliöön aseteltuna $n^2$ kolikkoa. Jokainen kolikko on joko kruuna (merk. 1) tai klaava (merk. 0). Kuviosta löytyvä alineliö on kruunaneliö, jos sen kaikki kolikot ovat kruunoja.

Esimerkki, jossa n=5 ja suurin löytyvä kruunaneliön sivu on 2.

Kuviosta etsitään suurin mahdollinen kruunaneliö. Kysymys kuuluu: kuinka monta kolikoiden konfiguraatiota on, joissa suurin löytyvä kruunaneliö on sivultaan $k$ ? Merkitään tätä lukumäärää $h(n, k)$ .

Ratkaisu

Tutkitaan kahta laskutapaa: Inkluusio-ekskluusio ja Markovin ketju. Näistä ensimmäinen toimii kun $k$ on suuri ja jälkimmäinen, kun $k$ on pieni (2 tai 3). Kumpikaan ei toki kovin suurille $n$ toimi. Suurin tapaus, jonka saamme näillä keinoin kokonaan ratkaistua on $n=8$ .

Inkluusio-ekskluusio

Lasketaan $n\times n$ -kolikkoneliöiden lukumäärä, joista löytyy (ainakin) $k\times k$ -kruunaneliö. Merkitään tätä lukumäärää $f(n, k)$ . (Kysytty $h(n, k)$ saadaan sitten $h(n, k) = f(n, k)-f(n, k+1)$ .) Tätä varten tehdään määritelmä (jossa indeksointi aloitetaan nollasta)

$A_{ij} =$ niiden neliöiden joukko, joissa on k-sivuinen kruunaneliö lähtien indeksistä (i, j), $i, j = 0, 1, \dots , n-k$

Esimerkki joukosta $A_{ij}$ . Tässä n=6 ja k=3.

Esimerkki joukosta $A_{ij}$ . Tässä n=6 ja k=3.

Nythän $f(n, k) = | \cup_{i,j} A_{ij}|$ ja inkluusio-ekskluusio kaavan mukaan saadaan

$f(n, k) = | \bigcup_{i,j} A_{ij}| = \sum_{\emptyset \neq J \subset \{A_{ij}\} } (-1)^{|J|+1} |\bigcap_{A_{ij} \in J} A_{ij}|$

Leikkauksen $\bigcap_{A_{ij} \in J} A_{ij}$ koko saadaan laskettua selvittämällä vastaavan kolikkojen yhdisteen koko $U_J = |\bigcup_{A_{ij} \in J} S_{ij}|$ , missä $S_{ij}$ on kyseisen alineliön (sen, jonka vaaditaan olevan kruunaneliö) kolikot. Kaikkien tämän yhdisteen kolikkojen on siis oltava kruunoja, kun taas loput $n^2 - U_J$ saavat olla mitä vaan, joten

$|\bigcap_{A_{ij} \in J} A_{ij}| = 2^{n^2-U_J}$

Joukkojen $A_{ij}$ lukumäärän $(n-k+1)^2$ kasvaessa läpikäytävien joukkojen $J$ lukumäärä $2^{(n-k+1)^2} - 1$ kasvaa hyvin nopeasti. Eri kokoisia yhdisteitä $U_J$ on kuitenkin maksimissaan $n^2$ kappaletta. Jos saman yhdistekoon tuottavien $J$ -joukkojen lukumäärän laskulle olisi tehokas keino, paranisi tämä algoritmi huomattavasti. Kun yhdisteessä on $r$ joukkoa, niin suurille r yhdisteen koko näyttäisi olevan suurinpiirtein normaalijakautunut (paitsi loppupäässä, jossa koko on rajoitettu $n^2$ :lla; kaikkien ( $r = (n-k+1)^2$ ) yhdisteen kokohan on tietysti $n^2$ ). Tätä tutkintalinjaa ei kuitenkaan jatkettu pitemmälle.

Markovin ketju

Ajatellaan että kolikkoneliö muodostetaan rivi kerrallaan. Pidetään jokaiselle sarakkeelle kirjaa, kuinka pitkä putki kruunoja siinä on tullut. Riittää rajoittaa putken pituudeksi $k-1$ eli sen yli ei mennä vaikka tulisikin kruuna. Tiloina on siis kaikki n-vektorit $(r_j)$ , missä $r_j \in \{ 0,1,\dots, k-1 \}$ ( $k^n$ kappaletta) ja siirtymät näiden välillä tehdään mahdollisien rivien ( $2^n$ kappaletta) avulla. Lisäksi on yksi absorboiva tila (kutsutaan lopputilaksi), johon siirrytään, jos k-sivuinen kruunaneliö on muodustunut. Kruunaneliön muodustuminen pystytään päättelemään sarakkeiden kruunaputkista: kun uusi rivi lisätään, kasvatetaan putkia ja nyt annetaan putken kasvaa aina $k$ :hon asti. Kruunaneliö syntyy, jos tästä putkivektorista löytyy $k$ -putki, jossa jokainen arvo on $k$ . Jos kruunaneliö syntyi, siirrytään lopputilaan. Jos taas ei, niin rajoitetaan putket taas korkeintaan $k-1$ :een ja siirrytään syntyneeseen tilaan.

Tämähän ei oikeastaan ole Markovin ketju, sillä siirtymämatriisiin ei laiteta todennäköisyyksiä, vaan tämän siirtymän tuottavan rivien lukumäärä. Tämän takia esim. lopputilan itsesiirtymäänkin laitetaan arvo $2^n$ . Lähtötila on nollavektori ja koko kolikkoneliö saadaan lisäämällä $n$ riviä, joten lukumäärä $f(n, k)$ saadaan siirtymämatriisin $n$ :nnen potenssin paikasta, joka vastaa tiloja (alkutila, lopputila).

Otetaan esimerkiksi $n=3, k=2$ . Tällöin tilat ovat (merkitään lopputilaa (-1, -1, -1))

[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (-1, -1, -1)]

Siirtymämatriisi ja sen kolmas potenssi ovat

”Siirtymä”-matriisi, joka laskee 3×3 kolikkoneliöiden, joista löytyy 2×2 kruunaneliö, lukumäärän

Koodit

Seuraavassa yllä kuvaillut algoritmit toteutettuna SageMath-koodina. Funktio f(n, k) valitsee sopivamman algoritmin riippuen parametreistä n ja k.

import itertools

def fMarkov(n, k):
    
    def hasRun(s):
        run = 0
        for x in s:
            if x==k:
                run += 1
                if run==k: return True
            else:
                run = 0
        return False
    
    rows = list(itertools.product(*[[0,1]]*n))
    states = list(itertools.product(*[range(k) for _ in range(n)]))
    startState = (0,)*n
    endState = (-1,)*n
    states.append(endState)
    stateToMatInd = {s: i for i,s in enumerate(states)}
    startI = stateToMatInd[startState]
    endI = stateToMatInd[endState]
    mat = matrix(ZZ, len(states), sparse=False)
    for i1, s1 in enumerate(states[:-1]):
        for r in rows:
            s2 = tuple( min(k, s1[j]+1) if r[j]==1 else 0  for j in range(n))
            if hasRun(s2):
                mat.add_to_entry(i1, endI, 1)
            else:
                s2 = tuple(min(k-1, x) for x in s2)
                mat.add_to_entry(i1, stateToMatInd[s2], 1)
    mat.add_to_entry(endI, endI, len(rows))
    return (mat**n)[startI][endI]

def fIE(n, k):
    squares = [(i,j) for i in range(n-k+1) for j in range(n-k+1)]
    squareSets = {(i,j): set((i+i1, j+j2) for i1 in range(k)
                             for j2 in range(k)) for i,j in squares}
    sizeForUSize = {u: 2**(n**2-u) for u in range(n**2+1) } 
    tot = 0
    for r in range(1, len(squares)+1):
        for J in itertools.combinations(squares, r):
            U = set().union(*[squareSets[t] for t in J])
            tot += (-1)**(r+1) * sizeForUSize[len(U)]
    return tot

def f(n, k):
    if k>n: return 0
    if k==n: return 1
    if k==0: return 2**(n**2)
    if k==1: return 2**(n**2)-1
    if k==2 and n<14 : return fMarkov(n, k)
    if k==3 and n<9: return fMarkov(n, k)
    return fIE(n, k)
    

import time
startTime = time.time()
n = 6
fVals = [f(n, k) for k in range(n+1)]
#print (fVals)
print ([fVals[k]-(fVals[k+1] if k<n else 0) for k in range(n+1)])
print ("Time: ", time.time()-startTime)

Tulokset

n	k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7	k=8
3	1	416	94	1
4	1	42175	22913	446	1
5	1	15701272	17364903	486337	1918	1
6	1	21418970800	45575022927	1716842688	8632385	7934	1
7	1	107224417436159	434119929848225	21481265058911	124196411584	144634177	32254	1
8	1	1968910887183791358	15477075016864949170	994438116039714639	6311672705366016	8378550282432	2365317953	130046	1

Lukumäärät h(n, k)

Arvo $f(n, 2)$ (eli nxn-matriisien lukumäärä, joista löytyy (ainakin) 2×2 kruunaneliö) on OEIS-jono A255938. Funktio fMarkov() kykenee laskemaan vielä termin

f(13, 2) = 747083368584493829509302940089141575261663191900672

Tehtäviä

Tutkitaan nyt $3 \times n$ kolikkosuorakaidetta. Olkoon lisäksi jokainen kolikko painotettu, niin että kruunan todennäköisyys on $p$ .
a) Olkoon $p = \frac{1}{2}$ . Mikä on ensimmäinen $n$ , jolle todennäköisyys, että suorakaiteesta löytyy $3 \times 3$ kruunaneliö, on yli 0.5?
b) Mille arvolle $p$ todennäköisyys $3 \times 3$ kruunaneliön löytymiselle $3 \times 5$ suorakaiteesta on 0.25?
c) Oletetaan, että saat aluksi valita suorakaiteen pituuden $n$ . Mutta tämän myötä (kaikkien kolikoiden kruuna-tn) $p$ muuttuu kaavan $p = \max(0, \frac{2}{3} - \frac{n}{1000})$ mukaan. Miten $n$ kannattaa valita, jotta $3 \times 3$ kruunaneliön löytymisen todennäköisyys maksimoituu?
Inkluusio-ekskluusio koodissa yhdiste lasketaan jokaiselle $J$ -joukolle uudestaan. Tätä voisi parannella: generoidaan $J$ -joukot itse ja pidetään aina siihen mennessä syntynyt yhdiste muistissa. Ks. myös OEIS-linkin kaavaa (eikö se tosin ole hyvin epätehokas, koska siinä on vielä tulo J-joukon potenssijoukon yli??)