Viikkotehtävä: determinanttipeli (viikko 42/2018)

kombinatoriikka
peli
determinantti

#1

Viikkotehtävä

Vastausaikaa su 21.10.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Kaksi pelaajaa pelaa peliä 3\times3-ruudukossa. Ensimmäinen pelaaja kirjoittaa johonkin ruutuun ykkösen, toinen johonkin vapaaseen ruutuun nollan, ja näin vuorotellaan kunnes ruudukko on täynnä. Lopuksi lasketaan ruudukon determinantti:

\det \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{array} \right) = \begin{array}{l} a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32}\\ \:\:-a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} - a_{13}a_{22}a_{31}.\\ \end{array}

Ensimmäinen pelaaja voittaa, jos determinantti ei ole nolla. Toinen pelaaja voittaa, jos determinantti on nolla. Kumpi pelaaja voittaa, jos kumpikin pelaa mahdollisimman hyvin?


#2

#3

#4

Tämä vaikuttikin yllättävän vaikealta tehtävältä, tai ehkä viime viikolla oli muita kiireitä, koska yhtään oikeaa vastausta ei tullut. En spoilaa ratkaisua vielä, mutta annan muutaman vihjeen:

  • determinantti on nolla, jos jokin rivi tai sarake sisältää pelkkiä nollia (silloin kaikki termit ovat nollia)
  • determinantti on nolla, jos yksi rivi tai sarake on toisen monikerta, tällaisessa nolla-yksi-matriisissa siis silloin kun kaksi riviä tai saraketta ovat samat (silloin vastintermit kumoavat toisensa pareittain)
  • (vaikeammin kaavasta luettavissa on, että determinantti on nolla myös jos kaikki kolme pistettä ovat samalla suoralla, mutta se taitaa tässä nolla-yksi-tapauksessa redusoitua aiempiin tapauksiin)

Tämä ei liity tehtävään, mutta determinantin vertailulla nollaan saadaan näppärä muotoilu suoran yhtälölle kahden pisteen kautta: laitetaan kahdelle riville kahden pisteen koordinaatit ja kolmannelle tuntemattomat koordinaatit, jolloin determinantti on nolla jos pisteet ovat samalla suoralla tai tuntematon piste on sama kuin jompikumpi kahdesta muusta. Jos pisteet ovat tasossa, z-koordinaateiksi pitää laittaa esim. 1, koska nollia täynnä oleva sarake tuottaa aina determinantin arvoksi nollan. –Lineaarikuvausten näkökulmasta determinantin selittää hyvin seuraava video:


#5

Olkoon A ensimmäisenä pelaava pelaaja ja B toisena. Osoitetaan, että B voittaa aina konstruoimalla hänelle voittostrategia. Ilman yleisyyden menettämistä voidaan olettaa, että A valitsee ensimmäisellä siirrollaan luvun a_{22}, koska determinantin kaava on symmetrinen ruutujen suhteen. Osoitetaan, että B voittaa valitsemalla ruudun a_{11}.

Ilman yleisyyden menettämistä voidaan olettaa, että A valitsee toisella vuorollaan jonkin ruuduista a_{21}, a_{31}, a_{32} tai a_{33}. B voi nyt valita ruudun a_{13}, mikä pakottaa A:n valitsemaan ruudun a_{12}. Tarvittaessa peilaamalla matriisin sen toisen pystyrivin suhteen voidaan olettaa, että A:n ensimmäinen siirto olikin jokin ruuduista a_{21}, a_{31} ja a_{32}. Pelatkoon B nyt sille pystyrivin 3 ruuduista, joka ei ole samalla vaakarivillä A:n toisella siirrolla valitseman ruudun kanssa. Tämä pakottaa A:n valitsemaan oikean pystyrivin viimeisen jäljellä olevan ruudun. B voittaa nyt valitsemalla vasemmalta pystyriviltä sen ruudun, joka on samalla vaakarivillä B:n viimeisimmän valitun ruudun kanssa, koska tämä saa aikaan identtiset pystyrivit 1 ja 3, tarvittaessa A:n seuraavan siirron jälkeen.

Huomautus: kirjoitin ensiksi ratkaisun, joka käsitteli 4 eri tapausta. Sain tämän puristettua kahteen tapaukseen, jonka edelleen tiivistin yllä olevaan muotoon. Ratkaisu ei ole helppolukuisin mahdollinen, mutta jollain mittapuulla elegantti.


#6

Oikealta näyttää. Piirtelin kaavioita asiasta varmistuakseni. Alkusiirtojen jälkeen tilanne on siis

\begin{array}{|c|c|c|} \hline 0 & & \\ \hline &1& \\ \hline & & \phantom{0}\\ \hline \end{array}

ja voidaan olettaa, että seuraava ykkönen menee johonkin seuraavassa kysymysmerkillä merkityistä ruuduista, jolloin nollan voi pelata seuraavasti:

\begin{array}{|c|c|c|} \hline 0 & & 0\\ \hline ?&1& \\ \hline ?& ?& \\ \hline \end{array}

Nyt ykkösiä pelaavalla on pakotettu siirto:

\begin{array}{|c|c|c|} \hline 0 &1 & 0\\ \hline ?&1& \\ \hline ?& ?& \\ \hline \end{array}

Sitten nolla oikeaan sarakkeeseen pakottaa laittamaan ykkösen jäljellä olevaan ruutuun samassa sarakkeessa, ja nollia pelaava voi tehdä vasemmasta sarakkeesta samanlaisen kuin oikeasta.