University of Washington
Department of Mathematics Homework 1

MATH 394: Probability I

Instructor: Arman Jahangiri

Homework Policy

Submission and Deadline

Please:

• Submit homework as a single PDF on Gradescope by 10:00 PM (Pacific Time) on the listed due date.
• Begin each problem on a new page, and ensure that pages are correctly tagged in Gradescope.
• Write solutions clearly and legibly.
• Typesetting solutions in LaTeX is encouraged, but not required.

Late Days

Each student is allotted six late days for the quarter. A late day extends a homework deadline by up to 24 hours without penalty. For example, submitting an assignment anytime between 10:01 PM on the due date and 10:00 PM the following day counts as one late day.

The following rules apply:

• No explanation is required to use late days.
• At most two late days may be used on any single homework assignment.
• Late days may not be used on the final homework assignment or on any assignment for which solutions have already been released.
• It is the student’s responsibility to keep track of how many late days have been used during the quarter.

Once all late days have been exhausted, additional late submissions will incur a penalty of 10% per day, up to a maximum deduction of 50%. Assignments submitted more than five days late, or after solutions have been released, will not be accepted.

Submission Issues and Technical Difficulties

If a serious technical issue prevents a timely Gradescope submission, students may temporarily submit their assignment by email to the instructor at armanjg@uw.edu. In such cases:

• The submission must consist of a single PDF file. The email subject line must follow the format: \[ \texttt {HW\# Submission - FULL NAME - STUDENT ID}. \]
• Once the Gradescope issue has been resolved, the student must upload the exact same file to Gradescope as soon as possible.
• The student should clearly indicate in the Gradescope submission that the assignment was previously submitted by email before the deadline.

Email submissions are intended only for genuine technical emergencies and should not be used as a substitute for timely Gradescope submission.

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 23.

Three people get into an empty elevator at the first floor of a building that has 10 floors. Each presses the button for their desired floor, unless one of the others has already pressed that button. Assume that they are equally likely to want to go to floors 2 through 10, independently of each other.

What is the probability that the buttons for 3 consecutive floors are pressed?

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 3.

Fred is planning to go out to dinner each night of a certain week, Monday through Friday, with each dinner being at one of his ten favorite restaurants.

(a)

How many possibilities are there for Fred’s schedule of dinners for that Monday through Friday, if Fred is not willing to eat at the same restaurant more than once?

(b)

How many possibilities are there for Fred’s schedule of dinners for that Monday through Friday, if Fred is willing to eat at the same restaurant more than once, but is not willing to eat at the same place twice in a row or more?

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 15–18.

Give story proofs for the following identities.

(a)

Show that \[ \sum _{k=0}^{n} {n \choose k}=2^n. \]

(b)

Show that \[ \sum _{k=0}^{n}{n \choose k}^2={2n \choose n}, \] for all positive integers \(n\).

(c)

Show that \[ \sum _{k=1}^{n} k{n \choose k}^2 = n{2n-1 \choose n-1}, \] for all positive integers \(n\).

Hint: Consider choosing a committee of size \(n\) from two groups of size \(n\) each, where only one of the two groups has people eligible to become the chair of the committee.

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 25.

A city with 6 districts has 6 robberies in a particular week. Assume the robberies are located randomly, with all possibilities for which robbery occurred where equally likely.

What is the probability that some district had more than 1 robbery?

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 5.

A knock-out tournament is being held with \(2^n\) tennis players. This means that for each round, the winners move on to the next round and the losers are eliminated, until only one person remains. For example, if initially there are \(2^4=16\) players, then there are 8 games in the first round, then the 8 winners move on to round 2, then the 4 winners move on to round 3, then the 2 winners move on to round 4, the winner of which is declared the winner of the tournament. There are various systems for determining who plays whom within a round, but these do not matter for this problem.

(a)

How many rounds are there?

(b)

Count how many games in total are played, by adding up the numbers of games played in each round.

(c)

Count how many games in total are played, this time by directly thinking about it without doing almost any calculation.

Hint: How many players need to be eliminated?

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 49.

A fair die is rolled \(n\) times. What is the probability that at least 1 of the 6 values never appears?

Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 53.

Fred needs to choose a password for a certain website. Assume that he will choose an 8-character password, and that the legal characters are the lowercase letters \(a,b,c,\dots ,z\), the uppercase letters \(A,B,C,\dots ,Z\), and the numbers \(0,1,\dots ,9\).

(a)

How many possibilities are there if he is required to have at least one lowercase letter in his password?

(b)

How many possibilities are there if he is required to have at least one lowercase letter and at least one uppercase letter in his password?

(c)

How many possibilities are there if he is required to have at least one lowercase letter, at least one uppercase letter, and at least one number in his password?