Hard

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 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.)

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.)

The most I can come up with is n-1 as well.

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.

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}".)

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?

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 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.

Don't you have a degree in stats or something in addition to your knowledge of pirpetual motions?

(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 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}".)

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} }

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} }

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.

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 TheMaster37

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

No it isn't.

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.

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

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).

Bump! (for comic effect - see topic listing)

Originally posted by PBE6
Bump! (for comic effect - see topic listing)

Unbump! 😛