Hard

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.

Originally posted by forkedknight
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.

S is not stated to be defined by k. I said only that S is some subset of {1, 2, 3, ... k}. Your answer has to be valid for any possible S, which is why it is an estimate.

it doesn't like the less than or equal symbol, and doesn't save what I typed, so I may reply tomorrow...

Originally posted by forkedknight
it doesn't like the less than or equal symbol, and doesn't save what I typed, so I may reply tomorrow...

Nice 🙂 I'm eager to see it.

Originally posted by ChronicLeaky
Nice 🙂 I'm eager to see it.

What about:

For k a natural number and K={1, 2, ..., k}, then S is a subset of K, S={a_1, a_2, ... ,a_m} with a_i < a_(i+1) and a_i in K for all i. Then we have,
(n choose a_1) x [The sum of ( [(n-a_i) choose (k-a_i)] - [(n-[a_i + 1]) choose (k-[a_i + 1])] ), a_i in S] choices of the required sets.

n choose a_1 gives us the number of ways of chooseing our minimum intersection. Then multiplying this by (n-a_1 choose k-a_1) gives us the number of sets with an intersection of at least a_1 elements (the elements choosen by our (n choose a_1) and any other elements that happen to correspond when we choose two subsets. Thus, we need to remove any subset which intersects with another, with the intersection having more than a_1 elements. (n-(a_1+1) choose k-(a_1+1)) does this for us, with a_1+1 NOT (necessarily) being a_2 - it is just the natural number one greater than a_1. However, this removes every subset that intersects with another with the intersection being greater than a_1 elements. So, we need to choose the other sets that will have intersections of size a_i. We do this in a similar way.

Sorry if that's confusing - I would advise you to write out the formula above (a_i being a subscript i) before trying to interprit it!

I think, however, that this is wrong. I think I may be choosing some sets twice. I shall give it a bit more thought... Nice problem!

Originally posted by Swlabr
What about:

For k a natural number and K={1, 2, ..., k}, then S is a subset of K, S={a_1, a_2, ... ,a_m} with a_i < a_(i+1) and a_i in K for all i. Then we have,
(n choose a_1) x [The sum of ( [(n-a_i) choose (k-a_i)] - [(n-[a_i + 1]) choose (k-[a_i + 1])] ), a_i in S] choices of the required sets.

n choose a_1 gives us the number of ways of chooseing ...[text shortened]... I think I may be choosing some sets twice. I shall give it a bit more thought... Nice problem!

perhaps in the sum it should be (n-a_i) choose (k-a_1), as we have n-a_i choices, but we still need subsets of size k. We have placed a_1 elements, and so we need subsets of size k-a_1.

I think I need to sleep on this...