Wiskundemeisjes

Wie kan er winnen?

Ionica en Jeanine doen een spelletje. Ze beginnen met een lege 2008 x 2008 matrix. Om de beurt kiezen ze een reëel getal en vullen dat in op een lege plek in de matrix. Jeanine mag beginnen en het spel stopt als de hele matrix gevuld is. Ionica wint als de ingevulde matrix determinant nul heeft, Jeanine wint in alle andere gevallen. Welk wiskundemeisje heeft een winnende strategie?

Deze vraag komt uit de laatste editie van de beroemde Putnam-wedstrijd. Er zijn verschillende juiste oplossingen mogelijk, Manjul Bhargava verzon een bijzonder mooie...

14 reacties op “Wie kan er winnen?”

1. Rogier:
   zaterdag 13 december 2008 om 13:10

   Ik vind deze eigenlijk niet zo moeilijk...

   Ionica hoeft alleen te zorgen dat twee rijen of twee kolommen exact hetzelfde zijn. Stel dat ze ervoor kiest de eerste en tweede kolom hetzelfde te laten worden. Elke keer als Jeanine een getal in de tweede kolom neerzet, zet Ionica hetzelfde getal ernaast in de eerste kolom, en vice versa. Zo krijg je uiteindelijk twee dezelfde kolommen, en aangezien de determinant van teken wisselt bij het verwisselen van twee kolommen, maar tegelijkertijd hetzelfde blijft moet de determinant wel 0 zijn.

2. Vincent:
   zaterdag 13 december 2008 om 15:07

   ...maar dat roept de vraag op hoe het zit met een 2009 bij 2009 matrix!

   P.S. ligt het aan mij of worden de sommetjes die je ter voorkoming van spam steeds moeilijker?

3. Sander Z:
   zaterdag 13 december 2008 om 15:30

   Ik had ook een oplossing bedacht, maar die is wat ingewikkelder:

   Als Jeanine een getal plaatst in een bepaalde rij, dan zet Ionica een getal in dezelfde rij. De plaatst en waarde doen er niet toe. Alleen als Ionica de laatste positie vult in een rij, dan moet ze ervoor zorgen dat de som van alle waardes in die rij precies 0 is.
   Als de hele matrix is gevuld, dan is de som van de kolomvectoren nul en dus is de determinant ook 0.
   Deze oplossing lijkt een beetje op die van Mangul, alleen de manier waarop wordt bereikt dat de som in een bepaalde rij (of kolom) nul is, is wat anders...

4. KP:
   zaterdag 13 december 2008 om 18:12

   Telkens als J. het getal a op positie (i,j) zet, zet I. datzelfde getal er naast en wel op (i,j+1) als j oneven is en op (i,j-1) als j even is. Op deze manier onstaat een matrix waarin kolom 2j-1 en 2j altijd gelijk zijn. NB I. kan dit blijven doen want dankzij deze strategie is, als J. aan zet is, elk tweetal posities (i,2j-1) en (i,2j) of beide leeg of beide gevuld.

5. Tim dJ:
   zaterdag 13 december 2008 om 18:15

   @KP: Dat was precies wat rogier zei.

6. Vincent:
   zaterdag 13 december 2008 om 19:23

   Mijn gevoel zegt dat Jeanine wint in het 2007-bij-2007-geval, maar om nou te zeggen dat ik een elegante winnende strategie heb: nee. Iemand een idee?

7. han:
   zondag 14 december 2008 om 11:48

   kan iemand hier even uitleggen hoe die determinant werkt

8. HJ:
   zondag 14 december 2008 om 12:46

   Het makkelijkste is om je naar wikipedia te verwijzen. Om deze opgave te kunnen waarderen moet je weten dat determinant nul een bijzondere betekenis heeft, die te maken heeft met de vectoren die gevormd worden door de kolommen (of rijen) van de matrix. De eerste oplossing zorgt ervoor dat twee kolommen gelijk worden en dat is de determinant nul, zonder dat je verder iets hoeft te rekenen. Verreweg de makkelijkste oplossing als je mij vraagt. Persoonlijk vraag ik me af of er een strategie is die werkt door genoeg nullen op strategische plaatsen te zetten.

9. KP:
   zondag 14 december 2008 om 14:31

   @Tim dJ: Dat kan, maar ik ben te dom om spoilers te lezen ...

10. Rogier:
    maandag 15 december 2008 om 14:33

    Wat waren de andere Putnamvragen eigenlijk?

11. Oase:
    maandag 15 december 2008 om 16:28

    Putnam, maar what's in a mane...

12. Ionica:
    maandag 15 december 2008 om 16:37

    @Oase: Oeps...is verbeterd!

13. jan van rongen:
    dinsdag 16 december 2008 om 16:49

    2007*2007.Jeanine zet een cijfer in vakje (2007,2007). Ionica zet een cijfer in vakje (i,j). Jeanine kiest nu twee kolommen of rijen waar (i,j) in ligt maar (2007,2007) niet. Speelt dan de strategie van Ionica op het 2008*2008 bord.

14. Vincent:
    woensdag 17 december 2008 om 12:07

    Ha! Eindelijk een opmerking over het oneven geval! Ik ben nog niet helemaal overtuigd echter Is het niet zo dat Jeanine op die manier haar eigen graf graaft? Zij was toch degene die de determinant NIET nul wilde maken?

Plaats een reactie