AMC 10 Skills: Stars and Bars (5 Examples)

all right this is the start of the 2016 10 a problem number 20 however before I start the problem I'm going to explain a concept that is pretty much my pain necessary to get this problem correct but you might not be there could be a longer route but this is the most efficient way to attack this problem and so we're gonna do some examples of Stars and Bars if you only if you're very comfortable with Stars and Bars you know the concept very well I will put a link in the description that will skip straight to the problems explanation so feel free to go down there and click that and go right to the explanation of the problem but for those of you who maybe are slightly comfortable Stars and Bars or you don't fully understand what it is we're gonna go over that first with I don't know a few examples actually and I'll give each of the examples a timestamp in the description as well um what is Stars and Bars um it has different names actually I've heard from other people it's also called rice and chopsticks sticks and stones and so why we call it that let's see here's an example of how it works three friends have seven identical pieces of candy and each one has at least one piece in how many ways can this happen all you're gonna do is picture the pieces of candy as dots so we made seven dots on the board now alternatively you could make seven stars but I've already made three stars in the time it took me to make seven doubts and I mean these are pretty hard to make so that's where stars and bars gets its name is star the star is here now what about the rice and chopsticks or sticks and stones but we need dividers the bars are dividers sticks chopsticks dividers bars all the same thing and what we're going to do is we're going to put we're just place them here on our own we'll put one here and say one here and this is going to represent the first person on the left if you're grouping these three people get gets one piece of candy four dots here means the next person gets four and the next person gets two for a total of and pieces of candy distributed okay so let's see how that works then we basically need to figure out where do these dividers go and the deal is that for three people you're gonna need two dividers right because you create three groups when you do it now where can the dividers go let's say I moved one to the outside over here that's not really allowed because that gives zero five and two and this friend doesn't get any candy maybe they're I don't know I wouldn't get choked by me I won't uh yeah so basically you can't have this situation where you place it outside of the dots furthermore you cannot place two dividers within one gap if you will gap between the dots because that again would indicate five zero two and somebody would still get zero now you can for some problems but we're gonna do approach those a little bit differently when we do a different example probably example two um so really where can we put the dividers then we can only put them in between the rice or the dots or the Stars or the stones whatever you want to call it you can give it your own pet name if you want um you can only put them in the gaps that are available the question is how many gaps are there well if there's seven items there's one less gap right there's six gaps one two three four five six and if I had eight there would be seven gaps and nine wouldn't get eight gaps and so on so we want to know each of these gaps can only get one bar and we have two dividers or two bars to place so the answer is going to be six choose we have seven dots here right one two three four five six yeah six choose two right this is the way I write it and you can also write combinations like this you can also write it as the combination of six things taken two at a time but I prefer this notation if you want to use your own notation that's fine as well well one of the other options so combination then of six things taken two at a time what are the six things it's the six gaps and you need to choose any two of them right so six choose two which two do you choose determines how many pieces each person gets let's say the people are Aaron Brad and Charlie right then the first one on the Aaron's candy then Brad gets the middle and Charlie gets the third right so that's how stars and bars works um again if you can't see this is the bar those are the stars right these are the stones and sticks or rice and chopsticks and so on okay so that's example one this comes out to 15 really briefly you should know this shortcut n choose 2 is equal to n times n minus 1 over 2 if you're not sure why check it out on your own I will have another video about combinations in the future that kind of goes through more of these combinations shortcuts ok so that's it for this one let's get on to example 2 alright so this is example 2 three friends have eight identical pieces of candy in how many ways can this happen a slight change from the first example in the first example they each had to have one and this one there's no guarantee of that so if I put the eight dots out here three four five six seven eight there are seven gaps but now if I can put two dividers here if I wanted that's okay because we get to 0 6 no problem there's no guarantee that they each get one this time that's gonna make it more complicated how many slots can these dividers actually go in you can't really think of it in that way this time instead we're gonna switch gears and it's very much related but we're going to say that each of the pieces of candy is that a letter C 5 6 7 8 and link the dividers the letters D now if I was to make a random setup for example this would be eight zero zero so the first person gets eight and his two friends both get zero right so then what can we do if we like this CD see see the cccc right then this would be the first friend gets one and then three and then four that's the total of eight pieces of candy distributed so in this way we can think about it instead as letters right and you can just say how many words can you create let's think about this in several ways first off you might already know that if I wanted to know how many words which is a loosely used word how many words can I make with this how many arrangements that are unique could be created with these letters it's the total of the letters 8 sees and 2ds 10 and then you need to choose two of them to be DS right and then you could also say what if I chose where the C's go instead you could say 10 choose 8 and these are equal you probably already know but if the two numbers down here add to the top numbers then they're equal so for example 5 choose 2 is equal to 5 choose 3 ok so yeah that's gonna be the answer for this problem basically where you place the leonard DS determines who gets what candy in what order okay so that's this example in the previous one there are formulas that go with these so like in example 1 the formula if there's n pieces of candy or and objects and you're you're breaking them up into our groups it's n minus 1 choose R minus 1 but I don't know about you but I'm not so good at memorizing all the formulas that I need to know I'd much rather be able to derive it by concept by thinking about it from internal memory kind of understanding the technique used rather than just the formula now this one's not the same way if I needed to divide by into three groups it would be the end pieces of candy or n objects plus the R groups which is actually 3 and then minus 1 and then it would be choose R minus 1 right 10 choose 2 is what this would come out to 8 plus 3 minus 1 three months or choose 3-1 and this one over here we had seven pieces of candy and three people so if you put the seven in here and the three in here it comes out to six choose two um again I don't recommend you try memorizing these but if you have a photographic memory disregard that advice maybe you're good at memorizing all these formulas and you know exactly when to apply them okay on to the next example all right so this is the last of the easier type examples for Stars and Bars the next ones will get a little bit more complicated this one you don't have to use Stars and Bars that's the same with a lot of these problems there's more than one way to solve them and so it says how many ways are there to put five indistinguishable balls so you can't tell the balls apart into two distinguishable so you can tell the boxes apart um so you could do it with Stars and Bars if you wanted to you could say that the balls are dots one two three four five balls and we need only one divider and technically it could go anywhere it could go here here here here here or here and wherever you put it like this would be one in four one in the left box four in the right box they are distinguishable so basically how many places do I have to place it only need one divider because there's only two boxes so one two three four five there's six places to choose one to be a divider we could also done it with letters if we wanted to we could have said that the balls are all the letter B 3 4 5 and the letter D is the divider and again you will see it's six choose five or six choose one either of those things is identical okay so Stars and Bars is possible or you could do letters I forgot to mention in the last example how letters work the word thing actually what you usually do let's say there was two dividers instead so three distinguishable boxes um then how would this work with five and two dividers you could say that there's seven total letters in right seven factorial and then you could just divide by the number of the copy letters like duplicate there's five bees so you'll divide by five factorial and the 2ds is two factorial and this problem doesn't have two dividers I'm just saying so we can understand how many ordered words we can create but the thing you have to understand is that this is the same thing as seven choose two so I've got seven total spaces to place letters choose two to be DS or I could say again seven choose five and that's also the same thing on to the next example okay this is example four of the Stars and Bars concept how many quadruples oh by the way this comes from intermediate I don't have the other book in front of me intermediate counting and probability this book from the art of problem solving it's problem seven point four so it's from chapter seven the section is seven point two the problem is seven point four and that's where I pulled it from we just want to give attribution so how many quadruples a B C and D of positive integers this is important that it says positive integers that's going to be your the difference of how you approach the question or solutions to a plus B plus C plus D is equal to 17 well you can think of it just like Stars and Bars or rice and chopsticks it's just that the 17 is going to be 17 dots right we're not gonna put them all out here right there's 17 dots in this list and we need to break those 17 dots into four groups which means we need three dividers once you start to recognize that rice and chopsticks or Stars and Bars and various problems you can just apply it pretty easily it's not that hard now so I've got seventeen dots if they all have to be at least one that means no dividers can come out here they can only go in between in the gaps and only one divider per gap right two dividers in the same gap would allow one of them to be zero but this says positive integers so it's actually a really quick application of the concept there's sixteen gaps and you need to choose three of them calculate that and that's your answer next example all right this is the final example of the Stars and Bars concept Before we jump into the 2016 10 a problem 20 I chose this example because it contributes directly to our understanding of problem 20 like the kind of thinking the techniques that we're going to be applying so how many solutions does the equation V plus W plus X plus y plus Z equals 21 have where V W X Y & Z and this is important or all non-negative integers I would imagine that many of you have seen the word non-negative and did not consider 0 and got one wrong either in practice or on a real test so I'm sure you're familiar with how careful we have to be with this non-negative integers okay so it's a little bit like example 4 but in example 4 it was only positive integer solutions that counted now we're allowed to have zero we could approach it like we talked about in example two and that would be considerate as we only use rice and chopsticks and consider that there's 21 grains of rice which we will consider as 21 ours right 21 so there's 21 R's here and then we're gonna need dividers and to have five letters that take on our variables that take on these values we are going to need four dividers so there's four Leonard days so what do we have then we have 21 R's and four DS is 25 and we can either choose the ours or choose the DS it doesn't matter it still comes out the same this will be the answer if you calculate it it comes out to 12 560 now that's not the way they explained it in the book in the book it's a o-p-s intermediate counting and probability problems 7.5 they give another explanation I want you to consider it as well there's always especially with County and probability it's better to be able to think about an attack a problem with multiple attack plans right looking at it from different angles and then on a test when you're under time pressure the chance that you think of one of those solution paths is greatly increased if you know more than one you're capable of recognizing so the way they explained it in here is something along the lines of this if you let V prime equal V plus 1 and W prime equal W plus 1 and so on all the way down to Z prime equals Z plus 1 now if because we know that V is non negative one of its possible values is 0 and if it takes on the value of 0 no matter what V prime will be positive right because it'll be 0 plus 1 which is 1 so V prime W prime is different all of these have to be positive now ok so then what if we add in V prime plus W prime plus X prime plus y prime plus Z prime that would give us V Plus 1 plus W plus 1 all the way down to Z plus 1 which would be V plus W plus X plus y plus Z plus v and since this is 21 this becomes 26 and now we have five new variables that we created based on the old ones all the prime versions of them but these are now all forced to be positive and now we could think of it as the normal rice and chopsticks or Stars and Bars you would have 26 dots because that's what we have to equal now and then you would need four dividers but it's not the dots you should focus on it's the gaps between the dots right so one two three gaps right then that's because there's four dots and for 26 dots you would get 25 gaps and you would choose four of them to be holding of dividers all right so this is the same answer that we got in the other version that we did earlier so now we're going to move on to the actual question problem number 20 here we

Channel: TheBeautyofMath

Views: 11,902

Keywords: AMC10, AMC12, AIME, Competition Math, AOPS, MathCounts, Math, Mathematics, AMC 10, AMC 12, AMC 8, Math Kangaroo, Counting, Stars and Bars

Id: PGDaKxFVS9Q

Length: 17min 33sec (1053 seconds)

Published: Sat May 23 2020