15-344/Homework Assignment 10

From Drorbn
Jump to: navigation, search

This assignment is due by Friday December 11 at 5PM. It can be submitted either to Gaurav during his office hours on Thursday December 10 at 3:30-5:30 or during his office hours on Friday December 11 at 4-5, both at 215 Huron room 1012. It can also be submitted to a drop box near Dror's office, Bahen 6178, at any time between Thursday December 10 at 5 and Friday December 11 at 5.

Here and everywhere, neatness counts!! You may be brilliant and you may mean just the right things, but if the teaching assistants will be having hard time deciphering your work they will give up and assume it is wrong.

Reread your notes for November 26 through December 3. Remember that reading math isn't like reading a novel! If you read a novel and miss a few details most likely you'll still understand the novel. But if you miss a few details in a math text, often you'll miss everything that follows. So reading math takes reading and rereading and rerereading and a lot of thought about what you've read.

Solve and submit your solutions of the following three problems:

Problem 1. What is the probability that a soccer game with 2n goals ends with a tie, and that this tie is the first tie in the game (except before the first goal)?

Problem 2. How many possible histories are there for a soccer game that ends with the score (m,n), where m>n, if it is known that the first team is never behind the second?

Problem 3. Let n be a natural number. How many sequences of integers 0=a_1\leq a_2\leq\ldots\leq a_n are there, such that a_k<k for every 1\leq k\leq n? For example, for n=3 the allowed sequences are 000, 001, 002, 011, and 012.

Dror's notes above / Students' notes below

Homework Assignment 10 Solutions

1)What is the probability that a soccer game with 2n goals ends with a tie, and that the tie is the first tie in the game (except before the first goal)?

A) 2n goals ending with a tie means n goals each ((n,n) on the Catalan diagram). Number of possibilities with no tie before (n,n) is basically the number of possible paths to (n,n) without crossing the diagonal line. This is equal to: C_{n-1} = \frac{1}{n}\binom{2(n-1)}{n-1}

Total number of possible games with 2n goals is \binom{2n}{n}

The required probability is: C_{n-1} = 2\frac{\frac{1}{n}\binom{2(n-1)}{n-1}}{\binom{2n}{n}}

The reason why we multiply the probability by two is because there are two possible cases (either above the diagonal or below the diagonal).

2)How many possible histories are there for a soccer game that ends with the score (m,n), where m>n, if it is known that the first team is never behind?

A) This can be thought of as an A-dominant game. The total number of possibilities with end score (n,m) is \binom{n+m}{n} Using Andre's Reflection, we need to find the number of good paths (A-dominant paths): Total paths - Bad paths (any paths that cross the diagonal) = Good Paths.

Number of Bad Paths to (n,m) = \binom{n+m}{n-1}, so using Andre's Reflection, we have

\binom{n+m}{n} - \binom{n+m}{n-1} = \frac{(n+m)!}{n!m!} - \frac{(n+m)!}{(n-1)!(m+1)!}

Simplifying it gives:

\frac{(n+m)!(m-n+1)}{n!(m+1)!}

3) Let n be a natural number. How many sequences of integers 0=a_1\leq a_2\leq\ldots\leq a_n are there, such that a_k<k for every 1\leq k\leq n? For example, for n=3 the allowed sequences are 000, 001, 002, 011, and 012.

A) This could also be thought as an A-dominant game. We can think of each digit in a sequence as the score difference between the two teams at a certain point in the game. For example, 000 would mean the score started with a tie and ended with a tie. Likewise, 012 would mean that (starting from the right end), Team A led by two goals in the first third of the game, by one goal at half time and gave up another goal and tied the game in the end. In the 3 digit sequence case, the total goal in the game is 3 therefore sequences like 022 are not possible. (this would mean Team B was down by two goals and then scored two to tie the game -> 4 goals total). Therefore, for sequences of length n, the number number of sequences is C_{n} = \frac{1}{n+1}\binom{2n}{n}