=========================preview======================
(COMP170)2006_f_midterm1_slides.pdf
Back to COMP170 Login to download
======================================================
COMP 170 C Fall 2006
Midterm 1 Solution
Q1. Suppose that we have a student hall with 9 rooms labelled A, B, . . . , I.
How many ways are there to assign 10 students to the 9 hall rooms so that every student is assigned and no hall room is empty?
This is exactly the number of onto functions from S10 to S9 (Si, being a set with i elements)
This is exactly the number of onto functions from S10 to S9 (Si, being a set with i elements)
Note that there should be exactly one pair of stu-dents get assigned to the same room, while all the others get assigned an individual room.
10
There are 2 ways of choosing that pair.
This is exactly the number of onto functions from S10 to S9 (Si, being a set with i elements)
Note that there should be exactly one pair of stu-dents get assigned to the same room, while all the others get assigned an individual room.
There are 10 ways of choosing that pair.
2
Once the pair is chosen, there are 9! ways of as-sigining the students to the rooms.
This is exactly the number of onto functions from S10 to S9 (Si, being a set with i elements)
Note that there should be exactly one pair of stu-
dents get assigned to the same room, while all the
others get assigned an individual room.
10
There are 2 ways of choosing that pair.
Once the pair is chosen, there are 9! ways of as-sigining the students to the rooms.
So the answer is
10
9! = 16329600
2
Q2. Suppose you have 5 standard six-sided dice; one red, one green, one yellow, one black, one or-ange. Each die has the numbers 1-6 on its sides. Roll all of the dice. An outcome of a roll is a number for each die.
An outcome contains a
(i)
two-of-a-kind if there are at least two dice showing the same number;
(ii)
three-of-a-kind if there are at least three dice showing the same number;
(iii) four-of-a-kind if there are at least four dice showing the same number;
(iv) .ve-of-a-kind if all .ve dice show the same number.
(a)
How many possible outcomes are there?
(a)
How many possible outcomes are there?
(a)
How many possible outcomes are there?
65 = 7776 65 = 7776
(b)
How many possible outcomes contain a .ve-of-a-kind?
(a)
How many possible outcomes are there?
65 = 7776
(b)
How many possible outcomes contain a .ve-of-a-kind?
(c)
How many possible outcomes contain a four-of-a-kind but no .ve-of-a-kind?
(c)
How many possible outcomes contain a
four-of-a-kind but no .ve-of-a-kind?
Each such outcome is uniquely determined by
(i)
the value of the four-of-a-kind,
(ii)
the color of the die that is not part of the four-of-a-kind and
(iii) the value of that die. So the answer is
6 5 5 = 150.
(d)
How many possible outcomes contain a three-of-a-kind but no four-of-a-kind?
(d)
How many possible outcomes contain a three-of-a-kind but no four-of-a-kind?
Each such outcome is uniquely determined by
(i)
the value of the three-of