How many distinct tiles can be formed in the game of Tsuro?

[davee123]

So, there's this game called "Tsuro". Pretty neat. The game contains square tiles, each with 4 line segments drawn on it, connecting points along the edges.

A little more specifically, each tile has 8 points on the edges, 2 on each side, evenly distributed on each side (IE each point is 1/3 of the distance of the whole edge from the corner).

,--o--o--.
|        |
o        o
|        |
o        o
|        |
`--o--o--'

4 line segments (curved or straight) are then drawn between these endpoints such that each endpoint is used exactly once.

How many distinct tiles are possible?

---

I figured out this answer by way of brute force, because I couldn't come up with a good logical solution, mostly thanks to the rotation factor. Can anyone think of a good way of proving the end result?

DaveE

 

[AKG]

$$\frac{4!{{8}\choose{4}}}{2^4} = 105$$

Is that right?

Label the vertices 1 through 8. Now the number of way to put four edges in so that each vertex coincides with one and only one edge is equal to the number of ways to put four directed edges so that each vertex coincides with one and only one directed edge, divided by the number of unique directed graphs that correspond to a given undirected graph. Well, the number of unique directed graphs that correspond to a given undirected graph is 2⁴, because given four undirected edges, there are two possibilities for a direction for each edge, and there are four edges, and the choices for the directions the edges are independent from one another.

So now we have to find the number of directed graphs. First, we choose the initial vertices of the edges, and there are ${{8}\choose{4}}$ ways to do this. Now take these four vertices, and list them in order (recall we labelled them 1 - 8). We now have to find terminal vertices for these edges. There are four vertices remaining, and there are 4! ways to arrange them. Each arrangement gives rise to a unique way to pair one of the terminal vertices to an initial vertex, and thus gives rise to a unique directed graph where the initial vertices of the directed edges are as chosen when we did the ${{8}\choose{4}}$.

So:

$$\frac{1}{2^4} \times 4! \times {{8}\choose{4}}$$

 

[chroot]

Well, there's no such thing as a curved line segment. Curves are curves, line segments are lines.

If you can actually draw curved lines on the tiles, then there are infinite number of distinct tiles.

- Warren

 

[davee123]

Perhaps a little more clarification, sorry.

1) There's not that many tiles. Less than 50.

2) The specific arc of the curve is irrelevant. The important thing about the line segments is that where they're connected from and to, not the shape of the segment. Hence, top-side left to right-side top is a distinct connection.

3) Further, connections are not directional. Top-side left to right-side top is also the same connection as right-side top to top-side left. And FURTHER, it's the same as left-side bottom to top-side left, because it's just rotated. 270 degrees.

DaveE

 

[AKG]

There's a much simpler solution, given the way I interpreted it. I was actually going this way at first, but I wasn't formulating it the right way so I thought I was double counting. First, look at vertex 1 and choose its "partner". There are 7 such choices. Next, look at the smallest unoccupied vertex. Then choose its partner, there are 5 choices. Then choose the next smallest unoccupied vertex, and choose its partner: 3 choices. Finally, choose the next smallest unoccupied vertex, and you have one choice for its partner:

7 x 5 x 3 x 1 = 105

Now if we regard two tiles as the same if one can be obtained from another by rotation, then it becomes trickier.

 

[AKG]

How many tiles have 90 degree symmetry (i.e., you can rotate by 90 degrees and get something that looks the same)? 4.

How many have 180 degree symmetry (i.e. they don't have 90 degree symmetry, but if you rotate by 180 degrees you get something looking the same)? 3 + 3 + 2 + 2 + 2 + 2 = 14. But we want to divide by 2, so we get 7.

How many have no symmetry? (4x3) + (4x3) + (4x2) + (4x4x3) = 80

total:91

So I gues something's wrong here; I'll have to think about it some more.

 

[davee123]

Just as an example, because in re-reading the above, it comes across as a bit unclear, here are example tiles. Notice that these three images constitute only two distinct tiles, as one is merely a rotation of another. The third image, however, is mirrored and rotated, and therefore is not the same as the other two.

DaveE

 

[NateTG]

AKG - I count 5 with 4-symetry:
1-2
1-4
1-5
1-6
1-8

And (I haven't checked yet) but I think there are a 14 with 2-symetry.
So I think the number of tiles is going to be 76 tiles.

 

[AKG]

You're right, there are 5 with 4-symmetry. And I also counted 14 with 2-symmetry, so I divided 14 by 2 to get 7.

 

[davee123]

Further hints:

There are far fewer than 76 tiles!

When I found the answer, it was enough of a bizarre number that it made me second guess myself, so I had to write a program to verify. Here's how it works:

It goes through the 105 combinations, and each time that it finds a tile that it already found (thanks to rotation), it doesn't count it. Some tiles are unique (none need throwing out), some tiles get derived twice (1 is thrown out), and some tiles get derived four times (3 are thrown out).

For naming purposes, let's name the points. Clockwise, starting with the top side, let's name the points A,B,C,D,E,F,G,H.

The program goes through (just like the 7 x 5 x 3 x 1 logic) and picks AB, and tries all the possible combinations of AB. Then it picks AC, and tries all combinations of that. Then AD, then AE, etc.

The first tile it finds is AB-CD-EF-GH. But that's unique. It'll never find that tile again. So even though it's symmetrical along both diagonals, the vertical, the horizontal, and rotationally symmetrical at 90 degrees, 180 degrees, AND 270 degrees, it's only ever *derived* once.

By comparison, let's look at AB-CH-DG-EF. It's derived *twice*. The other time it's derived as AF-BE-CD-GH. But it's never derived in any other format.

Then, let's take a look at AC-BD-EH-FG. It's derived *four* times, also as: AG-BH-CF-DE, AD-BC-EG-FH, and AH-BG-CE-DF.

DaveE

 

[NateTG]

davee - you're right, I've got it backwards. It will be something like:

5 Tiles with 4 symetry are counted once
14 tiles with 2 symetry are counted twice
18 tiles with 1 symetry are counted 4 times each

That would be a total of 37 tiles.

 

[davee123]

davee - you're right, I've got it backwards. It will be something like:

5 Tiles with 4 symetry are counted once
14 tiles with 2 symetry are counted twice
18 tiles with 1 symetry are counted 4 times each

That would be a total of 37 tiles.

Very close! The 14 and 18 are a little off, but the 5 is correct. As I'm re-analyzing the problem, I'm discovering a little bit more about *why* there are 5 with all-around symmetry, N with 180-symmetry and M with no symmetry. But it's quite confusing, nonetheless.

You know (for instance) that in order to be *fully* symmetrical, all 4 lines must be of the same type. By "type" I mean one of the 6 (or 8 depending on whether you want to count mirror images) different classes of line segments that can possibly be drawn on the tile. Anyway, if the *all* types of lines used on the tile aren't all the same, the tile won't be symmetrical when you rotate it 90 degrees.

By the same token, in order to be 180-degree symmetrical, you have to use *two* distinct types of lines. If you use 1 type of line, you'll be 90-degree symmetrical, and if you use 3 or 4, you won't be symmetrical at all. Further, some classes of lines won't intermix. One line type in particular is *really good* at intermixing with other types for 180-symmetry.

DaveE

 

[AKG]

I counted by hand 8 distinct 2-symmetry tiles. If we counted rotations as distinct, this would give 16 tiles. There are 5 4-symmetry tiles, and 105 tiles in total (counting rotations as distinct), so there are

105 - 5 - 16 = 4 x 21

no-symmetry tiles. But not counting rotations as distinct, this gives 21 no-symmetry tiles, so we get a total of 5 + 8 + 21 = 34 tiles.

I tried generalizing this, so we look at a regular n-gon, and have 2 vertices on each edge (a 2-gon will be like a football), and counting the number of tiles:

n = 1, T(n) = 1
n = 2, T(n) = 3
n = 3, T(n) = 7
n = 4, T(n) = 34 (assuming the above is right)
n = 5, T(n) = 5 + (9x7x5x3 - 5)/5 = 193

I tried plugging this into http://www.research.att.com/~njas/sequences/ but nothing came up.

 

[davee123]

so we get a total of 5 + 8 + 21 = 34 tiles.

Close, but not quite. Again, 5 is correct, 8 and 21 are slightly off.

I tried generalizing this, so we look at a regular n-gon, and have 2 vertices on each edge (a 2-gon will be like a football), and counting the number of tiles:

n = 1, T(n) = 1
n = 2, T(n) = 3
n = 3, T(n) = 7
n = 4, T(n) = 34 (assuming the above is right)
n = 5, T(n) = 5 + (9x7x5x3 - 5)/5 = 193

I tried plugging this into http://www.research.att.com/~njas/sequences/ but nothing came up.

Wow, I'm not sure I follow the logic you got for n=5, but my program verified that that's correct!

T(1) = 1
T(2) = 3
T(3) = 7
T(4) = 30-something
T(5) = 193
T(6) = 1799
T(7) = 19311
T(8) = 254143

Sadly, the program isn't very happy much beyond 7. It took a few minutes to calculate 8, and probably would take a few hours to do 9, so I think I'll skip that!

Oh, and I didn't get any results either for pattern matches on the site you mentioned.

DaveE

 

[AKG]

Label the points on the 5-gon 1 through 10. So one side has 1 and 2 on it, the next had 3,4, the next has 5,6, etc. A tile clearly has either 5 symmetry or no-symmetry. If we join 1 to an odd number, then this tile cannot have 5 symmetry, since saying what 1 joins to determines what each odd number is joined to. In particular, if 1 is joined to x, then 3 is joined to 2+x (mod 10), 5 is joined to 4+x (mod 10), etc. Now if 1 is joined to something odd, then all odds will have to be joined to something odd. This would suggest that the odd numbers come in pairs, that is, there is an even number of odds, but there are only 5 odds, contradiction.

On the other hand, its easy to see that connecting 1 to any even point gives a perfectly valid, unique tile that corresponds to a unique 5-symmetry-having tile. There are 5 even numbers, so there are 5 five-symmetry tiles.

The total number of tiles, where if x and y are tiles where one is a rotation of another, then x and y are counted as distinct, is, as we've seen, just 9 x 7 x 5 x 3. Since there are 5 five-symmetry tiles, and since any tile is either 5 symmetry or no-symmetry, there are 9x7x5x3 - 5 no-symmetry tiles. We have to divide this number of 5 because, in the end, we want to ignore rotations, so the total number of no-symmetry tiles, where now if x and y are rotations of each other, they are counted as the same, is (9x7x5x3 - 5)/5. Adding this to the number of 5-symmetry tiles (namely, 5) gives the desired result.

In fact, if p is prime, then it's easy to apply the same argument, and count that the total number is:

p + ((2p-1)x(2p-3)x...x3 - p)/p

In particular, where p = 7, we get:

7 + (13x11x9x7x5x3 - 7)/7 = 19311

corresponding to what your program gave.

----------

Let x be the number of tiles of our square with 2-symmetry. Counting rotations as distinct, this gives 2x. There are 5 4-symmetry tiles, so the total number of no-symmetry tiles, counting rotations as distinct, is:

105 - 5 - 2x

Counting rotations as indistinct, we divide this by 4, and add to x and 5 to get the total:

5 + x + (105 - 5 - 2x)/4
5 + x + 25 - x/2
= 30 + x/2

I tried counting the number of 2-symmetry tiles by hand, and got 8, explaining why I got 34. So I must have counted wrong. Recounting, I get 10, so the answer is 35.

 

[davee123]

In fact, if p is prime, then it's easy to apply the same argument

Neat! Now we just need the general case :)

Recounting, I get 10, so the answer is 35.

Ding ding! We have a winner!

DaveE

 

[AKG]

Do you think you could get your computer to take input n, and for each divisor d of n, print out the number of tiles of the n-gon with d-symmetry?

n = 2
d = 2 : 3
d = 1 : 0


n = odd prime p
d = p : p
d = 1 : [(2p-1)(2p-3)...(3) - p]/p

n = 4
d = 4 : 5
d = 2 : 10
d = 1 : 20

I've convinced myself that for n odd, d = n : n. The argument is the same as when I said the thing about primes, since joining 1 to any even number will work, and joining 1 to an odd number implies the odd numbers come in pairs, which is false whenever n is odd. When n is even, d = n : n+1. Why, because 1 can be joined to all n even points. There is a single odd point that 1 can be joined to, and that is n+1. It's not hard to convince yourself that this is the case.

 

[davee123]

Do you think you could get your computer to take input n, and for each divisor d of n, print out the number of tiles of the n-gon with d-symmetry?

Up to 8, probably. But not beyond 8, unless I want to wait several hours while the CPU chomps itself to a slow death. At n=8, it goes through just over 2 million possible tiles and takes... about 10 minutes or so. I forget exactly, I sort of left it alone to do its thing, since I wasn't going to bother waiting more than a minute or so attentively. At n=9, it'd be up to 34 million (about 2 hours), and then 654 million at n=10 (about 2 days). I'll try it for 1-8 at least...

DaveE

 

[NateTG]

I've convinced myself that for n odd, d = n : n. The argument is the same as when I said the thing about primes, since joining 1 to any even number will work, and joining 1 to an odd number implies the odd numbers come in pairs, which is false whenever n is odd. When n is even, d = n : n+1. Why, because 1 can be joined to all n even points. There is a single odd point that 1 can be joined to, and that is n+1. It's not hard to convince yourself that this is the case.

Let's say I have a 9-sided figure.
We know that there are 4 non-symetric 3-arrangements.
Now, we can map these 3-arragements to (1-6),(7-12),(13-18), or to (1,2,9,10,17,18),(3,4,11-14),(5-8,15,16)
which must clearly be distinct, so there are at least 24 9-tiles with 3-symetry. I'll try hacking up something to count symetries tonight.