Assignment 3
https://cglab.ca/~morin/teaching/2804/assn3.html 1/4
COMP2804: Discrete Structures
II
Assignment 3
Your assignment must be submitted as a single PDF file through cuLearn
Late assignments will not be accepted under any circumstances. If you’re unable to complete
the assignment due to a valid and documented medical or personal situation then the weight
of this assignment can be shifted to the weight of the remaining assignments.
You are encouraged to collaborate on assignments, but at the level of discussion only. When
Past experience has shown conclusively that those who do not put adequate effort into the
assignments do not learn the material and have a probability near 1 of doing poorly on the
exams.
The answers should be concise, clear and neat.
When presenting proofs, every step should be justified.
Meat
1. ID
1. Make sure the first thing on page 1 of your assignment is your name and student number.
1. Probabilities of Scrabble Words
A scrabble hand is a set of 7 tiles, each having one of the english uppercase letters on them, drawn
uniformly at random from a bag of 100 tiles. The number of tiles of each letter are as follows:
3/10/2020 Assignment 3
https://cglab.ca/~morin/teaching/2804/assn3.html 2/4
E×12, A×9, I×9, O×8, N×6, R×6, T×6, L×4, S×4, U×4, D×4, G×3, B×2, C×2, M×2, P×2, F×2,
H×2, V×2, W×2, Y×2, K×1, J×1, X×1, Q×1, Z×1
1. What is the probability that a scrabble hand contains the word HEXAGON ?
2. What is the probability that a scrabble hand contains the word GARBAGE ?
3. What is the probability that a scrabble hand contains the word APPLE ?
Hint: Review the notes on uniform probability spaces (Oct 10, Section 5.4)
A rat feeder is essentially a straw whose diameter is just large enough for 1 (medicine) pill or 1
(food) pellet, but is long enough to hold many pills and pellets. The pill and pellets are put in at
one of the feeder and come out the other end (when the rat presses a pedal) in the same order they
were put in.
Suppose we place 25 identical pellets and 4 identical pills uniformly at random into a rat feeder.
The rat then comes and consumes one item from the feeder and then consumes another item
from the feeder.
1. Let be the event ” is a pellet” and let be the event ” is a pill”.
2. What is ?
3. What is ?
4. Are the events and independent? In other words, is ?
3. A Coin-Flipping Game
Consider the following coin tossing games. For each one, compute the probability that you win the
game. For each question, the answer is a rational number so you should give this number exactly
and give a decimal approximation of it as well.
1. You toss a fair coin twice and win if it comes up heads at least once.
2. You toss a fair coin 10 times and win if comes up heads at least five times.
3. You toss a fair coin twice and win if it comes up heads exactly once.
4. You toss a fair coin 10 times and win if comes up heads exactly five times.
4. Blindfolded Musical Chairs
x1 x2
A x1 B x2
Pr(A ∩ B)
Pr(A ∪ B)
A B Pr(A ∩ B) = Pr(A) ⋅ Pr(B)
3/10/2020 Assignment 3
https://cglab.ca/~morin/teaching/2804/assn3.html 3/4
We are playing a game of blindfolded musical chairs with 20 blindfolded people and 40 chairs.
When the music stops each person picks a chair uniformly at random and sits on it.
1. What is the probability that some chair has at least two people sitting on it?
2. What is the probability that some chair has at least three people sitting on it?
5. Random Number Weirdness
We independently pick two random numbers and from the set . (Note:
Independence means we may pick .)
1. What is the probability that and are both even?
2. Suppose I tell you that at least one of or is even. What is the (conditional) probability
that and are both even?
3. What is the probability that at least one of or is equal to ?
4. Suppose I tell you that at least one of or is even. What is the probability that at least
one of or is equal to ?
5. Suppose I tell you that at least one of or is even. What is the probability that at least
one of or is equal to ?
6. Uniqueness of Maximum and Median
Let be an odd integer. The \emph{median} of a sequence , denoted of numbers,
, is the unique value such that there are at least values less than or
equal to and at least values greater than or equal to .
For example,
since and ; and
since and .
Consider a uniform random sequence of numbers each chosen from the set
R1 R2 {1,…, 1000}
R1 = R2
R1 R2
R1 R2
R1 R2
R1 R2 1000
R1 R2
R1 R2 1000
R1 R2
R1 R2 999
n x1,…, xn
median(x1,…, xn) x ⌈n/2⌉
x ⌈n/2⌉ x
median(8, 4, 3, 4, 7, 5, 6) = 5
4, 3, 4, 5 ≤ 5 8, 7, 5, 6 ≥ 5
median(8, 5, 3, 4, 7, 5, 6) = 5
5, 3, 4, 5 ≤ 5 8, 5, 7, 5, 6 ≥ 5
x1,…, x7 7
{1, 2, 3,…, 10}
3/10/2020 Assignment 3
https://cglab.ca/~morin/teaching/2804/assn3.html 4/4
1. What is the probability that occurs exactly once in ?
2. What is the probability that occurs exactly once in ?
max{x1,…, x7} x1,…, x7
median(x1,…, x7) x1,…, x7 EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司