Mixing
How many colors are needed to color an infinite grid so that no sqaure have the same color in all 4 vertexes? [duplicate]
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
This question already has an answer here:
Monochromatic squares in a colored plane
2 answers
Suppose on a 2 dimension infinite grid, all nodes, or equivalently, all $(p,q)$ points, where $p, q in mathbb Z$, need to be painted with a color.
Is there a way that, given enough kinds of paiting colors, e.g. $n$, all sqaures will have at least 2 colors? i.e we can avoid to have any square that all its 4 vertexes are painted in the same color?
Or... is this impossible?
combinatorics graph-theory recreational-mathematics coloring
edited Jul 21 at 14:19
Mike Pierce
11k93574
asked Jul 21 at 14:09
athos
70411236
marked as duplicate by Mostafa Ayaz, José Carlos Santos, Parcly Taxel, Taroccoesbrocco, max_zorn Jul 22 at 5:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
5
down vote
favorite
This question already has an answer here:
Monochromatic squares in a colored plane
2 answers
Suppose on a 2 dimension infinite grid, all nodes, or equivalently, all $(p,q)$ points, where $p, q in mathbb Z$, need to be painted with a color.
Is there a way that, given enough kinds of paiting colors, e.g. $n$, all sqaures will have at least 2 colors? i.e we can avoid to have any square that all its 4 vertexes are painted in the same color?
Or... is this impossible?
combinatorics graph-theory recreational-mathematics coloring
edited Jul 21 at 14:19
Mike Pierce
11k93574
asked Jul 21 at 14:09
athos
70411236
marked as duplicate by Mostafa Ayaz, José Carlos Santos, Parcly Taxel, Taroccoesbrocco, max_zorn Jul 22 at 5:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Do you mean all unit squares or all squares of any size?
– Ross Millikan
Jul 21 at 14:17
@RossMillikan of any size
– athos
Jul 21 at 14:18
Grid-aligned squares, or are angled squares also allowed (much more complicated)?
– Joffan
Jul 21 at 14:26
@Joffan I... I was just thinking about some puzzle to amuse myself... and found it's too far beyond my reach. Maybe you can choose either way?
– athos
Jul 21 at 14:28
1
relevant paper: cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf
– Joffan
Jul 21 at 15:30
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
This question already has an answer here:
Monochromatic squares in a colored plane
2 answers
Suppose on a 2 dimension infinite grid, all nodes, or equivalently, all $(p,q)$ points, where $p, q in mathbb Z$, need to be painted with a color.
Is there a way that, given enough kinds of paiting colors, e.g. $n$, all sqaures will have at least 2 colors? i.e we can avoid to have any square that all its 4 vertexes are painted in the same color?
Or... is this impossible?
combinatorics graph-theory recreational-mathematics coloring
edited Jul 21 at 14:19
Mike Pierce
11k93574
asked Jul 21 at 14:09
athos
70411236
This question already has an answer here:
Monochromatic squares in a colored plane
2 answers
Suppose on a 2 dimension infinite grid, all nodes, or equivalently, all $(p,q)$ points, where $p, q in mathbb Z$, need to be painted with a color.
Is there a way that, given enough kinds of paiting colors, e.g. $n$, all sqaures will have at least 2 colors? i.e we can avoid to have any square that all its 4 vertexes are painted in the same color?
Or... is this impossible?
This question already has an answer here:
Monochromatic squares in a colored plane
2 answers
combinatorics graph-theory recreational-mathematics coloring
edited Jul 21 at 14:19
Mike Pierce
11k93574
asked Jul 21 at 14:09
athos
70411236
edited Jul 21 at 14:19
Mike Pierce
11k93574
edited Jul 21 at 14:19
Mike Pierce
11k93574
edited Jul 21 at 14:19
Mike Pierce
11k93574
11k93574
asked Jul 21 at 14:09
athos
70411236
asked Jul 21 at 14:09
athos
70411236
asked Jul 21 at 14:09
athos
70411236
70411236
marked as duplicate by Mostafa Ayaz, José Carlos Santos, Parcly Taxel, Taroccoesbrocco, max_zorn Jul 22 at 5:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Mostafa Ayaz, José Carlos Santos, Parcly Taxel, Taroccoesbrocco, max_zorn Jul 22 at 5:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Do you mean all unit squares or all squares of any size?
– Ross Millikan
Jul 21 at 14:17
@RossMillikan of any size
– athos
Jul 21 at 14:18
Grid-aligned squares, or are angled squares also allowed (much more complicated)?
– Joffan
Jul 21 at 14:26
@Joffan I... I was just thinking about some puzzle to amuse myself... and found it's too far beyond my reach. Maybe you can choose either way?
– athos
Jul 21 at 14:28
1
relevant paper: cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf
– Joffan
Jul 21 at 15:30
add a comment |Â
Do you mean all unit squares or all squares of any size?
– Ross Millikan
Jul 21 at 14:17
@RossMillikan of any size
– athos
Jul 21 at 14:18
Grid-aligned squares, or are angled squares also allowed (much more complicated)?
– Joffan
Jul 21 at 14:26
@Joffan I... I was just thinking about some puzzle to amuse myself... and found it's too far beyond my reach. Maybe you can choose either way?
– athos
Jul 21 at 14:28
1
relevant paper: cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf
– Joffan
Jul 21 at 15:30
Do you mean all unit squares or all squares of any size?
– Ross Millikan
Jul 21 at 14:17
Do you mean all unit squares or all squares of any size?
– Ross Millikan
Jul 21 at 14:17
@RossMillikan of any size
– athos
Jul 21 at 14:18
@RossMillikan of any size
– athos
Jul 21 at 14:18
Grid-aligned squares, or are angled squares also allowed (much more complicated)?
– Joffan
Jul 21 at 14:26
Grid-aligned squares, or are angled squares also allowed (much more complicated)?
– Joffan
Jul 21 at 14:26
@Joffan I... I was just thinking about some puzzle to amuse myself... and found it's too far beyond my reach. Maybe you can choose either way?
– athos
Jul 21 at 14:28
@Joffan I... I was just thinking about some puzzle to amuse myself... and found it's too far beyond my reach. Maybe you can choose either way?
– athos
Jul 21 at 14:28
1
1
relevant paper: cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf
– Joffan
Jul 21 at 15:30
relevant paper: cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf
– Joffan
Jul 21 at 15:30
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Solution for rectangles (now removed from question): In an infinite grid, you require an infinite number of colours. See the closing note in Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle? giving the size of a grid required to produce such a rectangle for $n$ colours:
For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $nn+1 choose 2+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.
Work on mono squares:
While the numbers are too big for comfortable imagination, these notes from Gasarch (link) gives a direction to infer the existence of a monochrome grid-aligned square in a sufficiently large 2- or 3-colored grid.
One of the key parts of the proof in that paper requires a rather large grid to guarantee the existence of a mono-colored $L$ (three points of the same colour in the form of an $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). I wanted to improve on this, at least for two colours and I think the process can apply for more:
Consider the top left to bottom right diagonal of a two-coloured $ntimes n$ grid.
If there are three regularly spaced points of the same colour on this diagonal, there is a mono $L$ in the grid. Proof: Consider the points that would form an $L$ with each possible pairing of these three points. If one of these is the relevant colour, that is a mono $L$. If all three are the opposite colour, they form a mono $L$ in that opposite colour.
How long a diagonal do we need to force three regular-spaced points of the same colour? Experimentally the answer is $9$, forced from the following initial patterns (shown red):
$mathtt colorredOOXOOXX?$
$mathtt colorredOOXXOOX?X$
$mathtt colorredOXOOXOXX?$
$mathtt colorredOXOXXOXO?$
$mathtt colorredOXXOOXXO?$
Where in each case the $mathtt?$ creates a regularly-spaced triplet whether filled with $mathttO$ or $mathttX$.
Thus any 2-coloured $9times 9$ grid contains a mono $L$, improving from the above paper's requirement for a $1539times 1539$ grid for this condition.
To force a mono-$L$ in a three-coloured grid by the same technique you would thus need $10$ regular-spaced points on the diagonal, creating a sparse lower-half grid of a suitable size to force an $L$ in the remaining two colours. I'm not sure how big this would be but again it should be lower than the corresponding grid size in the paper ($approx 3^3^34$).
Another observation: the diagonal sequences $mathtt OOXOO$, $mathtt OOXXOO$, or $mathtt OXOOXO$ will also produce a mono $L$ due to the pairs of matched colours at the same spacing. Effectively the three evenly-spaced matching colours is a special case of these where the central point does double duty to left and right. Thus the minimum diagonal length to guarantee a mono $L$ comes down to $8$:
$mathtt colorredOOXOXX?$
$mathtt colorredOOXXOXO?$
$mathtt colorredOXOOXX?$
$mathtt colorredOXOXXOO?$
$mathtt colorredOXXOO?X$
Some references for solved parts of this problem:
On Monochromatic Subsets Of A Rectangular Grid - a $5times 5$ 2-coloured grid must have a mono $L$.
Extremal binary matrices without constant
2-squares - a $15times 14$ 2-coloured grid must have a mono square
answered Jul 21 at 14:15
Joffan
31.8k43169
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Solution for rectangles (now removed from question): In an infinite grid, you require an infinite number of colours. See the closing note in Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle? giving the size of a grid required to produce such a rectangle for $n$ colours:
For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $nn+1 choose 2+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.
Work on mono squares:
While the numbers are too big for comfortable imagination, these notes from Gasarch (link) gives a direction to infer the existence of a monochrome grid-aligned square in a sufficiently large 2- or 3-colored grid.
One of the key parts of the proof in that paper requires a rather large grid to guarantee the existence of a mono-colored $L$ (three points of the same colour in the form of an $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). I wanted to improve on this, at least for two colours and I think the process can apply for more:
Consider the top left to bottom right diagonal of a two-coloured $ntimes n$ grid.
If there are three regularly spaced points of the same colour on this diagonal, there is a mono $L$ in the grid. Proof: Consider the points that would form an $L$ with each possible pairing of these three points. If one of these is the relevant colour, that is a mono $L$. If all three are the opposite colour, they form a mono $L$ in that opposite colour.
How long a diagonal do we need to force three regular-spaced points of the same colour? Experimentally the answer is $9$, forced from the following initial patterns (shown red):
$mathtt colorredOOXOOXX?$
$mathtt colorredOOXXOOX?X$
$mathtt colorredOXOOXOXX?$
$mathtt colorredOXOXXOXO?$
$mathtt colorredOXXOOXXO?$
Where in each case the $mathtt?$ creates a regularly-spaced triplet whether filled with $mathttO$ or $mathttX$.
Thus any 2-coloured $9times 9$ grid contains a mono $L$, improving from the above paper's requirement for a $1539times 1539$ grid for this condition.
To force a mono-$L$ in a three-coloured grid by the same technique you would thus need $10$ regular-spaced points on the diagonal, creating a sparse lower-half grid of a suitable size to force an $L$ in the remaining two colours. I'm not sure how big this would be but again it should be lower than the corresponding grid size in the paper ($approx 3^3^34$).
Another observation: the diagonal sequences $mathtt OOXOO$, $mathtt OOXXOO$, or $mathtt OXOOXO$ will also produce a mono $L$ due to the pairs of matched colours at the same spacing. Effectively the three evenly-spaced matching colours is a special case of these where the central point does double duty to left and right. Thus the minimum diagonal length to guarantee a mono $L$ comes down to $8$:
$mathtt colorredOOXOXX?$
$mathtt colorredOOXXOXO?$
$mathtt colorredOXOOXX?$
$mathtt colorredOXOXXOO?$
$mathtt colorredOXXOO?X$
Some references for solved parts of this problem:
On Monochromatic Subsets Of A Rectangular Grid - a $5times 5$ 2-coloured grid must have a mono $L$.
Extremal binary matrices without constant
2-squares - a $15times 14$ 2-coloured grid must have a mono square
answered Jul 21 at 14:15
Joffan
31.8k43169
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
add a comment |Â
up vote
2
down vote
Solution for rectangles (now removed from question): In an infinite grid, you require an infinite number of colours. See the closing note in Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle? giving the size of a grid required to produce such a rectangle for $n$ colours:
For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $nn+1 choose 2+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.
Work on mono squares:
While the numbers are too big for comfortable imagination, these notes from Gasarch (link) gives a direction to infer the existence of a monochrome grid-aligned square in a sufficiently large 2- or 3-colored grid.
One of the key parts of the proof in that paper requires a rather large grid to guarantee the existence of a mono-colored $L$ (three points of the same colour in the form of an $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). I wanted to improve on this, at least for two colours and I think the process can apply for more:
Consider the top left to bottom right diagonal of a two-coloured $ntimes n$ grid.
If there are three regularly spaced points of the same colour on this diagonal, there is a mono $L$ in the grid. Proof: Consider the points that would form an $L$ with each possible pairing of these three points. If one of these is the relevant colour, that is a mono $L$. If all three are the opposite colour, they form a mono $L$ in that opposite colour.
How long a diagonal do we need to force three regular-spaced points of the same colour? Experimentally the answer is $9$, forced from the following initial patterns (shown red):
$mathtt colorredOOXOOXX?$
$mathtt colorredOOXXOOX?X$
$mathtt colorredOXOOXOXX?$
$mathtt colorredOXOXXOXO?$
$mathtt colorredOXXOOXXO?$
Where in each case the $mathtt?$ creates a regularly-spaced triplet whether filled with $mathttO$ or $mathttX$.
Thus any 2-coloured $9times 9$ grid contains a mono $L$, improving from the above paper's requirement for a $1539times 1539$ grid for this condition.
To force a mono-$L$ in a three-coloured grid by the same technique you would thus need $10$ regular-spaced points on the diagonal, creating a sparse lower-half grid of a suitable size to force an $L$ in the remaining two colours. I'm not sure how big this would be but again it should be lower than the corresponding grid size in the paper ($approx 3^3^34$).
Another observation: the diagonal sequences $mathtt OOXOO$, $mathtt OOXXOO$, or $mathtt OXOOXO$ will also produce a mono $L$ due to the pairs of matched colours at the same spacing. Effectively the three evenly-spaced matching colours is a special case of these where the central point does double duty to left and right. Thus the minimum diagonal length to guarantee a mono $L$ comes down to $8$:
$mathtt colorredOOXOXX?$
$mathtt colorredOOXXOXO?$
$mathtt colorredOXOOXX?$
$mathtt colorredOXOXXOO?$
$mathtt colorredOXXOO?X$
Some references for solved parts of this problem:
On Monochromatic Subsets Of A Rectangular Grid - a $5times 5$ 2-coloured grid must have a mono $L$.
Extremal binary matrices without constant
2-squares - a $15times 14$ 2-coloured grid must have a mono square
answered Jul 21 at 14:15
Joffan
31.8k43169
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Solution for rectangles (now removed from question): In an infinite grid, you require an infinite number of colours. See the closing note in Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle? giving the size of a grid required to produce such a rectangle for $n$ colours:
For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $nn+1 choose 2+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.
Work on mono squares:
While the numbers are too big for comfortable imagination, these notes from Gasarch (link) gives a direction to infer the existence of a monochrome grid-aligned square in a sufficiently large 2- or 3-colored grid.
One of the key parts of the proof in that paper requires a rather large grid to guarantee the existence of a mono-colored $L$ (three points of the same colour in the form of an $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). I wanted to improve on this, at least for two colours and I think the process can apply for more:
Consider the top left to bottom right diagonal of a two-coloured $ntimes n$ grid.
If there are three regularly spaced points of the same colour on this diagonal, there is a mono $L$ in the grid. Proof: Consider the points that would form an $L$ with each possible pairing of these three points. If one of these is the relevant colour, that is a mono $L$. If all three are the opposite colour, they form a mono $L$ in that opposite colour.
How long a diagonal do we need to force three regular-spaced points of the same colour? Experimentally the answer is $9$, forced from the following initial patterns (shown red):
$mathtt colorredOOXOOXX?$
$mathtt colorredOOXXOOX?X$
$mathtt colorredOXOOXOXX?$
$mathtt colorredOXOXXOXO?$
$mathtt colorredOXXOOXXO?$
Where in each case the $mathtt?$ creates a regularly-spaced triplet whether filled with $mathttO$ or $mathttX$.
Thus any 2-coloured $9times 9$ grid contains a mono $L$, improving from the above paper's requirement for a $1539times 1539$ grid for this condition.
To force a mono-$L$ in a three-coloured grid by the same technique you would thus need $10$ regular-spaced points on the diagonal, creating a sparse lower-half grid of a suitable size to force an $L$ in the remaining two colours. I'm not sure how big this would be but again it should be lower than the corresponding grid size in the paper ($approx 3^3^34$).
Another observation: the diagonal sequences $mathtt OOXOO$, $mathtt OOXXOO$, or $mathtt OXOOXO$ will also produce a mono $L$ due to the pairs of matched colours at the same spacing. Effectively the three evenly-spaced matching colours is a special case of these where the central point does double duty to left and right. Thus the minimum diagonal length to guarantee a mono $L$ comes down to $8$:
$mathtt colorredOOXOXX?$
$mathtt colorredOOXXOXO?$
$mathtt colorredOXOOXX?$
$mathtt colorredOXOXXOO?$
$mathtt colorredOXXOO?X$
Some references for solved parts of this problem:
On Monochromatic Subsets Of A Rectangular Grid - a $5times 5$ 2-coloured grid must have a mono $L$.
Extremal binary matrices without constant
2-squares - a $15times 14$ 2-coloured grid must have a mono square
answered Jul 21 at 14:15
Joffan
31.8k43169
Solution for rectangles (now removed from question): In an infinite grid, you require an infinite number of colours. See the closing note in Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle? giving the size of a grid required to produce such a rectangle for $n$ colours:
For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $nn+1 choose 2+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.
Work on mono squares:
While the numbers are too big for comfortable imagination, these notes from Gasarch (link) gives a direction to infer the existence of a monochrome grid-aligned square in a sufficiently large 2- or 3-colored grid.
One of the key parts of the proof in that paper requires a rather large grid to guarantee the existence of a mono-colored $L$ (three points of the same colour in the form of an $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). I wanted to improve on this, at least for two colours and I think the process can apply for more:
Consider the top left to bottom right diagonal of a two-coloured $ntimes n$ grid.
If there are three regularly spaced points of the same colour on this diagonal, there is a mono $L$ in the grid. Proof: Consider the points that would form an $L$ with each possible pairing of these three points. If one of these is the relevant colour, that is a mono $L$. If all three are the opposite colour, they form a mono $L$ in that opposite colour.
How long a diagonal do we need to force three regular-spaced points of the same colour? Experimentally the answer is $9$, forced from the following initial patterns (shown red):
$mathtt colorredOOXOOXX?$
$mathtt colorredOOXXOOX?X$
$mathtt colorredOXOOXOXX?$
$mathtt colorredOXOXXOXO?$
$mathtt colorredOXXOOXXO?$
Where in each case the $mathtt?$ creates a regularly-spaced triplet whether filled with $mathttO$ or $mathttX$.
Thus any 2-coloured $9times 9$ grid contains a mono $L$, improving from the above paper's requirement for a $1539times 1539$ grid for this condition.
To force a mono-$L$ in a three-coloured grid by the same technique you would thus need $10$ regular-spaced points on the diagonal, creating a sparse lower-half grid of a suitable size to force an $L$ in the remaining two colours. I'm not sure how big this would be but again it should be lower than the corresponding grid size in the paper ($approx 3^3^34$).
Another observation: the diagonal sequences $mathtt OOXOO$, $mathtt OOXXOO$, or $mathtt OXOOXO$ will also produce a mono $L$ due to the pairs of matched colours at the same spacing. Effectively the three evenly-spaced matching colours is a special case of these where the central point does double duty to left and right. Thus the minimum diagonal length to guarantee a mono $L$ comes down to $8$:
$mathtt colorredOOXOXX?$
$mathtt colorredOOXXOXO?$
$mathtt colorredOXOOXX?$
$mathtt colorredOXOXXOO?$
$mathtt colorredOXXOO?X$
Some references for solved parts of this problem:
On Monochromatic Subsets Of A Rectangular Grid - a $5times 5$ 2-coloured grid must have a mono $L$.
Extremal binary matrices without constant
2-squares - a $15times 14$ 2-coloured grid must have a mono square
answered Jul 21 at 14:15
Joffan
31.8k43169
edited Jul 23 at 19:06
answered Jul 21 at 14:15
Joffan
31.8k43169
answered Jul 21 at 14:15
Joffan
31.8k43169
answered Jul 21 at 14:15
Joffan
31.8k43169
31.8k43169
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
add a comment |Â
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
OK, you have changed from rectangles to squares... I will think about this a bit more.
– Joffan
Jul 21 at 14:18
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
I'm sorry, my bad. I was thinking about square but somehow typed out a "rectangle".
– athos
Jul 21 at 14:22
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
@athos no problem... I 'm just thinking about how big a 2-coloured grid is required to force a grid-aligned square to start with.
– Joffan
Jul 21 at 14:58
add a comment |Â
Do you mean all unit squares or all squares of any size?
– Ross Millikan
Jul 21 at 14:17
@RossMillikan of any size
– athos
Jul 21 at 14:18
Grid-aligned squares, or are angled squares also allowed (much more complicated)?
– Joffan
Jul 21 at 14:26
@Joffan I... I was just thinking about some puzzle to amuse myself... and found it's too far beyond my reach. Maybe you can choose either way?
– athos
Jul 21 at 14:28
1
relevant paper: cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf
– Joffan
Jul 21 at 15:30