coloring 3x3 chessboard with two colors… The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)how many unique patterns exist for a $Ntimes N$ gridColorings of a $3times3$ chessboardCheckerboard coloring problemChessboard CombinatoricsProbability of $ 7$ white chessboard squares without neighboursCombinatorics arrangement on chessboardmaximum nonattacking black and white queens on infinite chessboardSimple chessboard exerciseThree knights on a 3x3 chess boardProblem in restricted 3 edge coloring$4times 4$ Chessboard ColoringsA computer screen shows a 98 × 98 chessboard, colored in the usual way.
Finding the path in a graph from A to B then back to A with a minimum of shared edges
How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time
What force causes entropy to increase?
He got a vote 80% that of Emmanuel Macron’s
Is there a writing software that you can sort scenes like slides in PowerPoint?
Wall plug outlet change
Is it ethical to upload a automatically generated paper to a non peer-reviewed site as part of a larger research?
Is above average number of years spent on PhD considered a red flag in future academia or industry positions?
What's the point in a preamp?
What information about me do stores get via my credit card?
Mortgage adviser recommends a longer term than necessary combined with overpayments
Why can't devices on different VLANs, but on the same subnet, communicate?
Do working physicists consider Newtonian mechanics to be "falsified"?
Segmentation fault output is suppressed when piping stdin into a function. Why?
How can I define good in a religion that claims no moral authority?
Arduino Pro Micro - switch off LEDs
How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?
What can I do if neighbor is blocking my solar panels intentionally?
Simulation of a banking system with an Account class in C++
How did passengers keep warm on sail ships?
Derivation tree not rendering
Do warforged have souls?
Did the new image of black hole confirm the general theory of relativity?
Make it rain characters
coloring 3x3 chessboard with two colors…
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)how many unique patterns exist for a $Ntimes N$ gridColorings of a $3times3$ chessboardCheckerboard coloring problemChessboard CombinatoricsProbability of $ 7$ white chessboard squares without neighboursCombinatorics arrangement on chessboardmaximum nonattacking black and white queens on infinite chessboardSimple chessboard exerciseThree knights on a 3x3 chess boardProblem in restricted 3 edge coloring$4times 4$ Chessboard ColoringsA computer screen shows a 98 × 98 chessboard, colored in the usual way.
$begingroup$
Consider a 3x3 chessboard with 9 elements. The elements are colored with black and white paints.
The task is to find the number of different chessboards of this type exist.
I don't know how to start with this problem....
combinatorics
$endgroup$
add a comment |
$begingroup$
Consider a 3x3 chessboard with 9 elements. The elements are colored with black and white paints.
The task is to find the number of different chessboards of this type exist.
I don't know how to start with this problem....
combinatorics
$endgroup$
1
$begingroup$
Does the orientation of the board matter? For instance, is the coloring that has a black square in the upper left corner and all the others squares white to be counted as different from the coloring that has a black square in the lower left corner and all the other squares white? Or are they to be counted as just one coloring, because the board can be rotated to turn one into the other?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:12
$begingroup$
Draw a shape! And try to color it. Check if anything is ambiguous for you in the problem statement.
$endgroup$
– hhsaffar
Dec 13 '13 at 23:12
$begingroup$
This MSE link shows a solution that takes symmetries into account.
$endgroup$
– Marko Riedel
Dec 13 '13 at 23:15
$begingroup$
HINT: If the orientation of the board does matter, you’re really just counting the number of ways of choosing a subset of the $9$ elements to be colored black. How many subsets are there?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:20
add a comment |
$begingroup$
Consider a 3x3 chessboard with 9 elements. The elements are colored with black and white paints.
The task is to find the number of different chessboards of this type exist.
I don't know how to start with this problem....
combinatorics
$endgroup$
Consider a 3x3 chessboard with 9 elements. The elements are colored with black and white paints.
The task is to find the number of different chessboards of this type exist.
I don't know how to start with this problem....
combinatorics
combinatorics
asked Dec 13 '13 at 23:09
user108696user108696
112
112
1
$begingroup$
Does the orientation of the board matter? For instance, is the coloring that has a black square in the upper left corner and all the others squares white to be counted as different from the coloring that has a black square in the lower left corner and all the other squares white? Or are they to be counted as just one coloring, because the board can be rotated to turn one into the other?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:12
$begingroup$
Draw a shape! And try to color it. Check if anything is ambiguous for you in the problem statement.
$endgroup$
– hhsaffar
Dec 13 '13 at 23:12
$begingroup$
This MSE link shows a solution that takes symmetries into account.
$endgroup$
– Marko Riedel
Dec 13 '13 at 23:15
$begingroup$
HINT: If the orientation of the board does matter, you’re really just counting the number of ways of choosing a subset of the $9$ elements to be colored black. How many subsets are there?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:20
add a comment |
1
$begingroup$
Does the orientation of the board matter? For instance, is the coloring that has a black square in the upper left corner and all the others squares white to be counted as different from the coloring that has a black square in the lower left corner and all the other squares white? Or are they to be counted as just one coloring, because the board can be rotated to turn one into the other?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:12
$begingroup$
Draw a shape! And try to color it. Check if anything is ambiguous for you in the problem statement.
$endgroup$
– hhsaffar
Dec 13 '13 at 23:12
$begingroup$
This MSE link shows a solution that takes symmetries into account.
$endgroup$
– Marko Riedel
Dec 13 '13 at 23:15
$begingroup$
HINT: If the orientation of the board does matter, you’re really just counting the number of ways of choosing a subset of the $9$ elements to be colored black. How many subsets are there?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:20
1
1
$begingroup$
Does the orientation of the board matter? For instance, is the coloring that has a black square in the upper left corner and all the others squares white to be counted as different from the coloring that has a black square in the lower left corner and all the other squares white? Or are they to be counted as just one coloring, because the board can be rotated to turn one into the other?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:12
$begingroup$
Does the orientation of the board matter? For instance, is the coloring that has a black square in the upper left corner and all the others squares white to be counted as different from the coloring that has a black square in the lower left corner and all the other squares white? Or are they to be counted as just one coloring, because the board can be rotated to turn one into the other?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:12
$begingroup$
Draw a shape! And try to color it. Check if anything is ambiguous for you in the problem statement.
$endgroup$
– hhsaffar
Dec 13 '13 at 23:12
$begingroup$
Draw a shape! And try to color it. Check if anything is ambiguous for you in the problem statement.
$endgroup$
– hhsaffar
Dec 13 '13 at 23:12
$begingroup$
This MSE link shows a solution that takes symmetries into account.
$endgroup$
– Marko Riedel
Dec 13 '13 at 23:15
$begingroup$
This MSE link shows a solution that takes symmetries into account.
$endgroup$
– Marko Riedel
Dec 13 '13 at 23:15
$begingroup$
HINT: If the orientation of the board does matter, you’re really just counting the number of ways of choosing a subset of the $9$ elements to be colored black. How many subsets are there?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:20
$begingroup$
HINT: If the orientation of the board does matter, you’re really just counting the number of ways of choosing a subset of the $9$ elements to be colored black. How many subsets are there?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:20
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Suppose that rotating them does not matter, then we have two colors for each square and
so a total of $2^9$ possibillities.
For the other case, (possibillities that can be made by rotation of another possibillity are considered the same) we can use group theory. I will asume here that the bottom of the board is just black. Because we have $4$ possible roations and no mirroring (because the bottom of the board is black) we get as symmetry group $C_4$, the cyclic group of order $4$. No we will check the orbis of the squares after rotations. This will give us the following:
So for the total possibillities we get (by The Counting Theorem):
$$
frac1sum_gin G |X^g| = \
frac1C_4 (1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= \
frac14(1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= 160.
$$
Where $X$ is the set of colourings of the chessboard and $X^g$ is the subset of $X$ consisting of those points which are left fixed by the element $g in G$.
So this will give us a total of $160$ chessboards,
If the back of the chessboard is also in account, for example see-through, please add this to the question. This will give the symmetric group $D_4$ and some extra possobillities, for if you want to work it out.
$endgroup$
add a comment |
$begingroup$
If you consider rotations and reflections to be the same.
Number of $ntimes n$ binary matrices under action of dihedral group of the square $D_4$.
http://oeis.org/A054247
$$a(n)=begincasesdfrac18left(2^n^2+2cdot2^n^2/4+3cdot2^n^2/2+2cdot2^(n^2+n)/2right) & n= 0pmod2 \
dfrac18left(2^n^2+2cdot2^(n^2+3)/4+2^(n^2+1)/2+4cdot2^(n^2+n)/2right)& n= 1pmod2endcases$$
beginalign*
a(3)&=,dfrac18left(2^3^2+2cdot2^(3^2+3)/4+2^(3^2+1)/2+4cdot2^(3^2+3)/2right)\
&=,dfrac18left(2^9+2cdot2^3+2^5+4cdot2^6right)=dfrac2^9+2^4+2^5+2^88=,quadlargecolorred102
endalign*
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f606031%2fcoloring-3x3-chessboard-with-two-colors%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose that rotating them does not matter, then we have two colors for each square and
so a total of $2^9$ possibillities.
For the other case, (possibillities that can be made by rotation of another possibillity are considered the same) we can use group theory. I will asume here that the bottom of the board is just black. Because we have $4$ possible roations and no mirroring (because the bottom of the board is black) we get as symmetry group $C_4$, the cyclic group of order $4$. No we will check the orbis of the squares after rotations. This will give us the following:
So for the total possibillities we get (by The Counting Theorem):
$$
frac1sum_gin G |X^g| = \
frac1C_4 (1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= \
frac14(1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= 160.
$$
Where $X$ is the set of colourings of the chessboard and $X^g$ is the subset of $X$ consisting of those points which are left fixed by the element $g in G$.
So this will give us a total of $160$ chessboards,
If the back of the chessboard is also in account, for example see-through, please add this to the question. This will give the symmetric group $D_4$ and some extra possobillities, for if you want to work it out.
$endgroup$
add a comment |
$begingroup$
Suppose that rotating them does not matter, then we have two colors for each square and
so a total of $2^9$ possibillities.
For the other case, (possibillities that can be made by rotation of another possibillity are considered the same) we can use group theory. I will asume here that the bottom of the board is just black. Because we have $4$ possible roations and no mirroring (because the bottom of the board is black) we get as symmetry group $C_4$, the cyclic group of order $4$. No we will check the orbis of the squares after rotations. This will give us the following:
So for the total possibillities we get (by The Counting Theorem):
$$
frac1sum_gin G |X^g| = \
frac1C_4 (1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= \
frac14(1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= 160.
$$
Where $X$ is the set of colourings of the chessboard and $X^g$ is the subset of $X$ consisting of those points which are left fixed by the element $g in G$.
So this will give us a total of $160$ chessboards,
If the back of the chessboard is also in account, for example see-through, please add this to the question. This will give the symmetric group $D_4$ and some extra possobillities, for if you want to work it out.
$endgroup$
add a comment |
$begingroup$
Suppose that rotating them does not matter, then we have two colors for each square and
so a total of $2^9$ possibillities.
For the other case, (possibillities that can be made by rotation of another possibillity are considered the same) we can use group theory. I will asume here that the bottom of the board is just black. Because we have $4$ possible roations and no mirroring (because the bottom of the board is black) we get as symmetry group $C_4$, the cyclic group of order $4$. No we will check the orbis of the squares after rotations. This will give us the following:
So for the total possibillities we get (by The Counting Theorem):
$$
frac1sum_gin G |X^g| = \
frac1C_4 (1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= \
frac14(1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= 160.
$$
Where $X$ is the set of colourings of the chessboard and $X^g$ is the subset of $X$ consisting of those points which are left fixed by the element $g in G$.
So this will give us a total of $160$ chessboards,
If the back of the chessboard is also in account, for example see-through, please add this to the question. This will give the symmetric group $D_4$ and some extra possobillities, for if you want to work it out.
$endgroup$
Suppose that rotating them does not matter, then we have two colors for each square and
so a total of $2^9$ possibillities.
For the other case, (possibillities that can be made by rotation of another possibillity are considered the same) we can use group theory. I will asume here that the bottom of the board is just black. Because we have $4$ possible roations and no mirroring (because the bottom of the board is black) we get as symmetry group $C_4$, the cyclic group of order $4$. No we will check the orbis of the squares after rotations. This will give us the following:
So for the total possibillities we get (by The Counting Theorem):
$$
frac1sum_gin G |X^g| = \
frac1C_4 (1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= \
frac14(1cdot 2^9 + 4 cdot 2^3 + 2 cdot 2^5+ 4 cdot 2^3)= 160.
$$
Where $X$ is the set of colourings of the chessboard and $X^g$ is the subset of $X$ consisting of those points which are left fixed by the element $g in G$.
So this will give us a total of $160$ chessboards,
If the back of the chessboard is also in account, for example see-through, please add this to the question. This will give the symmetric group $D_4$ and some extra possobillities, for if you want to work it out.
edited Dec 14 '13 at 0:54
answered Dec 14 '13 at 0:12
user112167user112167
1,2621715
1,2621715
add a comment |
add a comment |
$begingroup$
If you consider rotations and reflections to be the same.
Number of $ntimes n$ binary matrices under action of dihedral group of the square $D_4$.
http://oeis.org/A054247
$$a(n)=begincasesdfrac18left(2^n^2+2cdot2^n^2/4+3cdot2^n^2/2+2cdot2^(n^2+n)/2right) & n= 0pmod2 \
dfrac18left(2^n^2+2cdot2^(n^2+3)/4+2^(n^2+1)/2+4cdot2^(n^2+n)/2right)& n= 1pmod2endcases$$
beginalign*
a(3)&=,dfrac18left(2^3^2+2cdot2^(3^2+3)/4+2^(3^2+1)/2+4cdot2^(3^2+3)/2right)\
&=,dfrac18left(2^9+2cdot2^3+2^5+4cdot2^6right)=dfrac2^9+2^4+2^5+2^88=,quadlargecolorred102
endalign*
$endgroup$
add a comment |
$begingroup$
If you consider rotations and reflections to be the same.
Number of $ntimes n$ binary matrices under action of dihedral group of the square $D_4$.
http://oeis.org/A054247
$$a(n)=begincasesdfrac18left(2^n^2+2cdot2^n^2/4+3cdot2^n^2/2+2cdot2^(n^2+n)/2right) & n= 0pmod2 \
dfrac18left(2^n^2+2cdot2^(n^2+3)/4+2^(n^2+1)/2+4cdot2^(n^2+n)/2right)& n= 1pmod2endcases$$
beginalign*
a(3)&=,dfrac18left(2^3^2+2cdot2^(3^2+3)/4+2^(3^2+1)/2+4cdot2^(3^2+3)/2right)\
&=,dfrac18left(2^9+2cdot2^3+2^5+4cdot2^6right)=dfrac2^9+2^4+2^5+2^88=,quadlargecolorred102
endalign*
$endgroup$
add a comment |
$begingroup$
If you consider rotations and reflections to be the same.
Number of $ntimes n$ binary matrices under action of dihedral group of the square $D_4$.
http://oeis.org/A054247
$$a(n)=begincasesdfrac18left(2^n^2+2cdot2^n^2/4+3cdot2^n^2/2+2cdot2^(n^2+n)/2right) & n= 0pmod2 \
dfrac18left(2^n^2+2cdot2^(n^2+3)/4+2^(n^2+1)/2+4cdot2^(n^2+n)/2right)& n= 1pmod2endcases$$
beginalign*
a(3)&=,dfrac18left(2^3^2+2cdot2^(3^2+3)/4+2^(3^2+1)/2+4cdot2^(3^2+3)/2right)\
&=,dfrac18left(2^9+2cdot2^3+2^5+4cdot2^6right)=dfrac2^9+2^4+2^5+2^88=,quadlargecolorred102
endalign*
$endgroup$
If you consider rotations and reflections to be the same.
Number of $ntimes n$ binary matrices under action of dihedral group of the square $D_4$.
http://oeis.org/A054247
$$a(n)=begincasesdfrac18left(2^n^2+2cdot2^n^2/4+3cdot2^n^2/2+2cdot2^(n^2+n)/2right) & n= 0pmod2 \
dfrac18left(2^n^2+2cdot2^(n^2+3)/4+2^(n^2+1)/2+4cdot2^(n^2+n)/2right)& n= 1pmod2endcases$$
beginalign*
a(3)&=,dfrac18left(2^3^2+2cdot2^(3^2+3)/4+2^(3^2+1)/2+4cdot2^(3^2+3)/2right)\
&=,dfrac18left(2^9+2cdot2^3+2^5+4cdot2^6right)=dfrac2^9+2^4+2^5+2^88=,quadlargecolorred102
endalign*
answered Mar 25 at 5:34
D.MatthewD.Matthew
414
414
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f606031%2fcoloring-3x3-chessboard-with-two-colors%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Does the orientation of the board matter? For instance, is the coloring that has a black square in the upper left corner and all the others squares white to be counted as different from the coloring that has a black square in the lower left corner and all the other squares white? Or are they to be counted as just one coloring, because the board can be rotated to turn one into the other?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:12
$begingroup$
Draw a shape! And try to color it. Check if anything is ambiguous for you in the problem statement.
$endgroup$
– hhsaffar
Dec 13 '13 at 23:12
$begingroup$
This MSE link shows a solution that takes symmetries into account.
$endgroup$
– Marko Riedel
Dec 13 '13 at 23:15
$begingroup$
HINT: If the orientation of the board does matter, you’re really just counting the number of ways of choosing a subset of the $9$ elements to be colored black. How many subsets are there?
$endgroup$
– Brian M. Scott
Dec 13 '13 at 23:20