Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 70

Summer 2022

Discrete Mathematics and Probability Theory

HW 5

Sundry

Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)

1   Computability Basics

Consider the problem of determining if a function F returns TRUE.  That is, given a function F that takes inputs from some (possibly infinite) set X , we want to know if there is any input x ∈ X such that F(x) returns TRUE. Prove that this problem is undecidable.

2   Unprogrammable Programs

Prove whether the programs described below can exist or not.

(a) A program P(F,x,y) that returns true if the program F outputs y when given x as input (i.e. F(x) = y) and false otherwise.

(b) A program P that takes two programs F and G as arguments, and returns true if F and G halt on the same set of inputs (or false otherwise).

3   Probability Warm-Up

(a)  Suppose that we have a bucket of 30 red balls and 70 blue balls. If we pick 20 balls uniformly out of the bucket, what is the probability of getting exactly k red balls (assuming 0 ≤ k ≤ 20) if the sampling is done with replacement, i.e. after we take a ball out the bucket we return the ball back to the bucket for the next round?

(b)  Same as part (a), but the sampling is without replacement, i.e.  after we take a ball out the bucket we do not return the ball back to the bucket.

(c) If we roll a regular, 6-sided die 5 times.  What is the probability that at least one value is observed more than once?

4   Monty Halls Revenge

Due to a quirk of the television studio’s recruitment process, Monty Hall has ended up drawing all the contestants for his game show from among the ranks of former CS70 students. Unfortunately for Monty, the former students’ amazing probability skills have made his cars-and-goats gimmick unprofitable for the studio. Monty decides to up the stakes by asking his contestants to generalise to three new situations with a variable number of doors, goats, and cars:

(a) There are n doors for some n > 2. One has a car behind it, and the remaining n − 1 have goats.

As in the ordinary Monty Hall problem, Monty will reveal one door with a goat behind it after you make your first selection. How would switching affect the odds that you select the car?    (Hint: Think about the size of the sample space for the experiment where you always switch. How many of those outcomes are favorable?)

(b) Again there are n > 2 doors, one with a car and n − 1 with goats, but this time Monty will reveal n−2 doors with goats behind them instead of just one. How does switching affect the odds of winning in this modified scenario?

(c) Finally, imagine there are k < n−1 cars and nk goats behind the n > 2 doors. After you make your first pick, Monty will reveal j < n −k doors with goats.  What values of j , k maximize the relative improvement in your odds of winning if you choose to switch?  (i.e.  what j , k maximizes the ratio between your odds of winning when you switch, and your odds of winning when you do not switch?)

5   Easter Eggs

You made the trek to Soda for a Spring Break-themed homework party, and every attendee gets to leave with a party favor. You’re given a bag with 20 chocolate eggs and 40 (empty) plastic eggs. You pick 5 eggs (uniformly) without replacement.

(a) What is the probability that the first egg you drew was a chocolate egg?     (b) What is the probability that the second egg you drew was a chocolate egg?

(c)  Given that the first egg you drew was an empty plastic one, what is the probability that the fifth egg you drew was also an empty plastic egg?

6   Poisoned Smarties

Supposed there are 3 people who are all owners of their own Smarties factories.   Burr Kelly, being the brightest and most innovative of the owners, produces considerably more Smarties than her competitors and has a commanding 45% of the market share. Yousef See, who inherited her riches, lags behind Burr and produces 35% of the world’s Smarties. Finally Stan Furd, brings up the rear with a measly 20%. However, a recent string of Smarties related food poisoning has forced

the FDA investigate these factories to find the root of the problem. Through her investigations, the inspector found that one Smarty out of every 100 at Kelly’s factory was poisonous. At See’s factory, 1.5% of Smarties produced were poisonous. And at Furd’s factory, the probability a Smarty was poisonous was 0.02.

(a) What is the probability that a randomly selected Smarty will be safe to eat?

(b) If we know that a certain Smarty didnt come from Burr Kellys factory, what is the probability

that this Smarty is poisonous?

(c)  Given this information, if a randomly selected Smarty is poisonous, what is the probability it came from Stan Furd’s Smarties Factory?

7   Peaceful rooks

A friend of yours, Eithen Quinn, is fascinated by the following problem: placing m rooks on an n × n chessboard, so that they are in peaceful harmony (i.e.  no two threaten each other).  Each rook is a chess piece, and two rooks threaten each other if and only if they are in the same row or column.  You remind your friend that this is so simple that a baby can accomplish the task.  You forget however that babies cannot understand instructions, so when you give the m rooks to your baby niece, she simply puts them on random places on the chessboard.  She however, never puts two rooks at the same place on the board.

(a) Assuming your niece picks the places uniformly at random, what is the chance that she places the (i+1)st rook such that it doesn’t threaten any of the first i rooks, given that the first i rooks don’t threaten each other?

(b) What is the chance that your niece actually accomplishes the task and does not prove you wrong?

(c) Now imagine that the rooks can be stacked on top of each other, then what would be the probability that your niece’s placements result in peace? Assume that two rooks threaten each other if they are in the same row or column. Also two pieces stacked on top of each other are obviously in the same row and column, therefore they threaten each other.

(d) Explain the relationship between your answer to the previous part and the birthday paradox. In particular if we assume that 23 people have a 50% chance of having a repeated birthday (in a 365-day calendar), what is the probability that your niece places 23 stackable pieces in a peaceful position on a 365 × 365 board?

8   Kolmogorov Complexity

Compressing a bit string x of length n can be interpreted as the task of creating a program of fewer than n bits that returns x. The Kolmogorov complexity of a string K(x) is the length of an optimally-compressed copy of x; that is, K(x) is the length of shortest program that returns x.

(a) Explain why the notion of the "smallest positive integer that cannot be defined in under 280 characters" is paradoxical.

(b) Prove that for any length n, there is at least one string of bits that cannot be compressed to less than n bits.

(c)  Say you have a program K that outputs the Kolmogorov complexity of any input string. Under the assumption that you can use such a program K as a subroutine, design another program P that takes an integer n as input, and outputs the length-n binary string with the highest Kolmogorov complexity. If there is more than one string with the highest complexity, output the one that comes first lexicographically.

(d) Let’s say you compile the program P you just wrote and get an m bit executable, for some m ∈ N (i.e.  the program P can be represented in m bits).   Prove that the program P (and consequently the program K) cannot exist.

(Hint: Consider what happens when P is given a very large input n.)