CSE 312 – Problem Set 2

Instructions

For each problem (other than the gradescope question), you must briefly explain/justify how you obtained your answer, as correct answers without an explanation will not receive full credit. Writing the explanation is an important part of the learning process. Moreover, in the event of an incorrect answer, we can still try to give you partial credit based on the explanation you provide. A higher number of mathematical symbols in your solution will not make your solution more precise or “better” – what is important is that the logical flow is complete and can be followed by the graders. Relying exclusively on mathematical symbols in fact often makes the solution less readable. Avoid expressions such as “it’s easy to see” and “clearly” – just explain these steps.

Use section solutions as a model for what your solutions should look like.

Unless a problem states otherwise, you should leave your answer in terms of factorials, combinations, etc., for instance \(26^7\) or \(26!/7!\) or \(26 \cdot \binom {26}{7}\) are all good forms for final answers. Also, you may find the following short note (by Francis E. Su at Harvey Mudd) helpful.

Submission: There are two gradescope "assignments" for this problem set:

a)

You will do an “online assignment” on gradescope for problem 5. See link in problem below.

b)

You must upload a pdf of your written solutions to Gradescope under “PSet 2 [Written]”. The use of LaTeX is highly recommended. We have provided a LaTeX template that you can use as a starting point. (Note that if you want to hand-write your solutions, you’ll need to scan them. We will not grade work that we are unable to read, so please write neatly if you handwrite.)

Remember to “select pages” to identify which problem is on which page as part of your gradescope upload. Please put each numbered problem on its own page of the pdf (this will make selecting pages easier when you submit), and ensure that your pdfs are oriented correctly (e.g. not upside-down or sideways).

Due Date: This assignment is due at 11:59 PM Wednesday April 15.

Collaboration: Please read the full collaboration policy on the syllabus. If you work with others (and you may), you must still write up your solution independently and name all of your collaborators somewhere on your assignment. In addition, please indicate which problems you used the 312 Learning Assistant on.

Late policy. You have a total of six late days during the quarter, but can only use up to three late days on any one problem set. Please plan ahead, as we will not be willing to add any additional late days except in absolute, verifiable emergencies.

1  Pigeonhole practice (10 points)

In the following problem assume that every year has exactly 365 days and, of course, 12 months. Ignore leap years and ignore year of birth.

a)

(3 points) Show that if there are 200 people registered for CSE 312, then there is some month such that at least 17 people were born in that month (again, ignore year of birth).

b)

For each of the following properties a group of people might possess, either give the minimum number of people that must be in a group to ensure that the property holds, or else indicate that the property need not hold even for arbitrarily large groups of people. In either case, justify your answer.

(i)

(2 points) At least 3 people were born on the same day of the week.

(ii)

(2 points) At least 4 people were born in the same month.

(iii)

(3 points) At least 2 people were born exactly one week apart.

2  Thinking Combinatorially (10 points)

We saw in Lecture 2 that combinatorial proofs can be more elegant than algebraic proofs and also provide insights into an equation that goes beyond algebra. Here’s your opportunity to try your hand at this. Prove the following identity using a combinatorial argument; an algebraic solution will be marked substantially incorrect.

\[\textup {For all integer }a\geq b\geq 0,\qquad \binom {a}{b}2^{a-b} = \displaystyle \sum _{i=b}^a{\binom {a}{i}\binom {i}{b}}\]

Hint: The following hint provides one possible way to think about the problem; you are welcome to use a different approach if you prefer.

• For the left hand side: Think about how you can apply the product rule so that for the first step there are \(\binom {a}{b}\) choices and for the second step there are \(2^{a-b}\) choices.
• For the right hand side, first figure out what counting scenario gives \(\binom {a}{i}\binom {i}{b}\). After that, think about how you can modify the scenario to include all possible values of \(i\); your result will use the sum rule.

(i)

(5 points) Provide a counting scenario where the number of choices is equal to the left hand side of the equation. Explain your reasoning.

(ii)

(5 points) Find another way to count the same quantity that gives the expression on the right hand side. Use the two different ways of counting to justify the identity.

3  How many ways? (8 points)

a)

(4 points) We have 10 people and 30 rooms. How many different ways are there to assign the (distinguishable) people to the (distinguishable) rooms? (Any number of people can go into any of the 30 rooms.)

b)

(4 points) We have 20 identical (indistinguishable) apples. How many different ways are there to place the apples into 30 (distinguishable) boxes? (Any number of apples can go into any of the boxes.)

4  Principle of Inclusion and Exclusion (10 points)

How many positive integers are there less than 1000 that are relatively prime to 100, i.e., have no common factor with 100?

5  Sample Spaces and Probabilities [Online, 20 points]

Do the gradescope question asking for sizes of sample spaces and probability computations. We will not be able to award partial credit, so please enter your submissions carefully.

6  Random Questions (16 points)

For each of the following scenarios, first describe the sample space and indicate how big it is (i.e., what its cardinality is), and then compute the event size and conclude with the probability.

a)

(4 points) You flip a fair coin 50 times. What is the probability of exactly 20 heads?

b)

(4 points) What is the probability that the digit 1 doesn’t appear among \(n\) digits where each digit is one of (0-9) and all sequences are equally likely?

c)

(4 points) Suppose you randomly permute the numbers \(1, 2, \ldots , 500\). That is, you select a permutation uniformly at random. What is the probability that the number \(3\) ends up in the \(130\)-th position in the resulting permutation? (For example, in the permutation \(1,3,2,5,4\) of the numbers \(1\ldots 5\), the number 2 is in the 3rd position in the permutation and the number 4 is in the 5th position.)

d)

(4 points) A fair coin is flipped \(n\) times (each outcome in \(\{H, T\}^n\) is equally likely). What is the probability that all heads occur at the end of the sequence? (The case that there are no heads is a special case of having all heads at the end of the sequence, i.e. 0 heads.)