I have a set N of size n (you can take N = {1, 2, 3, ..., n} if you like, an integer k between 1 and n inclusive, and a subset S of {1, 2, 3, ... , k}. I choose subsets of N such that each chosen subset has k elements, and, given two distinct chosen subsets, the number of elements common to both is an element of S. At most how many sets can I choose?
(I didn't invent this question; someone asked me this earlier and I wasted the better part of the morning on it. I have a complicated solution, but it involves more structure than the problem might actually demand, so I'm requesting a simple solution.)
Originally posted by ChronicLeakyNot sure I'm understanding the question properly, but I think the answer is n-1
I have a set N of size n (you can take N = {1, 2, 3, ..., n} if you like, an integer k between 1 and n inclusive, and a subset S of {1, 2, 3, ... , k}. I choose subsets of N such that each chosen subset has k elements, and, given two distinct chosen subsets, the number of elements common to both is an element of S. At most how many sets can I choose? ...[text shortened]... s more structure than the problem might actually demand, so I'm requesting a simple solution.)
Originally posted by ChronicLeakyThe most I can come up with is n-1 as well.
I have a set N of size n (you can take N = {1, 2, 3, ..., n} if you like, an integer k between 1 and n inclusive, and a subset S of {1, 2, 3, ... , k}. I choose subsets of N such that each chosen subset has k elements, and, given two distinct chosen subsets, the number of elements common to both is an element of S. At most how many sets can I choose? ...[text shortened]... s more structure than the problem might actually demand, so I'm requesting a simple solution.)
N = {1, 2, .. , n}
S = {1, 2}
subsets are { {1, 2}, {1, 3}, {1, 4}, ... , {1, n} }
or you could use '2' instead of '1' as the common element... result is the same.
There will be one common element between any two of those subsets of N.
Originally posted by ChronicLeakyBeats the shhit out of me. The solution probably has a few of those exclamation marks in it, but if it ain't Benjamins, I don't count it.
I have a set N of size n (you can take N = {1, 2, 3, ..., n} if you like, an integer k between 1 and n inclusive, and a subset S of {1, 2, 3, ... , k}. I choose subsets of N such that each chosen subset has k elements, and, given two distinct chosen subsets, the number of elements common to both is an element of S. At most how many sets can I choose?
Originally posted by DoctorScribblesDon't you have a degree in stats or something in addition to your knowledge of pirpetual motions?
Beats the shhit out of me. The solution probably has a few of those exclamation marks in it, but if it ain't Benjamins, I don't count it.
(EDIT: By that I mean that this is shouting for some sort of probabilistic approach, kind of in the manner of the posters above. In particular, if one thinks of the size of S as being a uniform random variable, one can sometimes think of this sort of extremal problem as kind of an optimisation problem, which is why I called in the dude who can optimise his stable's profitability. My solution is uglyass ghetto geometry.)
Originally posted by ChronicLeakyThen I would say it is:
I should clarify. S is given to you, so your answer must be, a priori, in terms of N, k and S.
(e.g. you can't just say "S = {1, 2}".)
n - k + 1
N = {1, ..., n}
S = {1, ..., k}
subsets are { {1, ..., k-1, k}, {1, ..., k-1, k+1}, {1, ..., k-1, k+2}, ...,
{1, ..., k-1, n} }
Originally posted by forkedknightI think you misunderstood my clarification; I repeat that you cannot say "S =" anywhere in your solution because S is given to you. Your answer should be an inequality with "number of sets" on the left and some expression in terms of S, N and k on the right.
Then I would say it is:
n - k + 1
N = {1, ..., n}
S = {1, ..., k}
subsets are { {1, ..., k-1, k}, {1, ..., k-1, k+1}, {1, ..., k-1, k+2}, ...,
{1, ..., k-1, n} }
Ok, some preliminary work...
N = {1, 2, ..., n}
Given is a number k, along with S, a subset of {1, 2, ..., k}
We make subsets of N, containing k elements. There are (n over k) of those sets. Lets put all those subsets in a set we call s(N).
We have a condition;
C) The number of common elements in any two elements from s(N) is an element from S.
The question is:
At most how many elements of s(N) satisfy C?
Since the question is about the MOST possible number of subsets, we have to assume S is as big as possible (the bigger S is, the more subsets we can choose). Thus S = {1, 2, ..., k}.
ChronicLeaky, the answer you are thinking of is a formula that gives you the EXACT number of sets you can choose.
I didn't 'choose' a set S, I just clarified for you what it contained. The subset S is a fuction of k; since S = {1, 2, k-1, k}, they are totally dependent on eachother, so any equation for the number of subset need only be an expression interms of k and n.
I will, however, give this answer another try:
In order for "any two subsets to contain a common element", there needs to be at least one element common to all subsets. Let's assume this element is '1'. There will then be k-1 other elements in each subset.
Since the arity of both S and each other chosen subset s(N) is k, the number of common elements (if there are any) will always be a member of S.
I will assert that the number of possible subsets is C(n-1, k-1), where C(n, r) is "n choose r".
This simplifies to (n-1)! / ( (n-k)! * (k-1)! )
Therefore, for k=2 (like my first answer), C(n-1, 1) = n-1.
The ideal k, to get the maximum number of subsets, will be (n-1)/2 + 1 (with integer division). This is because the maximum for C(n,r) is when r = n/2, so we want (n-1)/2 = k-1
Originally posted by forkedknightThe point is that you cannot "clarify what S contains", because the question asks for an estimate which works for any S. You've solved the problem in the case of a particular S, but not in general.
I didn't 'choose' a set S, I just clarified for you what it contained. The subset S is a fuction of k; since S = {1, 2, k-1, k}, they are totally dependent on eachother, so any equation for the number of subset need only be an expression interms of k and n.
I will, however, give this answer another try:
In order for "any two subsets to contain a c ...[text shortened]... ion). This is because the maximum for C(n,r) is when r = n/2, so we want (n-1)/2 = k-1
It's time for a hint, which is that the sharpest estimate possible depends only on N and the size of S, and not explicitly on k (implicit is the fact that S is limited by k).