CS70-Homework 8 Solved

1        Counting, Counting, and More Counting
The only way to learn counting is to practice, practice, practice, so here is your chance to do so. For this problem, you do not need to show work that justifies your answers. We encourage you to leave your answer as an expression (rather than trying to evaluate it to get a specific number).

(a)    How many ways are there to arrange n 1s and k 0s into a sequence?

(b)   A bridge hand is obtained by selecting 13 cards from a standard 52-card deck. The order of the cards in a bridge hand is irrelevant.

How many different 13-card bridge hands are there? How many different 13-card bridge hands are there that contain no aces? How many different 13-card bridge hands are there that contain all four aces? How many different 13-card bridge hands are there that contain exactly 6 spades?

(c)    Two identical decks of 52 cards are mixed together, yielding a stack of 104 cards. How many different ways are there to order this stack of 104 cards?

(d)   How many 99-bit strings are there that contain more ones than zeros?

(e)    An anagram of FLORIDA is any re-ordering of the letters of FLORIDA, i.e., any string made up of the letters F, L, O, R, I, D, and A, in any order. The anagram does not have to be an English word.

How many different anagrams of FLORIDA are there? How many different anagrams of ALASKA are there? How many different anagrams of ALABAMA are there? How many different anagrams of MONTANA are there?

(f)     How many different anagrams of ABCDEF are there if: (1) C is the left neighbor of E; (2) C is on the left of E (and not necessarily E’s neighbor)

(g)    We have 9 balls, numbered 1 through 9, and 27 bins. How many different ways are there to distribute these 9 balls among the 27 bins? Assume the bins are distinguishable (e.g., numbered 1 through 27).

(h)   We throw 9 identical balls into 7 bins. How many different ways are there to distribute these 9 balls among the 7 bins such that no bin is empty? Assume the bins are distinguishable (e.g., numbered 1 through 7).

(i)     How many different ways are there to throw 9 identical balls into 27 bins? Assume the bins are distinguishable (e.g., numbered 1 through 27).

(j)     There are exactly 20 students currently enrolled in a class. How many different ways are there to pair up the 20 students, so that each student is paired with one other student?

(k)    How many solutions does x0 +x1 +···+xk = n have, if each x must be a non-negative integer? (l) How many solutions does x0 +x1 = n have, if each x must be a strictly positive integer?

(m) How many solutions does x0 +x1 +···+xk = n have, if each x must be a strictly positive integer?

2        Binomial Beads
(a)    Alistair is making school spirit keychains, which consist of a sequence of n beads on a string. He has blue beads and gold beads. How many unique keychains can he make with exactly k ≤ n blue beads?

(b)   Alistair decides to sell his keychains! He decides on the following pricing scheme:

•  Blue beads have a value of x

•  Gold beads have a value of y

•  The price of a keychain is the product of the values of all of its beads.

What is the price of a keychain with exactly k ≤ n blue beads?

(c)    Alistair decides to make exactly one of every possible unique keychain. If he sells every keychain he creates, how much revenue will he make? Use parts (a) and (b), and leave your answer in summation form.

(d)   Draw a connection between part (c) and the binomial theorem.

(x+y)n =  xkyn−k

Hint: How do you calculate the product (x + y)(x + y)?

3        Minesweeper
Minesweeper is a game that takes place on a grid of squares. When you click a square, it disappears to reveal either an integer ∈ [1,8], a mine, or a blank space. If it reveals a mine, you instantly lose. If it reveals a number, that number refers to the number of mines adjacent to that square (including diagonally adjacent). If it reveals a blank space, there were 0 mines adjacent to it.

You are playing on a 8x8 board with 10 mines randomly distributed across the board. In your first move, you click a square near the center of the board.

(a)    What is the probability that the square reveals...

i.       a mine?

ii.      a blank space?

iii.    the number k?

(b)   The first square you picked revealed the number k. For your next move, you want to minimize the probability of picking a mine. Should you pick a square adjacent to your first pick, or a different square? Your answer should depend on the value of k.

(c)    Your first move resulted in the number 1. You pick the square to the right for your next move.

What is the probability that this square reveals the number 4?

4        Playing Strategically
Bob, Eve and Carol bought new slingshots. Bob is not very accurate hitting his target with probability 1/3. Eve is better, hitting her target with probability 2/3. Carol never misses. They decide to play the following game: They take turns shooting each other. For the game to be fair, Bob starts first, then Eve and finally Carol. Any player who gets shot has to leave the game. The last person standing wins the game. What is Bob’s best course of action regarding his first shot?

(a)    Compute the probability of the event E1 that Bob wins in a duel against Eve alone, assuming he shoots first.

(b)   Compute the probability of the event E2 that Bob wins in a duel against Eve alone, assuming he shoots second.

(c)    Compute the probability of the same events for a duel of Bob against Carol.

(d)   Assuming that both Eve and Carol play rationally, conclude that Bob’s best course of action is to shoot into the air (i.e., intentionally miss)! (Hint: What happens if Bob misses? What if he doesn’t?)

5        Weathermen
Tom is a weatherman in New York. On days when it snows, Tom correctly predicts the snow 70% of the time. When it doesn’t snow, he correctly predicts no snow 95% of the time. In New York, it snows on 10% of all days.

(a)    If Tom says that it is going to snow, what is the probability it will actually snow?

(b)   What is Tom’s overall accuracy?

(c)    Tom’s friend Jerry is a weatherman in Alaska. Jerry claims that she is a better weatherman than Tom even though her overall accuracy is lower. After looking at their records, you determine that Jerry is indeed better than Tom at predicting snow on snowy days and sun on sunny days. How is this possible?

Hint: what is the weather like in Alaska?