Black-White Grid coluring without cycles
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
(I am assuming this is a known question but can't find the right terminology)
Given a $NtimesN$ grid, colour some of the squares black so that there are no cycles in the "graph". For example, this is a valid 3x3 coloring
@@@
@
@@@
and this is not:
@@@
@@
@
What is the largest (most black squares) for $NtimesN$? It is clearly 3 for 2x2 and 7 for 3x3, but a general formula is not apparent. Even a good algorithm is not obvious.
Here is how to get 72 for 10x10:
@ @@@@@@@@
@@ @ @ @ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @ @ @ @
@@@@@@@@@@
Which shows why this might be tricky, since I could not find (yet) a way to turn this into a regular construction.
Thanks, Joseph
graph-theory coloring
asked Sep 4 at 9:29
pepster
764
add a comment |Â
up vote
4
down vote
favorite
(I am assuming this is a known question but can't find the right terminology)
Given a $NtimesN$ grid, colour some of the squares black so that there are no cycles in the "graph". For example, this is a valid 3x3 coloring
@@@
@
@@@
and this is not:
@@@
@@
@
What is the largest (most black squares) for $NtimesN$? It is clearly 3 for 2x2 and 7 for 3x3, but a general formula is not apparent. Even a good algorithm is not obvious.
Here is how to get 72 for 10x10:
@ @@@@@@@@
@@ @ @ @ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @ @ @ @
@@@@@@@@@@
Which shows why this might be tricky, since I could not find (yet) a way to turn this into a regular construction.
Thanks, Joseph
graph-theory coloring
asked Sep 4 at 9:29
pepster
764
I don't know whether it's optimal, but it seems to me that zig-zagging gives a pretty decent result. For even $N$ we get $frac N2(N+1)$ and for odd $N$ we get $N + fracN-12(N+1)$.
– Arthur
Sep 4 at 9:33
decent or not, I am asking about the maximum. For example, I suspect that for 10x10 the answer is 72, but can't find a proof or argument why this is the maximum.
– pepster
Sep 4 at 9:37
How did you get 72 for 10 by 10? Best I can do is 69.
– Mike Earnest
Sep 4 at 14:32
1
I can also only get 69 (without trying for too long) but if 72 is possible then my answer shows that it's the maximum.
– Misha Lavrov
Sep 4 at 18:25
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
(I am assuming this is a known question but can't find the right terminology)
Given a $NtimesN$ grid, colour some of the squares black so that there are no cycles in the "graph". For example, this is a valid 3x3 coloring
@@@
@
@@@
and this is not:
@@@
@@
@
What is the largest (most black squares) for $NtimesN$? It is clearly 3 for 2x2 and 7 for 3x3, but a general formula is not apparent. Even a good algorithm is not obvious.
Here is how to get 72 for 10x10:
@ @@@@@@@@
@@ @ @ @ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @ @ @ @
@@@@@@@@@@
Which shows why this might be tricky, since I could not find (yet) a way to turn this into a regular construction.
Thanks, Joseph
graph-theory coloring
asked Sep 4 at 9:29
pepster
764
(I am assuming this is a known question but can't find the right terminology)
Given a $NtimesN$ grid, colour some of the squares black so that there are no cycles in the "graph". For example, this is a valid 3x3 coloring
@@@
@
@@@
and this is not:
@@@
@@
@
What is the largest (most black squares) for $NtimesN$? It is clearly 3 for 2x2 and 7 for 3x3, but a general formula is not apparent. Even a good algorithm is not obvious.
Here is how to get 72 for 10x10:
@ @@@@@@@@
@@ @ @ @ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @ @ @ @
@@@@@@@@@@
Which shows why this might be tricky, since I could not find (yet) a way to turn this into a regular construction.
Thanks, Joseph
graph-theory coloring
graph-theory coloring
asked Sep 4 at 9:29
pepster
764
asked Sep 4 at 9:29
pepster
764
edited Sep 4 at 19:58
asked Sep 4 at 9:29
pepster
764
asked Sep 4 at 9:29
pepster
764
asked Sep 4 at 9:29
pepster
764
764
I don't know whether it's optimal, but it seems to me that zig-zagging gives a pretty decent result. For even $N$ we get $frac N2(N+1)$ and for odd $N$ we get $N + fracN-12(N+1)$.
– Arthur
Sep 4 at 9:33
decent or not, I am asking about the maximum. For example, I suspect that for 10x10 the answer is 72, but can't find a proof or argument why this is the maximum.
– pepster
Sep 4 at 9:37
How did you get 72 for 10 by 10? Best I can do is 69.
– Mike Earnest
Sep 4 at 14:32
1
I can also only get 69 (without trying for too long) but if 72 is possible then my answer shows that it's the maximum.
– Misha Lavrov
Sep 4 at 18:25
add a comment |Â
I don't know whether it's optimal, but it seems to me that zig-zagging gives a pretty decent result. For even $N$ we get $frac N2(N+1)$ and for odd $N$ we get $N + fracN-12(N+1)$.
– Arthur
Sep 4 at 9:33
decent or not, I am asking about the maximum. For example, I suspect that for 10x10 the answer is 72, but can't find a proof or argument why this is the maximum.
– pepster
Sep 4 at 9:37
How did you get 72 for 10 by 10? Best I can do is 69.
– Mike Earnest
Sep 4 at 14:32
1
I can also only get 69 (without trying for too long) but if 72 is possible then my answer shows that it's the maximum.
– Misha Lavrov
Sep 4 at 18:25
I don't know whether it's optimal, but it seems to me that zig-zagging gives a pretty decent result. For even $N$ we get $frac N2(N+1)$ and for odd $N$ we get $N + fracN-12(N+1)$.
– Arthur
Sep 4 at 9:33
I don't know whether it's optimal, but it seems to me that zig-zagging gives a pretty decent result. For even $N$ we get $frac N2(N+1)$ and for odd $N$ we get $N + fracN-12(N+1)$.
– Arthur
Sep 4 at 9:33
decent or not, I am asking about the maximum. For example, I suspect that for 10x10 the answer is 72, but can't find a proof or argument why this is the maximum.
– pepster
Sep 4 at 9:37
decent or not, I am asking about the maximum. For example, I suspect that for 10x10 the answer is 72, but can't find a proof or argument why this is the maximum.
– pepster
Sep 4 at 9:37
How did you get 72 for 10 by 10? Best I can do is 69.
– Mike Earnest
Sep 4 at 14:32
How did you get 72 for 10 by 10? Best I can do is 69.
– Mike Earnest
Sep 4 at 14:32
1
1
I can also only get 69 (without trying for too long) but if 72 is possible then my answer shows that it's the maximum.
– Misha Lavrov
Sep 4 at 18:25
I can also only get 69 (without trying for too long) but if 72 is possible then my answer shows that it's the maximum.
– Misha Lavrov
Sep 4 at 18:25
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
There is an upper bound of $leftlfloorfrac23(N^2+N-1)rightrfloor$ which is tight for certain values of $N$.
If there are $B$ black squares, they have $4B$ sides. Of these, we subtract the ones that are along the sides of the grid: there are at most $4N-1$ of these (not $4N$ because then we'd get a cycle around the grid's boundary). Because there are no cycles, there are at most $2(B-1)$ places where two black squares are adjacent (this is the number of edges in a tree).
So the remaining $ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ sides correspond to boundaries between a black square and a white square.
On the other hand, there are at most $4(N^2-B)-1$ such boundaries, because each one meets one side of a white square (and at least one white square touches the side of the grid). So we have
$$
2B - 4N + 3 le 4(N^2-B) - 1
$$
which we can solve to get $B le frac23(N^2+N-1)$.
I can match this upper bound when $N equiv 4 pmod 6$ (in which case the bound with the floor included is $frac23(N^2+N-2)$). In that case, the $10 times 10$ construction generalizes to repeating the following blocks of height $6$:
@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @
except removing the first row of the top block and the last row of the bottom block. (The pattern can be extended horizontally to any even length, including $N$.)
We could of course count the black squares manually, but the fact that this construction has $frac23(N^2+N-2)$ black squares also follows by going through the proof above: this construction will have $2(B-2)$ black-square to black-square boundaries, since there are $2$ connected components, and of the $4N$ sides of the grid, all but $2$ border black squares. This lets us solve for $B$.
answered Sep 4 at 18:18
Misha Lavrov
38k55093
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
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
There is an upper bound of $leftlfloorfrac23(N^2+N-1)rightrfloor$ which is tight for certain values of $N$.
If there are $B$ black squares, they have $4B$ sides. Of these, we subtract the ones that are along the sides of the grid: there are at most $4N-1$ of these (not $4N$ because then we'd get a cycle around the grid's boundary). Because there are no cycles, there are at most $2(B-1)$ places where two black squares are adjacent (this is the number of edges in a tree).
So the remaining $ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ sides correspond to boundaries between a black square and a white square.
On the other hand, there are at most $4(N^2-B)-1$ such boundaries, because each one meets one side of a white square (and at least one white square touches the side of the grid). So we have
$$
2B - 4N + 3 le 4(N^2-B) - 1
$$
which we can solve to get $B le frac23(N^2+N-1)$.
I can match this upper bound when $N equiv 4 pmod 6$ (in which case the bound with the floor included is $frac23(N^2+N-2)$). In that case, the $10 times 10$ construction generalizes to repeating the following blocks of height $6$:
@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @
except removing the first row of the top block and the last row of the bottom block. (The pattern can be extended horizontally to any even length, including $N$.)
We could of course count the black squares manually, but the fact that this construction has $frac23(N^2+N-2)$ black squares also follows by going through the proof above: this construction will have $2(B-2)$ black-square to black-square boundaries, since there are $2$ connected components, and of the $4N$ sides of the grid, all but $2$ border black squares. This lets us solve for $B$.
answered Sep 4 at 18:18
Misha Lavrov
38k55093
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
add a comment |Â
up vote
2
down vote
There is an upper bound of $leftlfloorfrac23(N^2+N-1)rightrfloor$ which is tight for certain values of $N$.
If there are $B$ black squares, they have $4B$ sides. Of these, we subtract the ones that are along the sides of the grid: there are at most $4N-1$ of these (not $4N$ because then we'd get a cycle around the grid's boundary). Because there are no cycles, there are at most $2(B-1)$ places where two black squares are adjacent (this is the number of edges in a tree).
So the remaining $ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ sides correspond to boundaries between a black square and a white square.
On the other hand, there are at most $4(N^2-B)-1$ such boundaries, because each one meets one side of a white square (and at least one white square touches the side of the grid). So we have
$$
2B - 4N + 3 le 4(N^2-B) - 1
$$
which we can solve to get $B le frac23(N^2+N-1)$.
I can match this upper bound when $N equiv 4 pmod 6$ (in which case the bound with the floor included is $frac23(N^2+N-2)$). In that case, the $10 times 10$ construction generalizes to repeating the following blocks of height $6$:
@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @
except removing the first row of the top block and the last row of the bottom block. (The pattern can be extended horizontally to any even length, including $N$.)
We could of course count the black squares manually, but the fact that this construction has $frac23(N^2+N-2)$ black squares also follows by going through the proof above: this construction will have $2(B-2)$ black-square to black-square boundaries, since there are $2$ connected components, and of the $4N$ sides of the grid, all but $2$ border black squares. This lets us solve for $B$.
answered Sep 4 at 18:18
Misha Lavrov
38k55093
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
add a comment |Â
up vote
2
down vote
up vote
2
down vote
There is an upper bound of $leftlfloorfrac23(N^2+N-1)rightrfloor$ which is tight for certain values of $N$.
If there are $B$ black squares, they have $4B$ sides. Of these, we subtract the ones that are along the sides of the grid: there are at most $4N-1$ of these (not $4N$ because then we'd get a cycle around the grid's boundary). Because there are no cycles, there are at most $2(B-1)$ places where two black squares are adjacent (this is the number of edges in a tree).
So the remaining $ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ sides correspond to boundaries between a black square and a white square.
On the other hand, there are at most $4(N^2-B)-1$ such boundaries, because each one meets one side of a white square (and at least one white square touches the side of the grid). So we have
$$
2B - 4N + 3 le 4(N^2-B) - 1
$$
which we can solve to get $B le frac23(N^2+N-1)$.
I can match this upper bound when $N equiv 4 pmod 6$ (in which case the bound with the floor included is $frac23(N^2+N-2)$). In that case, the $10 times 10$ construction generalizes to repeating the following blocks of height $6$:
@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @
except removing the first row of the top block and the last row of the bottom block. (The pattern can be extended horizontally to any even length, including $N$.)
We could of course count the black squares manually, but the fact that this construction has $frac23(N^2+N-2)$ black squares also follows by going through the proof above: this construction will have $2(B-2)$ black-square to black-square boundaries, since there are $2$ connected components, and of the $4N$ sides of the grid, all but $2$ border black squares. This lets us solve for $B$.
answered Sep 4 at 18:18
Misha Lavrov
38k55093
There is an upper bound of $leftlfloorfrac23(N^2+N-1)rightrfloor$ which is tight for certain values of $N$.
If there are $B$ black squares, they have $4B$ sides. Of these, we subtract the ones that are along the sides of the grid: there are at most $4N-1$ of these (not $4N$ because then we'd get a cycle around the grid's boundary). Because there are no cycles, there are at most $2(B-1)$ places where two black squares are adjacent (this is the number of edges in a tree).
So the remaining $ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ sides correspond to boundaries between a black square and a white square.
On the other hand, there are at most $4(N^2-B)-1$ such boundaries, because each one meets one side of a white square (and at least one white square touches the side of the grid). So we have
$$
2B - 4N + 3 le 4(N^2-B) - 1
$$
which we can solve to get $B le frac23(N^2+N-1)$.
I can match this upper bound when $N equiv 4 pmod 6$ (in which case the bound with the floor included is $frac23(N^2+N-2)$). In that case, the $10 times 10$ construction generalizes to repeating the following blocks of height $6$:
@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @
except removing the first row of the top block and the last row of the bottom block. (The pattern can be extended horizontally to any even length, including $N$.)
We could of course count the black squares manually, but the fact that this construction has $frac23(N^2+N-2)$ black squares also follows by going through the proof above: this construction will have $2(B-2)$ black-square to black-square boundaries, since there are $2$ connected components, and of the $4N$ sides of the grid, all but $2$ border black squares. This lets us solve for $B$.
answered Sep 4 at 18:18
Misha Lavrov
38k55093
edited Sep 4 at 20:38
answered Sep 4 at 18:18
Misha Lavrov
38k55093
answered Sep 4 at 18:18
Misha Lavrov
38k55093
answered Sep 4 at 18:18
Misha Lavrov
38k55093
38k55093
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
add a comment |Â
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
This is nice. I had an upper bound of $frac2(N^2 + N) - 13$, which is one more in some cases. Unfortunately it is probably not tight (gives 27 for 6x6, while It seems the the value is 26).
– pepster
Sep 4 at 19:38
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
I have change the lower-bound construction to show that it is tight for $N equiv 4 pmod 6$. Probably for other values of $N bmod 6$ there is a difference by $1$ or $2$, which can be found with more casework. (E.g., I'm sure we can show that when $N$ is even, there are at least $2$ white-edge or white-white boundaries, which improves the bound to $frac23(N^2+N)-1$ in such cases.)
– Misha Lavrov
Sep 4 at 20:41
add a comment |Â
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%2f2904832%2fblack-white-grid-coluring-without-cycles%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
I don't know whether it's optimal, but it seems to me that zig-zagging gives a pretty decent result. For even $N$ we get $frac N2(N+1)$ and for odd $N$ we get $N + fracN-12(N+1)$.
– Arthur
Sep 4 at 9:33
decent or not, I am asking about the maximum. For example, I suspect that for 10x10 the answer is 72, but can't find a proof or argument why this is the maximum.
– pepster
Sep 4 at 9:37
How did you get 72 for 10 by 10? Best I can do is 69.
– Mike Earnest
Sep 4 at 14:32
1
I can also only get 69 (without trying for too long) but if 72 is possible then my answer shows that it's the maximum.
– Misha Lavrov
Sep 4 at 18:25