- 20 May '08 05:19I 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.) - 20 May '08 14:22

Not sure I'm understanding the question properly, but I think the answer is n-1*Originally posted by ChronicLeaky***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.)** - 20 May '08 19:40

The most I can come up with is n-1 as well.*Originally posted by ChronicLeaky***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. - 20 May '08 22:54 / 5 edits

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.*Originally posted by ChronicLeaky***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?** - 21 May '08 04:48 / 1 edit

Don't you have a degree in stats or something in addition to your knowledge of pirpetual motions?*Originally posted by DoctorScribbles***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.) - 21 May '08 18:49

Then I would say it is:*Originally posted by ChronicLeaky***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} } - 21 May '08 23:15 / 1 edit

I 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.*Originally posted by forkedknight***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} } - 22 May '08 12:46Ok, 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. - 22 May '08 13:34 / 1 editI 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 - 22 May '08 14:20

No it isn't.*Originally posted by TheMaster37*

ChronicLeaky, the answer you are thinking of is a formula that gives you the EXACT number of sets you can choose.

I'm not asking how to choose S to maximise the number of sets I can choose. I'm asking for a general estimate that holds for any given S. - 22 May '08 14:23

The 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.*Originally posted by forkedknight***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). - 22 May '08 22:00 / 1 edit

As stated in the problem, S isn't "limited" by k; S is*Originally posted by ChronicLeaky***The 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.**

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).*defined*by k.

I don't see how you see my work as 'defining' S in any way -- it is merely stated in terms of k.