Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member ChronicLeaky
    Don't Fear Me
    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. Standard member forkedknight
    Defend the Universe
    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. Standard member ChronicLeaky
    Don't Fear Me
    20 May '08 22:42 / 1 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. Standard member DoctorScribbles
    BWA Soldier
    20 May '08 22:54 / 5 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. Standard member ChronicLeaky
    Don't Fear Me
    21 May '08 04:48 / 1 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. Standard member forkedknight
    Defend the Universe
    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. Standard member ChronicLeaky
    Don't Fear Me
    21 May '08 23:15 / 1 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. Standard member TheMaster37
    Kupikupopo!
    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. Standard member forkedknight
    Defend the Universe
    22 May '08 13:34 / 1 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. Standard member ChronicLeaky
    Don't Fear Me
    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. Standard member ChronicLeaky
    Don't Fear Me
    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. Standard member PBE6
    Bananarama
    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. Standard member forkedknight
    Defend the Universe
    22 May '08 22:00 / 1 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.