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 $\displaystyle 2n$

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

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

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

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

$\displaystyle g(2n)=g(2n-2)+n+1$ with $\displaystyle g(0)=0$

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

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

To prove the recursive relation, verify that the mapping

$\displaystyle \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 $\displaystyle 2n-2$ and

those partitions of $\displaystyle 2n$ for which $\displaystyle a_1\geq 3$

and that there are $\displaystyle n+1$ partitions of $\displaystyle 2n$ with $\displaystyle 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
$\displaystyle \frac{n(n+6)}{8}$ (n even)
$\displaystyle \frac{(n+1)(n+3)}{8}$ (n odd)