help permutations and combinations question (1 Viewer)

[happypolarbear944]

There are 50 balls that are colored either, red, yellow, green, purple, or blue. There must be at least 4 balls of each color and no color can be on more than 1/3 of the balls. How many combinations are there?

 

[liamkk112]

we know that there are at least 4 balls of each colour, and there are five colours, so there are 20 balls already fixed in colour. this reduces the problem to 30 balls that can be coloured 5 different colours, and no colour can be on more than 1/3 of the balls. i am not good at combinatorics lol but hopefully this helps, i will try to come up with a solution

 

[ISAM77]

It's been a while since I did this topic. Dunno if I'm right, but hoping to help you at least.

As Liam said, since there must be at least 4 balls of each colour; 4x5=20, gives us 20 balls fixed in place. Hence, we have to find the remaining combinations.

Since 1 colour can be no more than 1/3 of the balls. 1/3 * 50 = 16.67. 16 is the maximum for one colour out of the 50. But 4 of each have already been chosen to meet the minimum requirement. Hence, 12 is the maximum for one colour in the remaining 30 slots. We could say we have 12 red balls to choose from, 12 yellow, 12 green, 12 purple, and 12 blue; which is 60 balls in total. Now Choose 30 out of these 60 for all possible combinations.

I'm not confident about my answer as I haven't touched this topic in months. But if I am right:
60C30 = 1.18 * 10^17 would be my final answer.

 

[s97127]

There are 50 balls that are colored either, red, yellow, green, purple, or blue. There must be at least 4 balls of each color and no color can be on more than 1/3 of the balls. How many combinations are there?

I'm going to give this a try tonight. Where did you get this problem from?

 

[s97127]

My answer is 17,151. Is it correct?

 

[liamkk112]

It's been a while since I did this topic. Dunno if I'm right, but hoping to help you at least.

As Liam said, since there must be at least 4 balls of each colour; 4x5=20, gives us 20 balls fixed in place. Hence, we have to find the remaining combinations.

Since 1 colour can be no more than 1/3 of the balls. 1/3 * 50 = 16.67. 16 is the maximum for one colour out of the 50. But 4 of each have already been chosen to meet the minimum requirement. Hence, 12 is the maximum for one colour in the remaining 30 slots. We could say we have 12 red balls to choose from, 12 yellow, 12 green, 12 purple, and 12 blue; which is 60 balls in total. Now Choose 30 out of these 60 for all possible combinations.

I'm not confident about my answer as I haven't touched this topic in months. But if I am right:
60C30 = 1.18 * 10^17 would be my final answer.

i think this is wrong, there are 50 balls not 60. also u havent considered the case where one colour does not take up 1/3 of the balls, eg 10 10 10 10 10 instead. tbh this question is really hard bc theres so many different cases to consider, the 1/3 restriction is kinda crazy

 

[happypolarbear944]

bump!

 

[ISAM77]

bump!

Do you have the final answer?

 

[ISAM77]

There are 50 balls that are colored either, red, yellow, green, purple, or blue. There must be at least 4 balls of each color and no color can be on more than 1/3 of the balls. How many combinations are there?

@Luukas.2 . Reckon you could give this a crack if you have time pls?

 

[happypolarbear944]

Do you have the final answer?

really sorry, but i don't have the final answer

 

[Luukas.2]

The problem is finding the number of different solutions of the equation

​

where is the number of red balls, etc, subject to the constraints that:

• 
• 
• 

Equations like this are called Diophantine equations and the number of solutions can be counted by the "stars and bars" method - neither of which is formally in any HSC course. Without the constraints, the number of combinations / solutions would simply be:

​

Taking into account the constraint that there must be at least 4 of each colour, and noting that the stars-and-bars approach is designed for at least one of each, we can transform using (and similar), so that is the number of red balls more than 3, so that the minimum value of is 1, consistent with how stars-and-bars counting works. This yields:

​

The number of solutions here is then

​

However, this does not account for the constraint that , etc. We now need to count the cases where one or more colours would have too many balls, and subtract those.

Can anyone complete the solution from here?

 

[s97127]

really sorry, but i don't have the final answer

Where did you get this problem from?

 

[happypolarbear944]

Where did you get this problem from?

idk friend gave it to me

 

[s97127]

