Let's discuss Mathematics

[peter grimes]

Depends on how many different veneers are available

 

[ParadigmShifter]

Interesting question. I guess you are studying either combinatorics or group theory dutchfire

I did combinatorics but didn't do anything like that so presumably this is group theory.

First, I thought "well we can rotate the table so we can always pick the top left tile to be up (say) and vary the rest, accounting for duplicates in the rotation of the table".

This is FALSE though, the pattern

lu
dr

cannot be rotated so that it has an up arrow in the top left corner.

So then I investigated the symmetry groups of that pattern, it has rotational group order of 4 (every 90 degree rotation gives you the same pattern), but it's symmetry group is very interesting, no matter which plane of symmetry you use to reflect in, you get this pattern:

ur
ld

And performing the mirror image operation twice in the same plane gets back the original pattern.

I then did a brief investigation of the symmetry groups of the pattern

uu
uu

which has a rotation group of order 1 (i.e. you need to turn it 360 degrees before you get back the original shape).

The reflection group however has 4 elements in it, which are the rotations of the table.

So my first guess is that there are 9 different patterns, of the form:

Order if rotation group: 1, 2 or 4
and
Number of members in the reflection group: 1, 2 or 4

so all combinations of those, i.e. 3x3.

That's my first guess. I have another more complicated guess based on the orders of the reflection groups rather than the number of members, which would be 48. I can do an explanation of that too

What I implicitly assume is that no 2 "different" patterns have the same symmetry groups as each other, which may or may not be true

EDIT: Doh, of course that's not true, rotations of the all the arrows in the first pattern I considered gives 4 different patterns with the same symmetry groups (I think ). Hmm, I'm changing my guess to 48 then...

EDIT2: I'm also fairly open to 96 or 192 being the correct answer

 

[ParadigmShifter]

Right, I've had another cup of tea and am ready to tackle this problem again.

I have a new approach involving modulo arithmetic and only considering the rotation symmetry of the designs.

I'll get some beers and then post my investigation.

Good question btw dutchy.

 

[ParadigmShifter]

OK, I guess this is going to be quite a large post/series of posts.

If anyone has any simple answers, feel free to interrupt me.

First, I'm going to reduce this to a problem in algebra and group theory, and I'm going to ditch "up", "down", "left" and "right" by assigning them numbers from the group of integers modulo 4.

0 = Up
1 = Right
2 = Down
3 = Left

Next, I am going to describe the pattern by a string of numbers starting from the top left and going round clockwise, so the string 0123 correspond to

01
32

i.e.

up right
left down

I'm going to consider the 3 different cases separately, the case for rotation symmetry of 4 (pattern unchanged by rotation through 90 degrees), case for rotation symmetry 2 (unchanged by rotation through 180 degrees), and rotation symmetry of 1 (can only get back to original pattern by rotating through 360 degrees).

