Sunday, October 07, 2007

Balanced Incomplete Block Designs and Steiner Triple Systems

When I was playing Take It Easy today I realised that the tiles formed a block design. So the thought immediately came to mind: "is there a Steiner Triple System in this game?" At this point you're thinking, "well duh, didn't you know that?" I guess I'm just slow.

A block design is a set of b subsets (called blocks) of a set X, each of size k. Set X has v elements, each of which appears in r blocks. In an incomplete block design, not all k-element subsets of of X are in the list of blocks. In a balanced incomplete block design (BIBD) there is a number λ such that any two elements of X appear in λ blocks together. This is called a (v, b, r, k, λ) BIBD.
Let me clarify. X = {1, 2, 3, 4, 5, 6, 7, 8, 9} so v=9. Each tile is a subset of size 3 of those numbers, so k=3. There are 27 tiles, so b=27. From this we can determine r... there are 27 tiles with 3 numbers each, so there are 81 numbers in all - and each can be one of 9 values, so each must appear 9 times, so r=9. It's true in a block design that v*r = k*b.

What about λ? 7 and 8 appear together on 3 tiles - with 1, 5, and 9. But how many times do 1 and 5 appear together on a tile? Never! So there is no value for λ and the block design is not balanced. That's a pity because I can't show you how λ*(v − 1) = r*(k − 1).

A Steiner triple system is a set of m elements with 3-element subsets such that for any two elements they appear together in exactly one 3-element subset.

Set contains a Steiner triple system - the subsets of size 3 are the sets, and for any two cards there is a unique third card which forms a set. For any two numbers which appear together on a tile, there are 3 such tiles on which they appear (e.g. 178, 578, 978). However it's not the case that on any two tiles there's a unique third tile which makes up the triple... e.g. 123 and 178. Unless we do something really cunning...

Take any two tiles. If they have two numbers in common, the third tile in the triple is the other tile with those two numbers on it. If the tiles have zero numbers in common, e.g. 123 and 578, the third tile is the tile with exactly the numbers that don't appear on either tile, so 946 in this case. That tile is unique. If the tiles have one number in common, then the third tile is the tile with that number and two completely different numbers, e.g. the third tile for 123 and 178 is 146. So now, given any two tiles there's a unique third tile forming the triple (or set). That's a Steiner triple system! Woohoo!

In fact, the simpler rule is that in each of the 3 positions on the tile the numbers must be all the same or all different. There are only 3 dimensions rather than 4, and Take It Easy has only 27 tiles instead of 81.

I decided long ago to collect games with Steiner triple systems so I guess I have to get Take It Easy now and I could use it to play Set. Hmm... could I use Set cards to play Take It Easy?


Maria said...

I wish a layout of cards would come up like that more often in SET.

I have got better at SET but I don't think I've ever won.

Maria said...

Just like to report I've never beaten Mr Coffee at a game of Set yet, but I got as close as I ever have today. 13 to 12!

Getting there!