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

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