please five explanation

[namitb]

How many ways can 30 identical balls be divided into 3 groups??

[e.cartman]

are groups distinguishable?

[Nyssa]

IMO 19

 

The Groups will be (1,1,28),(1,2,27),(2,2,26)…..(9,10,11)(10,10,10)

So take the last group in the above sets... it can have a maximum of 28 and minimum of 10.

 

I'm assuming the 3 groups are not distinguishable.

 

I could be wrong. What is the OA ?

[osuguy]

since there are no restriction:

1st ball can be placed in one of the 3 groups - 3 choices

2nd ball can be placed in one of the 3 groups - 3 choices

3rd ball can be placed in one of the 3 groups - 3 choices

and so on.....

so, total number of choices.... 3^30

(i am assuming a group can have zero ball as the question does not have any restriction). any comments?

[e.cartman]

Imo, 3^30 would be wrong for case of identical balls. Since by nature you cannot tell one ball from the next. So although the balls have the choices like you stated. Many of the arrangements look the same to humans and so right answer would be much smaller, along the lines of Nyssa I think.

[digitaljinx]

are there answer choices with this problem? might be easier to solve that way but i got 78. There has to be an easier way to solve this than to list all the options, which is what i did?

[digitaljinx]

nyssa - what about (1,3,26) (1,4,25)... and there are 14 just for this group. the next group starts at 2,2,26 and there are 13 options in this group. the pattern stops at (10,10,10) because the process will repeat.

[axeman]

29*14

 

Lets consider the groups to be distinguishable and each group has at least one ball at all times ( else there won't be 3 groups). So in that case, the minimum no. of combinations possible will be 28 ( if take the first group as a reference group, then it can have 1 - 28 balls ). Now lets go back from max. balls possible in a group to the minimum. If group 1 has 28 balls, there is only one possibility for the other groups ( 1,1 ). If group 1 has 27 balls then there are 2 combinations for the other groups ( 1,2 ) and (2,1). Extending this we get the total no. of combinations to be 1 + 2 +3 +...28. Or n(n + 1)/2 where n is the maximum no. of balls that a group can have. in this case it'll be 29*14. I tried this with 6 balls and 3 groups and it seems to be working. But not sure of the principle behind this coz I can't think of a formula to prove this.

[digitaljinx]

The problem with this approach is that the balls are identical so 1,2,27 is the same as 2,1,27. Maybe?

[shyamprasadrao]

namit OA, and if you have the official explanation alsoo!!

[bose]

if each group has equal number of balls then ans is (30c10 20c10 10c10 )/3!

if each group can have any # of balls then ans is (n+r-1)C (r-1)=(33-1)C(3-1)=32C2

[amitabh007]

30c10/10!

[genius_in_the_gene]

Imo 3^30.

[Ralph303]

I think that the answer is 406 if order does matter, and 56 if order does not.

 

 

The way I am reading it is you need 3 groups, so you have to have at least one in each group, thus max group size is 28, min is 1. I disagree with 3^30 because that would require the same physical ball to be in different groups at the same time, i.e., at the extreme end you have all 30 balls in all 3 groups simultaneously!

 

If order does matter, as in (27,2,1) and (27,1,2) count as two arrangements, then there are 1+2+3+...28 possibilities, because there is exactly 1 way if the first group has 28, 2 if the first group is 27 (see examples above), and so on. This can be expressed as [(n-2)^2+(n-2)]/2

 

 

If order does not matter, then there is still exactly one arrangement for (28,1,1). When the first group is 27, there is only one unique arrangement, since (27,2,1) is equivalent to (27,1,2). Following this pattern, we can see a unique group is any arrangement such that: G1>=G2>=G3. If there is an arrangement that is not monotonically decreasing, then we know it is not unique since it was enumerated as a decreasing set previously.

 

Moving on to 26 as the first group, we have 2 possibilities, namely:

(26,3,1) and

(26,2,2)

 

Similarly, for 25 balls in the first group, we have:

(25,4,1)

(25,3,2)

...note that the next step in the pattern will be a duplicate, namely (25,2,3), so we can move on to the next step

 

With 24 in the first group, there are three arrangements:

24,5,1

24,4,2

24,3,3

By the same token, there will also be 3 new arrangements with 23 in the first group, 4 new arrangements for each of 22 & 21, and so on.

 

In other words, starting at n-2, the possible total arrangements is the sum of the following series:

1,1,2,2,3,3,...M

 

where M is the term such that we get to n-(n/2).

So for n=30 stop at the 14th term, since we want to get from (n-2), or 28, through n-15, or 15. We can stop at the n/2 because continuing the enumeration pattern outlined above yields only duplicates. For example, (14,15,1) was already counted as (15,14,1).

 

Notice that the series counting unique arrangements resembles the series that counted ordered arrangements. The sum of the series up to the Mth term will be (M/2)^2 + M/2, as long as M/2 is an even integer i.e., M needs to be divisible by 4. In the case of n=30:

M=(n-2)/2=(30-2)/2=28/2=14,

so M/2 = 7

 

 

7^2+7 = 49+7 = 56

 

 

I suspect that there is a better formula out there for any N objects of X types arranged into R groups, which would certainly make this problem type easier to solve. I haven't looked at series and their sums for over 10 yrs though, so I don't really remember how to work with them.

This was really tough. Can you advise what problem set is this from???:hmm:

 

Maybe I am wrong, or there is a better solution. But I think this is correct unless I made an arithmetic mistake somewhere.

[gmatbestshot]

Hi,

I did a search of this and found this problem here:

 

assorted cat questions « vasu

 

OA choices are:

a) 146

b) 75

c) 130

d) 91

[Ralph303]

Ah yeh beat me LOL... OK the true and correct answer is B.

 

Thanks to this answer I can see what I did wrong now. I was starting my pattern with (n,29-n,1), so when I got to 14 it seemed the pattern would repeat in reverse with (14,15,1) which had already been accounted for. What I missed was the groups of (14,14,2); (14,13,3)...(13,13,4); and so on. Adding these in, we get 75. As I suspected, not the most elegant solution. I should have gone with increasing groups to avoid the trap that got me. If something like this ever came up for me on a real test, I would congratulate myself on having gotten to a level that was obviously ridiculously above my normal range, and taken a wild guess. But that's just me.

 

Oh well, I have never studied any problem like this (just regular permutations and combos) so I am grateful I got a chance to learn something. Where do these types of problems come from? Do they have any practical use in e.g., engineering?

[ashk29]

Its like finding the solutions to the equation X+Y+Z = 30 , where X,Y,Z are integers and not equal to zero

 

ans = 75

[zeal_huyi]

How many ways can 30 identical balls be divided into 3 groups??

 

Imagine you place the balls in a straight line with gaps between them.

(* = BALL)

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Here are 30 balls.

 

You need to divide them up into 3 groups. What you can do is start placing dividers into the gaps. Suppose you place a divider into one of the gaps, you then already divided the balls into 2 groups: the balls left of the divider as one group and the balls right of the divider as another group.

(| = divider)

* * * * * * * * * | * * * * * * * * * * * * * * * * * * * * *

 

 

So you need 2 dividers to accomplish the task.

* * * * * * * * | * * * * * * * * * * * * * * * | * * * * * * *

 

If you think about what you're essentially doing, you're just CHOOSING the gaps to place your dividers. There are 30-1=29 gaps, and you need 3-1=2 dividers. Therefore 29 choose 2 is your answer.