Posts on January 5, 2007

Check out xkcd!
Mood: cheerful
Posted on 2007-01-05 10:37:00
Tags: rave ljbackup xkcd webcomic
Words: 82

So I recently got turned on to the webcomic xkcd. I discovered them from the sandwich strip, but there are lots of other computery random strips, as well as a few sweet ones. Even better, it's syndicated so you can just friend xkcd_rss to get the latest ones on your friends page. And don't forget to rollover to check out the extra tooltip :-)

In other news, LJBackup seems to be working again. Let me know if you have a problem with it...

The wonderful game called Tsuro
Mood: okay
Posted on 2007-01-05 23:39:00
Tags: math
Words: 794

One of the things I did over break was play a beautiful game called Tsuro. It's a quick (20 minutes or so) game that supports up to 8 people (it's actually better with 8 people!) with simple rules. And it's a thing of beauty, both in artwork and elegant design.

The board is a 6x6 grid that tiles are placed on. It starts empty. The tiles take the following form:

```
1   2
---+---+---
|         |
|         |
8 +         + 3
|         |
|         |
7 +         + 4
|         |
|         |
---+---+---
6   5
```

where the numbers 1-8 label the points on each tile. Each point on a tile is connected via a path to exactly one other tile, so a tile that had 1 connected to 8, 2 to 6, 3 to 4 and 5 to 7 would look something like:
```
1   2
---+---+---
|  |   |  |
| /    |  |
8 +-     / /+ 3
|     | | |
|     / | |
7 +--  |   \+ 4
|  \-+-   |
|   /  \  |
---+---+---
6   5
```

except a whole lot prettier.

Now, every player has a piece which starts on the outside of the board, lining up with the 2 pieces per tile edge rule. You have a hand of tiles, and on your turn you play a tile on a space your piece touches. You then move all pieces that touch that on the paths the tile indicates, so if your piece started on the 6 point it would move to the 2 point. Of course, if your piece then ends up touching a tile that exists, your piece follows the paths on that tile, and so on. The goal is to survive; your piece dies if it goes off the board, and both pieces die if there is a head-on collision of pieces.

The neat part is that there are exactly 35 tiles, enough to fill up the 6x6 grid save one empty square. In order to survive the game, your piece must end up touching that empty square. It's an elegant end condition.

But it gets even better. I wondered how many different tiles there could possibly be, excluding rotations of the same tile. (since you can rotate them when you play them) If the answer was in fact 35, that each distinct tile was used exactly once and that just happened to work out to be 6^2-1 that would be proof that this game was, in fact, given to us mere mortals from the heavens.

Let's not get ahead of ourselves, though. Firstly, how many tiles are there without caring about rotations? The way I came up with counting it is to first arrange 1-8 in a row - there are 8! ways to do this. Now pair up each consecutive number, so if we had the string 46231785, that would pair 4 and 6, 2 and 3, 1 and 7, and 8 and 5. However, we're clearly overcounting here. Firstly, the order of each pair doesn't matter, so that's 2^4=16 times we're overcounting. Secondly, the order of the pairs doesn't matter, so that's 4!=24 times we're overcounting. Putting it all together, this gives 8!/(2^4*4!)=105. Another, simpler way to count (suggested to me by djedi) is that there are 7 choices to pair point 1 with. There are 5 choices to pair the next point with, 3 for the next and the last is determined, so that gives 7*5*3=105. Good to know!

Now the tricky part. I thought there was some nice way to count the symmetries, but I was thinking of Pólya counting, which is pretty neat but I couldn't see how to apply it. Not that I could remember this in Austin, so I used the Orbit-stabilizer theorem instead.

There are three types of symmetries a tile can had - 90 degree symmetry, 180 degree symmetry and no symmetry. Let's count how many tiles have each.

90 degree - a 90 degree rotation takes 1->3, 2->4, 3->5, 4->6, 5->7, 6->8, 7->1 and 8->1. So we have the chains 1->3->5->7 and 2->4->6->8. This gives the following tiles: (12)(34)(56)(78), (14)(36)(58)(72), (16)(38)(52)(74), (18)(32)(54)(76), (15)(37)(26)(48). It's surprisingly hard to find all these.

180 degree - here the chains are 1->5, 2->6, 3->7, and 4->8. If we list all these out, excluding the ones that have 90 degree symmetry, we get 10 tiles. (another mistake I made was counting 20 of these, but I was counting each rotation of each tile)

no symmetry - we'll count these by elimination, thank goodness.

So each 90 degree tile shows up once in the list of 105, each 180 degree tile shows up twice in the list of 105, and each tile with no symmetry shows up four times in the list of 105. So, there are (105-5-10*2)/4=20 distinct tiles with no symmetry. Adding, we get a total of 5+10+20=35 tiles, just like we wanted!!

Anyway, that's why the game is truly beautiful. We're going to game night at a game store tomorrow night and I'll see if they have a copy :-)