Cups Problem (Combinations)

[AlexBaylor]

There is an empty cabinet that needs to get filled with cups. It can fit three rows of five with two cups high. With thirty gray and thirty yellow cups at your disposal, how many possible combinations of cups (that don’t use more than thirty cups total) are there that don’t fulfill the pattern? Show your work.

Pattern Rules

1. The middle spot in each row must be empty or gray*
2. The other spots must be empty or yellow*
3. Each row across must be symmetrical by height (0 cups, 1 cup, 2 cups)

*Only the completely visible cup (One cup high then that cup, otherwise just the top cup) counts




Example of a working pattern...

 

[AlexBaylor]

I've solved the problem up to having a number of 9 cups with either color and so currently I'm at 10 solutions that don't work

 

[Dr.Peterson]

My first step would be to rewrite the problem so that it is easier to follow; it isn't very clearly written. For example, the asterisks should not be needed.

Then I'd try making a simpler problem that is easier to work with, but equivalent. For example, since each row must be symmetrical, you could consider only three stacks per row (the last two being repeats of the first two, and so requiring no additional choices).

Then show us what you have done. It appears that you are doing a separate calculation for each total number of cups, which may not be the most efficient way to solve the problem. We may be able to give you new ideas to try. We won't, of course, just give you the answer.

 

[AlexBaylor]

I actually made this problem for my friends because this is how I sort my cups in my kitchen. I was trying to post this on sites because I don't know an efficient way to solve my own problem. Up to this point, I've just been checking every solution because I don't know a better way to do that with all of the rules and regulations.

 

[AlexBaylor]

I actually made this problem for my friends because this is how I sort my cups in my kitchen. I was trying to post this on sites because I don't know an efficient way to solve my own problem. Up to this point, I've just been checking every solution because I don't know a better way to do that with all of the rules and regulations. View attachment 13024

I'm only 11% done with checking every solution and I'm doing it on a google spreadsheet

 

[AlexBaylor]

I'm only 11% done with checking every solution

basically stumped myself

 

[Dr.Peterson]

I can't tell what you mean by "checking every solution", so I don't know how inefficient you are being. Do you know any math that would be useful? If you want help, you need to show some actual work, not just tell us how little you've done.

In any case, have you tried doing what I suggested, and clarifying the rules?

Here's a start. You say, "The middle spot in each row must be empty or gray* - *Only the completely visible cup (One cup high then that cup, otherwise just the top cup) counts ". As I interpret this, it means that the middle spot might contain either (a) nothing, or (b) one gray cup, or (c) any cup (gray or yellow) with a gray cup on top. That boils down to only four possibilities: _, G, YG, GG. Am I right?

Another thing you can do, since you asked for the number of arrangements that don't fit the pattern (why??), is to first find the total number of ways to arrange cups, ignoring your pattern. Start with one row, then you can just multiply.

And here's an introduction to what you might do: How many ways are there to place cups if you ignore color (considering only the number of cups in each pile, and not requiring symmetry)? Answer: there are 3 ways to fill each pile (0, 1, or 2 cups), and 15 piles, for a total of 3^15 = 14,348,907. That's ignoring color! So I hope you aren't just listing all ways ...

 

[AlexBaylor]

