5
$\begingroup$

Suppose you have $n^2$ tiles that look like this:

enter image description here

How many ways can you place them in a square grid of $n$ by $n$ tiles so that each edge of each tile only touches an edge of the same color on an adjacent square?

My reasoning was as follows:

Suppose we start by placing a tile in the top-left corner. There are $4$ options for how this tile can be rotated. Then we place the $2n-1$ tiles in the same row and in the same column as that first tile. There are $2$ ways to place each of these, since they will each share one side with an already-placed square when they are laid down. The rest of the tiles are forced and have exactly one option for placement. Thus the number of placements is $$4*2^{2n-2}$$ $$=2^{2n}$$

However, the problem is that some arrangements produced this way are rotations and reflections of other arrangements. How can I count the number of unique arrangements that cannot be obtained by any other with a rotation or reflection?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is only a partial answer ...

If $n$ is odd, then no configuration can be rotated or mirrored:

Mirrors are impossible because of the diagonals in the middle row and column.

Rotations are impossible, because if a configuration could be rotated, then that means that along every one of the 4 outside sides of length $n$, there would be the same number of black edges, and the same number of white edges. But since $n$ is odd, the number of black edges has to be different from the number of white edges. Thus, there cannot be the same number of black edges as white edges on the outside of the $nxn$ figure if the configuration can be rotated. However, if $n$ is odd, then for any valid configuration, the number of black edges on the outside must equal the number of white edges on the outside: since the opposite sides of any single tile have opposite colors, it must be true that the opposite outside edges of any $nxn$ figure with $n$ being add will have to have opposite colors as well. Therefore, there cannot be any valid configuration that can be rotated for any odd $n$. So, for odd $n$, the number of unique configurations is exactly $2^{2n}$

For even $n$, one useful observation is that every valid configuration that can be rotated must have a left-right and up-down mirror. This is because for even $n$, the opposite edges on the outside of any row or column must have the same color. So, for example, take a valid configuration that can be rotated, and suppose the leftmost edge of row i is black. Then by rotation that means that the bottom of column i, the right side of row n-i, and the top of column n-i must all be black as well. But since the opposite ends of each row and column must have the same color, we also have that the right edge of row i, the top of column i, the left side of row n-i, and the bottom of column n-i must all be black as well. And you can do the same reasoning for any of the inside edges. Thus, any rotatable configuration has to be left-right symmetric as well as top-down symmetric. Thus, there is no need to consider any rotations; you just need to figure out the mirror cases.

Let's call any configuration that has a left-right as well as a top-down mirror a 2-way mirror configuration. How many of those are there? Well, let's start in the top-left corner. This tile can be put in 4 ways, and after that, you can tile each of the $\frac{n}{2}-1$ other squares to finish up the left half of the outside length in 2 ways, so you can tile the left half of the top row in $4*2^{\frac{n}{2}-1}$ ways. However, once you have done that, and given that we are trying to get a 2-way mirror configuration, the rest of that top row is fixed as well given the left-right mirror. But then, given the top-down mirror, the bottom row is fixed as well.

OK, so now we can finish the top half of the left column in $2^{\frac{n}{2}-1}$ ways, which by top-down symmetry fixes the bottom half as well, and by left-right symmetry the right column. And now having all the outsides fixed, the rest of the figure will be fixed as well.

So, in sum, there are

$$4*2^{\frac{n}{2}-1}*2^{\frac{n}{2}-1}=2^n$$

2-way mirror configurations.

Now, how many 1-way mirror configurations are there?

Since by a 90 degree rotation every left-right 1-way mirror becomes a top-down 1-way mirror, we only need to count the left-right one-way mirrors. Again, we can put in the tile in the top-left in 4 ways, and after that there are again $2^{\frac{n}{2}-1}$ ways to finish up the left half of the top row, which by left-right symmetry will finish up the whole top row. Now we can tile the rest of the left column, where each of the $n-1$ squares can be tiled in 2 ways. However, of these $2^{n-1}$ possible ways to tile the rest of the left column, there will be $2^{\frac{n}{2}-1}$ tilings that end up with a top-down symmetry, which in this case we don't want. In other words, there will be $2^{n-1}-2^{\frac{n}{2}-1}$ ways to tile the rest of the left column without a top-down symmetry. So, in total there will be:

$$4*2^{\frac{n}{2}-1}*(2^{n-1}-2^{\frac{n}{2}-1})=2^{\frac{n}{2}+1}*(2^{n-1}-2^{\frac{n}{2}-1})=2^{\frac{3n}{2}}-2^n$$

Left-right mirror but not 2-way mirror configurations.

Of course, you get the same number of top-down but not 2-way mirror configurations.

Finally, since each 2-way mirror configuration has 4 identical copies, and each 1-way mirror configuration 2, that means that with the formula $2^{2n}$ we overcounted 3 times the umber of 2-mirrors, and 1 time the number of 1-way mirrors. Thus, we get that there are:

$$2^{2n}-3*2^n-(2^{\frac{3n}{2}}-2^n)=$$

$$2^{2n}-3*2^n-2^{\frac{3n}{2}}+2^n=$$

$$2^{2n}-2*2^n-2^{\frac{3n}{2}}=$$

$$2^{2n}-2^{n+1}-2^{\frac{3n}{2}}$$

unique configurations when $n$ is even

$\endgroup$
6
  • $\begingroup$ Yes, I see how that works for odd $n$... Any idea how to approach finding the number of duplicates for even $n$? $\endgroup$ May 29, 2017 at 16:00
  • $\begingroup$ @Frpzzd I haven't found anything super useful yet ... So far I tried two strategies: 1. Fix one of the quadrants (which can be done in $2^n$ ways), and then figure out possible mirrors and rotations from that ... 2. Start with 2x2 figure, and try to get some recursive relation going to go to 4x4, 6x6, etc. So far I got stuck with both strategies... $\endgroup$
    – Bram28
    May 29, 2017 at 16:34
  • 1
    $\begingroup$ @Frpzzd OK, I figured out 1 useful thing about even $n$: there is no need to consider rotations in additions to mirrors, since there can't be any valid configuration that is rotatable but not mirrorable. I added the reasoning for this to my Answer. $\endgroup$
    – Bram28
    May 29, 2017 at 17:05
  • $\begingroup$ @Frpzzd OK, I think I got it ... $\endgroup$
    – Bram28
    May 29, 2017 at 17:48
  • $\begingroup$ Wow... that's a really great solution. Thank you! $\endgroup$ May 29, 2017 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .