Subsets of a set with common elements between themselves
$begingroup$
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
edited Jan 5 at 2:29
bof
52.6k559121
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
$endgroup$
|
show 7 more comments
$begingroup$
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
edited Jan 5 at 2:29
bof
52.6k559121
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
$endgroup$
1
$begingroup$
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
$endgroup$
– Mario Carneiro
Jan 5 at 1:18
$begingroup$
@MarioCarneiro Right, I corrected the errors
$endgroup$
– Vladimir Vargas
Jan 5 at 1:27
$begingroup$
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
$endgroup$
– Mario Carneiro
Jan 5 at 1:51
1
$begingroup$
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
$endgroup$
– Alex Kruckman
Jan 5 at 2:19
1
$begingroup$
Also, this is off-topic, but what's the deal with your profile picture?
$endgroup$
– Alex Kruckman
Jan 5 at 2:20
|
show 7 more comments
$begingroup$
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
edited Jan 5 at 2:29
bof
52.6k559121
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
$endgroup$
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
combinatorics extremal-combinatorics combinatorial-designs
edited Jan 5 at 2:29
bof
52.6k559121
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
edited Jan 5 at 2:29
bof
52.6k559121
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
edited Jan 5 at 2:29
bof
52.6k559121
edited Jan 5 at 2:29
bof
52.6k559121
edited Jan 5 at 2:29
bof
52.6k559121
52.6k559121
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
asked Jan 5 at 0:57
Vladimir VargasVladimir Vargas
3,39211630
3,39211630
1
$begingroup$
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
$endgroup$
– Mario Carneiro
Jan 5 at 1:18
$begingroup$
@MarioCarneiro Right, I corrected the errors
$endgroup$
– Vladimir Vargas
Jan 5 at 1:27
$begingroup$
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
$endgroup$
– Mario Carneiro
Jan 5 at 1:51
1
$begingroup$
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
$endgroup$
– Alex Kruckman
Jan 5 at 2:19
1
$begingroup$
Also, this is off-topic, but what's the deal with your profile picture?
$endgroup$
– Alex Kruckman
Jan 5 at 2:20
|
show 7 more comments
1
$begingroup$
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
$endgroup$
– Mario Carneiro
Jan 5 at 1:18
$begingroup$
@MarioCarneiro Right, I corrected the errors
$endgroup$
– Vladimir Vargas
Jan 5 at 1:27
$begingroup$
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
$endgroup$
– Mario Carneiro
Jan 5 at 1:51
1
$begingroup$
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
$endgroup$
– Alex Kruckman
Jan 5 at 2:19
1
$begingroup$
Also, this is off-topic, but what's the deal with your profile picture?
$endgroup$
– Alex Kruckman
Jan 5 at 2:20
1
1
$begingroup$
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
$endgroup$
– Mario Carneiro
Jan 5 at 1:18
$begingroup$
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
$endgroup$
– Mario Carneiro
Jan 5 at 1:18
$begingroup$
@MarioCarneiro Right, I corrected the errors
$endgroup$
– Vladimir Vargas
Jan 5 at 1:27
$begingroup$
@MarioCarneiro Right, I corrected the errors
$endgroup$
– Vladimir Vargas
Jan 5 at 1:27
$begingroup$
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
$endgroup$
– Mario Carneiro
Jan 5 at 1:51
$begingroup$
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
$endgroup$
– Mario Carneiro
Jan 5 at 1:51
1
1
$begingroup$
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
$endgroup$
– Alex Kruckman
Jan 5 at 2:19
$begingroup$
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
$endgroup$
– Alex Kruckman
Jan 5 at 2:19
1
1
$begingroup$
Also, this is off-topic, but what's the deal with your profile picture?
$endgroup$
– Alex Kruckman
Jan 5 at 2:20
$begingroup$
Also, this is off-topic, but what's the deal with your profile picture?
$endgroup$
– Alex Kruckman
Jan 5 at 2:20
|
show 7 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
$endgroup$
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%2f3062304%2fsubsets-of-a-set-with-common-elements-between-themselves%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
$begingroup$
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
$endgroup$
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
answered Jan 5 at 3:29
Mike EarnestMike Earnest
26.9k22152
26.9k22152
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%2f3062304%2fsubsets-of-a-set-with-common-elements-between-themselves%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$
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
$endgroup$
– Mario Carneiro
Jan 5 at 1:18
$begingroup$
@MarioCarneiro Right, I corrected the errors
$endgroup$
– Vladimir Vargas
Jan 5 at 1:27
$begingroup$
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
$endgroup$
– Mario Carneiro
Jan 5 at 1:51
1
$begingroup$
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
$endgroup$
– Alex Kruckman
Jan 5 at 2:19
1
$begingroup$
Also, this is off-topic, but what's the deal with your profile picture?
$endgroup$
– Alex Kruckman
Jan 5 at 2:20