1. ## 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.

2. ## 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.

3. ## Re: Groups puzzle

Ahhhhhh.....thanks Chip. Clear.
So in the example, 1,1,4 and 1,5 don't qualify...

4. ## 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$

5. ## 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

6. ## Re: Groups puzzle

Originally Posted by DenisB
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
$\frac{n(n+6)}{8}$ (n even)
$\frac{(n+1)(n+3)}{8}$ (n odd)