15-344/Homework Assignment 10

From Drorbn
Revision as of 19:39, 15 December 2015 by ChrisKim (Talk | contribs)

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).