The flag colouring problem
Ok so I came across this question. It goes something like this :
A new flag is to be designed with 6 vertical stripes using all 4 colours. In how many ways can this be done so that no 2 adjacent stripes have the same colour and it is given that we have to use all the 4 colours for 4 stripes ( we cannot use less than 4 colours to colour the stripes. For example, for a given set of colours {1,2,3,4}, the solution cannot be like 1,2,1,2,1,2). I've been struggling to come up with a solution. Can someone show me how it is done?
combinatorics permutations
asked Nov 30 at 20:26
sayantan dasgupta
102
add a comment |
Ok so I came across this question. It goes something like this :
A new flag is to be designed with 6 vertical stripes using all 4 colours. In how many ways can this be done so that no 2 adjacent stripes have the same colour and it is given that we have to use all the 4 colours for 4 stripes ( we cannot use less than 4 colours to colour the stripes. For example, for a given set of colours {1,2,3,4}, the solution cannot be like 1,2,1,2,1,2). I've been struggling to come up with a solution. Can someone show me how it is done?
combinatorics permutations
asked Nov 30 at 20:26
sayantan dasgupta
102
"all four colors for four strips". Does that mean you can't do 1,2,3,4,3,2 because the middle four and the last four don't have the color 1? If so that would mean the fifth and sixth strips must both be the same color as the first an second.
– fleablood
Nov 30 at 20:45
No. I mean that your above configuration must be present. By "all four colours for four strips" I mean that all the four colours must be used in a particular configuration. For example, the configuration 1,2,3,1,2 is not valid since you've not used the colour 4 anywhere but 1,2,3,4,3,2 is valid since you've used all the four colours atleast once.
– sayantan dasgupta
Nov 30 at 20:49
add a comment |
Ok so I came across this question. It goes something like this :
A new flag is to be designed with 6 vertical stripes using all 4 colours. In how many ways can this be done so that no 2 adjacent stripes have the same colour and it is given that we have to use all the 4 colours for 4 stripes ( we cannot use less than 4 colours to colour the stripes. For example, for a given set of colours {1,2,3,4}, the solution cannot be like 1,2,1,2,1,2). I've been struggling to come up with a solution. Can someone show me how it is done?
combinatorics permutations
asked Nov 30 at 20:26
sayantan dasgupta
102
Ok so I came across this question. It goes something like this :
A new flag is to be designed with 6 vertical stripes using all 4 colours. In how many ways can this be done so that no 2 adjacent stripes have the same colour and it is given that we have to use all the 4 colours for 4 stripes ( we cannot use less than 4 colours to colour the stripes. For example, for a given set of colours {1,2,3,4}, the solution cannot be like 1,2,1,2,1,2). I've been struggling to come up with a solution. Can someone show me how it is done?
combinatorics permutations
combinatorics permutations
asked Nov 30 at 20:26
sayantan dasgupta
102
asked Nov 30 at 20:26
sayantan dasgupta
102
asked Nov 30 at 20:26
sayantan dasgupta
102
asked Nov 30 at 20:26
sayantan dasgupta
102
asked Nov 30 at 20:26
sayantan dasgupta
102
102
"all four colors for four strips". Does that mean you can't do 1,2,3,4,3,2 because the middle four and the last four don't have the color 1? If so that would mean the fifth and sixth strips must both be the same color as the first an second.
– fleablood
Nov 30 at 20:45
No. I mean that your above configuration must be present. By "all four colours for four strips" I mean that all the four colours must be used in a particular configuration. For example, the configuration 1,2,3,1,2 is not valid since you've not used the colour 4 anywhere but 1,2,3,4,3,2 is valid since you've used all the four colours atleast once.
– sayantan dasgupta
Nov 30 at 20:49
add a comment |
"all four colors for four strips". Does that mean you can't do 1,2,3,4,3,2 because the middle four and the last four don't have the color 1? If so that would mean the fifth and sixth strips must both be the same color as the first an second.
– fleablood
Nov 30 at 20:45
No. I mean that your above configuration must be present. By "all four colours for four strips" I mean that all the four colours must be used in a particular configuration. For example, the configuration 1,2,3,1,2 is not valid since you've not used the colour 4 anywhere but 1,2,3,4,3,2 is valid since you've used all the four colours atleast once.
– sayantan dasgupta
Nov 30 at 20:49
"all four colors for four strips". Does that mean you can't do 1,2,3,4,3,2 because the middle four and the last four don't have the color 1? If so that would mean the fifth and sixth strips must both be the same color as the first an second.
– fleablood
Nov 30 at 20:45
"all four colors for four strips". Does that mean you can't do 1,2,3,4,3,2 because the middle four and the last four don't have the color 1? If so that would mean the fifth and sixth strips must both be the same color as the first an second.
– fleablood
Nov 30 at 20:45
No. I mean that your above configuration must be present. By "all four colours for four strips" I mean that all the four colours must be used in a particular configuration. For example, the configuration 1,2,3,1,2 is not valid since you've not used the colour 4 anywhere but 1,2,3,4,3,2 is valid since you've used all the four colours atleast once.
– sayantan dasgupta
Nov 30 at 20:49
No. I mean that your above configuration must be present. By "all four colours for four strips" I mean that all the four colours must be used in a particular configuration. For example, the configuration 1,2,3,1,2 is not valid since you've not used the colour 4 anywhere but 1,2,3,4,3,2 is valid since you've used all the four colours atleast once.
– sayantan dasgupta
Nov 30 at 20:49
add a comment |
1 Answer
1
active
oldest
votes
First, lets forget about the restriction that we must use all four colours (i.e. we are now counting how many ways this can be done using four or less colours).
You then have $4$ choices for the first stripe.
Then $3$ choices for the second stripe (cannot be the same colour as the first stripe).
Similarly, $3$ choices for each of the following stripes.
Thus, there are $4 times 3 times 3 times 3 times 3 times 3 = 972$ combinations.
However, we must subtract the patterns that do not use all $4$ colours, so you ask yourself how many ways you can colour the flag with three or less colours, with no two adjacent stripes having the same colour.
There are $C_3^4 = 4$ ways of picking three colours out of four, and the number of patterns for the chosen set of colours is done using the above logic, giving $3 times 2 times 2 times 2 times 2 times 2 = 96$ combinations.
It follows that we are left with $972-4 times 96 = 588$ patterns.
However, as pointed out in the comments, the patterns that only use $2$ colours have been subtracted twice instead of just once, so we must add one set of these back in.
There are $C_2^4 = 6$ ways you can choose two colours out of four, and after you have selected two colours, there are only $2$ possible patterns (namely having the two colours alternating, or you can calculate $2 times 1 times 1 times 1 times 1 times 1 = 2$ like before). Thus, we must add back in $6 times 2 = 12$ patterns.
In total, the answer is $972-4 times 96 + 6 times 2 = 600$ patterns.
answered Nov 30 at 20:38
glowstonetrees
2,285318
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3020591%2fthe-flag-colouring-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
First, lets forget about the restriction that we must use all four colours (i.e. we are now counting how many ways this can be done using four or less colours).
You then have $4$ choices for the first stripe.
Then $3$ choices for the second stripe (cannot be the same colour as the first stripe).
Similarly, $3$ choices for each of the following stripes.
Thus, there are $4 times 3 times 3 times 3 times 3 times 3 = 972$ combinations.
However, we must subtract the patterns that do not use all $4$ colours, so you ask yourself how many ways you can colour the flag with three or less colours, with no two adjacent stripes having the same colour.
There are $C_3^4 = 4$ ways of picking three colours out of four, and the number of patterns for the chosen set of colours is done using the above logic, giving $3 times 2 times 2 times 2 times 2 times 2 = 96$ combinations.
It follows that we are left with $972-4 times 96 = 588$ patterns.
However, as pointed out in the comments, the patterns that only use $2$ colours have been subtracted twice instead of just once, so we must add one set of these back in.
There are $C_2^4 = 6$ ways you can choose two colours out of four, and after you have selected two colours, there are only $2$ possible patterns (namely having the two colours alternating, or you can calculate $2 times 1 times 1 times 1 times 1 times 1 = 2$ like before). Thus, we must add back in $6 times 2 = 12$ patterns.
In total, the answer is $972-4 times 96 + 6 times 2 = 600$ patterns.
answered Nov 30 at 20:38
glowstonetrees
2,285318
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
add a comment |
First, lets forget about the restriction that we must use all four colours (i.e. we are now counting how many ways this can be done using four or less colours).
You then have $4$ choices for the first stripe.
Then $3$ choices for the second stripe (cannot be the same colour as the first stripe).
Similarly, $3$ choices for each of the following stripes.
Thus, there are $4 times 3 times 3 times 3 times 3 times 3 = 972$ combinations.
However, we must subtract the patterns that do not use all $4$ colours, so you ask yourself how many ways you can colour the flag with three or less colours, with no two adjacent stripes having the same colour.
There are $C_3^4 = 4$ ways of picking three colours out of four, and the number of patterns for the chosen set of colours is done using the above logic, giving $3 times 2 times 2 times 2 times 2 times 2 = 96$ combinations.
It follows that we are left with $972-4 times 96 = 588$ patterns.
However, as pointed out in the comments, the patterns that only use $2$ colours have been subtracted twice instead of just once, so we must add one set of these back in.
There are $C_2^4 = 6$ ways you can choose two colours out of four, and after you have selected two colours, there are only $2$ possible patterns (namely having the two colours alternating, or you can calculate $2 times 1 times 1 times 1 times 1 times 1 = 2$ like before). Thus, we must add back in $6 times 2 = 12$ patterns.
In total, the answer is $972-4 times 96 + 6 times 2 = 600$ patterns.
answered Nov 30 at 20:38
glowstonetrees
2,285318
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
add a comment |
First, lets forget about the restriction that we must use all four colours (i.e. we are now counting how many ways this can be done using four or less colours).
You then have $4$ choices for the first stripe.
Then $3$ choices for the second stripe (cannot be the same colour as the first stripe).
Similarly, $3$ choices for each of the following stripes.
Thus, there are $4 times 3 times 3 times 3 times 3 times 3 = 972$ combinations.
However, we must subtract the patterns that do not use all $4$ colours, so you ask yourself how many ways you can colour the flag with three or less colours, with no two adjacent stripes having the same colour.
There are $C_3^4 = 4$ ways of picking three colours out of four, and the number of patterns for the chosen set of colours is done using the above logic, giving $3 times 2 times 2 times 2 times 2 times 2 = 96$ combinations.
It follows that we are left with $972-4 times 96 = 588$ patterns.
However, as pointed out in the comments, the patterns that only use $2$ colours have been subtracted twice instead of just once, so we must add one set of these back in.
There are $C_2^4 = 6$ ways you can choose two colours out of four, and after you have selected two colours, there are only $2$ possible patterns (namely having the two colours alternating, or you can calculate $2 times 1 times 1 times 1 times 1 times 1 = 2$ like before). Thus, we must add back in $6 times 2 = 12$ patterns.
In total, the answer is $972-4 times 96 + 6 times 2 = 600$ patterns.
answered Nov 30 at 20:38
glowstonetrees
2,285318
First, lets forget about the restriction that we must use all four colours (i.e. we are now counting how many ways this can be done using four or less colours).
You then have $4$ choices for the first stripe.
Then $3$ choices for the second stripe (cannot be the same colour as the first stripe).
Similarly, $3$ choices for each of the following stripes.
Thus, there are $4 times 3 times 3 times 3 times 3 times 3 = 972$ combinations.
However, we must subtract the patterns that do not use all $4$ colours, so you ask yourself how many ways you can colour the flag with three or less colours, with no two adjacent stripes having the same colour.
There are $C_3^4 = 4$ ways of picking three colours out of four, and the number of patterns for the chosen set of colours is done using the above logic, giving $3 times 2 times 2 times 2 times 2 times 2 = 96$ combinations.
It follows that we are left with $972-4 times 96 = 588$ patterns.
However, as pointed out in the comments, the patterns that only use $2$ colours have been subtracted twice instead of just once, so we must add one set of these back in.
There are $C_2^4 = 6$ ways you can choose two colours out of four, and after you have selected two colours, there are only $2$ possible patterns (namely having the two colours alternating, or you can calculate $2 times 1 times 1 times 1 times 1 times 1 = 2$ like before). Thus, we must add back in $6 times 2 = 12$ patterns.
In total, the answer is $972-4 times 96 + 6 times 2 = 600$ patterns.
answered Nov 30 at 20:38
glowstonetrees
2,285318
edited Nov 30 at 21:00
answered Nov 30 at 20:38
glowstonetrees
2,285318
answered Nov 30 at 20:38
glowstonetrees
2,285318
answered Nov 30 at 20:38
glowstonetrees
2,285318
2,285318
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
add a comment |
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
This is not quite right; you have only subtracted out the flags which do not contain blue. You also need to subtract out the flags which do have red, and those without green, and those without yellow. However, flags missing two colors have now been doubly removed, so you need to add those back in.
– Mike Earnest
Nov 30 at 20:46
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
But using the logic for three or less colours, aren't we limiting ourselves to only 3 colour choices for the first strip? Since we could have arrangements like 4,1,2,1,2,1 or 3,1,2,1,2,1 or 2,1,2,1,2,1 or 1,2,1,2,1,2. So we could also have 4 colours for the first strip
– sayantan dasgupta
Nov 30 at 20:54
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
In the logic for three colours, I mean that you FIRST pick your three colours (say you decide you are only going to use ${1,2,3}$) THEN you decide on how you colour the flag. Sorry for my error
– glowstonetrees
Nov 30 at 21:01
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
Yep that logic is right now. Thanks for the help.
– sayantan dasgupta
Dec 1 at 9:53
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3020591%2fthe-flag-colouring-problem%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
"all four colors for four strips". Does that mean you can't do 1,2,3,4,3,2 because the middle four and the last four don't have the color 1? If so that would mean the fifth and sixth strips must both be the same color as the first an second.
– fleablood
Nov 30 at 20:45
No. I mean that your above configuration must be present. By "all four colours for four strips" I mean that all the four colours must be used in a particular configuration. For example, the configuration 1,2,3,1,2 is not valid since you've not used the colour 4 anywhere but 1,2,3,4,3,2 is valid since you've used all the four colours atleast once.
– sayantan dasgupta
Nov 30 at 20:49