On a 2-dimensional Van der Waerden-like theorem on 2-coloured square grids
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let us consider a $ntimes n$ grid. We colour each point of the grid using two colours.
We say that a grid is bad is there exists a set of 4 points on the grid with same color which are the vertices a square whose sides are parallel to the sides of the grid.
A grid which is not bad is said to be good.
Example: let say we colour using Red (R) or Blue (B).
The $3times 3$ grid $beginmatrix R & B & Rcr B & R & B cr R & B & B endmatrix$ is good.
A theorem of Furstenberg and Weiss states that there exists $ngeq 0$ such that any $(n+1)times (n+1)$ grid is bad.
The natural question which arises is :
Question. What is the minimal value of $n$ ? In other words, what is the value of the unique integer such that there is a $ntimes n$ good grid, but there is no $(n+1)times (n+1)$ good grid ?
I don't know the answer, nor any estimate on the size of $n$. For the moment, the only method I coud think of to solve the problem is to use a computer.
The only small thing I know is that there is a $5times 5$ good grid, so $ngeq 5.$
For example, the following grid is good:
$$beginmatrix
R & R & R & R & Rcr
B & R & B & R & B cr
B & R & B & B & R cr
B & B & R & R & B cr
R & B & B & R & B
endmatrix$$
Thanks in advance for your answers!
combinatorics puzzle
asked Aug 18 at 0:02
GreginGre
1,27328
add a comment |Â
up vote
0
down vote
favorite
Let us consider a $ntimes n$ grid. We colour each point of the grid using two colours.
We say that a grid is bad is there exists a set of 4 points on the grid with same color which are the vertices a square whose sides are parallel to the sides of the grid.
A grid which is not bad is said to be good.
Example: let say we colour using Red (R) or Blue (B).
The $3times 3$ grid $beginmatrix R & B & Rcr B & R & B cr R & B & B endmatrix$ is good.
A theorem of Furstenberg and Weiss states that there exists $ngeq 0$ such that any $(n+1)times (n+1)$ grid is bad.
The natural question which arises is :
Question. What is the minimal value of $n$ ? In other words, what is the value of the unique integer such that there is a $ntimes n$ good grid, but there is no $(n+1)times (n+1)$ good grid ?
I don't know the answer, nor any estimate on the size of $n$. For the moment, the only method I coud think of to solve the problem is to use a computer.
The only small thing I know is that there is a $5times 5$ good grid, so $ngeq 5.$
For example, the following grid is good:
$$beginmatrix
R & R & R & R & Rcr
B & R & B & R & B cr
B & R & B & B & R cr
B & B & R & R & B cr
R & B & B & R & B
endmatrix$$
Thanks in advance for your answers!
combinatorics puzzle
asked Aug 18 at 0:02
GreginGre
1,27328
This question, Size of a 3-colored square grid to produce a monochrome rectangle, might be related.
– Peter Kagey
Aug 18 at 0:15
1
And this question on MathOverflow, The Problem about 2-coloring finite plane, says the answer is $n=14$. (That is, there is a good $14 times 14$ grid, but no good $15 times 15$ grid.)
– Peter Kagey
Aug 18 at 0:16
Thank you very much!
– GreginGre
Aug 18 at 7:35
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let us consider a $ntimes n$ grid. We colour each point of the grid using two colours.
We say that a grid is bad is there exists a set of 4 points on the grid with same color which are the vertices a square whose sides are parallel to the sides of the grid.
A grid which is not bad is said to be good.
Example: let say we colour using Red (R) or Blue (B).
The $3times 3$ grid $beginmatrix R & B & Rcr B & R & B cr R & B & B endmatrix$ is good.
A theorem of Furstenberg and Weiss states that there exists $ngeq 0$ such that any $(n+1)times (n+1)$ grid is bad.
The natural question which arises is :
Question. What is the minimal value of $n$ ? In other words, what is the value of the unique integer such that there is a $ntimes n$ good grid, but there is no $(n+1)times (n+1)$ good grid ?
I don't know the answer, nor any estimate on the size of $n$. For the moment, the only method I coud think of to solve the problem is to use a computer.
The only small thing I know is that there is a $5times 5$ good grid, so $ngeq 5.$
For example, the following grid is good:
$$beginmatrix
R & R & R & R & Rcr
B & R & B & R & B cr
B & R & B & B & R cr
B & B & R & R & B cr
R & B & B & R & B
endmatrix$$
Thanks in advance for your answers!
combinatorics puzzle
asked Aug 18 at 0:02
GreginGre
1,27328
Let us consider a $ntimes n$ grid. We colour each point of the grid using two colours.
We say that a grid is bad is there exists a set of 4 points on the grid with same color which are the vertices a square whose sides are parallel to the sides of the grid.
A grid which is not bad is said to be good.
Example: let say we colour using Red (R) or Blue (B).
The $3times 3$ grid $beginmatrix R & B & Rcr B & R & B cr R & B & B endmatrix$ is good.
A theorem of Furstenberg and Weiss states that there exists $ngeq 0$ such that any $(n+1)times (n+1)$ grid is bad.
The natural question which arises is :
Question. What is the minimal value of $n$ ? In other words, what is the value of the unique integer such that there is a $ntimes n$ good grid, but there is no $(n+1)times (n+1)$ good grid ?
I don't know the answer, nor any estimate on the size of $n$. For the moment, the only method I coud think of to solve the problem is to use a computer.
The only small thing I know is that there is a $5times 5$ good grid, so $ngeq 5.$
For example, the following grid is good:
$$beginmatrix
R & R & R & R & Rcr
B & R & B & R & B cr
B & R & B & B & R cr
B & B & R & R & B cr
R & B & B & R & B
endmatrix$$
Thanks in advance for your answers!
combinatorics puzzle
asked Aug 18 at 0:02
GreginGre
1,27328
asked Aug 18 at 0:02
GreginGre
1,27328
asked Aug 18 at 0:02
GreginGre
1,27328
asked Aug 18 at 0:02
GreginGre
1,27328
1,27328
This question, Size of a 3-colored square grid to produce a monochrome rectangle, might be related.
– Peter Kagey
Aug 18 at 0:15
1
And this question on MathOverflow, The Problem about 2-coloring finite plane, says the answer is $n=14$. (That is, there is a good $14 times 14$ grid, but no good $15 times 15$ grid.)
– Peter Kagey
Aug 18 at 0:16
Thank you very much!
– GreginGre
Aug 18 at 7:35
add a comment |Â
This question, Size of a 3-colored square grid to produce a monochrome rectangle, might be related.
– Peter Kagey
Aug 18 at 0:15
1
And this question on MathOverflow, The Problem about 2-coloring finite plane, says the answer is $n=14$. (That is, there is a good $14 times 14$ grid, but no good $15 times 15$ grid.)
– Peter Kagey
Aug 18 at 0:16
Thank you very much!
– GreginGre
Aug 18 at 7:35
This question, Size of a 3-colored square grid to produce a monochrome rectangle, might be related.
– Peter Kagey
Aug 18 at 0:15
This question, Size of a 3-colored square grid to produce a monochrome rectangle, might be related.
– Peter Kagey
Aug 18 at 0:15
1
1
And this question on MathOverflow, The Problem about 2-coloring finite plane, says the answer is $n=14$. (That is, there is a good $14 times 14$ grid, but no good $15 times 15$ grid.)
– Peter Kagey
Aug 18 at 0:16
And this question on MathOverflow, The Problem about 2-coloring finite plane, says the answer is $n=14$. (That is, there is a good $14 times 14$ grid, but no good $15 times 15$ grid.)
– Peter Kagey
Aug 18 at 0:16
Thank you very much!
– GreginGre
Aug 18 at 7:35
Thank you very much!
– GreginGre
Aug 18 at 7:35
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2886297%2fon-a-2-dimensional-van-der-waerden-like-theorem-on-2-coloured-square-grids%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
This question, Size of a 3-colored square grid to produce a monochrome rectangle, might be related.
– Peter Kagey
Aug 18 at 0:15
1
And this question on MathOverflow, The Problem about 2-coloring finite plane, says the answer is $n=14$. (That is, there is a good $14 times 14$ grid, but no good $15 times 15$ grid.)
– Peter Kagey
Aug 18 at 0:16
Thank you very much!
– GreginGre
Aug 18 at 7:35