This page is dedicated to problem solving on the notions of rule of sum (also known as Addition Principle) and rule of product (also known as Multiplication Principle). To solve problems on this page, you should be familiar with the following notions:
The rule of sum and the rule of product are two basic principles of counting that are used to build up the theory and understanding of enumerative combinatorics.
Contents
Introduction
The rule of sum (Addition Principle) and the rule of product (Multiplication Principle) are stated as below.
Rule of Sum - Statement:
If there are choices for one action, and choices for another action and the two actions cannot be done at the same time, then there are ways to choose one of these actions.
Rule of Product - Statement:
If there are ways of doing something, and ways of doing another thing after that, then there are ways to perform both of these actions.
Here is an example based on the above rules.
Calvin wants to go to Milwaukee. He can choose from bus services or train services to head from home to downtown Chicago. From there, he can choose from 2 bus services or 3 train services to head to Milwaukee. How many ways are there for Calvin to get to Milwaukee?
He has ways to get to downtown Chicago. (Rule of sum)
From there, he has ways to get to Milwaukee. (Rule of sum)
Hence, he has ways to get to Milwaukee in total. (Rule of product)
Try the following problems.
There are 3 flights from California to France, and 2 flights from France to India. Sanjeet wants to fly from California to France and then to India.
How many choices does he have for his flight plan?
A restaurant offers 5 choices of appetizer, 10 choices of the main course and 4 choices of dessert. A customer can choose to eat just one course, or two different courses, or all three courses. Assuming that all food choices are available, how many different possible meals does the restaurant offer?
Note: When you eat a course, you only pick one of the choices.
Examples
This section includes the basic examples and problems that will warm you up for the next section of problem solving.
Calvin wants to go to Milwaukee. He can choose from bus services or train services to head from home to downtown Chicago. From there, he can choose from 2 bus services or 3 train services to head to Milwaukee.
This time, he has to purchase a bus concession (which will only allow him to take buses), or a train concession (which will only allow him to take trains). If he only has money for of these concessions, how many ways are there for him to get to Milwaukee?
If Calvin purchases a bus concession, he has ways to get to Milwaukee. (Rule of product)
If Calvin purchases a train concession, he has ways to get to Milwaukee. (Rule of product)
Hence, he has ways to get to Milwaukee in total. (Rule of sum)
Six friends Andy, Bandy, Candy, Dandy, Endy and Fandy want to sit in a row at the cinema. If there are only six seats available, how many ways can we seat these friends?
For the first seat, we have a choice of any of the 6 friends. After seating the first person, for the second seat, we have a choice of any of the remaining 5 friends. After seating the second person, for the third seat, we have a choice of any of the remaining 4 friends. After seating the third person, for the fourth seat, we have a choice of any of the remaining 3 friends. After seating the fourth person, for the fifth seat, we have a choice of any of the remaining 2 friends. After seating the fifth person, for the sixth seat, we have a choice of only 1 of the remaining friend. Hence, by the rule of product, there are ways to seat these 6 people.
Note: More generally, this problem is known as a permutation. There are ways to seat people in a row.
How many positive divisors does have?
Any positive divisor of 2000 must have the form , where and are integers satisfying . There are 5 possibilities for and 4 possibilities for , and hence there are (rule of product) positive divisors of 2000 in all.
The following problems will take you through the practice of the two rules discussed above.
How many parallelograms are formed when a set of 5 parallel lines intersects a set of 4 parallel lines?
Details and Assumptions
- All parallel lines are extended indefinitely.
If you count the ways of climbing 3 steps you will find that there are 4 ways of climbing 3 steps.Imagine that the person's legs are so long that they have capacity of climbing 11 steps at a time.Also the person is allowed only to climb upwards.
Then find the number of ways in which you can climb 11 steps?
Bonus: Generalize this for steps.
Three children, each accompanied by a guardian seek admission in a school. The Princi wants to interview all the 6 persons one after the other subject to only one condition that no child is interviewed before its guardian. In how many ways can this be done ?
Problem Solving
This section contains the problems ranging from the simple problems to the hard ones. Try the listed problems and boost up your understanding in problem solving.
Naema goes to the store to buy juice for her birthday party. The store sells jugs of orange juice, apple juice, and cranberry juice. The store also sells frozen cans of grape juice, peach juice, mango juice, and pear juice. If Naema wants only one can or jug of juice, how many different choices does she have?
If someone painted the outside of a cube made out of unit cubes, how many unit cubes would have paint on exactly 2 sides?
From my way to school from house, there are 5 post boxes. My mother gave me 13 (distinct) letters to post. If I can post each letter in any post box I want, in how many ways can I post the letters?
In an escape game, you have found a padlock with numbers from 1 to 60. You have previously found a piece of paper inside a clear bottle. On the piece of paper is a picture of a padlock and four clues:
1) Four numbers complete the sequence.
2) No two numbers are the same.
3) The second number is twice the third.
4) The third number is prime.
How many possible combinations exist for the padlock?
Determine the number of 3 digit positive integers whose digits have a product that is 144?
Daniel wants to get a 100-day streak on Brilliant.org. He plans to do so in the following manner:
On the first day, he does problem. On the second day, he does problems. On the third day, he does problems. This pattern continues on until the th day. On the th day, he does problem. On the th day, he does problems. In general, on the th day, he does problems. Finally, on the th day, he does problem, completing his streak.
In total, how many problems did he do?
A Kaboobly Dooists is a person who does a lot of Kaboobly Doo.
One winter evening, four Kaboobly Dooists, Alice, Bob, Charles and Dick come to see you. Unfortunately you had nothing for them except 5 apples, 4 oranges, 3 mangoes. And you do not wish to spend all 12 of the fruits on them as you wish to keep 8 for yourself. So, you give a total of 4 fruits, one fruit to each of them.
In how many ways can you do this?
The number 2014 has 4 distinct digits; 1 digit is odd, and 3 digits are even, of which one is zero.
How many 4-digit numbers (the first cannot be 0) have these properties?
Let be the number of integers from to (inclusive) which do not contain the digit . What are the last three digits of ?
How many ordered pairs , where are subsets of are there, such that ?
Details and assumptions
Students who are unfamiliar with Set Notation can refer to the blog post on Set Notation for definitions.
