Tiling problem
Angelo Wentzler
I've got an interesting problem. (Well, that's what I think anyway...)
It goes like this:
Given a grid of squares, tile it with black and white tiles and make
the largest possible square so that no square contained in it has four
equally colored corners.
This means that the big square itself may not have four equally colored corners
either...
It seemed fun to write a program to find such squares, so I did. Suffices
to note that any NxN square must contain an (N-1)x(N-1) square, so starting
with a 2x2 and using branch & bounded search additional squares can easily be
found.
My computer is fairly slow (8MHz), but after only 6 hours of calculation I
came up with an 11x11 square. About 24 hours later I still hadn't found a
12x12 square!! (An abundance of 11x11, though...)
Two days later: still nothing.
If there is a 12x12 square, it must be found eventually, or the process must
stop. This is because the number of 11x11 squares is not infinite (nor is the
number of squares of any size), so that the tree of possibilities is either
finite or it has an infinite branch (producing the needed 12x12.)
But would the difference in time between the 11x11 and the 12x12 really be that
big?
Of course it made me wonder if there was a limit to the size of those squares.
I can't believe there is no 12x12 (why would 12 be the limit? Why not 13?)
but belief is not something to mention on sci.math. I would appreciate some
extra help, though, like: is it possible to make rules for this tiling?
Can you prove there is a limit and if so, what is that limit? Generalising
to more colours than just two would be fun, too.
Please send any comments/ideas/solutions to me by email, because I don't read
news regularly (I should, I know.)
Angelo Wentzler
Torben AEgidius Mogensen
I did some calculations on the expected number of such tiled squares
of side-length N. There are 2^(N^2) B/W coloured squares total. A
square of side-length N has sum{i=1}{N-1}{i^2} subsquares. There are
16 colourations of the corners of a square, of which 14 are legal.
This means that the chance that a random square of side-length N is
correctly tiled is approximately (14/16)^(sum{i=1}{N-1}{i^2}). Since
there are 2^(N^2) possible squares, the expected number of correct
squares is
2^(N^2)*(14/16)^(sum{i=1}{N-1}{i^2})
The table below shows the approximate values of this estimate
N correct tilings
2 13
3 263
4 10106
5 610930
6 4.4e07
7 3.0e09
8 1.4e11
9 3.6e12
10 3.8e13
11 1.3e14
12 1.0e14
13 1.5e13
14 3.2e11
15 7.4e08
16 142450
17 1.74
18 1.0e-6
So by this estimate the maximum size would be around 17. How good is
this estimate? I tried to find all solutions for the small sized
squares and got these exact results
N tilings
2 13
3 284
4 11066
5 782718
So the estimate is not too bad, if a bit on the low side. So I still
expect the limit to be around 17, quite likely exactly 17.
As for the time to search for 12x12 squares compared to the time to
search for 11x11 squares: one out of (approx.) every 2.1e22 11x11
square is correctly tiled but only one out of 2.2e29 12x12 square is.
So one would expect the time to find the first correctly tiled 12x12
square to be about 1.0e8 times as long as the time to find the first
correctly tiled 11x11 square.
Torben Mogensen (tor...@diku.dk)
Torben AEgidius Mogensen
>I did some calculations on the expected number of such tiled squares
>of side-length N. There are 2^(N^2) B/W coloured squares total. A
>square of side-length N has sum{i=1}{N-1}{i^2} subsquares. There are
>16 colourations of the corners of a square, of which 14 are legal.
>This means that the chance that a random square of side-length N is
>correctly tiled is approximately (14/16)^(sum{i=1}{N-1}{i^2}). Since
>there are 2^(N^2) possible squares, the expected number of correct
>squares is
> 2^(N^2)*(14/16)^(sum{i=1}{N-1}{i^2})
>The table below shows the approximate values of this estimate
> N correct tilings
> 2 13
^^ This should be 14. Typing error.
> 3 263
> 4 10106
> 5 610930
> 6 4.4e07
> 7 3.0e09
> 8 1.4e11
> 9 3.6e12
> 10 3.8e13
> 11 1.3e14
> 12 1.0e14
> 13 1.5e13
> 14 3.2e11
> 15 7.4e08
> 16 142450
> 17 1.74
> 18 1.0e-6
>So by this estimate the maximum size would be around 17. How good is
>this estimate? I tried to find all solutions for the small sized
>squares and got these exact results
> N tilings
> 2 13
> 3 284
> 4 11066
> 5 782718
As Dan Hoey pointed out to me, these figures are wrong. First of all I
used 0..(n-1) counting, so you should read e.g. 14 instead of 13.
Secondly, I counted some solutions twice. This was easy to fix (a
silly mistake really). The corrected numbers are
N tilings relative error
2 14 1
3 276 1.049
4 10980 1.086
5 781712 1.280
If anything this makes the estimate better. It is still too low,
though. The relative error is increasing, but there is not data enough
to see how quickly. Getting the exact number of solutions for
side-length 6 is going to take quite some time, so I don't think I'll
try.
Torben Mogensen (tor...@diku.dk)
Ken Grant
>Given a grid of squares, tile it with black and white tiles and make
>the largest possible square so that no square contained in it has four
>equally colored corners.
>Of course it made me wonder if there was a limit to the size of those squares.
>Can you prove there is a limit and if so, what is that limit? Generalising
>to more colours than just two would be fun, too.
I think it follows from (Grunwald/Gallai?) n-dimensional version of
the Van der Waerden theorem that there is a limit, doesn't it?
(see the books _Recurrence in ergodic theory and combinatorial
number theory_, _Ramsey theory_ by Graham et. al., _Mathematics of
Ramsey Theory_.)
I don't know if there's a significantly easier proof of this special
case.
Ken Grant.
Robert B. Israel
In <rcbaaw.7...@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
Wentzler) writes:
>Given a grid of squares, tile it with black and white tiles and make
>the largest possible square so that no square contained in it has four
>equally colored corners.
>My computer is fairly slow (8MHz), but after only 6 hours of calculation I
>came up with an 11x11 square. About 24 hours later I still hadn't found a
>12x12 square!! (An abundance of 11x11, though...)
>Two days later: still nothing.
Here's a 12 x 12 square, which I found quite rapidly using a "tabu search"
program. No 13 x 13 yet, though.
000011011111
011010010101
001100110011
010110100110
010100101010
011001100101
101101001100
100101010110
110011010010
101010011001
110011001011
100110100101
--
Robert Israel isr...@math.ubc.ca
Department of Mathematics or isr...@unixg.ubc.ca
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
Robert B. Israel
>Given a grid of squares, tile it with black and white tiles and make
>the largest possible square so that no square contained in it has four
>equally colored corners.
>My computer is fairly slow (8MHz), but after only 6 hours of calculation I
>came up with an 11x11 square. About 24 hours later I still hadn't found a
>12x12 square!! (An abundance of 11x11, though...)
>Two days later: still nothing.
On an overnight run with over 1.2 million steps of tabu search, I did
find a 13x13 square:
0001101010110
0101011000011
1100001101110
0110101011000
0101100001101
0000110101011
1011101100001
0110000110111
0011010101100
1010110000110
1000011011101
1101110110000
1011000011010
Since 12x12 only took a few thousand steps, I think this is a good
time to quit.
I am a terminator.
Would the following be a recursive solution?
0
1
Kinda small--let's double the size.
00
00
Um ... no internal squares in these little squares so no 4 colored corners.
Doubling again:
0011
0011
1100
1100
Now your starting to worry. The internal squares have 4 (colored) corners.
In general, the internal 0 (or the internal 1) has two 0 corners and two
1 corners. So that's OK.
00110011
00110011
11001100
11001100
00110011
00110011
11001100
11001100
Recursing makes a checkerboard so internal squares have two colors on the
corners.
0011001100110011
0011001100110011
1100110011001100
1100110011001100
0011001100110011
0011001100110011
1100110011001100
1100110011001100
0011001100110011
0011001100110011
1100110011001100
1100110011001100
0011001100110011
0011001100110011
1100110011001100
1100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
Henry Choy
ch...@cs.usask.ca
I guess they don't have all 4 sides the same color either.
Bummer.
Torben AEgidius Mogensen
>In article <israel.7...@unixg.ubc.ca>, isr...@unixg.ubc.ca (Robert B. Israel) writes:
>|> In <rcbaaw.7...@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
>|> Wentzler) writes:
>|>
>|> >Given a grid of squares, tile it with black and white tiles and make
>|> >the largest possible square so that no square contained in it has four
>|> >equally colored corners.
>Would the following be a recursive solution?
>0
>1
>Kinda small--let's double the size.
>00
>00
>Um ... no internal squares in these little squares so no 4 colored corners.
Note that the posting did not say INTERNAL squares. The whole square
also counts.
>Doubling again:
>0011
>0011
>1100
>1100
>Now your starting to worry. The internal squares have 4 (colored) corners.
>In general, the internal 0 (or the internal 1) has two 0 corners and two
>1 corners. So that's OK.
Note also that ALL subsquares must be considered, not just those that
are centered. The top-left 2x2 subsquare (and many more) has for
identical corners.
Torben Mogensen (tor...@diku.dk)
I am a terminator.
|> In article <israel.7...@unixg.ubc.ca>, isr...@unixg.ubc.ca (Robert B. Israel) writes:
|> |> In <rcbaaw.7...@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
|> |> Wentzler) writes:
|> |>
|> |> >Given a grid of squares, tile it with black and white tiles and make
|> |> >the largest possible square so that no square contained in it has four
|> |> >equally colored corners.
Never mind my previous post, but can such an n x n square be constructed
as a permutation of an n x n checkerboard?
Henry Choy
ch...@cs.usask.ca
C.E. Thompson
periodic boundary conditions. This brings the probabilisticly suggested largest
square down from about 17 to about 11, and so it might be more ammenable to
a brute-force-and-ignorance computational attack.
This version could be stated as: colour the tiles of the infinite plane square
lattice black and white, periodically with period N in both directions, such
that the only (orthogonally oriented) squares with all four corners the same
colour have both sides divisible by N.
Chris Thompson
JANET: ce...@uk.ac.cam.phx
Internet: ce...@phx.cam.ac.uk
Angelo Wentzler
>Henry Choy
>ch...@cs.usask.ca
Not all of them. There is only one 2x2 square that can be constructed from
a 2x2 checkerboard. Manually (my search program is at home) I found some
squares with the same property for the smaller sizes. I have also added
some counterexamples.
solution checkerboard Counterexample
10 10 11
01 01 01
101 101 111
011 010 010
100 101 011
1010 1010 1111
0110 0101 0101
1001 1010 0110
0110 0101 1100
For such solutions the following holds:
odd dimension: #black=#white+1
even dimension: #black=#white
So "balanced squares" would be a good name.
Note that a balanced square doesn't necessarily have two white and two black
corners.
In the small example each solution is derived from the previous one, but
I don't think that's necessary. You could make a balanced square from an
unbalanced smaller one. Just mirror the 3x3 to get an example.
Still, could the following be true?
Any balanced NxN square must contain at least one balanced ixi subsquare for
each 1<i<N
If this were true, then the same approach for normal squares would be
possible: just take a 2x2 balanced square (*the* 2x2 balanced square) and
just keep expanding it to obtain one for any dimension (up to a certain
limit...)
Because if the above holds, those balanced ixi subsquares in particular will
contain balanced subsquares too, etc.
Could make a nice subset of the correct solutions...
Angelo Wentzler
C.E. Thompson
(Torben AEgidius Mogensen) writes:
|> ce...@cus.cam.ac.uk (C.E. Thompson) writes:
|>
|> >It occured to me that one could put more constraints on the problem by using
|> >periodic boundary conditions. This brings the probabilisticly suggested largest
|> >square down from about 17 to about 11, and so it might be more ammenable to
|> >a brute-force-and-ignorance computational attack.
|> >
|> >This version could be stated as: colour the tiles of the infinite plane square
|> >lattice black and white, periodically with period N in both directions, such
|> >that the only (orthogonally oriented) squares with all four corners the same
|> >colour have both sides divisible by N.
|>
|> is a bit on the low side. But the suggestion sounds interesting.
My first reaction to this was to point out that the "periodic boundary
conditions" version is really more restrictive -- in term of the original
problem one is demanding that i x (N-i) rectangles ("wrap-round squares")
have their 4 corners not all the same, as well as the i x i squares, for
1 <= i <= N-1. Thus the N = 12 solution that Robert Israel posted:
bb
||
000011011111
011010010101
001100110011
010110100110
010100101010
011001100101
101101001100
100101010110
110011010010
a-> 101010011001 <-a
a-> 110011001011 <-a
100110100101
||
bb
has several wrap-round squares (e.g. the 1x11 rectangles marked a and b)
which violate the stronger condition.
But I then noticed, to my considerable astonishment, that Robert Israel's
later N = 13 solution:
0001101010110
0101011000011
1100001101110
0110101011000
0101100001101
0000110101011
1011101100001
0110000110111
0011010101100
1010110000110
1000011011101
1101110110000
1011000011010
*does* satisfy the stronger condition, having no i x (13-i) rectangles with
four corners the same. Unless this is a consequence of his search strategy,
there is something very odd going on.
The probabilistic argument I had in mind, following Torben Morgensen's
original one, involves assuming that the probability of each sub-square
violating the conditions is 7/8, independently of the others. For N=13 there
are 650 regular sub-squares (giving Torben's estimate of 2^169*(7/8)^650 =
1.511e13 solutions) and another 364 wrap-round ones, giving an estimate of
2^169*(7/8)^1014 = 1.175e-8 solutions. So the undoubted existence of at
least one solution suggests that the assumption of independence was not
a very good one!
Torben AEgidius Mogensen
>It occured to me that one could put more constraints on the problem by using
>periodic boundary conditions. This brings the probabilisticly suggested largest
>square down from about 17 to about 11, and so it might be more ammenable to
>a brute-force-and-ignorance computational attack.
>
>This version could be stated as: colour the tiles of the infinite plane square
>lattice black and white, periodically with period N in both directions, such
>that the only (orthogonally oriented) squares with all four corners the same
>colour have both sides divisible by N.
Well, since someone already posted a 13x13 solution, an estimate of 11
is a bit on the low side. But the suggestion sounds interesting.
Torben Mogensen (tor...@diku.dk)
Robert B. Israel
>But I then noticed, to my considerable astonishment, that Robert Israel's
>later N = 13 solution:
> 0001101010110
> 0101011000011
> 1100001101110
> 0110101011000
> 0101100001101
> 0000110101011
> 1011101100001
> 0110000110111
> 0011010101100
> 1010110000110
> 1000011011101
> 1101110110000
> 1011000011010
>*does* satisfy the stronger condition, having no i x (13-i) rectangles with
>four corners the same. Unless this is a consequence of his search strategy,
>there is something very odd going on.
As a matter of fact, there *is* something odd going on. A close look at
this solution shows that all the rows are cyclic permutations of
001101a101100, where "a" is either 0 or 1, each row being displaced 5
places to the left from the previous one. If you write one of these
13-tuples as <c_i>_{i=0..12}, it satisfies the condition that for all
i and 1 <= j <= 12, c_i, c_{i+j}, c_{i+5j} and c_{i+6j} are not all the
same (considering the subscripts mod 13). Thus such a 13-tuple generates
a square that works (with periodic boundary condition). The only 13-tuples
for which this works are these two and those obtained from them by cyclic
permutation and interchanging 1 and 0. I also tried shifts other than 5
(so for some b, 1<=b<=12, you want c_i,c_{i+j},c_{i+bj} and c_{i+(b+1)j}
never to be all the same). No more examples except for b=8 (which is
equivalent to b=5 by left<->right symmetry). Unfortunately, there are no
14-, 15-, 16- or 17-tuples with the analogous properties either.
I don't think that my search strategy has any inherent bias towards
solutions with any particular regularity or periodicity. I tried running
the 13 x 13 square again, with the following result:
1011010011010
0001111010110
0111001000011
1100011101010
1001010100111
0101110001101
0000100111011
1010111100001
0110010110101
0011001101100
1110101000110
1000001011101
1101100110000
If there's structure here, it's certainly more subtle than last time.
I haven't checked whether this satisfies the periodic boundary condition.
C.E. Thompson
|> this solution shows that all the rows are cyclic permutations of
|> 001101a101100, where "a" is either 0 or 1, each row being displaced 5
|> places to the left from the previous one. If you write one of these
|> 13-tuples as <c_i>_{i=0..12}, it satisfies the condition that for all
|> i and 1 <= j <= 12, c_i, c_{i+j}, c_{i+5j} and c_{i+6j} are not all the
|> same (considering the subscripts mod 13). Thus such a 13-tuple generates
|> a square that works (with periodic boundary condition). The only 13-tuples
|> for which this works are these two and those obtained from them by cyclic
|> permutation and interchanging 1 and 0. I also tried shifts other than 5
|> (so for some b, 1<=b<=12, you want c_i,c_{i+j},c_{i+bj} and c_{i+(b+1)j}
|> never to be all the same). No more examples except for b=8 (which is
|> equivalent to b=5 by left<->right symmetry). Unfortunately, there are no
|> 14-, 15-, 16- or 17-tuples with the analogous properties either.
It really looks as thought there ought to be some significance in the fact
that 001101a101100 is the pattern of quadratic residues mod 13 (a at the
point 0 mod 13), and in the fact that 5 and 8 are the square roots of -1
mod 13. But naive attempts to use the same rules for larger primes don't
work. (They do work for N=5, 01a10 shifted 2 for each new row.)
|> I don't think that my search strategy has any inherent bias towards
|> solutions with any particular regularity or periodicity. I tried running
|> the 13 x 13 square again, with the following result:
|>
|> 1011010011010
|> 0001111010110
|> 0111001000011
|> 1100011101010
|> 1001010100111
|> 0101110001101
|> 0000100111011
|> 1010111100001
|> 0110010110101
|> 0011001101100
|> 111010*000110
|> 1000001011101
|> 1101100110000
|>
|> If there's structure here, it's certainly more subtle than last time.
|> I haven't checked whether this satisfies the periodic boundary condition.
Not quite. But if the 1 at the point which I have taken the liberty of
marking with a * is replaced by a 0, then it does satisfy the stronger
periodic constraints. This rather suggests that most (all?) 13x13 solutions
of the weaker problem are "not far" from a solution of the stronger one.