Name the problem: dividing indexed coins in bins
Does any of you know the name of the problem described below? I am especially interested in possible generalizations of this problem.
I looked through my textbooks on combinatorics but could not find a similar problem.
Problem Statement.
I have 36 different coins. Each side has a number printed on it ranging from 1 to 6.
With notation {NumberSideA, NumberSideB} this would give:
{1,1}, {1,2}, ..., {1,6},
{2,1}, {2,2}, ..., {2,6},
...,
{6,1}, {6,2}, ..., {6,6}.
I want to divide all of these into a number of bins such that in each bin, there are at most 4 different indices on Side A and at most 4 different indices on Side B.
Furthermore, any combination of 2 bins should contain coins with at most 5 different indices on Side A and at most 5 different indices on side B.
- What is the minimum number of bins for which this is possible?
combinatorics
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
add a comment |
Does any of you know the name of the problem described below? I am especially interested in possible generalizations of this problem.
I looked through my textbooks on combinatorics but could not find a similar problem.
Problem Statement.
I have 36 different coins. Each side has a number printed on it ranging from 1 to 6.
With notation {NumberSideA, NumberSideB} this would give:
{1,1}, {1,2}, ..., {1,6},
{2,1}, {2,2}, ..., {2,6},
...,
{6,1}, {6,2}, ..., {6,6}.
I want to divide all of these into a number of bins such that in each bin, there are at most 4 different indices on Side A and at most 4 different indices on Side B.
Furthermore, any combination of 2 bins should contain coins with at most 5 different indices on Side A and at most 5 different indices on side B.
- What is the minimum number of bins for which this is possible?
combinatorics
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min
– T. Ford
Dec 19 '18 at 15:44
Six bins is minimal as shown in my completely rewritten answer.
– Daniel Mathias
Jan 4 at 17:14
add a comment |
Does any of you know the name of the problem described below? I am especially interested in possible generalizations of this problem.
I looked through my textbooks on combinatorics but could not find a similar problem.
Problem Statement.
I have 36 different coins. Each side has a number printed on it ranging from 1 to 6.
With notation {NumberSideA, NumberSideB} this would give:
{1,1}, {1,2}, ..., {1,6},
{2,1}, {2,2}, ..., {2,6},
...,
{6,1}, {6,2}, ..., {6,6}.
I want to divide all of these into a number of bins such that in each bin, there are at most 4 different indices on Side A and at most 4 different indices on Side B.
Furthermore, any combination of 2 bins should contain coins with at most 5 different indices on Side A and at most 5 different indices on side B.
- What is the minimum number of bins for which this is possible?
combinatorics
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
Does any of you know the name of the problem described below? I am especially interested in possible generalizations of this problem.
I looked through my textbooks on combinatorics but could not find a similar problem.
Problem Statement.
I have 36 different coins. Each side has a number printed on it ranging from 1 to 6.
With notation {NumberSideA, NumberSideB} this would give:
{1,1}, {1,2}, ..., {1,6},
{2,1}, {2,2}, ..., {2,6},
...,
{6,1}, {6,2}, ..., {6,6}.
I want to divide all of these into a number of bins such that in each bin, there are at most 4 different indices on Side A and at most 4 different indices on Side B.
Furthermore, any combination of 2 bins should contain coins with at most 5 different indices on Side A and at most 5 different indices on side B.
- What is the minimum number of bins for which this is possible?
combinatorics
combinatorics
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
edited Dec 19 '18 at 17:23
hpmor123
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
asked Dec 19 '18 at 13:57
hpmor123hpmor123
63
63
you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min
– T. Ford
Dec 19 '18 at 15:44
Six bins is minimal as shown in my completely rewritten answer.
– Daniel Mathias
Jan 4 at 17:14
add a comment |
you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min
– T. Ford
Dec 19 '18 at 15:44
Six bins is minimal as shown in my completely rewritten answer.
– Daniel Mathias
Jan 4 at 17:14
you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min
– T. Ford
Dec 19 '18 at 15:44
you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min
– T. Ford
Dec 19 '18 at 15:44
Six bins is minimal as shown in my completely rewritten answer.
– Daniel Mathias
Jan 4 at 17:14
Six bins is minimal as shown in my completely rewritten answer.
– Daniel Mathias
Jan 4 at 17:14
add a comment |
2 Answers
2
active
oldest
votes
The problem is a variation of Latin Square. It is equivalent to ask how many colors are needed to color a 6x6 grid lattice such that:
- each color occupies at most 4 grids of any row and any column.
- no two color together occupies a whole row or a whole column.
This certainly cannot be done with two colors. The following example shows with 3 colors, this is possible.
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
add a comment |
- What is the minimum number of bins for which this is possible?
My previous claim that 7 bins is minimal was incorrect. I wrote a short program in C to search for a solution in 6 bins. This is the output:
0 0 0 1 1 2
0 0 0 1 1 3
0 0 0 4 4 5
1 4 5 1 1 5
2 2 3 3 4 2
2 2 3 3 5 2
The numbers in this grid indicate which bin each coin is in. The indices for the coins are the (x, y) column and row values (not shown). This is known to be a minimal solution because the program would not have assigned any coin to the sixth bin if could be placed into one of the first five subject to the stated restrictions.
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
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%2f3046418%2fname-the-problem-dividing-indexed-coins-in-bins%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
The problem is a variation of Latin Square. It is equivalent to ask how many colors are needed to color a 6x6 grid lattice such that:
- each color occupies at most 4 grids of any row and any column.
- no two color together occupies a whole row or a whole column.
This certainly cannot be done with two colors. The following example shows with 3 colors, this is possible.
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
add a comment |
The problem is a variation of Latin Square. It is equivalent to ask how many colors are needed to color a 6x6 grid lattice such that:
- each color occupies at most 4 grids of any row and any column.
- no two color together occupies a whole row or a whole column.
This certainly cannot be done with two colors. The following example shows with 3 colors, this is possible.
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
add a comment |
The problem is a variation of Latin Square. It is equivalent to ask how many colors are needed to color a 6x6 grid lattice such that:
- each color occupies at most 4 grids of any row and any column.
- no two color together occupies a whole row or a whole column.
This certainly cannot be done with two colors. The following example shows with 3 colors, this is possible.
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
The problem is a variation of Latin Square. It is equivalent to ask how many colors are needed to color a 6x6 grid lattice such that:
- each color occupies at most 4 grids of any row and any column.
- no two color together occupies a whole row or a whole column.
This certainly cannot be done with two colors. The following example shows with 3 colors, this is possible.
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
answered Dec 20 '18 at 14:14
ablmfablmf
2,37442352
2,37442352
add a comment |
add a comment |
- What is the minimum number of bins for which this is possible?
My previous claim that 7 bins is minimal was incorrect. I wrote a short program in C to search for a solution in 6 bins. This is the output:
0 0 0 1 1 2
0 0 0 1 1 3
0 0 0 4 4 5
1 4 5 1 1 5
2 2 3 3 4 2
2 2 3 3 5 2
The numbers in this grid indicate which bin each coin is in. The indices for the coins are the (x, y) column and row values (not shown). This is known to be a minimal solution because the program would not have assigned any coin to the sixth bin if could be placed into one of the first five subject to the stated restrictions.
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
add a comment |
- What is the minimum number of bins for which this is possible?
My previous claim that 7 bins is minimal was incorrect. I wrote a short program in C to search for a solution in 6 bins. This is the output:
0 0 0 1 1 2
0 0 0 1 1 3
0 0 0 4 4 5
1 4 5 1 1 5
2 2 3 3 4 2
2 2 3 3 5 2
The numbers in this grid indicate which bin each coin is in. The indices for the coins are the (x, y) column and row values (not shown). This is known to be a minimal solution because the program would not have assigned any coin to the sixth bin if could be placed into one of the first five subject to the stated restrictions.
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
add a comment |
- What is the minimum number of bins for which this is possible?
My previous claim that 7 bins is minimal was incorrect. I wrote a short program in C to search for a solution in 6 bins. This is the output:
0 0 0 1 1 2
0 0 0 1 1 3
0 0 0 4 4 5
1 4 5 1 1 5
2 2 3 3 4 2
2 2 3 3 5 2
The numbers in this grid indicate which bin each coin is in. The indices for the coins are the (x, y) column and row values (not shown). This is known to be a minimal solution because the program would not have assigned any coin to the sixth bin if could be placed into one of the first five subject to the stated restrictions.
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
- What is the minimum number of bins for which this is possible?
My previous claim that 7 bins is minimal was incorrect. I wrote a short program in C to search for a solution in 6 bins. This is the output:
0 0 0 1 1 2
0 0 0 1 1 3
0 0 0 4 4 5
1 4 5 1 1 5
2 2 3 3 4 2
2 2 3 3 5 2
The numbers in this grid indicate which bin each coin is in. The indices for the coins are the (x, y) column and row values (not shown). This is known to be a minimal solution because the program would not have assigned any coin to the sixth bin if could be placed into one of the first five subject to the stated restrictions.
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
edited Jan 4 at 17:11
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
answered Dec 24 '18 at 3:36
Daniel MathiasDaniel Mathias
3856
3856
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.
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%2f3046418%2fname-the-problem-dividing-indexed-coins-in-bins%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
you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min
– T. Ford
Dec 19 '18 at 15:44
Six bins is minimal as shown in my completely rewritten answer.
– Daniel Mathias
Jan 4 at 17:14