Posers and Puzzles

Posers and Puzzles

  1. Standard memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    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. Joined
    14 Dec '05
    Moves
    5692
    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 memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16172
    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 memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    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. Standard memberDoctorScribbles
    BWA Soldier
    Tha Brotha Hood
    Joined
    13 Dec '04
    Moves
    49088
    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. Standard memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    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. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16172
    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 memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    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. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    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 memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16172
    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. Standard memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    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 memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    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 memberPBE6
    Bananarama
    False berry
    Joined
    14 Feb '04
    Moves
    28719
    22 May '08 20:03
    Bump! (for comic effect - see topic listing)
  14. Joined
    27 Apr '08
    Moves
    473
    22 May '08 20:13
    Originally posted by PBE6
    Bump! (for comic effect - see topic listing)
    Unbump! 😛
  15. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16172
    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.
Back to Top