Term
Topic: Counting
A multiple-choice test contains 10 questions. There are four possible answers for each question.
In how many ways can a student answer the questions on the test if the student answers every question? |
|
Definition
Here, there are 4 choices per question, and 10 questions.
Choosing an answer for each question is a sequential task, so there are 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 = 4^10 ways to answer. |
|
|
Term
Topic: Counting
A multiple-choice test contains 10 questions. There are four possible answers for each question.
In how many ways can a student answer the questions on the test if the student can leave answers blank? |
|
Definition
Here, there are 5 choices per question (a, b, c, d and N/A), and 10 questions.
Choosing an answer for each question is a sequential task, so there are 5^10 ways to answer. |
|
|
Term
Topic: Counting
How many strings of three decimal digits do not contain the same digit three times? |
|
Definition
| There are 103 = 1000 decimal strings with 3 digits, and there are 10 of them containing three equal digits: 000, 111, . . . , 999. Therefore, there are 1000 − 10 = 990 strings that do not contain the same digit three times. |
|
|
Term
Topic: Counting
How many strings of three digits begin with an odd number? |
|
Definition
| There are 5 odd digits, therefore we have 5 × 10 × 10 = 500 strings of three decimal digits beginning with an odd digit. |
|
|
Term
Topic: Counting
Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4. |
|
Definition
| There are four possible remainders when an integer is divided by 4: 0, 1, 2, or 3 (these are pigeonholes). Therefore, by the pigeonhole principle at least two (= ceiling(5/4)) of the five given remainders (these are pigeons) must be the same. |
|
|
Term
Topic: Counting
There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed? |
|
Definition
| The 38 time periods are the pigeonholes, and the 677 classes are the pigeons. By the generalized pigeonhole principle there is at least one time period in which at least ceiling(677/38) = 18 classes are meeting. Since each class must meet in a different room, we need 18 rooms. |
|
|
Term
Topic: Counting
List all the permutations of {a, b, c}. |
|
Definition
| This is a permutation and repeats are not allowed. Therefore, there are P(3, 3) = 3! 0! = 6 permutations, which are: (a, b, c) ; (a, c, b) ; (b, a, c) ; (b, c, a) ; (c, a, b) ; (c, b, a) |
|
|
Term
Topic: Counting
Find the number of 5-permutations of a set with nine elements. |
|
Definition
| P(n, r) where n = 9 and r = 5. P(9, 5) = 9!/(9 − 5)! = 9!/4! = 15,120. |
|
|
Term
Topic: Counting
How many bit strings of length 10 contain exactly four 1s? |
|
Definition
| This is just asking us to choose 4 out of 10 slots to place 1’s in. C(10, 4) = 10!/(4! × 6!) = (10 × 9 × 8 × 7)/4! = 210. |
|
|
Term
Topic: Counting
How many 5 cards can be drawn from a deck of 52 cards? |
|
Definition
| C(52, 5) = 52!/[5!(52-5)!] = 52!/(5!*47!) |
|
|
Term
Topic: Counting
How many ways can one draw 3 diamonds and 2 clubs from a deck of 52 cards? |
|
Definition
# of ways to draw 3 diamonds: C(13, 3) = 13!/[3!(13-3)!] = 13!/(3!*10!) = 13*11*2 = 286
# of ways to draw 2 clubs: C(13, 2) = 13!/[2!(13-2)!] = 13!/(2!*11!) = 13*6 = 78
286*78 = 22308 total ways/combinations |
|
|