I ask how many don't fit the solution because my goal is to find an approximate probability for the chances I can't sort my cups in that specific pattern (I've never gotten that result when putting the cups away for three years, so I was curious of the chances for it to happen). Sorry to annoy you with my lack of providing my work, I've been doing it exclusively on a Google spreadsheet and didn't feel that comfortable giving access to it at first (here it is https://docs.google.com/spreadsheets/d/1C_Emh3Ooxf2DDhA1EIxmLkXHyQ9iNinTUJztqJPd2n0/edit?usp=sharing). I know that there are 465 possibilities that I have to check through though ({1+2+3+4...+30} If this method is unclear to you just look at the spreadsheet and that might clear up some of the misunderstandings). I have been posting this problem on Math sites to see if anyone has a more efficient way to solve the problem because I wasn't able to figure one out. Thanks for all your help so far and I hope eventually I can solve this problem.

 

[AlexBaylor]

I ask how many don't fit the solution because my goal is to find an approximate probability for the chances I can't sort my cups in that specific pattern (I've never gotten that result when putting the cups away for three years, so I was curious of the chances for it to happen). Sorry to annoy you with my lack of providing my work, I've been doing it exclusively on a Google spreadsheet and didn't feel that comfortable giving access to it at first (here it is https://docs.google.com/spreadsheets/d/1C_Emh3Ooxf2DDhA1EIxmLkXHyQ9iNinTUJztqJPd2n0/edit?usp=sharing). I know that there are 465 possibilities that I have to check through though ({1+2+3+4...+30} If this method is unclear to you just look at the spreadsheet and that might clear up some of the misunderstandings). I have been posting this problem on Math sites to see if anyone has a more efficient way to solve the problem because I wasn't able to figure one out. Thanks for all your help so far and I hope eventually I can solve this problem.

I just figured out that I was neglecting that there are 30 more possibilities than my math (It's actually 2+3+4...+31), so there are 495 possibilities for me to look through with my inefficient method

 

[JeffM]

I am going to assume that this is not for a class. This is a problem in combinatorics, which is about counting efficiently.

Suppose the rules only let you come up with 2 possible patterns in a single row, A or B. Then the total number of possible patterns would be 2 * 2 * 2 = 8. AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB. So we can generalize that the total number of patterns will equal r * r * r, where r is the number of possible patterns in a single row. So we need to find the number of patterns possible in a single row. With me so far?

There are three possibilities in terms of stacking. No stacks, 1 high, or 2 high. How many ways can you have no cups? Just one way. How many ways can you have them 1 high? Well, you can have a gray in the middle, and if that is true, you must have yellow in every other spot in that row to ensure that the row is symmetric in terms of height. Or you can have an empty in the middle, in which case you must have empty in every other spot, which is the no cups situation already counted. So there are two ways if we have no stacking or stacking one high.

If we have them stacked 2 high, then the middle spot must be grey on top, and the others must be yellow on top. So there is just one way with stacked 2 high.

Thus there are 3 ways to arrange each row, and there are 3 rows. So there are 27 different possible patterns that fit the rules.

Now subtract 27 from the total number of ways that the rows can be arranged, and you have the number of patterns that break the rules. It is going to be an immense number compared to 27.

 

[JeffM]

This is quick and dirty.

There are seven ways to fill each slot: no cup, yellow cup, grey cup, yellow- yellow stack, yellow-grey stack, grey-yellow stack, and grey-grey stack. And there are 15 slots. So the total number of possibilities is

[MATH]t = 7^{15} \implies log(t) = 15log(7) \approx 12.68 \implies t = 4,700,000,000,000.[/MATH]
So the probability that sticking cups in at random will follow the rules is 0 for all practical purposes.

 

[Dr.Peterson]

I ask how many don't fit the solution because my goal is to find an approximate probability for the chances I can't sort my cups in that specific pattern (I've never gotten that result when putting the cups away for three years, so I was curious of the chances for it to happen).

We ask people to include the entire problem they are really working on, because often the piece they show us is not part of a good method to solve their real problem. So I'm glad you've said more here.

But I'm wondering whether you meant exactly what you said here. As written, this is asking for the probability that there is no way to organize, the way you like, the particular set of cups you have at the moment; but the original question doesn't deal with whether there is a solution for a particular set of cups, just with whether a particular arrangement is a solution. So that sounds like you want the probability that a random arrangement fits/doesn't fit your pattern. Which are you really looking for?

It happens that when I do dishes I have similar thoughts about how I arrange cups in the drainer, and my thought is generally, can any set of cups I have be arranged in a symmetrical manner, or not? It is never about the probability that a random arrangement is symmetrical. (I allow any kind of symmetry. And no, I'm not obsessive about this; my mind is just running faster than my hands, and needs something to think about.)

The probability that a random set of cups can be arranged nicely will be far higher than the probability that a random arrangement is nice.

 

[AlexBaylor]

I am going to assume that this is not for a class. This is a problem in combinatorics, which is about counting efficiently.

Suppose the rules only let you come up with 2 possible patterns in a single row, A or B. Then the total number of possible patterns would be 2 * 2 * 2 = 8. AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB. So we can generalize that the total number of patterns will equal r * r * r, where r is the number of possible patterns in a single row. So we need to find the number of patterns possible in a single row. With me so far?

There are three possibilities in terms of stacking. No stacks, 1 high, or 2 high. How many ways can you have no cups? Just one way. How many ways can you have them 1 high? Well, you can have a gray in the middle, and if that is true, you must have yellow in every other spot in that row to ensure that the row is symmetric in terms of height. Or you can have an empty in the middle, in which case you must have empty in every other spot, which is the no cups situation already counted. So there are two ways if we have no stacking or stacking one high.

If we have them stacked 2 high, then the middle spot must be grey on top, and the others must be yellow on top. So there is just one way with stacked 2 high.

Thus there are 3 ways to arrange each row, and there are 3 rows. So there are 27 different possible patterns that fit the rules.

Now subtract 27 from the total number of ways that the rows can be arranged, and you have the number of patterns that break the rules. It is going to be an immense number compared to 27.

"Well, you can have a gray in the middle, and if that is true, you must have yellow in every other spot in that row to ensure that the row is symmetric in terms of height." You could have Yellow on just the outsides with gray in the center

 

[AlexBaylor]

This is quick and dirty.

There are seven ways to fill each slot: no cup, yellow cup, grey cup, yellow- yellow stack, yellow-grey stack, grey-yellow stack, and grey-grey stack. And there are 15 slots. So the total number of possibilities is

[MATH]t = 7^{15} \implies log(t) = 15log(7) \approx 12.68 \implies t = 4,700,000,000,000.[/MATH]
So the probability that sticking cups in at random will follow the rules is 0 for all practical purposes.

I'm not sticking them randomly though, I'm placing them according to a pattern and I'm getting random cups (Number and color)

 

[AlexBaylor]

We ask people to include the entire problem they are really working on, because often the piece they show us is not part of a good method to solve their real problem. So I'm glad you've said more here.

But I'm wondering whether you meant exactly what you said here. As written, this is asking for the probability that there is no way to organize, the way you like, the particular set of cups you have at the moment; but the original question doesn't deal with whether there is a solution for a particular set of cups, just with whether a particular arrangement is a solution. So that sounds like you want the probability that a random arrangement fits/doesn't fit your pattern. Which are you really looking for?

It happens that when I do dishes I have similar thoughts about how I arrange cups in the drainer, and my thought is generally, can any set of cups I have be arranged in a symmetrical manner, or not? It is never about the probability that a random arrangement is symmetrical. (I allow any kind of symmetry. And no, I'm not obsessive about this; my mind is just running faster than my hands, and needs something to think about.)

The probability that a random set of cups can be arranged nicely will be far higher than the probability that a random arrangement is nice.

I'm slightly confused by your question, but maybe the spreadsheet will tell you what I'm looking for??

 

[JeffM]

"Well, you can have a gray in the middle, and if that is true, you must have yellow in every other spot in that row to ensure that the row is symmetric in terms of height." You could have Yellow on just the outsides with gray in the center

Except that is not what you say are the rules. "The other spots must be "yellow or empty."

Thus, if we stacking 1 high, the middle spot must be grey and all others must be yellow."

If yo do not specify the rules exactly, then our answers will not fit the rules.

 

[AlexBaylor]

This is what I'm saying works

 

[Dr.Peterson]

I'm not sticking them randomly though, I'm placing them according to a pattern and I'm getting random cups (Number and color)

This strongly suggests that I was right here:

As written, this is asking for the probability that there is no way to organize, the way you like, the particular set of cups you have at the moment. ...

The probability that a random set of cups can be arranged nicely will be far higher than the probability that a random arrangement is nice.

That is, you are not really asking for the probability that a random placement turns out to follow the pattern, but about the probability that a random collection of cups makes it possible for you to deliberately follow the pattern. Right?

I'm slightly confused by your question, but maybe the spreadsheet will tell you what I'm looking for??

I learned nothing from the spreadsheet, which looks almost empty to me. But my sense is that you may be going through every possible set of cups, one by one, to determine whether it can be arranged. That is an entirely different question than what you first asked, "How many possible combinations of cups (that don’t use more than thirty cups total) are there that don’t [not "can't"] fulfill the pattern?"

Does what I just said explain my question?

Finally, I asked you to restate the rules more clearly, and gave an example. Can you do that, to help us out?

 

[Dr.Peterson]

I went back and looked more closely at your spreadsheet, and realized that the heading tells me to look at each sheet within it. I'd looked only at the first, which is nearly empty.

It looks like you are using the sheet just to keep a record, for each of the 495 possible sets of up to 30 cups, whether you are able to arrange it following your rules; but you are determining that manually, without using the spreadsheet to determine it for you, or even just writing out your thinking. Very likely if you recorded why some can and some can't be done, you would discover a pattern that would make an efficient method possible. That is what I would do. (I haven't given it any thought yet.)

Before I can give it any thought, I have to know clearly what the rules are. For example, you say each row must be symmetrical by height; does that imply that it doesn't have to be symmetrical by color? Can a row be, say, _, GY, G, YY, _?

 

[AlexBaylor]

I went back and looked more closely at your spreadsheet, and realized that the heading tells me to look at each sheet within it. I'd looked only at the first, which is nearly empty.

It looks like you are using the sheet just to keep a record, for each of the 495 possible sets of up to 30 cups, whether you are able to arrange it following your rules; but you are determining that manually, without using the spreadsheet to determine it for you, or even just writing out your thinking. Very likely if you recorded why some can and some can't be done, you would discover a pattern that would make an efficient method possible. That is what I would do. (I haven't given it any thought yet.)

Before I can give it any thought, I have to know clearly what the rules are. For example, you say each row must be symmetrical by height; does that imply that it doesn't have to be symmetrical by color? Can a row be, say, _, GY, G, YY, _?

"Can a row be, say, _, GY, G, YY, _?", Yes, it can. Also, some other things I know: You must have 18 or fewer grays, if no yellow then you must have 6 or fewer grays, you must have 27 or fewer yellows, if no gray you must have 24 or fewer yellows, if no gray you must have an even number of yellow