The problem is finding the number of different solutions of the equation

​

where is the number of red balls, etc, subject to the constraints that:

• 
• 
• 

Equations like this are called Diophantine equations and the number of solutions can be counted by the "stars and bars" method - neither of which is formally in any HSC course. Without the constraints, the number of combinations / solutions would simply be:

​

Taking into account the constraint that there must be at least 4 of each colour, and noting that the stars-and-bars approach is designed for at least one of each, we can transform using (and similar), so that is the number of red balls more than 3, so that the minimum value of is 1, consistent with how stars-and-bars counting works. This yields:

​

The number of solutions here is then

​

However, this does not account for the constraint that , etc. We now need to count the cases where one or more colours would have too many balls, and subtract those.

Can anyone complete the solution from here?

46376 - (5*5985 -10*70) = 17151

 

[Luukas.2]

Carrying on from my earlier post, we had:

​

where is the number of red balls, etc, subject to the constraints that:

• 
• 
• 

Equations like this are called Diophantine equations and the number of solutions can be counted by the "stars and bars" method - neither of which is formally in any HSC course. Without the constraints, the number of combinations / solutions would simply be:

​

Taking into account the constraint that there must be at least 4 of each colour, and noting that the stars-and-bars approach is designed for at least one of each, we can transform using (and similar), so that is the number of red balls more than 3, so that the minimum value of is 1, consistent with how stars-and-bars counting works. This yields:

​

The number of solutions here is then

​

However, this does not account for the constraint that , etc. We now need to count the cases where one or more colours would have too many balls, and subtract those.

Suppose we set the number or red balls, [text]r[/tex] to be at least 17, producing an invalid solution:

​

The number of cases with 17 or more of the red balls is

​

This calculation includes cases where two of the colours exceed 17 balls because a solution like

​

is valid. However, whilst the red exceding 17 is mandated, the colour of the other is not ( is equally valid). Multiplying by the options for the fixed ball will double count the two-exceed-17 cases, so we need to look at the case where two colours (say, red and yellow) both have 17 or more balls:

​

The number of cases with 17 or more red and yellow is then

​

which is also the number of any two-balls-exceeds-17 case.

The number with exactly one colour having 17 or more balls is then

​

as we need to remove the yellow, pink, green, and blue exceeding 17 balls from the red base case.

It follows that the total number of possibilities is

​

which matches @s97127's answer exactly.

46376 - (5*5985 -10*70) = 17151

 

[ISAM77]

yeah, nah. I've done all combinatorics questions in the cambridge y11 ext 1 book and this isn't like anything I've seen before. Sometime in future, I'll have a look at what stars and bars is. Thx always, Luukas

 

[Luukas.2]

Suppose we had 10 balls of the five colours with no restrictions other than there must be at least 1 of each colour.

Imagine the colours as different bins, into which we put some number of each colour - blue, green, pink, red yellow (BGPRY).

A solution like B = 3, G = 1, P = 2, R = 3, Y = 1 is a solution of B + G + P + R + Y = 10. It can be represented as:

* * * | * | * * | * * * | *​

which is 10 stars for the ten balls and four bars to separate bin 1, bin 2, bin 3, bin 4, and bin 5.

We need to place the four bars in between the stars, but must have a star to start and to end, and no consecutive bars (so no empty bins). There are thus 10 - 1 = 9 places to out the bars and 5 - 1 = 4 bars to place, hence the number of combinations is:

​

 

[ISAM77]

Suppose we had 10 balls of the five colours with no restrictions other than there must be at least 1 of each colour.

Imagine the colours as different bins, into which we put some number of each colour - blue, green, pink, red yellow (BGPRY).

A solution like B = 3, G = 1, P = 2, R = 3, Y = 1 is a solution of B + G + P + R + Y = 10. It can be represented as:

* * * | * | * * | * * * | *​

which is 10 stars for the ten balls and four bars to separate bin 1, bin 2, bin 3, bin 4, and bin 5.

We need to place the four bars in between the stars, but must have a star to start and to end, and no consecutive bars (so no empty bins). There are thus 10 - 1 = 9 places to out the bars and 5 - 1 = 4 bars to place, hence the number of combinations is:

​

This was really intuitive and easy to follow. Can do the original question now thx to this. Good stuff!