Those are the only possibilities for the rotation symmetry since it has to be an integer which divides the order of the group, which is 4. (Can't remember whose theorem that is, Lagrange?).

Using modulo arithmetic you use the remainder when a number is divided by 4 so 3+1 = 4 == 0 mod 4.

With me so far???

 

[ParadigmShifter]

Symmetry 4 group (unchanged by any rotation).

I state without proof that if x is the first entry in the pattern, then the next must be x+1, the next x+2, and the final one x+3, all modulo 4. This is unchanged by any any rotation (obvious) and is the only such pattern (proof?).

Therefore there are 4 possibilities:

0123
1230
2301
3012

This is the easy case. 4 possibilities then.

 

[ParadigmShifter]

Symmetry 2 group (unchanged by rotations thru 180 degrees):

If we pick the top row of the pattern, we automatically fix the bottom row.

Let's say we choose x y to be the top row. Then the pattern string is then

x y x+2 y+2

However, we can't choose y = x+1 since then the group would have symmetry 4, same as above case.

So y = x, y = x+2 and y = x+3 are the only possibilities.

So for x = 0 we have

0022
0220
0321

Similarly for x = 1, 2 or 3.

This makes 12 in all. I'm going to state that these are all different but may have to think about that for a bit longer

EDIT: Whoops, I made a mistake, I used y = x+1 wrongly (giving 0123) instead of using y = x+2 (giving 0220). Corrected.
EDIT2: I'm an idiot, I had y = x+1 twice in the previous sentence Corrected

 

[ParadigmShifter]

OK, I've thought about whether any of those groups are the same after a rotation.

I'm going to introduce an operator R here which represents a rotation through 90 degrees clockwise.

So R(x,y,z,w) -> (z, x, y, w)

Let P be the original pattern. Then 2 patterns are equivalent if R(P) = P or R(R(P)) = R or R(R(R(P))) = R. R^4 always gives P.

Now I need to think of an invariant for this operation... (Drinks beer)

EDIT: Whoops, R is wrong there (drinks more beer)

rotating the symbols 90 degrees maps

xyzw to wxyz, but that's not the whole story (see next post)

 

[ParadigmShifter]

OK, a rotation of the pattern through 90 degrees does 2 things:

It cycles the symbols as per the previous post, but correctly this time (I edited above post though)
AND
It adds 1 to each symbols value

So

R(x,y,z,w) -> (w+1, x+1, y+1, z+1)

 

[ParadigmShifter]

Example:

Let's look at the symmetry 4 case.

R(0123) -> (3+1, 0+1, 1+1, 2+1) = (0,1,2,3)

So that looks right.

 

[uppi]

Now that you have the 2 and 4 groups, can't you just calculate how many are left over?

there are 4^4 = 256 combinations and we have to identify those in the same rotation groups.

4 are in the 4 group.
2*12 are in the 2 group (2 combinations per group).

that means there are 256 - 4 - 24 = 228 left, which have to be in the 1 group.
There should be always 4 combinations who are identical under rotation for those, which means there should be 228 / 4 = 57 different combinations.

That would mean that there are 4 + 12 + 57 = 73 different combinations.

Can you argue this way, or is this just me butchering group theory?

 

[ParadigmShifter]

Hmm that looks sensible, I want to prove that the 12 I just stated are unique under R though, and also "there should always be 4 combinations who are identical under rotation" seems like it need a proof as well.

EDIT: Where did you get 2*12 from as well? I thought my argument shows that there are at most 12 designs of order 2? - Hold on, I see, there are 2 coverings of the 4^4 possibilities.

 

[ParadigmShifter]

I'm thinking there should me a multiple of 4 in the answer however, I think the answer may turn out to be 64.

I could be wrong of course

EDIT: How about invariants for R? Can you think of one?

EDIT2: I made a mistake calculating the order 2 group, corrected.

 

[uppi]

I'm thinking there should me a multiple of 4 in the answer however, I think the answer may turn out to be 64.

I could be wrong of course

Actually my argument above should also prove, that it cannot be 64. If it was 64, there would need to be 4 representations in the 4^4 space for each one. As none can have more than 4 and there are ones with only one representation, there have to be more than 64.

EDIT: How about invariants for R? Can you think of one?

Wouldn't the invariants be those of the symmetry 4 group?

And I am not sure the number 12 is correct for the 2 group: With your construction scheme, you'd get 0022 and 2200, which are the same if rotated by 180°. I have to think about it a bit more, but I think it should be 6. That would lead to 70 different combinations (still not divisible by four).

EDIT: Actually no, 0022 and 2200 are not the same. But 0220 and 1133 are if rotated by 90°.

 

[ParadigmShifter]

I'm fairly convinced there are only 6 unique possibilities in the order 2 group.

Right, I calculate R(P) for the order 2 equations I had. R^2(P) = P obviously, since they are of order 2.

Case y = x:
R(x, x, x+2, x+2 ) = ( (x+2)+1, (x)+1, (x)+1, (x+2)+1 ) = (x+3, x+1, x+1, x+3)

Notice this is what happens if we take substitute x for x+3 in the original equations.

Case y = x+2

R(x, x+2, x+2, x) = (x+1, x+1, x+2+1, x+2+1) = (x+1, x+1, x+3, x+3) , which is the same as substituting x for x+1

etc.

 

[uppi]

Yes, I think you're right. 6 unique possibilities, which have 2 representations each: P and R(P). So there are 12 representations in total, which can be constructed by your formula.

 

[ParadigmShifter]

So it looks like the 4 symmetries will have coverage 1 from the 256, the 2 symmetries will have coverage 2, and the 1 symmetries will have coverage 4, making

4 of symmetry 1 = 4
12/2 of symmetry 2 = 6
256 - 16 = 240, covered 4 times for the symmetry 1 group = 240/4 = 60

so 70 seems correct???

EDIT: 2 beer maths edit
EDIT2: edited the 2 beer edit

I think 70 is right but the ones with no symmetry are going to be a pain

 

[ParadigmShifter]

I think the pattern and the problem is similar to that previous question we had about probability.

For an N sided table with N symbols (rotated 360/N degrees) at each vertex, we have

N patterns of order 1 = N
N^2 - N patterns of order 2 = (N^2 - N)/2
N^4 - N^2 patterns of order 4 = (N^4 - N^2))/4

