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 nratsun graafi.

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

Tehtäviä

  1. 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}.)
  2. 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).
  3. Perustele 4-syklien kaava.

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out /  Muuta )

Google photo

Olet kommentoimassa Google -tilin nimissä. Log Out /  Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out /  Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out /  Muuta )

Muodostetaan yhteyttä palveluun %s