Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By Idea

Thread: Groups puzzle

  1. #1
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,600
    Thanks
    300

    Groups puzzle

    Found this problem/puzzle:

    100 balls are divided into groups.
    The difference between any two groups is at most 2.
    In how many ways can this be done?
    Permutations are not considered as different.

    Example: Using 6 balls, the solution is 9:
    (1,1,1,1,1,1), (1,1,1,1,2), (1,1,2,2),
    (1,1,1,3), (1,2,3), (2,2,2),
    (2,4), (3,3), (6).

    I simply don't understand what's being asked.
    Like, why is difference between (1,1,1,1,1,1) and (1,2,3) at most 2?

    Can anybody explain it?
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2014
    From
    Illinois
    Posts
    261
    Thanks
    90

    Re: Groups puzzle

    I interpret this to mean that no group of the set may differ in how many balls are in that group by more than 2 from any other group. Thus (1,1,1,1,1,1) means there are 6 groups of 1 ball each, and (1,2,3) means there is one group of 1, one group of 2, and one group of 3. In both of these examples the number of balls in each group is within two of all the other groups. An arrangement that would not be allowed is (1,1,4) because there is a group of 4, which contains 3 balls more than the groups of 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,600
    Thanks
    300

    Re: Groups puzzle

    Ahhhhhh.....thanks Chip. Clear.
    So in the example, 1,1,4 and 1,5 don't qualify...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    677
    Thanks
    305

    Re: Groups puzzle

    we are looking at integer partitions of an even integer 2n

    \left(a_1,a_2,\text{...},a_r\right)

    a_1\geq  a_2\geq  \text{...}\geq  a_r\geq  1

    \sum _{i=1}^r a_i=2n with a condition 0\leq a_1-a_r\leq  2

    if g(2n) is the number of such partitions then

    g(2n)=g(2n-2)+n+1 with g(0)=0

    From this recursive relation we get g(2n)=\frac{n(n+3)}{2}

    so that g(100)=\frac{50*53}{2}=1325

    To prove the recursive relation, verify that the mapping

    \left(a_1,a_2,\text{...},a_r\right) \rightarrow  \left(a_2,a_3,\text{...},a_{r},a_1-2\right)

    is a one-to-one correspondence between partitions of 2n-2 and

    those partitions of 2n for which a_1\geq 3

    and that there are n+1 partitions of 2n with a_1\leq  2
    Last edited by Idea; Aug 27th 2016 at 01:55 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,600
    Thanks
    300

    Re: Groups puzzle

    Isn't the whole thing as simple as this:
    Code:
    n : 0 1   2 3   4 5   6 7    8  9  .......  100  101
    w : 0 1[1]2 3[2]5 6[3]9 10[4]14 15 ....... 1325 1326
    tn:     1     3     6     10
    w = ways
    tn = triangular numbers
    [] = increase from consecutive odd to even n's

    Using that fact then formula = n(n + 6) / 8 where n is even.
    n = 100: 100 * 106 / 8 = 1325

    If n is odd, do n-1 and add 1.

    Perhaps what you're showing is the same thing;
    I am not mathematically advanced enough to understand
    your advanced "language".
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    677
    Thanks
    305

    Re: Groups puzzle

    Quote Originally Posted by DenisB View Post
    Isn't the whole thing as simple as this:
    Code:
    n : 0 1   2 3   4 5   6 7    8  9  .......  100  101
    w : 0 1[1]2 3[2]5 6[3]9 10[4]14 15 ....... 1325 1326
    tn:     1     3     6     10
    w = ways
    tn = triangular numbers
    [] = increase from consecutive odd to even n's

    Using that fact then formula = n(n + 6) / 8 where n is even.
    n = 100: 100 * 106 / 8 = 1325

    If n is odd, do n-1 and add 1.

    Perhaps what you're showing is the same thing;
    I am not mathematically advanced enough to understand
    your advanced "language".
    Correct, we are doing the same thing

    \frac{n(n+6)}{8} (n even)

    \frac{(n+1)(n+3)}{8} (n odd)

    I was also giving a proof as to why these are the right formulas
    Last edited by Idea; Aug 29th 2016 at 08:59 AM.
    Thanks from DenisB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 8
    Last Post: Mar 30th 2012, 04:53 PM
  2. About minimal normal groups and subnormal groups
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: Oct 20th 2011, 01:53 PM
  3. Quotient Groups - Infinite Groups, finite orders
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Aug 11th 2010, 07:07 AM
  4. free groups, finitely generated groups
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: May 23rd 2009, 03:31 AM
  5. Order of groups involving conjugates and abelian groups
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Feb 5th 2009, 08:55 PM

Search Tags


/mathhelpforum @mathhelpforum