15-344/Homework Assignment 10 - Revision history

ChrisKim at 02:29, 17 December 2015

2015-12-17T02:29:53Z

← Older revision		Revision as of 22:29, 16 December 2015
Line 45:		Line 45:
	'''3) Let <math>n</math> be a natural number. How many sequences of integers <math>0=a_1\leq a_2\leq\ldots\leq a_n</math> are there, such that <math>a_k<k</math> for every <math>1\leq k\leq n</math>? For example, for <math>n=3</math> the allowed sequences are 000, 001, 002, 011, and 012.'''		'''3) Let <math>n</math> be a natural number. How many sequences of integers <math>0=a_1\leq a_2\leq\ldots\leq a_n</math> are there, such that <math>a_k<k</math> for every <math>1\leq k\leq n</math>? For example, for <math>n=3</math> 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, <math>000</math> would mean the score started with a tie and ended with a tie. Likewise, <math>012</math> 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 <math>022</math> 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 <math>n</math>, the number number of sequences is <math>C_{n} = \frac{1}{n}\binom{2n}{n}</math>		'''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, <math>000</math> would mean the score started with a tie and ended with a tie. Likewise, <math>012</math> 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 <math>022</math> 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 <math>n</math>, the number number of sequences is <math>C_{n} = \frac{1}{n+1}\binom{2n}{n}</math>

ChrisKim at 00:07, 16 December 2015

2015-12-16T00:07:15Z

← Older revision		Revision as of 20:07, 15 December 2015
Line 20:		Line 20:
	'''1)What is the probability that a soccer game with <math>2n</math> goals ends with a tie, and that the tie is the first tie in the game (except before the first goal)?'''		'''1)What is the probability that a soccer game with <math>2n</math> goals ends with a tie, and that the tie is the first tie in the game (except before the first goal)?'''

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

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

	A) This can be thought of as an A-dominant game.		'''A)''' This can be thought of as an A-dominant game.
	The total number of possibilities with end score <math>(n,m)</math> is <math>\binom{n+m}{n}</math>		The total number of possibilities with end score <math>(n,m)</math> is <math>\binom{n+m}{n}</math>
	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.		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.
Line 42:		Line 42:

	<math>\frac{(n+m)!(m-n+1)}{n!(m+1)!}</math>		<math>\frac{(n+m)!(m-n+1)}{n!(m+1)!}</math>

			'''3) Let <math>n</math> be a natural number. How many sequences of integers <math>0=a_1\leq a_2\leq\ldots\leq a_n</math> are there, such that <math>a_k<k</math> for every <math>1\leq k\leq n</math>? For example, for <math>n=3</math> 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, <math>000</math> would mean the score started with a tie and ended with a tie. Likewise, <math>012</math> 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 <math>022</math> 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 <math>n</math>, the number number of sequences is <math>C_{n} = \frac{1}{n}\binom{2n}{n}</math>

ChrisKim at 23:48, 15 December 2015

2015-12-15T23:48:55Z

← Older revision		Revision as of 19:48, 15 December 2015
Line 28:		Line 28:

	The reason why we multiply the probability by two is because there are two possible cases (either above the diagonal or below the diagonal).		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 <math>(m,n)</math>, where <math>m>n</math>, 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 <math>(n,m)</math> is <math>\binom{n+m}{n}</math>
			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 <math>(n,m) = \binom{n+m}{n-1}</math>, so using Andre's Reflection, we have

			<math>\binom{n+m}{n} - \binom{n+m}{n-1} = \frac{(n+m)!}{n!m!} - \frac{(n+m)!}{(n-1)!(m+1)!}</math>

			Simplifying it gives:

			<math>\frac{(n+m)!(m-n+1)}{n!(m+1)!}</math>

ChrisKim at 23:39, 15 December 2015

2015-12-15T23:39:32Z

← Older revision		Revision as of 19:39, 15 December 2015
Line 15:		Line 15:

	{{15-344:Dror/Students Divider}}		{{15-344:Dror/Students Divider}}

			Homework Assignment 10 Solutions

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

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

			Total number of possible games with <math>2n</math> goals is <math>\binom{2n}{n}</math>

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

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

Drorbn at 20:22, 7 December 2015

2015-12-07T20:22:41Z

← Older revision		Revision as of 16:22, 7 December 2015
Line 1:		Line 1:
	{{15-344/Navigation}}		{{15-344/Navigation}}
	This assignment is due <span style="color: blue;">at ~~TBA,~~ ~~yet~~ no ~~sooner~~ ~~than~~ Thursday December 10 at ~~6PM</span>.~~ ~~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~~.		This assignment is due <span style="color: blue;">by Friday December 11 at 5PM</span>. 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.		'''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.

Drorbn at 23:10, 3 December 2015

2015-12-03T23:10:47Z

← Older revision		Revision as of 19:10, 3 December 2015
Line 1:		Line 1:
	{{15-344/Navigation}}		{{15-344/Navigation}}
		⚫	This assignment is due <span style="color: blue;">at TBA, yet no sooner than Thursday December 10 at 6PM</span>. 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.
	{{In Preparation}}
⚫	This assignment is due <span style="color: blue;">~~...~~</span>. 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~~''' sections ... of our textbook, '''and~~''' 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.		'''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''' ~~problems ... in section ..., but~~ submit ~~only~~ your solutions of the ~~underlined~~ problems.		'''Solve''' and submit your solutions of the following three problems:

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

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

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

	{{15-344:Dror/Students Divider}}		{{15-344:Dror/Students Divider}}

Drorbn: Created page with "{{15-344/Navigation}} {{In Preparation}} This assignment is due .... Here and everywhere, '''neatness counts!!''' You may be brilliant and yo..."

2015-12-03T15:14:50Z

Created page with "{{15-344/Navigation}} {{In Preparation}} This assignment is due <span style="color: blue;">...</span>. Here and everywhere, '''neatness counts!!''' You may be brilliant and yo..."

New page

{{15-344/Navigation}}
{{In Preparation}}
This assignment is due <span style="color: blue;">...</span>. 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''' sections ... of our textbook, '''and''' 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''' problems ... in section ..., but submit only your solutions of the underlined problems.

'''In addition,''' ...

{{15-344:Dror/Students Divider}}