5. Stars & Bars · Mastering AMC 10/12

5.10%

Stars and Bars Fundamentals

In this section you will be able to count the ways to share identical objects among different bins by lining up stars and bars.

You have 8 identical computers for 3 students. The computers are identical, so only how many each student gets matters. How do you count that?

Write the computers in a row and drop in 2 bars. Everything left of the first bar goes to student 1, everything between the bars goes to student 2, and the rest goes to student 3.

Every row of stars and bars is exactly one way to share. So you only need to choose where the bars go.

Exploreplay first, formulas later

Try this: Move bar 1 (buttons or arrow keys) until student 2 gets nothing. What does the row look like?
Try this: Turn on "List all layouts". Count the boxes. Does the count match C(6, 2) = 15?
Try this: Set 5 computers and 2 students. Why are there exactly 6 layouts?

Name it

Theorem 5.1.1 · Stars and Bars

The number of ways to place $n$ identical objects into $k$ distinguishable bins is

\binom{n+k-1}{n}.

Remark 5.1.2

Stars and Bars is very useful, and can often be adapted based on situations. For example, if each bin has to have at least 1 object in it, we assign 1 object to each bin to start off, and apply our formula to the remaining $n - k$ objects and $k$ distinguishable bins.

Watch itpredict, then reveal

Example 5.1

How many ways are there to distribute 8 identical computers amongst 3 students?

1
Keep in mind that the computers are identical. What would the answer be if they were all different?

Predict first:
Your prediction

Try it

Problem 5.5.7(additional)

How many terms will be in the expansion of $(w + x + y + z)^{10}$ after simplifying?

Contest cornerreal contest problems

Problem 5.5.3

AMC 10

Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?

Checkpoint for section 5.1

Get 2 of 3 right to master this section. One try each, no hints.

5.20%

Stars and Bars With Constraints

In this section you will be able to handle minimums, inequalities and upper limits by changing the problem into plain stars and bars.

7 astronauts are stranded with only 10 identical meals, and everyone must get at least 1. Plain stars and bars allows empty bins. How do you fix that?

Hand out the minimums first. Once every astronaut has 1 meal, the rest can go anywhere: that’s plain stars and bars.

Two more moves make stars and bars fit almost any sum. For a sum that is less than something, add a slack variable that takes up the difference. For an upper limit (a die shows at most 6), count everything, then subtract the layouts that break the limit.

Exploreplay first, formulas later

Try this: Press "Give one to each". How many meals are left to share freely?
Try this: Press "Share the rest" a few times. Can any astronaut end up with 0 meals now?
Try this: Change the astronauts to 5. How many meals are left after giving one each? Predict the count first.

Name it

Concept 5.2.1 · Give the Minimums First

Stars and bars is extremely useful, and can often be adapted based on situations. For example, if each bin has to have at least 1 object in it, we assign each bin 1 object to start off with and apply our formula with $n - k$ objects and $k$ distinguishable bins:

\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}.

Watch itpredict, then reveal

Example 5.2

7 astronauts are stranded in space with only 10 identical meals left. Every astronaut must receive at least 1 meal or else, they will starve. How many ways are there to distribute meals under this constraint?

1
How can we deal with the condition that every astronaut must get at least 1 meal? How many meals are left after that?

Predict first:
Your prediction

Example 5.3

Modified AMC 10

For some particular value of $N$ , when $(a + b + c + d + 1)^N$ is expanded and like terms are combined, the resulting expression contains exactly 1001 terms that include all four variables $a, b, c,$ and $d$ , each to some positive power. What is $N$ ?

1
Every term looks like $a^p b^q c^r d^s \cdot 1^t$ . What must $p + q + r + s + t$ equal?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 5.4

In how many ways can the sum of the top faces on five regular 6-sided dice be 24?

1
Each die shows 1 to 6, so plain stars and bars won't respect the maximum of 6. How can we use stars and bars anyway? How many "minus ones" do we hand out?

Predict first:
Your prediction

Example 5.5

How many ways are there to choose positive integers $a, b, c,$ and $d$ such that $a + b + c + d < 13$ ?

1
Stars and bars needs an equation, not " $<$ ". How do we fix that?

open on YouTube

Contest cornerreal contest problems

Problem 5.5.1

AMC

Alice has 24 apples. In how many ways can she share them with Becky and Chris so that each of the three people has at least two apples?

Problem 5.5.2

AMC 10

When 7 fair standard 6-sided dice are thrown, the probability that the sum of the numbers on the top faces is 10 can be written as

\frac{n}{6^7},

where $n$ is a positive integer. What is $n$ ?

Problem 5.5.8(additional)

AMC 12

The expression

(x + y + z)^{2006} + (x - y - z)^{2006}

is simplified by expanding it and combining like terms. How many terms are in the simplified expression?

Problem 5.5.9(additional)

AIME

A fair die is rolled four times. The probability that each of the final three rolls is at least as large as the roll preceding it may be expressed in the form $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

Checkpoint for section 5.2

Get 2 of 3 right to master this section. One try each, no hints.

5.30%

Stars and Bars but Stars Are Groups

In this section you will be able to count shares that must be even, odd or matched by making each star a group.

Three squirrels share 19 acorns. One wants an odd number, one an even number, and one an even number of at least 4. What if the stars come in pairs?

