Challenge 94: Partitions into Groups and Subgroups

Share
Embed
  • Published on May 23, 2019
  • Starting with (potentially) the next week's challenge, the Weekly Math Challenge will adopt a problem submission process. If you are interested, please email an original problem and its solution to letssolvemathproblems7@gmail.com. =)
    Congratulations to Mr L and Th LEBL for successfully solving the last week's math challenge question! Mr L was the first person to solve the question.
    Welcome, everyone! LetsSolveMathProblems presents one weekly math challenge problem every Wednesday (continental U.S. time). To participate, please comment your proposed answer and explanation below (or discuss potential solutions with other viewers), keeping in mind that your comment should be left unedited to win the recognition prize. Up to the first ten people with correct solutions are recognized in the next challenge video. The solution to a challenge problem is posted as a separate video the following Wednesday.
    For more Weekly Math Challenges:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 30

  • LetsSolveMathProblems
    LetsSolveMathProblems  3 months ago +6

    Update: I was not feeling well throughout the past week and did not have enough time to review your submissions for the 95th Weekly Math Challenge, which will be postponed to next Wednesday. I sincerely apologize for the delay. Additionally, the solutions to the 93rd and 94th Challenges will be posted by next Wednesday at the latest. (I am out of town for the most of this week, but I will work on them when I return.) I am feeling much better now, and I hope to get caught up as soon as possible.

    Starting with (potentially) the next week's challenge, the Weekly Math Challenge will adopt a problem submission process. I believe doing so will help me decide whether the submission process can continue indefinitely in the future and also have the benefit of helping the Challenges 95-100 be especially creative and enjoyable. If you are interested, please email an original problem and its solution to letssolvemathproblems7@gmail.com. =)
    * I did not think it was possible for me to get a cold after recovering from one a couple weeks ago, but I was unfortunately proven wrong. I will post the solution to the last week's challenge as soon as my sore throat recovers enough for a long term filming.
    ** This video was re-uploaded because there was an error in the original problem statement: it did not specify that each group must be nonempty.

    • Santhosh Kumar
      Santhosh Kumar 3 months ago

      @letsSolvemathproblems I don't think so your are an highschool student and this year only your going to college 🤔🤔🤔🤔. Please repay to question 🙏🙏

  • Hrs
    Hrs 3 months ago

    check jee advanced from india

  • matyourin
    matyourin 3 months ago

    I have a weekly problem suggestion:
    If you have 3 circles on an euclidian plane, not intersecting, all different size, you can draw 2 tangent lines for each pair of these circles. I mean you draw 2 lines, each touching 2 of the circles, for each pair of circles. That will be 6 lines in total.
    Prove, that the 3 intersecting points of these 6 lines are all on one straight line.

  • Th LEBL
    Th LEBL 3 months ago +1

    1:49 it's me :o !!

  • Yassine Zaoui
    Yassine Zaoui 3 months ago

    I'm not sure that I found it and I m sorry because it's not simplified so that we can make a deduction for n>=2.
    So to start with, let's consider A and B the two groups with even number of people and A1,A2 and B1,B2 the two subgroups respictivily of A and B.
    We notice that the number of people in each of A1,B1 and A2,B2 is n so we can consider another process of dividing 2n people :
    Let C and D be 2 groups of n people each and we will divide each one into two subgroups ,for C, C1 with m people and C2 with n-m people and for D we have D1 with m people and D2 with n-m people such that m in 1..n-1.
    The numbers of ways to divide 2n people into 2 equal grps is 2nCn and for each value of m we will have mCn possibility of subgroups in each one in C1 and D1.
    At the end we conclude that
    a(n)=2nCn [ (nC1)²+...+(nCn-1)²]
    I have calculated this for some value of n (2, 3 and 8) and the sqrt was nearly 2nCn - 1.

    • Yassine Zaoui
      Yassine Zaoui 3 months ago

      I have just checked the internet and seemingly we can say that (nCm)²+...+(nCn-1)²=(2nCn)-2 and this according to cauchy product or something like that. We didn't study it yet at school 😅 I'm 17 and I have recently learnt about combinations and arrangements.
      Anyways, so
      Sqrt(an)= (2nCn)*sqrt(1*(1-(2/2nCn)) which is quite close to 2nCn-1 because for a=2nCn we have (a-1)²=a²-2a+1=a(n)+1 approximitly a(n).

  • Brian Lamptey
    Brian Lamptey 3 months ago

    Ummm, you can't split 2n people into two even numbered groups of people unless n is even.

    • Brian Lamptey
      Brian Lamptey 3 months ago

      @LetsSolveMathProblems My mistake, I was thinking of two equal groups.

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago

      If n = 3, 2n = 6 people can be split into a group of 2 and a group of 4.

  • 李琮韋
    李琮韋 3 months ago

    a_n=sum(k=1,n){C(2n,2k)C(2k,k)C(2n-2k,n-k)}=[C(2n,n)-1]^2-1

  • SUPRATIM SANTRA
    SUPRATIM SANTRA 3 months ago

    Sir it is really amazing... Plz keep on it.... I am of ur follower

  • Arthur Gershon
    Arthur Gershon 3 months ago

    It is equivalent to first divide the 2n people into equal groups of n AND THEN choose a subgroup of the same size from each group. The two chosen subgroups correspond to an equipartition of the first group of even size chosen in the given procedure, and the remainder corresponds to an equipartition of the second group of even size.

    This gives
    a[n_] = Sum[Binomial[2n, n] * (Binomial[n, k])^2, {k, 1, n - 1}]
    ... == Binomial[2n, n]*(Binomial[2n, n] - 2)
    ... == (Binomial[2n, n] - 1)^2 - 1.

    Note that x^2 > x^2 - 1 > (x - 1/2)^2 if and only if x > 5/4, and so Round[Sqrt[a[n]]] == Binomial[2n, n] - 1 if and only if Binomial[2n, n] - 1 > 5/4, which occurs if and only if n > 1.

  • Nicola C
    Nicola C 3 months ago

    aₙ=C(2n,2)C(2,1)C(2n-2,n-1)+C(2n,4)C(4,2)C(2n-4,n-2)+...+C(2n,2n-2)C(2n-2,n-1)C(2,1).
    That's because every partition of 2n elements into two distinct nonempty sets with an even number of elements can be made in C(2n,2)+C(2n,4)+... ways, but we have to multiply every term by the number of ways of partitioning a set into two different equal-in-size sets.
    We can compress it into
    aₙ=∑from k=1 to n-1 of C(2n,2k)C(2k,k)C(2n-2k,n-k), which can be simplified to
    aₙ=C(2n,n)((∑from k=0 to n of (C(n,k))²)-2).
    Now notice that the sum of the sqares of the binomials is C(2n,n).
    With that we are pretty much done, because we can write
    aₙ=C(2n,n)(C(2n,n)-2)=(C(2n,n))²-2C(2n,n)+1-1=(C(2n,n)-1)²-1.
    Therefore √(aₙ) is always very close to C(2n,n)-1 (you can check the relation of the problem holds for small n too, for n big enough C(2n,n)-1-√(aₙ) gets arbitrarily small) and we are done.

  • Xu Chen Tan
    Xu Chen Tan 3 months ago

    Let b_n = a_n + 2(2nCn) count the same thing but the two groups may be empty. We wish to show b_n = (2nCn)^2.
    Let the two groups be A, B and the 4 subgroups be A1, A2, B1, B2. We specify 2 sets, X and Y, of n people each. Note there are (2nCn)^2 ways to do this.
    Then X = A1 union B1, Y = A1 union B2 gives a bijection since A1, A2, B1, B2 are uniquely determined by X, Y and each choice of A1, A2, B1, B2 give a unique X, Y.
    Thus b_n = (2nCn)^2
    a_n = (2nCn)^2 - 2(2nCn)
    = (2nCn - 1)^2 - 1
    [sqrt(a_n)] = 2nCn - 1

  • Mokou Fujiwara
    Mokou Fujiwara 3 months ago

    Write combination function nCr as C(n,r)
    a_n = Sum(r=1 to n-1, C(2n,2r)*C(2r,r)*C(2(n-r),n-r))
    = Sum (r=1 to n-1, 2n!/(2r!*[2(n-r)]!) * 2r!/(r!)^2 * [2(n-r)]!/[(n-r)!]^2)
    = Sum(r=1 to n-1, 2n!/((r!)^2 * ((n-r)!^2))
    = Sum(r=1 to n-1, C(n,r)^2 * 2n! / (n!)^2)
    = C(2n,n) * (C(2n,n) - C(n,0)^2 - C(n,n)^2)
    = C(2n,n)^2 - 2C(2n,n) + 1 - 1
    = (C(2n,n) - 1)^2 - 1
    Round(sqrt(a_n)) = C(2n,n)-1
    =

    • Mokou Fujiwara
      Mokou Fujiwara 3 months ago

      This question I once thought it is hard, but after I found that first step is not required to form 2 equal groups, things are clear.
      First step: Choose 2r people to form first big group, that is C(2n,2r). The second group is formed by all people not in first group, has 2(n-r) people.
      Second step: Split 2 equal subgroup from each group. C(2r,r) for first group, C(2(n-r), (n-r)) for second group.
      First step and second step are independent events. 2 groups are split independently. Hence multiply all 3 combinations above for each r. Do you think that you're done? No, r range from 1 to n-1, remember not 0 to n as we cannot have empty big group! Do summation with this range, then we can do above computational process.

  • Jaime Araujo
    Jaime Araujo 3 months ago

    I beleive that I will go to the IMO...if someone offers.some tips I will be really grateful

    • Mokou Fujiwara
      Mokou Fujiwara 3 months ago

      @Jaime Araujo And there are several solutions already, with at least 2 different approaches. I have explained my own approach thoroughly (I hope).

    • Jaime Araujo
      Jaime Araujo 3 months ago

      @Mokou Fujiwara Thanks. but the only thing that I was searching was tip for the competition not to the challenge
      , but I still grateful

    • Mokou Fujiwara
      Mokou Fujiwara 3 months ago

      First division: 2 groups with even number of people. Not necessary equal in size.
      Second division: 2 sub-groups from a same group equal in size.
      Got it?

  • fabio alan
    fabio alan 3 months ago

    We want to express a_n as a sum of all the possibilities, so we can use the properties of factorial an such to get our answer.
    First, we choose 2k people from the 2n people (2nC2k) and get two groups, the first has 2k while the second one has 2(n-k) people. From here, we choose k people from the first group (2kCk) in order to divide them into the two subgroups, then we choose (n-k) people from the second one ((2n-2k)C(n-k)) to divide in two subgroups with equal quantity of people.

    So, the resulting sum is: a_n = S_{k =1}^{n-1}[2nC2k]*[2kCk]*[(2n-2k)C(n-k)] Pretty ugly at first, but we can simplify this by developing like this: a_n = S_{k =1}^{n-1}((2n)!/(2n-2k)!*(2k)!)*((2k)!/(k!*k!))*((2n-2k)!/(n-k)!*(n-k)!)

    We can simplify the (2k)! and the (2n-2k)! and get this: a_n = S_{k =1}^{n-1} ((2n)!/(k!*(n-k)!*k!*(n-k)!)). If we multiply and divide by n!*n!, we get: a_n = ((2n)!/n!*n!)*S_{k =1}^{n-1}(n!/k!*(n-k)!)(n!/(n-k)!*k!)=2nCn*S_{k =1}^{n-1}(nCk)^2.

    It is known that S_{k =0}^{n}(nCk)^2=2nCn, however we are missing the cases when k=0 and k=n in the sum. So we add and subtract then, resulting in: a_n = (2nCn)*S_{k =0}^{n}(nCk)^2 - 2*(2nCn)=(2nCn)^2-2*(2nCn)=(2nCn)^2-2*(2nCn)+1-1=((2nCn)-1)^2-1.

    So, sqrt{a_n}=sqrt{((2nCn)-1)^2-1}. Rounding up, we get sqrt{a_n}=(2nCn)-1

  • Rishav Gupta
    Rishav Gupta 3 months ago

    First we divide the set of 2n members into 2 groups with even
    members we can do it in (2n c 2r) ways
    Now we get two groups one with 2r elements and other with 2n-2r elements ,So no of subgroups of equal sizes we get from set of 2n elements is equal to
    (2n c 2r)*(2r c r)*(2n-2r c n-r)
    Solving this we get
    (2n c n) ((n c r ))^2
    Thus total ways is summing from r=1 to n-1
    (2n c n) can be taken out from summation and summing
    (n c r)^2 we get (2n c n) -2
    Thus total ways are
    (2n c n)^2-2(2n c n)=
    ((2n c n) -1)^2-1=a_n
    Thus [(a_n)^1/2]=((2n c n )-1)
    Hence Proved

  • Minh Cong Nguyen
    Minh Cong Nguyen 3 months ago

    a(n) = sum of C(2n,2i)*C(i,2i)*C(n-i, 2n-2i) for i from 1 to n-1
    a(n)= sum of (2n)!/(i!*(n-i)!)^2 for i from 1 to n-1
    a(n)= sum of (2n)!/(n!)^2 * (C(i)^2) for i from 1 to n-1
    a(n) = C(2n,n) * sum of C(i)^2 for i from 1 to n-1
    a(n) = C(2n,n) * (C(2n,n) -2 ), as the identity sum of C(i)^2 for i from 0 to n = C(2n,n) (which can be proven by the coefficient expansion of (1+x)^2n = (1+x)^n * (x+1)^n )
    Then round(sqrt(a(n))) = C(2n,n)-1

  • Aswini Banerjee
    Aswini Banerjee 3 months ago

    We can divide 2n people in groups of 2r and 2(n-r) in ²ⁿC₂ᵣ ways. Then we can divide group of 2r into subgroups of r and r in ²ʳCᵣ ways. For each division in group of 2r we can equally divide the remaining 2(n-r) people in C(2n-2r,n-r) subgroups.
    Thus aₙ =Σ²ⁿC₂ᵣ•²ʳCᵣ•C(2n-2r,n-r) from r=1 to n .
    Now expanding the nCr formula we get
    ²ⁿCₙ•Σ(n!)²/[(r!)²•(n-r)!²]
    = ²ⁿCₙ•Σ (ⁿCᵣ)² = aₙ
    now Σ (ⁿCᵣ)² from r= 1 to n is (²ⁿCₙ - 1)
    thus aₙ = ²ⁿCₙ•(²ⁿCₙ - 1)
    Now as n tends to a large number
    (²ⁿCₙ) tends to (²ⁿCₙ - 1)
    thus by rounding off √(aₙ) = (²ⁿCₙ - 1)

  • KRISHNA KAMALAKANNAN
    KRISHNA KAMALAKANNAN 3 months ago

    Call the number of people in the two groups 2k and 2n-2k. These groups get split into subgroups of size k, k, n-k, and n-k. There is another, equivalent way to do this process. You can first split the 2n people into 2 groups of size n. This can happen in (2n)C(n) ways. Next, you can split the two groups into subgroups of size k and n-k. This can be done in (n)C(k) * (n)C(k) = ( (n)C(k) )^2 ways. So the number of ways to do this entire process is (2n)C(n) * ( (n)C(k) )^2.
    Now we can let k range from 1 to n-1 in the sum k= 1...n-1 of (2n)C(n) * ( (n)C(k) )^2. After using a variant of Vandermonde's identity and pulling out a factor of (2n)C(n), you get (2n)C(n) ( (2n)C(n) - 2 ) = ( (2n)C(n) )^2 - 2 * (2n)C(n).
    Therefore a_n = ( (2n)C(n) )^2 - 2 * (2n)C(n).
    Notice that ( (2n)C(n) )^2 - 2 * (2n)C(n) is one less than ( (2n)C(n) - 1)^2. Therefore their square roots are also going to be very close. Therefore sqrt(a_n) is very close to sqrt(( (2n)C(n) - 1)^2 )) = (2n)C(n) - 1.
    Q.E.D.

  • Mohith S N Raju
    Mohith S N Raju 3 months ago +2

    a_n = nCr(nCr-2)
    consider the first group to be group A consisting of 2r elements and having subgroups a1 and a2 with r elements each . Similarly consider group B consisting of 2(n-r) elements and having subgroups a1 and a2 with (n-r) elements each.
    STEP1=now select n elements whose destined to be in either a1 or a3 (as the total number of elements in subgroups a1 and a3 is r+n-r=n) and the remaining n elements will end up in a2 or a4.
    thus there is 2nCn ways to do this
    STEP2=now the n elements selected is to be distributed in a1 a3 and a2 a4
    now the way this can be done is a1-1element a2-(n-1) elements
    for this we have to choose 1 element from n elements( selected in STEP 1) i.e. nC1
    now if a1 has 1 element a2 should also have 1 element and a4 (n-1) elements hence we now have to choose one element from n UNselected elements (from step 1) which is again nC1 ways
    thus in total nC1*nC1 ways
    similarly
    if a1-2element a2-(n-2) elements
    for this we have to choose 2 element from n elements( selected in STEP 1) i.e. nC2
    now if a1 has 2 element a2 should also have 2 element and a4 (n-2) elements hence we now have to choose two elements from n UNselected elements (from step 1) which is again nC2 ways
    thus in total nC2*nC2 ways
    .
    .
    .
    if a1-(n-1)element a2-(1) elements
    for this we have to choose (n-1) element from n elements( selected in STEP 1) i.e. nC(n-1)
    now if a1 has (n-1) element a2 should also have (n-1) element and a4 1 elements hence we now have to choose (n-1) elements from n UNselected elements (from step 1) which is again nC(n-1) ways
    thus in total nC(n-1)*nC(n-1) ways

    total for step 2= nC1*nC1 + nC2*nC2 + ..... nC(n-1)*nC(n-1)= 2nCn - 2

    GRAND TOTAL
    ANS=(2nCn)^2 -2(2nCn)
    ANS=(2nCn)^2 -2(2nCn)
    +1-1
    ANS=[2nCn-1]^2 -1
    {ANS}^0.5 rounds up to [2nCn-1]

    • Mohith S N Raju
      Mohith S N Raju 3 months ago

      @Mokou Fujiwara check out KRISHNA KAMALAKANNAN approach (in the comments) he has the same approach as I do
      may be that will help to make it more clear

    • Mokou Fujiwara
      Mokou Fujiwara 3 months ago

      Although I can't really understand your approach, I get exact same result with you.

  • Nitro Zox
    Nitro Zox 3 months ago +2

    For any arbitrary r belonging to 0 to 2n, let's say that we form of a group of 2r people. The number of ways of doing so is to just pick out any 2r people from 2n , so {2n C 2r}, here C stands form binomial coefficient.
    Now we have two groups of 2r and 2n-2r people. To make equal subgroups, we pick r from the 2r and n-r from the 2n-2r.
    So total number of ways, by the multiplication theorem is {2n C 2r} ×{ 2r C r } × { 2n -2r C n-r}.
    Now , on simplifying this value we get : { 2n C n} × {nCr}^2
    Now notice that we don't need empty groups, so we sum this value from r = 1 to n-1 .
    Use the fact that The sum of {nCr}^2 from r = 0 to n is {2nCn} which is proved easily by permutation and combination
    But we need to exclude the coefficients of {nC0} and {nCn}
    Hence our sum results in {2n C n} × ({2n C n } - 2}
    Which on forming perfect square and taking root gives the desired result.