The Game of Determinant

This is the second of two articles written especially for Ada Byron’s 200th birthday.

While sifting through Mathematicians Also Joke by S. Fedin, I came across a pretty interesting paragraph:

Мне рассказывали, что одно время среди первокурсников мехмата была популярна игра в “определитель” на деньги. Двое игроков чертят на бумаге определитель 3 x 3 с незаполненными ячейками. Затем по очереди вставляют в пустые ячейки цифры от 1 до 9. Когда все клетки заполнены, определитель считают – ответ с учетом знака и есть выигрыш (или проигрыш) первого игрока, выраженный в рублях. То есть, если, например, получилось число -23, то первый игрок платит второму 23 рубля, а если, скажем, 34, то наоборот, второй платит первому 34 рубля.

In case your Russian is not perfect, I will now retell that text in English.

The author describes what he calls the Game of Determinant. Alice and Bob take turns to fill the elements of a 3 x 3 matrix with numbers from 1 to 9. Fedin unfortunately does not proceed to explain what exactly he meant by that, and we thus have to choose from three possible interpretations:

  1. (Weak) Alice places number 1, then Bob places number 2 and so on.
  2. (Medium) Alice chooses any number from 1 to 9, then Bob chooses any other number and so on.
  3. (Strong) Again, Alice chooses any number, but Bob is now allowed to choose the same number.

I think that the weak variant is the most intuitive, so let us stick to it. When the matrix is filled, the players compute its determinant. I don’t think I can silently assume that all of you know what the determinant is, so here is the formula for the 3 x 3 case we are interested in:

The determinant is, according to Fedin, equal to the number of rubles* that Alice wins. If the determinant is negative (which will happen about half of the time in case of a thoughtless play), then Alice loses money.

* Actually, the Soviet ruble was quite valuable, so I believe smaller amounts of money were actually used. But this is completely off-topic.


Despite being pretty complicated, this game has only 9! = 362 880 possible sequences of moves. It is thus tempting to write a program that would make a complete analysis of the game, and this is exactly what I did. The program has one complicated part, namely a bijection between matrices and non-negative integers from a certain interval. The bijection I used is certainly much more difficult to describe than to code, so I will only say the magic words “numeral system with variable base” and send you to the code if you want further details. Everything else was easy.

And here come the results, which I find very unexpected. I used to think that Alice has more liberty and should thus be able to force a win. My intuition turned out to be totally incorrect, and indeed Bob can always win at least 124 units of money. An optimal game goes like this:

If you are interested, the compiled program and its source code are availible here and here.


And lastly, I am curious whether the second player still wins in medium and strong variants of the game. If you can shed light on this issue, the “Leave a Reply” box is definitely for you.

Advertisements
This entry was posted in Games. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s