COMP2804: Discrete Structures II
$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$
Assignment 3

Administrivia

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:

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)

2. Feeding Your Rat

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 $x_1$ from the feeder and then consumes another item $x_2$ from the feeder.

  1. Let $A$ be the event "$x_1$ is a pellet" and let $B$ be the event "$x_2$ is a pill".
  2. What is $\Pr(A\cap B)$?
  3. What is $\Pr(A\cup B)$?
  4. Are the events $A$ and $B$ independent? In other words, is $\Pr(A\cap B)=\Pr(A)\cdot\Pr(B)$?

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

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 $R_1$ and $R_2$ from the set $\{1,\ldots,1000\}$. (Note: Independence means we may pick $R_1=R_2$.)

  1. What is the probability that $R_1$ and $R_2$ are both even?
  2. Suppose I tell you that at least one of $R_1$ or $R_2$ is even. What is the (conditional) probability that $R_1$ and $R_2$ are both even?
  3. What is the probability that at least one of $R_1$ or $R_2$ is equal to $1000$?
  4. Suppose I tell you that at least one of $R_1$ or $R_2$ is even. What is the probability that at least one of $R_1$ or $R_2$ is equal to $1000$?
  5. Suppose I tell you that at least one of $R_1$ or $R_2$ is even. What is the probability that at least one of $R_1$ or $R_2$ is equal to $999$?

6. Uniqueness of Maximum and Median

Let $n$ be an odd integer. The \emph{median} of a sequence $x_1,\ldots,x_n$, denoted of numbers, $\mathrm{median}(x_1,\ldots,x_n)$, is the unique value $x$ such that there are at least $\lceil n/2\rceil$ values less than or equal to $x$ and at least $\lceil n/2\rceil$ values greater than or equal to $x$.

For example, \[
\mathrm{median}(\color{red}{8}, \color{blue}{4}, \color{blue}{3}, \color{blue}{4}, \color{red}{7}, \color{purple}{5}, \color{red}{6})=5 \] since $\color{blue}{4},\color{blue}{3},\color{blue}{4},\color{purple}{5} \le 5$ and $\color{red}{8},\color{red}{7},\color{purple}{5},\color{red}{6}\ge 5$; and \[
\mathrm{median}(\color{red}{8}, \color{purple}{5}, \color{blue}{3}, \color{blue}{4}, \color{red}{7}, \color{purple}{5}, \color{red}{6})=5 \] since $\color{purple}{5},\color{blue}{3},\color{blue}{4},\color{purple}{5} \le 5$ and $\color{red}{8},\color{purple}{5},\color{red}{7},\color{purple}{5},\color{red}{6}\ge 5$.

Consider a uniform random sequence $x_1,\ldots,x_7$ of $7$ numbers each chosen from the set $\{1,2,3,\ldots,10\}$

  1. What is the probability that $\max\{x_1,\ldots,x_7\}$ occurs exactly once in $x_1,\ldots,x_7$?
  2. What is the probability that $\mathrm{median}(x_1,\ldots,x_7)$ occurs exactly once in $x_1,\ldots,x_7$?