More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Problem Set 5
- A problem set with some problems from this lecture
Questions answered by this video:
In how many ways can you distribute 5 non-distinct objects into 2 boxes?
How many different solutions are there to x1 + x2 + x3 = 3?
How many different solutions are there to x1 + x2 + x3 = 8 if x1 < 3
What is the inclusion / exclusion principle, and how is it used to solve counting problems?
How many base 10 numbers have at least 1 zero and 1 one?
How many permutations are there of aaabbbccc without having three consecutive of the same letter?
How can you use the complement of a set to count the number of things in a set?
What is a derangement in combinatorics and how do you count them up?
In the hat check problem in which everyone gets a random hat, in how many ways does nobody get his hat back?
What is the pigeonhole principle and what are some problems that use it?
How can you prove that two people in a room were born on the same day of the month?
How can you prove that two people in the USA have the same number of hairs on their body?
If a test has a possible range of 0-100, how many people need to take the test to guarantee that at least 3 people get the same score?
If there are 51 houses on a street with addresses between 1000 and 1099, how can you prove that there are at least two houses with consecutive addresses?
If there are n computers on a network, prove that at least two computers are connected to the same number of other computers?
If a computer goes down at least one time each day, and during a 30-day month, it goes down at most 45 times, how can you prove that the computer goes down exactly 14 times in some consecutive period of days?
Staff Review
Currently 4.0/5 Stars.
This lecture deals with some more classic combinatorics problems. The inclusion / exclusion principle, permutations, combinations, and the pigeonhole principle are some well-known topics that are dealt with in this lesson. All of the examples that are done really solidify the concept of counting objects in different situations.