 Posers and Puzzles

1. 20 May '08 05:19
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.)
2. 20 May '08 14:22
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
3. 20 May '08 19:40
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.
4. 20 May '08 22:421 edit
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}".)
5. 20 May '08 22:545 edits
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.
6. 21 May '08 04:481 edit
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.)
7. 21 May '08 18:49
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} }
8. 21 May '08 23:151 edit
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.
9. 22 May '08 12:46
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.
10. 22 May '08 13:341 edit
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
11. 22 May '08 14:20
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.
12. 22 May '08 14:23
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).
13. 22 May '08 20:03
Bump! (for comic effect - see topic listing)
14. 22 May '08 20:13
Originally posted by PBE6
Bump! (for comic effect - see topic listing)
Unbump! 😛
15. 22 May '08 22:001 edit
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).
As stated in the problem, S isn't "limited" by k; S is 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.