When a share must be even, count it in pairs: write it as $2y$ and share out the $y$ pairs. An odd share is $2x + 1$ : hand out the 1 first, then pairs.

A group can also be a mix. Glue each banana to an apple and move the two together.

Exploreplay first, formulas later

Try this: Each ●● is a pair of candies. Move the bars. Can any child ever get an odd number?
Try this: Set 6 pairs. In how many ways can 12 candies be shared so that every child gets an even number?
Try this: Ex 5.7: give the odd squirrel 1 acorn and the third squirrel 4 first. How many pairs are left from 19 acorns?

Watch itpredict, then reveal

Example 5.6

Omega Learn

You have 11 apples and 5 bananas. You place them into 3 baskets. How many ways are there to do this if each basket must have more apples than bananas and at least 1 of any fruit?

1
Each basket needs more apples than bananas. What can we glue together?

open on YouTube

Example 5.7

Omega Learn Math Contest

Three squirrels have to distribute 19 identical acorns amongst themselves.

The first squirrel demands to have a positive odd number of acorns.
The second squirrel is fine with any non-negative even number of acorns.
The third squirrel insists he must get an even number of acorns greater than or equal to 4.

How many different ways can they distribute the acorns?

1
Write each squirrel's share with a variable that can be any non-negative integer. How?

open on YouTube

Try it

Problem 5.5.6(additional)

Omega Learn

Find the number of solutions to $a + b + c + d < 19$ where $a, b, c, d$ are positive integers, $a$ and $c$ must be odd, and $b$ and $d$ must be even.

Checkpoint for section 5.3

Get 2 of 3 right to master this section. One try each, no hints.

5.40%

Stars and Bars to Count Orderings

In this section you will be able to count line-ups where some people or objects can't be neighbors, by sharing the others into the gaps.

7 people sit in a row, and 3 of them are enemies who refuse to sit together. Instead of counting seats, count the people in the gaps between the enemies.

Mark where the enemies sit. The other people fill the gaps around them. The inner gaps need at least 1 person, and the two ends may be empty. That’s stars and bars with minimums.

Stars and bars counts the pattern. Then multiply by the number of ways to order the people inside it.

Exploreplay first, formulas later

Try this: The gaps between enemies need at least 1 friendly person. Which bins get a starter? Press the button.
Try this: Press "Share the rest". Read the row from left to right: where do the enemies sit?
Try this: The widget counts seat patterns only. Why do we still multiply by 3! and 4!?

Watch itpredict, then reveal

Example 5.8

How many ways are there for 7 people to sit in a line if 3 of them are enemies and refuse to sit next to each other?

1
We'll order the people later. First: without the condition, how many ways are there to choose 3 seats for the enemies?

Predict first:
Your prediction

Example 5.9

AIME

Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let $m$ be the maximum number of red marbles for which such an arrangement is possible, and let $N$ be the number of ways he can arrange the $m + 5$ marbles to satisfy the requirement. Find the remainder when $N$ is divided by $1000$ .

For steps 3 and 4: the red marbles and the 6 groups around the 5 greens.

1
At most how many marbles can have a right neighbor of the other color?

Predict first:
Your prediction

Example 5.10

AIME

There are two distinguishable flagpoles, and there are 19 flags, of which 10 are identical blue flags, and 9 are identical green flags. Let $N$ be the number of distinguishable arrangements using all of the flags in which each flagpole has at least one flag and no two green flags on either pole are adjacent. Find the remainder when $N$ is divided by $1000$ .

An example with fewer flags: pole 1, a red separator, then pole 2 on one long pole.

1
We'll use complementary counting: count arrangements where a pole may be empty, then subtract the ones with all flags on 1 pole. How many ways are there to put all 19 flags on 1 flagpole?

Predict first:
Your prediction

Try it

Problem 5.5.11(additional)

In how many ways can 8 students and 3 teachers sit in the front row if, between every pair of teachers, there must be at least 2 students?

Contest cornerreal contest problems

Problem 5.5.10(additional)

AIME

A gardener plants three maple trees, four oaks, and five birch trees in a row. He plants them in random order, each arrangement being equally likely. Let $\frac{m}{n}$ in lowest terms be the probability that no two birch trees are next to one another. Find $m + n$ .

Problem 5.5.12(additional)

AIME

Consider the paths of length 16 that go from the lower left corner to the upper right corner of an $8 \times 8$ grid. Find the number of such paths that change direction exactly 4 times.

Checkpoint for section 5.4

Get 2 of 3 right to master this section. One try each, no hints.

5.5

Practice Problems

In this section you will be able to mix every stars-and-bars move from this chapter on contest problems.

Two harder contest problems. One hides stars and bars inside a divisibility question, the other inside a count of factorizations. Each has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 5.5.4

AMC 10

A seven-digit positive integer is chosen at random. What is the probability that the number is divisible by 11, given that the sum of its digits is 61?

Problem 5.5.5

AMC 10Challenge

This problem also appears in the book as 3.3.18.

Let $D(n)$ denote the number of ways of writing the positive integer $n$ as a product

n = f_1 \cdot f_2 \cdots f_k,

where $k \ge 1$ , the $f_i$ are integers strictly greater than 1, and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number 6 can be written as $6$ , $2 \cdot 3$ , and $3 \cdot 2$ , so $D(6) = 3$ . What is $D(96)$ ?