etc.

which corresponds to

4, (16-4)/2 = 6, (256 - 16)/4 = 60

in this example.

EDIT: Perhaps??? On 3rd beer now

EDIT2: Nope, that can't work because coverage must divide a power of N. Hmm...

 

[uppi]

70 is right. I wrote a python program to check it:

Spoiler :

code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def rotate(s):
  tmp = s[3] + s[0:3]
  r=""
  for i in range(0,4):
    r= r + (str((int(tmp[i]) + 1)%4)) 
  return r

combs = []
poss = ["0","1","2","3"]
for i in poss:
  for j in poss:
    for k in poss:
      for l in poss:
	s = i+j+k+l
	combs.append(s)

unique = []

while len(combs) > 0:
  c = combs[0]
  unique.append(c)
  for i in range(0,4):
    try:
      combs.remove(c)
    except ValueError:
      ()
    c = rotate(c)

print unique
print len(unique)

results:
['0000', '0001', '0002', '0003', '0010', '0011', '0012', '0013', '0020', '0021', '0022', '0023', '0030', '0031', '0032', '0033', '0100', '0101', '0102', '0103', '0120', '0123', '0130', '0131', '0132', '0200', '0201', '0202', '0210', '0211', '0212', '0220', '0221', '0230', '0231', '0232', '0300', '0301', '0302', '0310', '0311', '0312', '0321', '0330', '0331', '0332', '1000', '1001', '1002', '1010', '1011', '1012', '1030', '1031', '1032', '1200', '1201', '1202', '1230', '1301', '1302', '1311', '1312', '1331', '2001', '2002', '2011', '2012', '2301', '3012']
70

 

[ParadigmShifter]

Nice program, I can sort of convert that to C++ in my head

You'll never be a games programmer though if you use text representations of your data

Clearly for the 2 sided table we have 2 possibilities (00 and 01), can we come up with a formula for an N sided table? You could modify that program to be recursive on N, or go the whole hog and use Lisp

We have 2, ???, 70, ... so far.

We could then probably use that sequence site to check which sequence it is and find the mathworld page that references it.

 

[uppi]

Nice program, I can sort of convert that to C++ in my head

You'll never be a games programmer though if you use text representations of your data

I was sort of shooting for a quick development time. Thus the use of Python and text representation. If I really needed the efficiency I could have used a nifty scheme to represent the data and C++ (and then I could have started to wonder how to parallelize it). That would probably have taken much more time.

Clearly for the 2 sided table we have 2 possibilities (00 and 01), can we come up with a formula for an N sided table? You could modify that program to be recursive on N, or go the whole hog and use Lisp

We have 2, ???, 70, ... so far.

We could then probably use that sequence site to check which sequence it is and find the mathworld page that references it.

Maybe that's just the physicist in me, but: How do I have to visualize a two sided table? I'll think about generalizing the program, but that has to wait at least until tomorrow.