ORMC AMC 10/12 Group

Week 4: Combinatorics

October 22, 2023

1 Warm-up Exercises
1. (1950 AHSME #45) Find number of diagonals that can be drawn in a polygon of 100 sides.

2. (1973 AHSME #2) One thousand unit cubes are fastened together to form a large cube with edge
length 10 units; this is painted and then separated into the original cubes. Find the number of these
unit cubes which have at least one face painted.

3. (1974 AHSME #24) A fair die is rolled six times. What is the probability of rolling at least a five
at least five times?

4. (1985 AJHSME #15) How many whole numbers between 100 and 400 contain the digit 2?

5. (1986 AHSME #10) The 120 permutations of AHSM E are arranged in dictionary order as if each
were an ordinary five-letter word. What is the last letter of the 86th word in this list?

6. (1987 AJHSME #25) Ten balls numbered 1 to 10 are in a jar. Jack reaches into the jar and randomly
removes one of the balls. Then Jill reaches into the jar and randomly removes a different ball. What
is the probability that the sum of the two numbers on the balls removed is?

7. (1980 AHSME #20) A box contains 2 pennies, 4 nickels, and 6 dimes. Six coins are drawn without
replacement, with each coin having an equal probability of being chosen. What is the probability that
the value of coins drawn is at least 50 cents?

1
2 Important Functions and Techniques
2.1 Functions
1. The factorial is a function on integers n, defined by n! = n · (n − 1) · · · 3 · 2 · 1. It is generally used on
its own to count re-orderings of distinct items. For example, the number of 5-digit numbers containing
the digits 1, 3, 5, 7, 9 each once would be 5!, since we have 5 choices for the first digit, 4 for the second,
and so on.
2. The permutation function is a slight generalization of factorials, where we are re-ordering a set of
items, but we may use only a subset of the items. It is generally written as n Pk , where we have n total
items and we are finding possible orderings of any k of them. If k < 0 or k > n, we define this number
to be 0. Otherwise, it is defined to be:
n!
n Pk = n · (n − 1) · (n − 2) · · · (n − (k − 1)) = .
(n − k)!

3. The combination function, also known as the binomial coefficients, is written as nk , or n Ck .

It is a version of permutations where we do not care about the order of the elements. Instead, we
only care about which k elements were chosen. Notice that each subset of k elements has k! possible
rearrangements, so there are k! times as many permutations as combinations. So, we have the following
definition:  
n n Pk n!
n Ck = = = .
k k! k!(n − k)!

2.2 Techniques
1. Stars-and-Bars gives a way to count how indistinguishable items can be sorted into distinguishable
containers. If the problem you are working on can be translated into the form “How many ways can n
identical balls be placed into m labeled boxes?”, then you can use stars-and-bars.
Write out n stars (∗), and draw m − 1 bars (|), separating the stars. The different boxes are indicated
by the spaces between the bars. For example:

∗ ∗ ∗ ∗ || =⇒ 4 balls in box 1, 0 balls in box 2, 0 balls in box 3

∗ ∗ ∗| ∗ | =⇒ 3 balls in box 1, 1 ball in box 2, 0 balls in box 3

∗| ∗ ∗|∗ =⇒ 1 ball in box 1, 2 balls in box 2, 1 ball in box 3

The total number of star-and-bar layouts is given by finding how many ways there are to place the n
 
n+m−1
stars among the total spots for n stars + m − 1 bars. This value is .
n

2. The Principle of Inclusion-Exclusion gives us a way to count the total number of elements in some
number of sets that may have overlap. You are likely familiar with the 2-set case:

|A ∪ B| = |A| + |B| − |A ∩ B|.

This generalizes to n sets in the following way:

n
[ n
X X X
Ai = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · · + (−1)n−1 |A1 ∩ · · · ∩ An |
i=1 i=1 i<j i<j<k

Consider any element X which
is in the

union of all the
Ai ’s. WLOG, X is in k of the sets. So, by the
formula above, X is counted k1 − k2 + · · · + (−1)n kk times. As you will see in the exercises later, all
of this adds up to 1, no matter what k is. So, every element is counted exactly once.

2
3 Examples
1. 12 students sit in a row, and each one raises either their left hand or right hand. How many ways can
exactly 5 students raise their right hand? 8 students?

2. Find the coefficient of x7 in (1 + x)12 . What about the coefficient of x4 ?

(Hint: can you see how this problem is similar to the previous one? This explains the connection
between binomial coefficients and combinations.)

3. In a town of 351 adults, every adult owns a car, motorcycle, or both. If 331 adults own cars and 45
adults own motorcycles, how many of the car owners do not own a motorcycle?

4. (2003 AMC 10A #21) 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?

4 Exercises (Important Identities)

1. Recall how we concluded in Example 2 that nk is the coefficient of xk in (1 + x)n . Use this to show

that:
     
n n n
+ + ··· + = 2n
0 1 n

2. To fill in the gap in our proof of the Principle of Inclusion-Exclusion, show that:
     
n n n n
− + · · · + (−1) = 0.
0 1 n

3. Show that the binomial coefficients satisfy the recurrence relation:

     
n n−1 n−1
= +
k k k−1

3
 4. (Hockey-Stick Theorem) Use the previous problem to show the following identity:
       
n n+1 n+m n+m+1
+ + ··· + = .
0 1 m m

5. (Vandermonde’s Identity) Show that:

  k   
m+n X m n
=
k i=0
i k−i

(Hint: Choose a group of size k out of a class with m right-handed people and n left-handed people)

5 Exercises (Practice Problems)

1. (2017 AMC 10B #13) There are 20 students participating in an after-school program offering classes
in yoga, bridge, and painting. Each student must take at least one of these three classes, but may take
two or all three. There are 10 students taking yoga, 13 taking bridge, and 9 taking painting. There are
9 students taking at least two classes. How many students are taking all three classes?

2. (2001 AMC 10 #19) Pat wants to buy four donuts from an ample supply of three types of donuts:
glazed, chocolate, and powdered. How many different selections are possible?

3. (2002 AIME I #1) Many states use a sequence of three letters followed by a sequence of three digits
as their standard license-plate pattern. Given that each three-letter three-digit arrangement is equally
likely, the probability that such a license plate will contain at least one palindrome (a three-letter
arrangement or a three-digit arrangement that reads the same left-to-right as it does right-to-left) is
m
, where m and n are relatively prime positive integers. Find m + n.
n

4. (2005 AMC 12A #18) Call a number prime-looking if it is composite but not divisible by 2, 3, or 5.
The three smallest prime-looking numbers are 49, 77, and 91. There are 168 prime numbers less than
1000. How many prime-looking numbers are there less than 1000?

4
 5. (2017 AIME II #1) Find the number of subsets of {1, 2, 3, 4, 5, 6, 7, 8} that are subsets of neither
{1, 2, 3, 4, 5} nor {4, 5, 6, 7, 8}.

6. (2018 AMC 10A #11) 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
n
,
67
where n is a positive integer. What is n?

7. (Mock AIME 3 Pre 2005 #2) Let N denote the number of 7 digit positive integers have the property
that their digits are in increasing order. Determine the remainder obtained when N is divided by 1000.
(Repeated digits are allowed.)

8. (2013 AIME I #6) Melinda has three empty boxes and 12 textbooks, three of which are mathematics
textbooks. One box will hold any three of her textbooks, one will hold any four of her textbooks, and
one will hold any five of her textbooks. If Melinda packs her textbooks into these boxes in random
order, the probability that all three mathematics textbooks end up in the same box can be written as
m
n , where m and n are relatively prime positive integers. Find m + n.

9. (2016 AMC 10A #20) 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 ?

10. (2020 AMC 10B #25) Let D(n) denote the number of ways of writing the positive integer n as a
product
n = f1 · f2 · · · fk ,
where k ≥ 1, the fi 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 · 3, and 3 · 2, so D(6) = 3. What is D(96)?

5
11. (2000 AIME II #7) Given that

1 1 1 1 1 1 1 1 N
+ + + + + + + = ,
2!17! 3!16! 4!15! 5!14! 6!13! 7!12! 8!11! 9!10! 1!18!
N
find the greatest integer that is less than 100 .

12. (2020 AIME I #7) A club consisting of 11 men and 12 women needs to choose a committee from
among its members so that the number of women on the committee is one more than the number of
men on the committee. The committee could have as few as 1 member or as many as 23 members. Let
N be the number of such committees that can be formed. Find the sum of the prime numbers that
divide N.

13. (1986 AIME #13) In a sequence of coin tosses, one can keep a record of instances in which a tail is
immediately followed by a head, a head is immediately followed by a head, and etc. We denote these by
TH, HH, and etc. For example, in the sequence TTTHHTHTTTHHTTH of 15 coin tosses we observe
that there are two HH, three HT, four TH, and five TT subsequences. How many different sequences
of 15 coin tosses will contain exactly two HH, three HT, four TH, and five TT subsequences?

14. (2001 AIME #2) Each of the 2001 students at a high school studies either Spanish or French, and
some study both. The number who study Spanish is between 80 percent and 85 percent of the school
population, and the number who study French is between 30 percent and 40 percent. Let m be the
smallest number of students who could study both languages, and let M be the largest number of
students who could study both languages. Find M − m.

15. (2021 AMC 12A #15) A choir director must select a group of singers from among his 6 tenors and
8 basses. The only requirements are that the difference between the number of tenors and basses must
be a multiple of 4, and the group must have at least one singer. Let N be the number of different
groups that could be selected. What is the remainder when N is divided by 100?

6
6 Challenge Exercises
1. (2020 AIME II #9) While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in
that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they
came back, they sat on those six chairs in such a way that if two of them sat next to each other before
the break, then they did not sit next to each other after the break. Find the number of possible seating
orders they could have chosen after the break.

2. (2007 AIME I #10) In a 6 x 4 grid (6 rows, 4 columns), 12 of the 24 squares are to be shaded so
that there are two shaded squares in each row and three shaded squares in each column. Let N be the
number of shadings with this property. Find the remainder when N is divided by 1000.

3. (2015 AIME I #12) Consider all 1000-element subsets of the set {1, 2, 3, ..., 2015}. From each such
subset choose the least element. The arithmetic mean of all of these least elements is pq , where p and q
are relatively prime positive integers. Find p + q.

4. (2018 AIME I #10) The wheel shown below consists of two circles and five spokes, with a label at
each point where a spoke meets a circle. A bug walks along the wheel, starting at point A. At every
step of the process, the bug walks from one labeled point to an adjacent labeled point. Along the inner
circle the bug only walks in a counterclockwise direction, and along the outer circle the bug only walks
in a clockwise direction. For example, the bug could travel along the path AJABCHCHIJA, which
has 10 steps. Let n be the number of paths with 15 steps that begin and end at point A. Find the
remainder when n is divided by 1000.

I A F
B E

C D

H G