Mixing
Mapping between overlapping sets
$begingroup$
My question concerns combinations and, more specifically, mutations between different combinations. It was inspired by the game of Dobble.
In the game Dobble, there are (or should be) 57 cards each showing 8 images from a set of 57 images. This means that for any two cards, there is one and only one image which is common to both cards.
In a general case, you can create a set of cards with n images per card, and a total of n * (n - 1) + 1 images (and the same number of cards).
Each image will appear on n cards, along with (n - 1) other images on each card, giving a total of n * (n - 1) other images, plus the given image, resulting in a total of n * (n - 1) + 1. Since each image appears n times, and there n images per card, there must also be n * (n - 1) + 1 cards.
So, the 8 images per card in Dobble lead to 8 * 7 + 1 = 57 images and cards.
A general solution for n images per card with m images in common between any two cards is only possible for certain values of m and n. Specifically, m has to be a factor of n * (n - 1) and the number of images (and cards) required is 1 + (n * (n - 1) / m).
There are cases where different values of m and n require the same number of images and cards. This suggests that there may be optimal ways of mapping two such sets of cards to each other, and it is the optimization of this mapping that I would like to explore.
Examples:
5 images per card, 2 common images on each card
requires 11 images (labelled here in hexadecimal, for simplicity):
12345
12 678
1 3 6 9A
1 4 7 9 B
1 5 8 AB
23 89 B
2 4 6 AB
2 5 7 9A
34 78 A
3 567 B
456 89
6 images per card, 3 common images per card
also requires 11 images:
123456
123 789
1 34 7 AB
1 45 89 B
1 5678 A
12 6 9AB
23 5 8 AB
2 45 7 9A
2 4 678 B
34 6 89A
3 567 9 B
The optimal mapping, if it exists, would require no more than 11 changes, all of which are additions. Using brute force, I have found a solution that requires 19 changes, with 8 alterations as well as 11 additions.
5 images 6 images Change
1) 12345 => 123456 +6
2) 12 678 => 1 5678 A 2 > 5 +A
3) 1 3 6 9A => 12 6 9AB 3 > 2 +B
4) 1 4 7 9 B => 1 34 7 AB 9 > A +3
5) 1 5 8 AB => 23 5 8 AB 1 > 2 +3
6) 23 89 B => 123 789 B > 7 +1
7) 2 4 6 AB => 2 4 678 B B > 8 +7
8) 2 5 7 9A => 2 45 7 9A +4
9) 34 78 A => 34 6 89A 7 > 6 +9
A) 3 567 B => 3 567 9 B +9
B) 456 89 => 1 45 89 B 6 > 1 +B
My brute force approach assumes that the numbers in one set correspond to the same image as the numbers in the other set. Since this is not necessarily true, it may be possible to find a more compact solution.
I would be interested to learn what formal studies have been done in this area ... and what practical applications this might have.
combinations
asked Jan 2 at 16:32
James NewtonJames Newton
1406
$endgroup$
add a comment |
$begingroup$
My question concerns combinations and, more specifically, mutations between different combinations. It was inspired by the game of Dobble.
In the game Dobble, there are (or should be) 57 cards each showing 8 images from a set of 57 images. This means that for any two cards, there is one and only one image which is common to both cards.
In a general case, you can create a set of cards with n images per card, and a total of n * (n - 1) + 1 images (and the same number of cards).
Each image will appear on n cards, along with (n - 1) other images on each card, giving a total of n * (n - 1) other images, plus the given image, resulting in a total of n * (n - 1) + 1. Since each image appears n times, and there n images per card, there must also be n * (n - 1) + 1 cards.
So, the 8 images per card in Dobble lead to 8 * 7 + 1 = 57 images and cards.
A general solution for n images per card with m images in common between any two cards is only possible for certain values of m and n. Specifically, m has to be a factor of n * (n - 1) and the number of images (and cards) required is 1 + (n * (n - 1) / m).
There are cases where different values of m and n require the same number of images and cards. This suggests that there may be optimal ways of mapping two such sets of cards to each other, and it is the optimization of this mapping that I would like to explore.
Examples:
5 images per card, 2 common images on each card
requires 11 images (labelled here in hexadecimal, for simplicity):
12345
12 678
1 3 6 9A
1 4 7 9 B
1 5 8 AB
23 89 B
2 4 6 AB
2 5 7 9A
34 78 A
3 567 B
456 89
6 images per card, 3 common images per card
also requires 11 images:
123456
123 789
1 34 7 AB
1 45 89 B
1 5678 A
12 6 9AB
23 5 8 AB
2 45 7 9A
2 4 678 B
34 6 89A
3 567 9 B
The optimal mapping, if it exists, would require no more than 11 changes, all of which are additions. Using brute force, I have found a solution that requires 19 changes, with 8 alterations as well as 11 additions.
5 images 6 images Change
1) 12345 => 123456 +6
2) 12 678 => 1 5678 A 2 > 5 +A
3) 1 3 6 9A => 12 6 9AB 3 > 2 +B
4) 1 4 7 9 B => 1 34 7 AB 9 > A +3
5) 1 5 8 AB => 23 5 8 AB 1 > 2 +3
6) 23 89 B => 123 789 B > 7 +1
7) 2 4 6 AB => 2 4 678 B B > 8 +7
8) 2 5 7 9A => 2 45 7 9A +4
9) 34 78 A => 34 6 89A 7 > 6 +9
A) 3 567 B => 3 567 9 B +9
B) 456 89 => 1 45 89 B 6 > 1 +B
My brute force approach assumes that the numbers in one set correspond to the same image as the numbers in the other set. Since this is not necessarily true, it may be possible to find a more compact solution.
I would be interested to learn what formal studies have been done in this area ... and what practical applications this might have.
combinations
asked Jan 2 at 16:32
James NewtonJames Newton
1406
$endgroup$
$begingroup$
en.wikipedia.org/wiki/Combinatorial_design en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
$endgroup$
– Lord Shark the Unknown
Jan 2 at 16:37
$begingroup$
An observation: It is easy to prove that an 'optimal mapping' with 11 additions and no other changes does not exist. Both sets of cards must contain 110 distinct triplets, and adding an image to any of the 5-image cards will introduce five triplets not already present.
$endgroup$
– Daniel Mathias
Jan 2 at 20:27
add a comment |
$begingroup$
My question concerns combinations and, more specifically, mutations between different combinations. It was inspired by the game of Dobble.
In the game Dobble, there are (or should be) 57 cards each showing 8 images from a set of 57 images. This means that for any two cards, there is one and only one image which is common to both cards.
In a general case, you can create a set of cards with n images per card, and a total of n * (n - 1) + 1 images (and the same number of cards).
Each image will appear on n cards, along with (n - 1) other images on each card, giving a total of n * (n - 1) other images, plus the given image, resulting in a total of n * (n - 1) + 1. Since each image appears n times, and there n images per card, there must also be n * (n - 1) + 1 cards.
So, the 8 images per card in Dobble lead to 8 * 7 + 1 = 57 images and cards.
A general solution for n images per card with m images in common between any two cards is only possible for certain values of m and n. Specifically, m has to be a factor of n * (n - 1) and the number of images (and cards) required is 1 + (n * (n - 1) / m).
There are cases where different values of m and n require the same number of images and cards. This suggests that there may be optimal ways of mapping two such sets of cards to each other, and it is the optimization of this mapping that I would like to explore.
Examples:
5 images per card, 2 common images on each card
requires 11 images (labelled here in hexadecimal, for simplicity):
12345
12 678
1 3 6 9A
1 4 7 9 B
1 5 8 AB
23 89 B
2 4 6 AB
2 5 7 9A
34 78 A
3 567 B
456 89
6 images per card, 3 common images per card
also requires 11 images:
123456
123 789
1 34 7 AB
1 45 89 B
1 5678 A
12 6 9AB
23 5 8 AB
2 45 7 9A
2 4 678 B
34 6 89A
3 567 9 B
The optimal mapping, if it exists, would require no more than 11 changes, all of which are additions. Using brute force, I have found a solution that requires 19 changes, with 8 alterations as well as 11 additions.
5 images 6 images Change
1) 12345 => 123456 +6
2) 12 678 => 1 5678 A 2 > 5 +A
3) 1 3 6 9A => 12 6 9AB 3 > 2 +B
4) 1 4 7 9 B => 1 34 7 AB 9 > A +3
5) 1 5 8 AB => 23 5 8 AB 1 > 2 +3
6) 23 89 B => 123 789 B > 7 +1
7) 2 4 6 AB => 2 4 678 B B > 8 +7
8) 2 5 7 9A => 2 45 7 9A +4
9) 34 78 A => 34 6 89A 7 > 6 +9
A) 3 567 B => 3 567 9 B +9
B) 456 89 => 1 45 89 B 6 > 1 +B
My brute force approach assumes that the numbers in one set correspond to the same image as the numbers in the other set. Since this is not necessarily true, it may be possible to find a more compact solution.
I would be interested to learn what formal studies have been done in this area ... and what practical applications this might have.
combinations
asked Jan 2 at 16:32
James NewtonJames Newton
1406
$endgroup$
My question concerns combinations and, more specifically, mutations between different combinations. It was inspired by the game of Dobble.
In the game Dobble, there are (or should be) 57 cards each showing 8 images from a set of 57 images. This means that for any two cards, there is one and only one image which is common to both cards.
In a general case, you can create a set of cards with n images per card, and a total of n * (n - 1) + 1 images (and the same number of cards).
Each image will appear on n cards, along with (n - 1) other images on each card, giving a total of n * (n - 1) other images, plus the given image, resulting in a total of n * (n - 1) + 1. Since each image appears n times, and there n images per card, there must also be n * (n - 1) + 1 cards.
So, the 8 images per card in Dobble lead to 8 * 7 + 1 = 57 images and cards.
A general solution for n images per card with m images in common between any two cards is only possible for certain values of m and n. Specifically, m has to be a factor of n * (n - 1) and the number of images (and cards) required is 1 + (n * (n - 1) / m).
There are cases where different values of m and n require the same number of images and cards. This suggests that there may be optimal ways of mapping two such sets of cards to each other, and it is the optimization of this mapping that I would like to explore.
Examples:
5 images per card, 2 common images on each card
requires 11 images (labelled here in hexadecimal, for simplicity):
12345
12 678
1 3 6 9A
1 4 7 9 B
1 5 8 AB
23 89 B
2 4 6 AB
2 5 7 9A
34 78 A
3 567 B
456 89
6 images per card, 3 common images per card
also requires 11 images:
123456
123 789
1 34 7 AB
1 45 89 B
1 5678 A
12 6 9AB
23 5 8 AB
2 45 7 9A
2 4 678 B
34 6 89A
3 567 9 B
The optimal mapping, if it exists, would require no more than 11 changes, all of which are additions. Using brute force, I have found a solution that requires 19 changes, with 8 alterations as well as 11 additions.
5 images 6 images Change
1) 12345 => 123456 +6
2) 12 678 => 1 5678 A 2 > 5 +A
3) 1 3 6 9A => 12 6 9AB 3 > 2 +B
4) 1 4 7 9 B => 1 34 7 AB 9 > A +3
5) 1 5 8 AB => 23 5 8 AB 1 > 2 +3
6) 23 89 B => 123 789 B > 7 +1
7) 2 4 6 AB => 2 4 678 B B > 8 +7
8) 2 5 7 9A => 2 45 7 9A +4
9) 34 78 A => 34 6 89A 7 > 6 +9
A) 3 567 B => 3 567 9 B +9
B) 456 89 => 1 45 89 B 6 > 1 +B
My brute force approach assumes that the numbers in one set correspond to the same image as the numbers in the other set. Since this is not necessarily true, it may be possible to find a more compact solution.
I would be interested to learn what formal studies have been done in this area ... and what practical applications this might have.
combinations
combinations
asked Jan 2 at 16:32
James NewtonJames Newton
1406
asked Jan 2 at 16:32
James NewtonJames Newton
1406
asked Jan 2 at 16:32
James NewtonJames Newton
1406
asked Jan 2 at 16:32
James NewtonJames Newton
1406
asked Jan 2 at 16:32
James NewtonJames Newton
1406
1406
$begingroup$
en.wikipedia.org/wiki/Combinatorial_design en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
$endgroup$
– Lord Shark the Unknown
Jan 2 at 16:37
$begingroup$
An observation: It is easy to prove that an 'optimal mapping' with 11 additions and no other changes does not exist. Both sets of cards must contain 110 distinct triplets, and adding an image to any of the 5-image cards will introduce five triplets not already present.
$endgroup$
– Daniel Mathias
Jan 2 at 20:27
add a comment |
$begingroup$
en.wikipedia.org/wiki/Combinatorial_design en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
$endgroup$
– Lord Shark the Unknown
Jan 2 at 16:37
$begingroup$
An observation: It is easy to prove that an 'optimal mapping' with 11 additions and no other changes does not exist. Both sets of cards must contain 110 distinct triplets, and adding an image to any of the 5-image cards will introduce five triplets not already present.
$endgroup$
– Daniel Mathias
Jan 2 at 20:27
$begingroup$
en.wikipedia.org/wiki/Combinatorial_design en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
$endgroup$
– Lord Shark the Unknown
Jan 2 at 16:37
$begingroup$
en.wikipedia.org/wiki/Combinatorial_design en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
$endgroup$
– Lord Shark the Unknown
Jan 2 at 16:37
$begingroup$
An observation: It is easy to prove that an 'optimal mapping' with 11 additions and no other changes does not exist. Both sets of cards must contain 110 distinct triplets, and adding an image to any of the 5-image cards will introduce five triplets not already present.
$endgroup$
– Daniel Mathias
Jan 2 at 20:27
$begingroup$
An observation: It is easy to prove that an 'optimal mapping' with 11 additions and no other changes does not exist. Both sets of cards must contain 110 distinct triplets, and adding an image to any of the 5-image cards will introduce five triplets not already present.
$endgroup$
– Daniel Mathias
Jan 2 at 20:27
add a comment |
0
active
oldest
votes
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%2f3059686%2fmapping-between-overlapping-sets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3059686%2fmapping-between-overlapping-sets%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
$begingroup$
en.wikipedia.org/wiki/Combinatorial_design en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
$endgroup$
– Lord Shark the Unknown
Jan 2 at 16:37
$begingroup$
An observation: It is easy to prove that an 'optimal mapping' with 11 additions and no other changes does not exist. Both sets of cards must contain 110 distinct triplets, and adding an image to any of the 5-image cards will introduce five triplets not already present.
$endgroup$
– Daniel Mathias
Jan 2 at 20:27