15-344/Homework Assignment 10

DBN: Classes: 2015-16: 15-344 / Navigation Welcome to Math 344! Edits to the Math 344 web sites no longer count for the purpose of good deed points. # Week of... Notes and Links 1 Sep 14 About This Class, Day One Handout, Tuesday, Hour 3 Handout, Thursday, Tutorial 1 Handout 2 Sep 21 Tuesday, Tutorial 2 Page 1, Tutorial 2 Page 2, Thursday, HW1 3 Sep 28 Tuesday, Class Photo, Tutorial 3 Page 1, Tutorial 3 Page 2, Thursday, HW2 4 Oct 5 Tuesday, Drawing $n$-cubes, Thursday, HW3 5 Oct 12 Tuesday, Tutorial Handout, Thursday, HW4 6 Oct 19 Tuesday, Tutorial Handout, Thursday 7 Oct 26 Term Test on Tuesday, Dijkstra Handout,Thursday,HW5 8 Nov 2 Tuesday, Tutorial Handout, Thursday, HW6, Sunday November 8 is the last day to drop this class 9 Nov 9 Monday-Tuesday is UofT Fall Break, Thursday, HW7 10 Nov 16 Tuesday, Thursday, HW8 11 Nov 23 Tuesday, Thursday, HW9 12 Nov 30 Tuesday, Thursday, HW10 13 Dec 7 Tuesday, FibonacciFormula.pdf, semester ends on Wednesday - no class Thursday F Dec 11-22 The Final Exam Register of Good Deeds Add your name / see who's in!

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}}$