Mathcamp 2020 Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveThis Math Jam will discuss solutions to the 2020 Mathcamp Qualifying Quiz. Mathcamp is an intensive 5-week-long summer program for mathematically talented high school students. More than just a summer camp, Mathcamp is a vibrant community, made up of a wide variety of people who share a common love of learning and passion for mathematics.
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: Marisa Debowsky
vapodaca
2020-05-12 19:30:12
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
hanakim
2020-05-12 19:30:36
hi
hi
Pixelboboready
2020-05-12 19:30:36
Hi
Hi
ASTR0N0M3R_11
2020-05-12 19:30:36
hello
hello
oboy
2020-05-12 19:30:36
Hi
Hi
Pixelboboready
2020-05-12 19:30:36
Hi
Hi
theodoremui
2020-05-12 19:30:36
hi
hi
sapphire1
2020-05-12 19:30:36
hi!
hi!
theodoremui
2020-05-12 19:30:36
so excited
so excited
eagle702
2020-05-12 19:30:36
Hello!
Hello!
Elaine_Wang
2020-05-12 19:30:36
Pixelboboready
2020-05-12 19:30:36
Hi vapodaca
Hi vapodaca
Elaine_Wang
2020-05-12 19:30:36
YAY!!!
YAY!!!
awesomeguy856
2020-05-12 19:30:36
hi
hi
theodoremui
2020-05-12 19:30:36
hi vapodaca
hi vapodaca
ancientwarrior
2020-05-12 19:30:36
hello!
hello!
Parna
2020-05-12 19:30:36
Good afternoon/evening!
Good afternoon/evening!
smartcookie12
2020-05-12 19:30:36
Hi
Hi
vapodaca
2020-05-12 19:30:43
I love the enthusiasm!
I love the enthusiasm!
vapodaca
2020-05-12 19:30:47
Before I introduce our guests, let me briefly explain how our online classroom works.
Before I introduce our guests, let me briefly explain how our online classroom works.
vapodaca
2020-05-12 19:30:54
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
vapodaca
2020-05-12 19:30:59
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
vapodaca
2020-05-12 19:31:09
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
vapodaca
2020-05-12 19:31:20
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
vapodaca
2020-05-12 19:31:30
Each year, Mathcamp creates a Qualifying Quiz, which is the main component of the application process. If you haven't already seen it, you can find the 2020 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, the following Mathcamp staff (all members of this year's Quiz committee) will discuss the problems and their solutions:
Each year, Mathcamp creates a Qualifying Quiz, which is the main component of the application process. If you haven't already seen it, you can find the 2020 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, the following Mathcamp staff (all members of this year's Quiz committee) will discuss the problems and their solutions:
vapodaca
2020-05-12 19:31:49
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
vapodaca
2020-05-12 19:32:02
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
vapodaca
2020-05-12 19:32:19
Mira Bernstein (MiraBernstein) has been a core organizer of Mathcamp since 1997, and is now on the faculty as well as the Board of Directors. She has also been a central architect of the Qualifying Quiz every year!
Mira Bernstein (MiraBernstein) has been a core organizer of Mathcamp since 1997, and is now on the faculty as well as the Board of Directors. She has also been a central architect of the Qualifying Quiz every year!
vapodaca
2020-05-12 19:32:34
Linus (Lopsy) is a returning mentor at Mathcamp. He often teaches algorithms-related classes and hosts strange trivia events.
Linus (Lopsy) is a returning mentor at Mathcamp. He often teaches algorithms-related classes and hosts strange trivia events.
vapodaca
2020-05-12 19:32:47
Let's turn the room over to Marisa now to get us started!
Let's turn the room over to Marisa now to get us started!
MarisaD
2020-05-12 19:32:56
Hi, everybody, and welcome to the annual Mathcamp Qualifying Quiz Jam!
Hi, everybody, and welcome to the annual Mathcamp Qualifying Quiz Jam!
MarisaD
2020-05-12 19:33:10
A big thanks as always to @vapodaca, @rrusczyk, and the AoPS team for hosting us.
A big thanks as always to @vapodaca, @rrusczyk, and the AoPS team for hosting us.
MarisaD
2020-05-12 19:33:14
Kevin, Linus, Mira, and I are here to talk about the Mathcamp 2020 QQ. To follow along, you should all have the quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
Kevin, Linus, Mira, and I are here to talk about the Mathcamp 2020 QQ. To follow along, you should all have the quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
MarisaD
2020-05-12 19:33:29
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
MarisaD
2020-05-12 19:33:37
If you applied this year, I strongly recommend having your own solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
If you applied this year, I strongly recommend having your own solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
MarisaD
2020-05-12 19:33:59
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We claim that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We claim that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
MarisaD
2020-05-12 19:34:04
Also, as @vapodaca pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
Also, as @vapodaca pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
MarisaD
2020-05-12 19:34:15
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/), or check out the AoPS Jam about the program and the application process from a few months ago: https://artofproblemsolving.com/school/mathjams-transcripts?id=514
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/), or check out the AoPS Jam about the program and the application process from a few months ago: https://artofproblemsolving.com/school/mathjams-transcripts?id=514
MarisaD
2020-05-12 19:34:27
(Since then, there have been some pretty big changes---like a global pandemic---so this year, Mathcamp will be online. But the QQ problems haven't changed!)
(Since then, there have been some pretty big changes---like a global pandemic---so this year, Mathcamp will be online. But the QQ problems haven't changed!)
MarisaD
2020-05-12 19:34:35
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
MarisaD
2020-05-12 19:34:43
We've got a lot to cover in the next two hours, so let's get started! I'll turn it over to Linus to kick us off with problem #1.
We've got a lot to cover in the next two hours, so let's get started! I'll turn it over to Linus to kick us off with problem #1.
Lopsy
2020-05-12 19:34:58
Heyo! Here we go:
Heyo! Here we go:
Lopsy
2020-05-12 19:35:03
Problem 1 Statement:
Caitlin wants to draw $n$ straight line segments, without lifting her pencil off the paper and without retracing her path, so that each segment crosses exactly one other segment (not counting intersections at vertices) and she ends up back where she started.
Problem 1a: Show how she can do this for $n = 6$. (Draw a picture!)
Problem 1 Statement:
Caitlin wants to draw $n$ straight line segments, without lifting her pencil off the paper and without retracing her path, so that each segment crosses exactly one other segment (not counting intersections at vertices) and she ends up back where she started.
Problem 1a: Show how she can do this for $n = 6$. (Draw a picture!)
Lopsy
2020-05-12 19:35:12
I empathize with Caitlin here.
I empathize with Caitlin here.
Lopsy
2020-05-12 19:35:16
This was meant to be a gentle prelude into the quiz. However, it is the most difficult question in the Math Jam, because none of you know how to upload a picture.
This was meant to be a gentle prelude into the quiz. However, it is the most difficult question in the Math Jam, because none of you know how to upload a picture.
Lopsy
2020-05-12 19:35:30
I’ll witness your best efforts at describing your solutions now. >
I’ll witness your best efforts at describing your solutions now. >
Elaine_Wang
2020-05-12 19:35:51
Yay!
Yay!
hliu1
2020-05-12 19:35:51
<a>
draw((0,0)--(4,1)--(3,5)--(2,1)--(6,0)--(3,3)--(0,0)); </a>
<a>
draw((0,0)--(4,1)--(3,5)--(2,1)--(6,0)--(3,3)--(0,0)); </a>
iscoconut
2020-05-12 19:35:51
a star
a star
iscoconut
2020-05-12 19:35:51
but it is a special star
but it is a special star
GeronimoStilton
2020-05-12 19:35:59
basically you have a central triangle and an outside triangle and you connect the points as if it is a star
basically you have a central triangle and an outside triangle and you connect the points as if it is a star
Parna
2020-05-12 19:36:03
Make an equilateral triangle and a bigger one around it, and connect noncorresponding edges
Make an equilateral triangle and a bigger one around it, and connect noncorresponding edges
PCampbell
2020-05-12 19:36:09
like a 6 pointed star kinda thing
like a 6 pointed star kinda thing
Purple_22
2020-05-12 19:36:09
a kind of inside-out star?
a kind of inside-out star?
Lopsy
2020-05-12 19:36:15
Bwa ha ha.
Bwa ha ha.
Lopsy
2020-05-12 19:36:36
This was a gentle introduction; ideally you found it after playing around for a while. Now comes the real test.
This was a gentle introduction; ideally you found it after playing around for a while. Now comes the real test.
Lopsy
2020-05-12 19:36:41
Problem 1b: For which values of $n$ is this possible?
Problem 1b: For which values of $n$ is this possible?
Lopsy
2020-05-12 19:36:53
The first thing we want: a construction showing how to do it for all n we can. Let’s start with even n. Tell me, how did you do it?
The first thing we want: a construction showing how to do it for all n we can. Let’s start with even n. Tell me, how did you do it?
awang11
2020-05-12 19:37:14
how on earth do i describe this construction
how on earth do i describe this construction
Lopsy
2020-05-12 19:37:24
We received a bunch of different approaches. Common pitfalls included: (1)
Constructions that don’t work for all $n$, e.g. by being two separate loops sometimes. (2) Pictures for $n=8, 10, \dots$ with no explanation of how to generalize. (3) Not drawing a picture?!?!
We received a bunch of different approaches. Common pitfalls included: (1)
Constructions that don’t work for all $n$, e.g. by being two separate loops sometimes. (2) Pictures for $n=8, 10, \dots$ with no explanation of how to generalize. (3) Not drawing a picture?!?!
Lopsy
2020-05-12 19:37:34
But there are a lot of ways to do it right. Here’s mine:
But there are a lot of ways to do it right. Here’s mine:
Lopsy
2020-05-12 19:37:46
By stacking a different number of zigzag crossings in the box, we can get any even $n \geq 8$.
By stacking a different number of zigzag crossings in the box, we can get any even $n \geq 8$.
etotheipiplus1
2020-05-12 19:37:52
I did it the same way!!!
I did it the same way!!!
Lopsy
2020-05-12 19:38:00
Now to finish up we just need to find the construction for odd $n$, and to rule out $n = 1, 2, 3, 4, 5$.
Now to finish up we just need to find the construction for odd $n$, and to rule out $n = 1, 2, 3, 4, 5$.
hliu1
2020-05-12 19:38:36
there are none for odd because the segments must be in disjoint pairs
there are none for odd because the segments must be in disjoint pairs
etotheipiplus1
2020-05-12 19:38:46
The odd ones aren't difficult, we just need to realize that we can make pairs of two using lines that cross each other
The odd ones aren't difficult, we just need to realize that we can make pairs of two using lines that cross each other
Lopsy
2020-05-12 19:38:57
Yeah. If each segment crosses one other, then you can pair the segments up into crossing pairs. So there must be an even number of ‘em.
Yeah. If each segment crosses one other, then you can pair the segments up into crossing pairs. So there must be an even number of ‘em.
Lopsy
2020-05-12 19:39:06
The last $n$ left are 2 and 4. 2 is, like, come on. For 4, you might persuade yourself it’s impossible by drawing pictures. Ideally, you found a convincing argument; mine is “there are only four vertices available, so you can’t even get two pairs of crossing lines.”
The last $n$ left are 2 and 4. 2 is, like, come on. For 4, you might persuade yourself it’s impossible by drawing pictures. Ideally, you found a convincing argument; mine is “there are only four vertices available, so you can’t even get two pairs of crossing lines.”
Lopsy
2020-05-12 19:39:27
All in all, this question rewards playing around and trying small cases. If you found yourself able to draw examples for $n=6,8,10,12,14,16,...$ but not for any odd $n$, you might have suspected that a parity argument (a proof based on whether numbers are even or odd) would be fruitful.
This question also tests clearly communicating your ideas in both pictures and English. This is something most people, frankly, need to work on.
All in all, this question rewards playing around and trying small cases. If you found yourself able to draw examples for $n=6,8,10,12,14,16,...$ but not for any odd $n$, you might have suspected that a parity argument (a proof based on whether numbers are even or odd) would be fruitful.
This question also tests clearly communicating your ideas in both pictures and English. This is something most people, frankly, need to work on.
Lopsy
2020-05-12 19:39:42
Last thing last: $n=0$ is possible (draw nothing). If you forgot this case, you lost 9 out of the possible 10 points.
Last thing last: $n=0$ is possible (draw nothing). If you forgot this case, you lost 9 out of the possible 10 points.
awang11
2020-05-12 19:39:59
excuse me what
excuse me what
Lopsy
2020-05-12 19:40:02
just kidding
just kidding
Lopsy
2020-05-12 19:40:04
Now, I’ll hand things off to Marisa’s Modular Mayhem!
Now, I’ll hand things off to Marisa’s Modular Mayhem!
MarisaD
2020-05-12 19:40:15
Thanks, Linus! Let's talk fortuitously:
Thanks, Linus! Let's talk fortuitously:
MarisaD
2020-05-12 19:40:25
Problem 2 Statement:
Problem 2 Statement:
MarisaD
2020-05-12 19:40:34
Here is a table of remainders when powers of $10$ are divided by $2020$:
Here is a table of remainders when powers of $10$ are divided by $2020$:
MarisaD
2020-05-12 19:40:39
$$ \begin{array}{rrr}
k & 10^k & Remainder \\ \hline
0 & 1 & 1 \\
1 & 10 & 10 \\
2 & 100 & 100 \\
3 & 1000 & 1000 \\
4 & 10000 & 1920 \\
5 & 100000 & 1020 \\
6 & 1000000 & 100 \\
7 & 10000000 & 1000 \\
8 & 100000000 & 1920 \\
9 & 1000000000 & 1020
\end{array} $$
$$ \begin{array}{rrr}
k & 10^k & Remainder \\ \hline
0 & 1 & 1 \\
1 & 10 & 10 \\
2 & 100 & 100 \\
3 & 1000 & 1000 \\
4 & 10000 & 1920 \\
5 & 100000 & 1020 \\
6 & 1000000 & 100 \\
7 & 10000000 & 1000 \\
8 & 100000000 & 1920 \\
9 & 1000000000 & 1020
\end{array} $$
MarisaD
2020-05-12 19:40:47
We see that the remainders repeat every four steps (period $4$), with two exceptions at the
beginning, $1$ and $10$.
We see that the remainders repeat every four steps (period $4$), with two exceptions at the
beginning, $1$ and $10$.
MarisaD
2020-05-12 19:40:52
We will call a sequence that repeats with period $4$, with two exceptions at the beginning, a fortuitous sequence (four-two-itous). (Note that sequences that have periods smaller than four (e.g. sequences that repeat every two steps) do not count as fortuitous.)
We will call a sequence that repeats with period $4$, with two exceptions at the beginning, a fortuitous sequence (four-two-itous). (Note that sequences that have periods smaller than four (e.g. sequences that repeat every two steps) do not count as fortuitous.)
MarisaD
2020-05-12 19:41:04
PROBLEM 2a: In addition to $2020$, for what other values of $m$ is the sequence of remainders when $10^k$ is divided by $m$ a fortuitous sequence?
PROBLEM 2a: In addition to $2020$, for what other values of $m$ is the sequence of remainders when $10^k$ is divided by $m$ a fortuitous sequence?
MarisaD
2020-05-12 19:41:17
Fun, it's a number theory problem! Our solution will be using the big hammer of the Chinese Remainder Theorem for 2b, but for 2a we'll just need modular arithmetic.
Fun, it's a number theory problem! Our solution will be using the big hammer of the Chinese Remainder Theorem for 2b, but for 2a we'll just need modular arithmetic.
MarisaD
2020-05-12 19:41:26
(A philosophical note: I'll talk through this pretty carefully. If you have clarifying questions along the way, please ask! If you're bored at the beginning, it's okay: I just want to make sure everybody is able to follow. If you're lost at the end, it's okay! I don't expect you to be checking the details in realtime, and you'll be able to come back to this transcript later to review.)
(A philosophical note: I'll talk through this pretty carefully. If you have clarifying questions along the way, please ask! If you're bored at the beginning, it's okay: I just want to make sure everybody is able to follow. If you're lost at the end, it's okay! I don't expect you to be checking the details in realtime, and you'll be able to come back to this transcript later to review.)
MarisaD
2020-05-12 19:41:32
If you feel comfortable with this problem and are just waiting for us to get to #3, then here's a question to entertain you in the meantime: What can you say about the general problem? What pairs $(a, m)$ give rise to a fortuitous sequence when we look at the remainders when $a^k$ is divided by $m$?
If you feel comfortable with this problem and are just waiting for us to get to #3, then here's a question to entertain you in the meantime: What can you say about the general problem? What pairs $(a, m)$ give rise to a fortuitous sequence when we look at the remainders when $a^k$ is divided by $m$?
MarisaD
2020-05-12 19:41:40
Anyway, returning to the main event:
Anyway, returning to the main event:
MarisaD
2020-05-12 19:41:47
PROBLEM 2a SOLUTION:
PROBLEM 2a SOLUTION:
MarisaD
2020-05-12 19:41:56
Let's do this in two steps: first we'll talk about how to get a repeating cycle of four remainders (the period $4$ condition), and then we'll figure out how to force the first two cases ($10^0$ and $10^1$) to be exceptions.
Let's do this in two steps: first we'll talk about how to get a repeating cycle of four remainders (the period $4$ condition), and then we'll figure out how to force the first two cases ($10^0$ and $10^1$) to be exceptions.
MarisaD
2020-05-12 19:42:09
In order to consider the relationship between $m$ (the stand-in for what was $2020$ in the example) and $10$, let's pull out all the factors in common with $10$ and write:
In order to consider the relationship between $m$ (the stand-in for what was $2020$ in the example) and $10$, let's pull out all the factors in common with $10$ and write:
MarisaD
2020-05-12 19:42:13
$m = 2^a 5^b n$, where the $n$ is relatively prime to $10$.
$m = 2^a 5^b n$, where the $n$ is relatively prime to $10$.
MarisaD
2020-05-12 19:42:28
Now, since $10$ is relatively prime to $n$, we know that $10^k$ will be periodic modulo $n$, and our goal is to make sure that that period is $4$.
Now, since $10$ is relatively prime to $n$, we know that $10^k$ will be periodic modulo $n$, and our goal is to make sure that that period is $4$.
MarisaD
2020-05-12 19:42:33
Can you write that as a statement about congruence relations, mod $n$?
Can you write that as a statement about congruence relations, mod $n$?
Imayormaynotknowcalculus
2020-05-12 19:43:51
$10^{k+4}\equiv 10^k\pmod{n}$
$10^{k+4}\equiv 10^k\pmod{n}$
atticus.cull
2020-05-12 19:43:51
$10^{k+4} = 10^k$
$10^{k+4} = 10^k$
Purple_22
2020-05-12 19:43:51
$10^k\equiv 10^{k+4}$ $(mod n)$ for sufficiently large $k$
$10^k\equiv 10^{k+4}$ $(mod n)$ for sufficiently large $k$
penrose43
2020-05-12 19:43:51
$10^6 \equiv 10^2$ modulo $n$
$10^6 \equiv 10^2$ modulo $n$
MarisaD
2020-05-12 19:44:02
That's right: we need $10^4 \equiv 10^0 \mod n$.
That's right: we need $10^4 \equiv 10^0 \mod n$.
MarisaD
2020-05-12 19:44:07
Or, in other words, $10^4 \equiv 1 \mod n$.
Or, in other words, $10^4 \equiv 1 \mod n$.
MarisaD
2020-05-12 19:44:17
Now, what condition will ensure that the period is not smaller than $4$?
Now, what condition will ensure that the period is not smaller than $4$?
Parna
2020-05-12 19:44:55
$10^2$ is not congruent to $1 \pmod n$
$10^2$ is not congruent to $1 \pmod n$
lin8989
2020-05-12 19:44:55
10^2 \not congruent to 1 mod n
10^2 \not congruent to 1 mod n
lilcritters
2020-05-12 19:44:55
$10^{k+2} \nequiv 10^k$
$10^{k+2} \nequiv 10^k$
Purple_22
2020-05-12 19:44:55
$10^k\not\equiv 10^{k+2}$ (mod $n$)
$10^k\not\equiv 10^{k+2}$ (mod $n$)
smartmonkey999
2020-05-12 19:44:55
$10^k \not \equiv 10^{k+2} \pmod{n}$
$10^k \not \equiv 10^{k+2} \pmod{n}$
hliu1
2020-05-12 19:44:55
$10^{k+2}$ is not equivalent to $10^k$ mod n
$10^{k+2}$ is not equivalent to $10^k$ mod n
MarisaD
2020-05-12 19:44:58
Yup: we need $10^2\not\equiv1\mod n$.
Yup: we need $10^2\not\equiv1\mod n$.
MarisaD
2020-05-12 19:45:03
Saying the same thing in a different way: we have to choose $n$ such that $10^4-1=9999$ is divisible by $n$, but $10^2-1=99$ is not divisible by $n$.
Saying the same thing in a different way: we have to choose $n$ such that $10^4-1=9999$ is divisible by $n$, but $10^2-1=99$ is not divisible by $n$.
MarisaD
2020-05-12 19:45:18
What's a nice way to factor $10^4-1$?
What's a nice way to factor $10^4-1$?
etotheipiplus1
2020-05-12 19:45:45
(10^2+1)(10^2-1)
(10^2+1)(10^2-1)
smartmonkey999
2020-05-12 19:45:45
difference of squares twice
difference of squares twice
winterrain01
2020-05-12 19:45:45
(10^2-1)(10^2+1)
(10^2-1)(10^2+1)
BakedPotato66
2020-05-12 19:45:45
diff. of squares
diff. of squares
Purple_22
2020-05-12 19:45:45
$(10^2+1)(10^2-1)$
$(10^2+1)(10^2-1)$
MarisaD
2020-05-12 19:45:50
Sure, the difference of squares formula is perfect here: $$10^4-1=(10^2+1)(10^2-1)=101\cdot99$$
Sure, the difference of squares formula is perfect here: $$10^4-1=(10^2+1)(10^2-1)=101\cdot99$$
MarisaD
2020-05-12 19:46:04
Now we know that $n$ has to be a factor of $101$ and/or $99$. Can we pick any factor? Does $n=3$ work?
Now we know that $n$ has to be a factor of $101$ and/or $99$. Can we pick any factor? Does $n=3$ work?
hliu1
2020-05-12 19:46:43
no, because it divides $10^2$
no, because it divides $10^2$
Purple_22
2020-05-12 19:46:43
It can't be a factor of $10^2-1$.
It can't be a factor of $10^2-1$.
Parna
2020-05-12 19:46:43
no, because it is a factor of $99$
no, because it is a factor of $99$
transcendental-number
2020-05-12 19:46:43
it can't be a factor of 10^2-1 or 10 would have an order of 2 mod n
it can't be a factor of 10^2-1 or 10 would have an order of 2 mod n
a.y.711
2020-05-12 19:46:43
no, because that violates 10^2 not equiv 1 mod n
no, because that violates 10^2 not equiv 1 mod n
MarisaD
2020-05-12 19:46:50
Right: there's the condition that $99$ is not divisible by $n$.
Right: there's the condition that $99$ is not divisible by $n$.
MarisaD
2020-05-12 19:46:51
So, I claim a tiny fact: $n$ has to be divisible by $101$. Why is that?
So, I claim a tiny fact: $n$ has to be divisible by $101$. Why is that?
transcendental-number
2020-05-12 19:47:41
101 is a prime and n=1 doesn't work
101 is a prime and n=1 doesn't work
bluelinfish
2020-05-12 19:47:41
if it wasn't, it would be divisible by 99
if it wasn't, it would be divisible by 99
rf20008
2020-05-12 19:47:41
because it has to be a factor of 101*99 and we know 99 doesn't work so it must be 101
because it has to be a factor of 101*99 and we know 99 doesn't work so it must be 101
hliu1
2020-05-12 19:47:41
because it's not a factor of $99,$ and the only factors of $9999$ that are not factors of $99$ are divislbe by $101$
because it's not a factor of $99,$ and the only factors of $9999$ that are not factors of $99$ are divislbe by $101$
MarisaD
2020-05-12 19:48:05
Good! Summarizing what folks said (I'm seeing a lot of correct answers!):
* Since $n$ is a factor of $101\cdot99$ and $101$ is prime, if $n$ were not divisible by $101$, it would be a factor of $99$, a contradiction.
* The converse is also true: if $n$ is divisible by $101$, then $99$ is not divisible by $n$.
Good! Summarizing what folks said (I'm seeing a lot of correct answers!):
* Since $n$ is a factor of $101\cdot99$ and $101$ is prime, if $n$ were not divisible by $101$, it would be a factor of $99$, a contradiction.
* The converse is also true: if $n$ is divisible by $101$, then $99$ is not divisible by $n$.
MarisaD
2020-05-12 19:48:13
So, what are all possible values for $n$?
So, what are all possible values for $n$?
Purple_22
2020-05-12 19:49:02
101 times a factor of 99
101 times a factor of 99
penrose43
2020-05-12 19:49:02
$101, 303, 909, 1111, 3333, 9999$
$101, 303, 909, 1111, 3333, 9999$
hliu1
2020-05-12 19:49:02
$101,303,909,1111,3333,9999$
$101,303,909,1111,3333,9999$
atticus.cull
2020-05-12 19:49:02
there are many!
there are many!
MarisaD
2020-05-12 19:49:07
Yes! The possible values of $n$ are all of the numbers that are $101$ times a factor of $99$, namely: $$\begin{align*}
101\cdot1&=101,\\
101\cdot3&=303,\\
101\cdot3^2&=909,\\
101\cdot11&=1111,\\
101\cdot11\cdot3&=3333,\\
101\cdot11\cdot3^2&=9999.
\end{align*}$$
Yes! The possible values of $n$ are all of the numbers that are $101$ times a factor of $99$, namely: $$\begin{align*}
101\cdot1&=101,\\
101\cdot3&=303,\\
101\cdot3^2&=909,\\
101\cdot11&=1111,\\
101\cdot11\cdot3&=3333,\\
101\cdot11\cdot3^2&=9999.
\end{align*}$$
MarisaD
2020-05-12 19:49:23
Any questions so far?
Any questions so far?
anagh
2020-05-12 19:49:34
why times a factor of 99???
why times a factor of 99???
MarisaD
2020-05-12 19:49:51
I was hoping someone would ask that!
I was hoping someone would ask that!
Purple_22
2020-05-12 19:50:17
Otherwise, it's not a factor of 9999.
Otherwise, it's not a factor of 9999.
dandan
2020-05-12 19:50:17
It has to divide $10^4 - 1$
It has to divide $10^4 - 1$
MarisaD
2020-05-12 19:50:35
Right: we need 101 to be a divisor of $n$, but $n$ can have other factors, too.
Right: we need 101 to be a divisor of $n$, but $n$ can have other factors, too.
MarisaD
2020-05-12 19:50:47
Alright, but we're not done yet. In order to understand what $m = 2^a 5^b n$ can be, we need to think about the other condition: that there are two exceptions at the beginning of our sequence of remainders.
Alright, but we're not done yet. In order to understand what $m = 2^a 5^b n$ can be, we need to think about the other condition: that there are two exceptions at the beginning of our sequence of remainders.
MarisaD
2020-05-12 19:50:57
Eventually, we will need $10^k$ to be zero modulo $2^a 5^b$. In order to have exactly two exceptions, what congruence conditions do we need?
Eventually, we will need $10^k$ to be zero modulo $2^a 5^b$. In order to have exactly two exceptions, what congruence conditions do we need?
hliu1
2020-05-12 19:52:20
10 is not divisible by $2^a5^b,$ while 100 is
10 is not divisible by $2^a5^b,$ while 100 is
MarisaD
2020-05-12 19:52:26
That's right: we want $10^2\equiv0\pmod{2^a5^b}$, but $10^1\not\equiv0\pmod{2^a5^b}$.
That's right: we want $10^2\equiv0\pmod{2^a5^b}$, but $10^1\not\equiv0\pmod{2^a5^b}$.
MarisaD
2020-05-12 19:52:33
In other words, $2^a5^b$ must be a factor of $100$, but not a factor of $10$.
In other words, $2^a5^b$ must be a factor of $100$, but not a factor of $10$.
MarisaD
2020-05-12 19:52:51
Time for a little arithmetic. There are nine factors of $100$ and four factors of $10$, and we can go off in a corner and check that $2^a5^b$ has to be one of the following five options:
$$\begin{align*}
2^2&=4,\\
2^2\cdot5&=20,\\
5^2&=25,\\
2\cdot5^2&=50,\\
2^2\cdot5^2&=100.
\end{align*}$$
Time for a little arithmetic. There are nine factors of $100$ and four factors of $10$, and we can go off in a corner and check that $2^a5^b$ has to be one of the following five options:
$$\begin{align*}
2^2&=4,\\
2^2\cdot5&=20,\\
5^2&=25,\\
2\cdot5^2&=50,\\
2^2\cdot5^2&=100.
\end{align*}$$
MarisaD
2020-05-12 19:53:01
Putting it all together: what are the possible values for $m$?
Putting it all together: what are the possible values for $m$?
bluelinfish
2020-05-12 19:53:27
any combination of the two
any combination of the two
Point142857Repeating
2020-05-12 19:53:27
30 values total? don't want to list
30 values total? don't want to list
MarisaD
2020-05-12 19:53:32
That's right: the possible values of $m$ are the $30$ numbers that are a product of a number in the first list with a number in the second list.
That's right: the possible values of $m$ are the $30$ numbers that are a product of a number in the first list with a number in the second list.
MarisaD
2020-05-12 19:53:36
In a table, these are:
$$ \begin{array}{ccccc}
404& 2020& 2525& 5050& 10100\\
1212& 6060& 7575& 15150& 30300\\
3636& 18180& 22725& 45450& 90900\\
4444& 22220& 27775& 55550& 111100\\
13332& 66660& 83325& 166650& 333300\\
39996& 199980& 249975& 499950& 999900
\end{array} $$
In a table, these are:
$$ \begin{array}{ccccc}
404& 2020& 2525& 5050& 10100\\
1212& 6060& 7575& 15150& 30300\\
3636& 18180& 22725& 45450& 90900\\
4444& 22220& 27775& 55550& 111100\\
13332& 66660& 83325& 166650& 333300\\
39996& 199980& 249975& 499950& 999900
\end{array} $$
MarisaD
2020-05-12 19:53:42
…so as my friend Yasha pointed out, we may reuse this qualifying quiz problem $505$ years from now.
…so as my friend Yasha pointed out, we may reuse this qualifying quiz problem $505$ years from now.
MarisaD
2020-05-12 19:53:50
Any questions on part a?
Any questions on part a?
MarisaD
2020-05-12 19:54:09
OK, on to part b!
OK, on to part b!
MarisaD
2020-05-12 19:54:14
PROBLEM 2b: In addition to $10$, for what other values of $a$ is the sequence of remainders when $a^k$ is divided by $2020$ a fortuitous sequence?
PROBLEM 2b: In addition to $10$, for what other values of $a$ is the sequence of remainders when $a^k$ is divided by $2020$ a fortuitous sequence?
MarisaD
2020-05-12 19:54:23
PROBLEM 2b SOLUTION:
PROBLEM 2b SOLUTION:
hliu1
2020-05-12 19:54:40
if you thought listing out the answers to part a) was bad...
if you thought listing out the answers to part a) was bad...
MarisaD
2020-05-12 19:54:45
Nah, it gets better!
Nah, it gets better!
MarisaD
2020-05-12 19:54:47
For this part, we'll need the Chinese remainder theorem. It says that if you know the remainders of dividing your favorite integer $n$ by several integers individually, then you can determine uniquely the remainder you would get when dividing $n$ by the product of these integers, under the condition that the divisors are pairwise coprime. (See https://www.cut-the-knot.org/blue/chinese.shtml for the full statement and the proof.)
For this part, we'll need the Chinese remainder theorem. It says that if you know the remainders of dividing your favorite integer $n$ by several integers individually, then you can determine uniquely the remainder you would get when dividing $n$ by the product of these integers, under the condition that the divisors are pairwise coprime. (See https://www.cut-the-knot.org/blue/chinese.shtml for the full statement and the proof.)
MarisaD
2020-05-12 19:55:05
The prime factorization of $2020$ is $2^2\cdot5\cdot101$. Using the Chinese Remainder Theorem, we can analyze the sequence $a^k \pmod{2020}$ by looking at the sequences mod $4$, mod $5$, and mod $101$ separately, and then we'll take our deductions and glue them together again at the end.
The prime factorization of $2020$ is $2^2\cdot5\cdot101$. Using the Chinese Remainder Theorem, we can analyze the sequence $a^k \pmod{2020}$ by looking at the sequences mod $4$, mod $5$, and mod $101$ separately, and then we'll take our deductions and glue them together again at the end.
MarisaD
2020-05-12 19:55:22
First, let's think about the "two exceptions at the beginning" condition of being a fortuitous sequence.
First, let's think about the "two exceptions at the beginning" condition of being a fortuitous sequence.
MarisaD
2020-05-12 19:55:23
For any $a$, I claim that the sequences $a^k\pmod{5}$ and $a^k\pmod{101}$ will be periodic, right from the start. Why?
For any $a$, I claim that the sequences $a^k\pmod{5}$ and $a^k\pmod{101}$ will be periodic, right from the start. Why?
Purple_22
2020-05-12 19:56:29
5 and 101 are prime
5 and 101 are prime
mathfun2019fortw
2020-05-12 19:56:29
prime
prime
transcendental-number
2020-05-12 19:56:29
101 and 5 are primes
101 and 5 are primes
MarvelousMasterMark
2020-05-12 19:56:29
because gcd(a,5) and gcd(a,101) are both 1
because gcd(a,5) and gcd(a,101) are both 1
MarisaD
2020-05-12 19:56:38
Right. Expanding this for clarity: if $a=0$ or $a=1$, it just repeats. Both $5$ and $101$ are prime, so if $a=5$ or $a=101$ then we get $0,0,0,\ldots$ as the sequences, respectively. Otherwise, $a$ is relatively prime to the modulus, so the set $\{a^0, a^1, a^2, \ldots, a^{p-2}\}$ gets us the full set of remainders.
Right. Expanding this for clarity: if $a=0$ or $a=1$, it just repeats. Both $5$ and $101$ are prime, so if $a=5$ or $a=101$ then we get $0,0,0,\ldots$ as the sequences, respectively. Otherwise, $a$ is relatively prime to the modulus, so the set $\{a^0, a^1, a^2, \ldots, a^{p-2}\}$ gets us the full set of remainders.
dandan
2020-05-12 19:56:43
By Fermat's Little Theorem? (5 and 101 are prime)
By Fermat's Little Theorem? (5 and 101 are prime)
MarisaD
2020-05-12 19:56:55
(Yes! You might have seen Fermat's Little Theorem, which tells us that $a^{p-1} \equiv 1 \mod p$.)
(Yes! You might have seen Fermat's Little Theorem, which tells us that $a^{p-1} \equiv 1 \mod p$.)
MarisaD
2020-05-12 19:57:01
That means we're not getting our two exceptions at the beginning from the $5$ or the $101$. How can we force the two exceptions that we need satisfy our fortuitousness requirement?
That means we're not getting our two exceptions at the beginning from the $5$ or the $101$. How can we force the two exceptions that we need satisfy our fortuitousness requirement?
ancientwarrior
2020-05-12 19:57:20
using the mod 4 part
using the mod 4 part
hliu1
2020-05-12 19:57:20
$2^2$ factor
$2^2$ factor
Purple_22
2020-05-12 19:57:25
If $a$ is 2 (mod 4)
If $a$ is 2 (mod 4)
MarisaD
2020-05-12 19:57:28
That's right: we will get two exceptional terms if, and only if, $a\equiv 2\mod 4$.
That's right: we will get two exceptional terms if, and only if, $a\equiv 2\mod 4$.
MarisaD
2020-05-12 19:57:33
(Looking at the sequence just $\mod 4$, we'll get $1,2,0,0,0,0,\ldots$.)
(Looking at the sequence just $\mod 4$, we'll get $1,2,0,0,0,0,\ldots$.)
MarisaD
2020-05-12 19:57:58
So that's the "two" of "fortuitous". Now we need conditions on $a$ so that the sequence has period $4$. When we consider the sequence $\mod 5$ and $\mod 101$, what are the conditions for periodicity?
So that's the "two" of "fortuitous". Now we need conditions on $a$ so that the sequence has period $4$. When we consider the sequence $\mod 5$ and $\mod 101$, what are the conditions for periodicity?
MarisaD
2020-05-12 19:59:31
(I'm seeing some answers about periodicity mod $101$; don't forget about $5$!)
(I'm seeing some answers about periodicity mod $101$; don't forget about $5$!)
MarisaD
2020-05-12 20:01:01
I'm seeing almost true statements, but let me propose an approach: the sequence must have period $1$, $2$, or $4 \mod 5$ and the $\mod 101$, and one of those two periods has to be exactly $4$.
I'm seeing almost true statements, but let me propose an approach: the sequence must have period $1$, $2$, or $4 \mod 5$ and the $\mod 101$, and one of those two periods has to be exactly $4$.
MarisaD
2020-05-12 20:01:14
Let's check two cases.
Let's check two cases.
MarisaD
2020-05-12 20:01:20
First, suppose $a^k$ has either period $1$ or $2 \mod 101$.
First, suppose $a^k$ has either period $1$ or $2 \mod 101$.
MarisaD
2020-05-12 20:01:24
(Restate that as a congruence for me, please?)
(Restate that as a congruence for me, please?)
ancientwarrior
2020-05-12 20:02:16
a is either 0 mod 101 or 1,-1 mod 101
a is either 0 mod 101 or 1,-1 mod 101
MarisaD
2020-05-12 20:02:19
Right, thanks: $a \equiv 0, \pm 1 \pmod{101}$.
Right, thanks: $a \equiv 0, \pm 1 \pmod{101}$.
MarisaD
2020-05-12 20:02:41
So under that assumption for 101, what happens $\mod 5$?
So under that assumption for 101, what happens $\mod 5$?
bluelinfish
2020-05-12 20:03:02
The period is exactly 4
The period is exactly 4
MarisaD
2020-05-12 20:03:06
Yep: in this case, $a^k$ has to be period $4 \mod 5$.
Yep: in this case, $a^k$ has to be period $4 \mod 5$.
MarisaD
2020-05-12 20:03:15
(That's how we get the whole sequence to have period 4.)
(That's how we get the whole sequence to have period 4.)
MarisaD
2020-05-12 20:03:23
What does that mean in the language of congruences?
What does that mean in the language of congruences?
Purple_22
2020-05-12 20:03:51
$a\equiv 2$ or $a\equiv 3$ (mod 5)
$a\equiv 2$ or $a\equiv 3$ (mod 5)
MarisaD
2020-05-12 20:03:59
Exactly. Or in other words, $a=\pm 2\pmod{5}$.
Exactly. Or in other words, $a=\pm 2\pmod{5}$.
MarisaD
2020-05-12 20:04:07
Now we have three conditions, with relatively prime moduli:
* $a\equiv 2\pmod 4$
* $a\equiv 0, \pm 1 \pmod{101}$, and
* $a\equiv \pm 2\pmod{5}$
Now we have three conditions, with relatively prime moduli:
* $a\equiv 2\pmod 4$
* $a\equiv 0, \pm 1 \pmod{101}$, and
* $a\equiv \pm 2\pmod{5}$
MarisaD
2020-05-12 20:04:17
How do we solve congruence equation systems in modular arithmetic?
How do we solve congruence equation systems in modular arithmetic?
Bobcats
2020-05-12 20:04:34
CRT!
CRT!
lilcritters
2020-05-12 20:04:34
Chinese Remainder Theorem
Chinese Remainder Theorem
MarisaD
2020-05-12 20:04:44
Yeah, using the Chinese Remainder Theorem! We can put these together to get our six solutions $\mod 2020$: $$a = \pm 102, \pm 202, \pm 302 \pmod{2020}$$
Yeah, using the Chinese Remainder Theorem! We can put these together to get our six solutions $\mod 2020$: $$a = \pm 102, \pm 202, \pm 302 \pmod{2020}$$
MarisaD
2020-05-12 20:04:53
You can do this by hand, taking careful inverses, but you can also ask Wolfram Alpha to help you do the calculation: for example, the first combination is https://www.wolframalpha.com/input/?i=ChineseRemainder%5B%7B2%2C0%2C2%7D%2C%7B4%2C101%2C5%7D%5D
You can do this by hand, taking careful inverses, but you can also ask Wolfram Alpha to help you do the calculation: for example, the first combination is https://www.wolframalpha.com/input/?i=ChineseRemainder%5B%7B2%2C0%2C2%7D%2C%7B4%2C101%2C5%7D%5D
ancientwarrior
2020-05-12 20:05:08
nice
nice
MarisaD
2020-05-12 20:05:12
I know, right? The CRT is great.
I know, right? The CRT is great.
MarisaD
2020-05-12 20:05:14
The only case left is when $a^k$ has period $4 \mod 101$. What's that in terms of congruences?
The only case left is when $a^k$ has period $4 \mod 101$. What's that in terms of congruences?
hliu1
2020-05-12 20:05:55
$10,99$ mod 101
$10,99$ mod 101
MarisaD
2020-05-12 20:06:04
Yep, thanks. Or in other words, $a = \pm 10 \mod{101}$.
Yep, thanks. Or in other words, $a = \pm 10 \mod{101}$.
MarisaD
2020-05-12 20:06:17
Then under that assumption, what are our options $\mod 5$?
Then under that assumption, what are our options $\mod 5$?
Purple_22
2020-05-12 20:06:32
Shouldn't that be 10 and 91?
Shouldn't that be 10 and 91?
MarisaD
2020-05-12 20:06:38
yep, that's right
yep, that's right
MarisaD
2020-05-12 20:06:47
(addition.)
(addition.)
Purple_22
2020-05-12 20:06:55
Anything would work.
Anything would work.
MarisaD
2020-05-12 20:07:02
That's right! Why?
That's right! Why?
bluelinfish
2020-05-12 20:07:26
for any residue, the period is 1,2, or 4
for any residue, the period is 1,2, or 4
dewdrop
2020-05-12 20:07:26
since every value mod 5 has a period of 1,2 or 4
since every value mod 5 has a period of 1,2 or 4
MarisaD
2020-05-12 20:07:29
Right: in this case, $a$ can have any value $\mod 5$, since $a^5 \equiv a \mod 5$ for all $a$.
Right: in this case, $a$ can have any value $\mod 5$, since $a^5 \equiv a \mod 5$ for all $a$.
MarisaD
2020-05-12 20:07:36
Now we can put those conditions together:
* $a = \pm 10 \pmod{101}$
* $a = 2 \pmod 4$
...for another Chinese Remainder Theorem application.
Now we can put those conditions together:
* $a = \pm 10 \pmod{101}$
* $a = 2 \pmod 4$
...for another Chinese Remainder Theorem application.
MarisaD
2020-05-12 20:07:41
The solutions this time are $a=\pm{10} \pmod{404}$.
The solutions this time are $a=\pm{10} \pmod{404}$.
MarisaD
2020-05-12 20:07:49
Or in other words (in terms of our favorite number, $2020$), we get: $$a= \pm 10, \pm 394, \pm 414, \pm 798, \pm 818 \pmod{2020}$$
Or in other words (in terms of our favorite number, $2020$), we get: $$a= \pm 10, \pm 394, \pm 414, \pm 798, \pm 818 \pmod{2020}$$
MarisaD
2020-05-12 20:07:53
Thus there are a total of 16 solutions mod 2020, and they are: $$a = 10, 102, 202, 302, 394, 414, 798, 818, 1202, 1222, 1606, 1626, 1718, 1818, 1918, 2010 \pmod{2020}$$
Thus there are a total of 16 solutions mod 2020, and they are: $$a = 10, 102, 202, 302, 394, 414, 798, 818, 1202, 1222, 1606, 1626, 1718, 1818, 1918, 2010 \pmod{2020}$$
MarisaD
2020-05-12 20:07:59
And, whew, our friend $a=10$ is indeed among them. Checks out.
And, whew, our friend $a=10$ is indeed among them. Checks out.
MarisaD
2020-05-12 20:08:09
Any questions before we move on to the next problem?
Any questions before we move on to the next problem?
etotheipiplus1
2020-05-12 20:08:16
Is this possible to solve without the CRT?
Is this possible to solve without the CRT?
MarisaD
2020-05-12 20:08:22
Not that I know of.
Not that I know of.
MarisaD
2020-05-12 20:08:32
OK! And with that, I'll hand it off to Mira. Onwards to problem 3!
OK! And with that, I'll hand it off to Mira. Onwards to problem 3!
MiraBernstein
2020-05-12 20:08:57
Hi everyone!
Problem 3 is hard! I honestly think it might be the hardest problem on the Quiz this year -- we seriously underestimated its difficulty when we placed it third. But we’ll start with Part (a), which is not too bad.
Hi everyone!
Problem 3 is hard! I honestly think it might be the hardest problem on the Quiz this year -- we seriously underestimated its difficulty when we placed it third. But we’ll start with Part (a), which is not too bad.
MiraBernstein
2020-05-12 20:09:07
Problem 3: There are three roads from Mathopolis to Campville: Red, Green, and Blue. The roads can intersect each other, but only at right angles, and a road cannot intersect itself.
There are six types of crossings, which we divide into two groups:
Let $a$ be the number of A-crossings and $b$ the number of B-crossings between Mathopolis and Campville.
Problem 3: There are three roads from Mathopolis to Campville: Red, Green, and Blue. The roads can intersect each other, but only at right angles, and a road cannot intersect itself.
There are six types of crossings, which we divide into two groups:
Let $a$ be the number of A-crossings and $b$ the number of B-crossings between Mathopolis and Campville.
MiraBernstein
2020-05-12 20:09:23
Before we proceed with the problem, let’s stare for a minute at these two groups of crossings and try to understand what’s going on here.
Note that each group has a Blue-Green, a Red-Green, and a Red-Blue intersection. The intersections in the two groups are mirror images of each other.
Before we proceed with the problem, let’s stare for a minute at these two groups of crossings and try to understand what’s going on here.
Note that each group has a Blue-Green, a Red-Green, and a Red-Blue intersection. The intersections in the two groups are mirror images of each other.
MiraBernstein
2020-05-12 20:09:36
Here’s an easy way to remember the two groups. Order the colors alphabetically: Blue, then Green, then Red, then back to Blue. In this order, turning left gives you an A intersection. Turning right gives you a B intersection.
Not sure if this helps you see it, but I found it a helpful mnemonic.
Here’s an easy way to remember the two groups. Order the colors alphabetically: Blue, then Green, then Red, then back to Blue. In this order, turning left gives you an A intersection. Turning right gives you a B intersection.
Not sure if this helps you see it, but I found it a helpful mnemonic.
MiraBernstein
2020-05-12 20:09:54
Also, I want to apologize in advance to any colorblind folks trying to follow this presentation! At first, I tried labeling the colors of the roads in all my pictures. But then things got really cluttered and confusing with so many labels, so I gave up.
Hopefully the combination of the text and the pictures will make it clear what’s going on, even if you can’t quite see the colors. If not, please ask! But this problem is confusing enough as it is, and it’s got to really suck without colors. So again, I apologize in advance.
Also, I want to apologize in advance to any colorblind folks trying to follow this presentation! At first, I tried labeling the colors of the roads in all my pictures. But then things got really cluttered and confusing with so many labels, so I gave up.
Hopefully the combination of the text and the pictures will make it clear what’s going on, even if you can’t quite see the colors. If not, please ask! But this problem is confusing enough as it is, and it’s got to really suck without colors. So again, I apologize in advance.
MiraBernstein
2020-05-12 20:10:06
OK, let’s get to the actual problem:
OK, let’s get to the actual problem:
MiraBernstein
2020-05-12 20:10:14
Part a: Find, with proof, the set of possible values of $a - b$ under the assumption that the Red Road does not intersect the Green Road.
Part a: Find, with proof, the set of possible values of $a - b$ under the assumption that the Red Road does not intersect the Green Road.
MiraBernstein
2020-05-12 20:10:36
Answer to Problem 3a: The possible values of $a-b$ are 0, 1, and -1.
Proof: First, we need to show that $a-b$ can actually take on each of these three values. That’s easy to do by example:
Answer to Problem 3a: The possible values of $a-b$ are 0, 1, and -1.
Proof: First, we need to show that $a-b$ can actually take on each of these three values. That’s easy to do by example:
MiraBernstein
2020-05-12 20:10:58
The interesting part is proving that these are the only possible values that $a-b$ can have.
First, let’s draw just the Red and Green roads (which for now we are assuming don’t intersect). Together they form a loop, which divides the island into two regions: INSIDE and OUTSIDE.
As you travel from Mathopolis to Campville along the Red Road, the INSIDE region is either on your left (“Case 1”) or on your right (“Case 2”).
The interesting part is proving that these are the only possible values that $a-b$ can have.
First, let’s draw just the Red and Green roads (which for now we are assuming don’t intersect). Together they form a loop, which divides the island into two regions: INSIDE and OUTSIDE.
As you travel from Mathopolis to Campville along the Red Road, the INSIDE region is either on your left (“Case 1”) or on your right (“Case 2”).
MiraBernstein
2020-05-12 20:11:16
Now let’s think about the Blue Road. Say we’re in Case 1. Here are all the ways the Blue Road can intersect the other two roads:
Now let’s think about the Blue Road. Say we’re in Case 1. Here are all the ways the Blue Road can intersect the other two roads:
MiraBernstein
2020-05-12 20:11:26
Suppose you’re in Case 1, traveling along the Blue Road from Mathopolis to Campville and keeping track of $a-b$ as you go along. As you go, you might go in and out of the Red-Green loop, but each time you do, this affects $a-b$.
What happens to $a-b$ when you cross from OUTSIDE to INSIDE the loop?
Suppose you’re in Case 1, traveling along the Blue Road from Mathopolis to Campville and keeping track of $a-b$ as you go along. As you go, you might go in and out of the Red-Green loop, but each time you do, this affects $a-b$.
What happens to $a-b$ when you cross from OUTSIDE to INSIDE the loop?
bluelinfish
2020-05-12 20:12:25
adds 1
adds 1
Th3Numb3rThr33
2020-05-12 20:12:25
changes by 1!
changes by 1!
atticus.cull
2020-05-12 20:12:25
Always increases by 1
Always increases by 1
dandan
2020-05-12 20:12:25
increases by 1
increases by 1
Bobcats
2020-05-12 20:12:25
It is a group A intersection
It is a group A intersection
penrose43
2020-05-12 20:12:25
it increases by 1
it increases by 1
SD2014
2020-05-12 20:12:25
increases by 1
increases by 1
dewdrop
2020-05-12 20:12:25
changes by 1
changes by 1
a.y.711
2020-05-12 20:12:25
a-b increases by 1
a-b increases by 1
Purple_22
2020-05-12 20:12:25
It goes up by 1.
It goes up by 1.
violeteagle
2020-05-12 20:12:25
a increases by 1
a increases by 1
MiraBernstein
2020-05-12 20:12:37
Great, lots of correct answers!
Great, lots of correct answers!
MiraBernstein
2020-05-12 20:12:47
Yup: according to our diagram, when you go from OUTSIDE to INSIDE -- whether you do it by crossing the Red Road or the Green Road -- you always add an A-crossing. So $a-b$ increases by 1.
Similarly, when you go from INSIDE to OUTSIDE the loop, you always add a B-crossing, so $a-b$ decreases by 1.
Yup: according to our diagram, when you go from OUTSIDE to INSIDE -- whether you do it by crossing the Red Road or the Green Road -- you always add an A-crossing. So $a-b$ increases by 1.
Similarly, when you go from INSIDE to OUTSIDE the loop, you always add a B-crossing, so $a-b$ decreases by 1.
MiraBernstein
2020-05-12 20:13:02
So what is $a-b$ if the Blue Road starts OUTSIDE the loop and ends INSIDE it?
So what is $a-b$ if the Blue Road starts OUTSIDE the loop and ends INSIDE it?
SD2014
2020-05-12 20:13:50
1
1
PCampbell
2020-05-12 20:13:50
$1$
$1$
atticus.cull
2020-05-12 20:13:50
1
1
Th3Numb3rThr33
2020-05-12 20:13:50
1
1
bluelinfish
2020-05-12 20:13:50
a-b=1
a-b=1
nia.tatrishvili
2020-05-12 20:13:50
1
1
CosmosNebula
2020-05-12 20:13:50
1
1
awang11
2020-05-12 20:13:50
1
1
dandan
2020-05-12 20:13:50
1
1
excelguruson
2020-05-12 20:13:50
1
1
Purple_22
2020-05-12 20:13:50
1
1
mathfun2019fortw
2020-05-12 20:13:50
1
1
hmgebg2000
2020-05-12 20:13:50
1
1
a.y.711
2020-05-12 20:13:50
a-b = 1
a-b = 1
lilcritters
2020-05-12 20:13:50
1
1
MarvelousMasterMark
2020-05-12 20:13:50
1
1
natalig
2020-05-12 20:13:50
difference increases by 1
difference increases by 1
penrose43
2020-05-12 20:13:50
1
1
LoveAfrica
2020-05-12 20:13:50
1
1
MiraBernstein
2020-05-12 20:14:06
Right!
Right!
MiraBernstein
2020-05-12 20:14:08
If the Blue Road starts OUTSIDE and ends INSIDE, then it must have crossed INTO the loop one more time than it crossed OUT of the loop. The initial value of $a-b$ (before any crossings) was 0, so the final value must be 1.
If the Blue Road starts OUTSIDE and ends INSIDE, then it must have crossed INTO the loop one more time than it crossed OUT of the loop. The initial value of $a-b$ (before any crossings) was 0, so the final value must be 1.
MiraBernstein
2020-05-12 20:14:28
It doesn't matter how many times it went in and out of the region, all but 1 cancel out!
It doesn't matter how many times it went in and out of the region, all but 1 cancel out!
MiraBernstein
2020-05-12 20:14:43
Similarly, if the Blue Road starts INSIDE and ends OUTSIDE the loop, then the final value of $a-b$ is -1. And if the Blue Road starts and ends in the same region, then the number of IN and OUT crossings is equal, so the final value of $a-b$ is 0.
Similarly, if the Blue Road starts INSIDE and ends OUTSIDE the loop, then the final value of $a-b$ is -1. And if the Blue Road starts and ends in the same region, then the number of IN and OUT crossings is equal, so the final value of $a-b$ is 0.
MiraBernstein
2020-05-12 20:14:55
Again, Case 2 is the opposite: if you start INSIDE and end OUTSIDE, then $a-b$ is -1, etc. But you still get the same possible set of values for $a-b$.
Again, Case 2 is the opposite: if you start INSIDE and end OUTSIDE, then $a-b$ is -1, etc. But you still get the same possible set of values for $a-b$.
MiraBernstein
2020-05-12 20:15:03
This completes the proof of Part a. Any questions before we go on to Part b?
This completes the proof of Part a. Any questions before we go on to Part b?
etotheipiplus1
2020-05-12 20:15:25
I like this problem!
I like this problem!
MiraBernstein
2020-05-12 20:15:32
Me too
Me too
MiraBernstein
2020-05-12 20:15:52
OK, moving on!
OK, moving on!
MiraBernstein
2020-05-12 20:16:03
Part b: Find the set of possible values of $a - b$ if Red Road and Green Road are allowed to intersect.
Part b: Find the set of possible values of $a - b$ if Red Road and Green Road are allowed to intersect.
MiraBernstein
2020-05-12 20:16:23
Answer to Problem 3b: The possible values of $a-b$ are still just 0, 1, and -1.
The proof is quite tricky! Before we go through it, I want to tell you about a common mistake that people made when solving this problem. Many applicants assumed that the intersections of Red Road and Green Road would look something like this:
Answer to Problem 3b: The possible values of $a-b$ are still just 0, 1, and -1.
The proof is quite tricky! Before we go through it, I want to tell you about a common mistake that people made when solving this problem. Many applicants assumed that the intersections of Red Road and Green Road would look something like this:
MiraBernstein
2020-05-12 20:16:37
Here Red Road and Green Road “zigzag” to and fro, with Red-Green crossings alternating between A and B. In this case, the proof is pretty simple and similar to Part (a).
Here Red Road and Green Road “zigzag” to and fro, with Red-Green crossings alternating between A and B. In this case, the proof is pretty simple and similar to Part (a).
MiraBernstein
2020-05-12 20:16:50
But the “zigzag” case is not the most general case!! Instead, the Red and Green Roads might look like this:
But the “zigzag” case is not the most general case!! Instead, the Red and Green Roads might look like this:
MiraBernstein
2020-05-12 20:17:16
Also, it’s no longer true that when the Blue Road enters and exits a region, the two crossings cancel out. In the example below, the Blue Road both enters and exits the shaded region through an A-crossing:
So you can see that things can get quite complicated!
Also, it’s no longer true that when the Blue Road enters and exits a region, the two crossings cancel out. In the example below, the Blue Road both enters and exits the shaded region through an A-crossing:
So you can see that things can get quite complicated!
MiraBernstein
2020-05-12 20:17:35
Proof of 3b: Let’s assign a depth to each region created by the Red and Green Roads, according to the following rules:
Proof of 3b: Let’s assign a depth to each region created by the Red and Green Roads, according to the following rules:
MiraBernstein
2020-05-12 20:17:47
Rule 1: Leaving Mathopolis by the Red Road, we assign depth 0 to the region on our left and depth 1 to the region on our right.
Rule 1: Leaving Mathopolis by the Red Road, we assign depth 0 to the region on our left and depth 1 to the region on our right.
MiraBernstein
2020-05-12 20:17:51
Rule 2A: Traveling along the Red Road: each time we pass Green A-crossing, the depth of the regions on both sides of the Red Road increases by 1.
Rule 2A: Traveling along the Red Road: each time we pass Green A-crossing, the depth of the regions on both sides of the Red Road increases by 1.
MiraBernstein
2020-05-12 20:17:59
Rule 2B: Each time we pass a Green B-crossing, the depth of the regions on both sides of the Red Road decreases by 1.
Rule 2B: Each time we pass a Green B-crossing, the depth of the regions on both sides of the Red Road decreases by 1.
MiraBernstein
2020-05-12 20:18:06
MiraBernstein
2020-05-12 20:18:35
We could just as well have stated these rules in terms of the Green Road -- the diagram would be exactly the same!
Rule 1: Leaving Mathopolis by the Green Road, we assign depth 1 to the region on our left and depth 0 to the region on our right.
Rule 2A: Traveling along the Green Road: each time we pass Red A-crossing, the depth of the regions on both sides of the Green Road increases by 1.
Rule 2B: Each time we pass a Red B-crossing, the depth of the regions on both sides of the Green Road decreases by 1.
We could just as well have stated these rules in terms of the Green Road -- the diagram would be exactly the same!
Rule 1: Leaving Mathopolis by the Green Road, we assign depth 1 to the region on our left and depth 0 to the region on our right.
Rule 2A: Traveling along the Green Road: each time we pass Red A-crossing, the depth of the regions on both sides of the Green Road increases by 1.
Rule 2B: Each time we pass a Red B-crossing, the depth of the regions on both sides of the Green Road decreases by 1.
MiraBernstein
2020-05-12 20:19:24
MiraBernstein
2020-05-12 20:19:41
Here is the map I showed you earlier, with regions labeled by depth
Here is the map I showed you earlier, with regions labeled by depth
MiraBernstein
2020-05-12 20:20:02
And here is a schematic representation of how these numbers were obtained (following the Red Road):
And here is a schematic representation of how these numbers were obtained (following the Red Road):
PCampbell
2020-05-12 20:20:16
Will we prove the rules are consistent and don't produce regions with multiple different depths?
Will we prove the rules are consistent and don't produce regions with multiple different depths?
MiraBernstein
2020-05-12 20:20:29
What an awesome question! Yes, we will, hold that thought!
What an awesome question! Yes, we will, hold that thought!
MiraBernstein
2020-05-12 20:20:34
For ow, assume this works
For ow, assume this works
etotheipiplus1
2020-05-12 20:20:42
It seems we can get the depth pretty high the more times it loops around
It seems we can get the depth pretty high the more times it loops around
MiraBernstein
2020-05-12 20:20:48
Yup, absolutely
Yup, absolutely
hliu1
2020-05-12 20:20:58
wait isn't each reigon defined with exactly one depth?
wait isn't each reigon defined with exactly one depth?
MiraBernstein
2020-05-12 20:21:06
Hold that thought
Hold that thought
MiraBernstein
2020-05-12 20:21:19
OK, so this depth concept is a little confusing I think
OK, so this depth concept is a little confusing I think
MiraBernstein
2020-05-12 20:21:32
So I'm pausing for a minute for more questios
So I'm pausing for a minute for more questios
MiraBernstein
2020-05-12 20:22:25
OK, moving on!
OK, moving on!
MiraBernstein
2020-05-12 20:22:33
Say by the time we get to Campville, the regions on either side of the Red Road have depth $K$ and $K+1$. What can we say about the contribution of Red-Green crossings to $a-b$?
Say by the time we get to Campville, the regions on either side of the Red Road have depth $K$ and $K+1$. What can we say about the contribution of Red-Green crossings to $a-b$?
atticus.cull
2020-05-12 20:23:58
K
K
smartmonkey999
2020-05-12 20:23:58
k crossings
k crossings
excelguruson
2020-05-12 20:23:58
a - b will be K
a - b will be K
hliu1
2020-05-12 20:23:58
K?
K?
a.y.711
2020-05-12 20:23:58
is it K?
is it K?
lilcritters
2020-05-12 20:23:58
added $K$ to $a-b$ total
added $K$ to $a-b$ total
MarvelousMasterMark
2020-05-12 20:23:58
+K
+K
Purple_22
2020-05-12 20:23:58
The Red-Green crossings add $K$ to $a-b$
The Red-Green crossings add $K$ to $a-b$
hmgebg2000
2020-05-12 20:23:58
K
K
MiraBernstein
2020-05-12 20:24:15
By construction, the contribution of Red-Green crossings to $a-b$ is precisely $K$: we started at 0 and got to $K$ by adding 1 for each Red-Green A-crossing and subtracting 1 for each Red-Green B-crossing.
By construction, the contribution of Red-Green crossings to $a-b$ is precisely $K$: we started at 0 and got to $K$ by adding 1 for each Red-Green A-crossing and subtracting 1 for each Red-Green B-crossing.
MiraBernstein
2020-05-12 20:24:33
(according to our depth rules 2A and 2B)
(according to our depth rules 2A and 2B)
iscoconut
2020-05-12 20:24:44
what happens to the depth when we add the blue line?
what happens to the depth when we add the blue line?
MiraBernstein
2020-05-12 20:24:54
Good question -- now we're finally ready for the blue road!
Good question -- now we're finally ready for the blue road!
MiraBernstein
2020-05-12 20:25:06
So the Blue Road does not affect depth at all.
So the Blue Road does not affect depth at all.
MiraBernstein
2020-05-12 20:25:16
The depth is defined just in terms of Red and Green.
The depth is defined just in terms of Red and Green.
MiraBernstein
2020-05-12 20:25:35
But depth helps us measure the contribution of the Blue Road to $a-b$.
But depth helps us measure the contribution of the Blue Road to $a-b$.
MiraBernstein
2020-05-12 20:25:45
Here are all the possible Blue-Red and Blue-Green crossings:
Here are all the possible Blue-Red and Blue-Green crossings:
MiraBernstein
2020-05-12 20:25:58
This diagram reminds you that:
* the depth to the right of the Red Road is always 1 more than the depth to its left.
* the depth to the right of the Green Road is always 1 less than the depth to its left.
* the depth on both sides of the Blue Road is the same: “regions” and “depth” are defined only in terms of Red and Green.
This diagram reminds you that:
* the depth to the right of the Red Road is always 1 more than the depth to its left.
* the depth to the right of the Green Road is always 1 less than the depth to its left.
* the depth on both sides of the Blue Road is the same: “regions” and “depth” are defined only in terms of Red and Green.
MiraBernstein
2020-05-12 20:27:41
According to the diagram, as we move along the Blue Road, how does the depth change when we cross to a new Red-Green region?
According to the diagram, as we move along the Blue Road, how does the depth change when we cross to a new Red-Green region?
atticus.cull
2020-05-12 20:28:51
increases at B's and decreases at A's
increases at B's and decreases at A's
smartmonkey999
2020-05-12 20:28:51
add or subtract 1
add or subtract 1
bluelinfish
2020-05-12 20:28:51
increases or decreases by 1
increases or decreases by 1
hliu1
2020-05-12 20:28:51
plus or minus 1?
plus or minus 1?
violeteagle
2020-05-12 20:28:51
Group A: depth decreases;
Group A: depth decreases;
penrose43
2020-05-12 20:28:51
it decreases at A crossings and increases at B crossings
it decreases at A crossings and increases at B crossings
MiraBernstein
2020-05-12 20:29:12
Yup! As we move along the Blue Road, the depth decreases by 1 after an A-crossing and increases by 1 after a B-crossing.
In other words, when depth decreases by 1, $a-b$ increases by 1, and vice versa.
Yup! As we move along the Blue Road, the depth decreases by 1 after an A-crossing and increases by 1 after a B-crossing.
In other words, when depth decreases by 1, $a-b$ increases by 1, and vice versa.
MiraBernstein
2020-05-12 20:29:25
OK, we’ve got all the pieces we need for the proof! Anyone want to try putting it all together?
OK, we’ve got all the pieces we need for the proof! Anyone want to try putting it all together?
Purple_22
2020-05-12 20:31:33
The Blue Road starts at depth 0 or 1 and ends at depth $K$ or $K+1$, so it contributes $-K$, $-K-1$, or $-K+1$ to $a-b$. The Red-Green crossings contribute $K$, for a total of $-1$, $0$, or $1$.
The Blue Road starts at depth 0 or 1 and ends at depth $K$ or $K+1$, so it contributes $-K$, $-K-1$, or $-K+1$ to $a-b$. The Red-Green crossings contribute $K$, for a total of $-1$, $0$, or $1$.
hliu1
2020-05-12 20:31:33
moving along the blue road, we start at a depth of $0$ or $1$ and end at a depth of, say, $N$ or $N-1$, then the crossings on the blue road and the negative of the crossings on the red&green roads differ by at most 1?
moving along the blue road, we start at a depth of $0$ or $1$ and end at a depth of, say, $N$ or $N-1$, then the crossings on the blue road and the negative of the crossings on the red&green roads differ by at most 1?
PCampbell
2020-05-12 20:31:33
the blue road starts in depth $0$ or $1$ and ends in $K$ or $K+1$. and $a-b$ for red-green crossings is $K$, for blue crossings is start depth - end depth
the blue road starts in depth $0$ or $1$ and ends in $K$ or $K+1$. and $a-b$ for red-green crossings is $K$, for blue crossings is start depth - end depth
violeteagle
2020-05-12 20:31:33
If K is positive, then Blue Road's intersections contribute -K or -(K+1) to the difference a-b.
If K is positive, then Blue Road's intersections contribute -K or -(K+1) to the difference a-b.
lin8989
2020-05-12 20:31:47
without the blue road, we have K, K+1, the value will be K, but everytime the depth decreases by 1, a-b to the contrary increases, so they cancel each other out, leaving -1, 0, 1
without the blue road, we have K, K+1, the value will be K, but everytime the depth decreases by 1, a-b to the contrary increases, so they cancel each other out, leaving -1, 0, 1
MiraBernstein
2020-05-12 20:31:57
Some great answers here. Let's go through this slowly.
Some great answers here. Let's go through this slowly.
MiraBernstein
2020-05-12 20:32:10
The Blue Road starts in one of the two Red-Green regions bordering Mathopolis (depth 0 and 1), and ends in one of the two Red-Green regions bordering Campville (depth $K$ and $K+1$).
So the increase in depth between the Blue Road’s initial region and its final region is either
$K-1$ or $K$ or $K+1$.
The Blue Road starts in one of the two Red-Green regions bordering Mathopolis (depth 0 and 1), and ends in one of the two Red-Green regions bordering Campville (depth $K$ and $K+1$).
So the increase in depth between the Blue Road’s initial region and its final region is either
$K-1$ or $K$ or $K+1$.
MiraBernstein
2020-05-12 20:32:26
Hence the Blue Road’s contribution to $a-b$ is either $-(K-1)$ or $-K$ or $-(K+1)$.
Hence the Blue Road’s contribution to $a-b$ is either $-(K-1)$ or $-K$ or $-(K+1)$.
MiraBernstein
2020-05-12 20:33:05
(because remember, each time depth increases, cotribution of Blue to $a-b$ decreases.)
(because remember, each time depth increases, cotribution of Blue to $a-b$ decreases.)
MiraBernstein
2020-05-12 20:33:11
As we saw earlier, the contribution of Red-Green crossings to $a-b$ is $K$. (This basically follows from the definition of depth.)
So we have shown that $a-b$ is 1, 0, or -1, as required.
As we saw earlier, the contribution of Red-Green crossings to $a-b$ is $K$. (This basically follows from the definition of depth.)
So we have shown that $a-b$ is 1, 0, or -1, as required.
etotheipiplus1
2020-05-12 20:33:22
We still have to prove that each region has only one depth
We still have to prove that each region has only one depth
MiraBernstein
2020-05-12 20:33:53
Indeed -- a bunch of people are reminding me that our definition of depth is a little suspect...
Indeed -- a bunch of people are reminding me that our definition of depth is a little suspect...
MiraBernstein
2020-05-12 20:34:16
But first, any questions about the argument so far?
But first, any questions about the argument so far?
MiraBernstein
2020-05-12 20:34:55
OK, let's prove the thing people have been clamoring about (which is awesome!) We need to show that our rules for assigning depth to regions are consistent. In mathematical terms, we need to show that the depth of a region is well-defined .
OK, let's prove the thing people have been clamoring about (which is awesome!) We need to show that our rules for assigning depth to regions are consistent. In mathematical terms, we need to show that the depth of a region is well-defined .
MiraBernstein
2020-05-12 20:35:08
Remember that we assign depth using diagrams like this:
Remember that we assign depth using diagrams like this:
MiraBernstein
2020-05-12 20:35:16
This diagram does not tell us what the actual map is. (In fact, it could correspond to several topologically different maps). It only shows us pieces of regions, and we don’t know how those pieces connect to each other. So how can we be sure that we didn’t label the same region with 2 in one part of the diagram and with 3 somewhere else?
This diagram does not tell us what the actual map is. (In fact, it could correspond to several topologically different maps). It only shows us pieces of regions, and we don’t know how those pieces connect to each other. So how can we be sure that we didn’t label the same region with 2 in one part of the diagram and with 3 somewhere else?
MiraBernstein
2020-05-12 20:35:35
This is not at all obvious, but fortunately we can prove it!
This is not at all obvious, but fortunately we can prove it!
MiraBernstein
2020-05-12 20:35:44
We want to show that if a diagram location that we labeled $x$ can be connected to a diagram location labeled $y$ (without crossing the Red or Green Roads), then $x=y$.
We want to show that if a diagram location that we labeled $x$ can be connected to a diagram location labeled $y$ (without crossing the Red or Green Roads), then $x=y$.
MiraBernstein
2020-05-12 20:35:59
We will examine the case where $x$ and $y$ are on opposite sides of the Red Road. The case where they are on the same side is proved similarly.
We will examine the case where $x$ and $y$ are on opposite sides of the Red Road. The case where they are on the same side is proved similarly.
MiraBernstein
2020-05-12 20:36:10
The dotted purple curve is the curve connecting $x$ and $y$ somewhere outside the diagram. We know nothing about it except that it doesn’t cross the Red or Green Roads.
The dotted purple curve is the curve connecting $x$ and $y$ somewhere outside the diagram. We know nothing about it except that it doesn’t cross the Red or Green Roads.
MiraBernstein
2020-05-12 20:36:16
We can also connect $x$ and $y$ inside the diagram, to form a purple loop:
We can also connect $x$ and $y$ inside the diagram, to form a purple loop:
MiraBernstein
2020-05-12 20:36:25
Unlike the dotted purple curve, we can decide exactly how to draw the solid purple curve to complete the loop. First, we cross the Red Road from $x$ to $x-1$. Then we go along the Red Road to $y$. Thus every Green-Red crossing between $x-1$ and $y$ corresponds to a Green-Purple crossing as well.
Unlike the dotted purple curve, we can decide exactly how to draw the solid purple curve to complete the loop. First, we cross the Red Road from $x$ to $x-1$. Then we go along the Red Road to $y$. Thus every Green-Red crossing between $x-1$ and $y$ corresponds to a Green-Purple crossing as well.
MiraBernstein
2020-05-12 20:36:35
The purple loop that we just drew has an INSIDE and an OUTSIDE, and it crosses the Red Road exactly once. Without loss of generality, let’s say the Red Road goes from OUTSIDE to INSIDE the loop (as suggested by the picture). What does this tell us about the number of times the Green Road crosses the purple loop?
The purple loop that we just drew has an INSIDE and an OUTSIDE, and it crosses the Red Road exactly once. Without loss of generality, let’s say the Red Road goes from OUTSIDE to INSIDE the loop (as suggested by the picture). What does this tell us about the number of times the Green Road crosses the purple loop?
MiraBernstein
2020-05-12 20:37:46
Wow, I'm getting no answers, I managed to confuse everyone!
Wow, I'm getting no answers, I managed to confuse everyone!
MiraBernstein
2020-05-12 20:37:48
MiraBernstein
2020-05-12 20:38:30
if the Red Road goes from outside to inside the loop, where is Mathopolis?
if the Red Road goes from outside to inside the loop, where is Mathopolis?
hliu1
2020-05-12 20:38:52
outside the loop
outside the loop
PCampbell
2020-05-12 20:38:52
outside
outside
excelguruson
2020-05-12 20:38:52
outside
outside
atticus.cull
2020-05-12 20:38:52
outside
outside
etotheipiplus1
2020-05-12 20:38:52
Outside
Outside
lin8989
2020-05-12 20:38:52
outside the loop
outside the loop
etotheipiplus1
2020-05-12 20:38:57
But Campville is inside
But Campville is inside
MiraBernstein
2020-05-12 20:39:14
Since the Red Road goes from OUTSIDE to INSIDE the purple loop, we know that Mathopolis is OUTSIDE the loop and Campville is INSIDE.
Since the Red Road goes from OUTSIDE to INSIDE the purple loop, we know that Mathopolis is OUTSIDE the loop and Campville is INSIDE.
MiraBernstein
2020-05-12 20:39:25
So what does that say about the Green Road relative to the loop?
So what does that say about the Green Road relative to the loop?
atticus.cull
2020-05-12 20:39:53
it crosses an odd number of times!
it crosses an odd number of times!
bluelinfish
2020-05-12 20:39:53
it goes from outside to inside
it goes from outside to inside
lilcritters
2020-05-12 20:39:53
crosses the purple loop an odd number of times
crosses the purple loop an odd number of times
MiraBernstein
2020-05-12 20:40:19
The Green Road and Red Road both go from Mathopolis to Campville.
The Green Road and Red Road both go from Mathopolis to Campville.
MiraBernstein
2020-05-12 20:40:27
So the Green Road also has to start OUTSIDE the purple loop and end INSIDE.
Therefore the number of times the Green Road goes INTO the purple loop is 1 more than than the number of times it goes OUT of the loop.
So the Green Road also has to start OUTSIDE the purple loop and end INSIDE.
Therefore the number of times the Green Road goes INTO the purple loop is 1 more than than the number of times it goes OUT of the loop.
MiraBernstein
2020-05-12 20:40:39
MiraBernstein
2020-05-12 20:40:57
How does this help us?
How does this help us?
MiraBernstein
2020-05-12 20:41:46
Looking at the diagram, we can see Green Road entrances INTO the purple loop correspond to Green-Red A-crossings between $x-1$ and $y$.
Green Road exits OUT of the purple loop correspond to Green-Red B-crossings between $x-1$ and $y$.
Looking at the diagram, we can see Green Road entrances INTO the purple loop correspond to Green-Red A-crossings between $x-1$ and $y$.
Green Road exits OUT of the purple loop correspond to Green-Red B-crossings between $x-1$ and $y$.
PCampbell
2020-05-12 20:42:14
it goes into the loop with A crossings and out with B crossings
it goes into the loop with A crossings and out with B crossings
MiraBernstein
2020-05-12 20:42:20
So as we head along the Red Road from $x-1$ to $y$, the number of $A$ crossings is 1 more than the number of $B$-crossings. According to our rules for labeling depth, this tells us that $(x-1)+1 = y$, or in other words, that $x=y$.
So as we head along the Red Road from $x-1$ to $y$, the number of $A$ crossings is 1 more than the number of $B$-crossings. According to our rules for labeling depth, this tells us that $(x-1)+1 = y$, or in other words, that $x=y$.
MiraBernstein
2020-05-12 20:42:32
This completes the proof of Problem 3. If you were able to wrap your mind around all that in real time, congratulations!
Believe it or not, some people did manage to fully solve this problem. (Some gave proofs similar to this one, but there are also other approaches.)
Any last questions on Problem 3?
This completes the proof of Problem 3. If you were able to wrap your mind around all that in real time, congratulations!
Believe it or not, some people did manage to fully solve this problem. (Some gave proofs similar to this one, but there are also other approaches.)
Any last questions on Problem 3?
violeteagle
2020-05-12 20:43:00
What happens with four roads?
What happens with four roads?
MiraBernstein
2020-05-12 20:43:07
Good question, I don't know!
Good question, I don't know!
MiraBernstein
2020-05-12 20:43:22
On to Problem 4 -- take it away, Kevin!
On to Problem 4 -- take it away, Kevin!
Lopsy
2020-05-12 20:43:25
(BTW, cutting in -- the concept of depth there might seem magical. But it can be motivated by thinking about the winding number of the curve formed by the red road followed by the green road backward.)
(BTW, cutting in -- the concept of depth there might seem magical. But it can be motivated by thinking about the winding number of the curve formed by the red road followed by the green road backward.)
KevinCarde
2020-05-12 20:43:45
Hello everyone! Here's a copy and paste of the problem statement:
Hello everyone! Here's a copy and paste of the problem statement:
KevinCarde
2020-05-12 20:43:48
Problem 4 Statement:
Mathematical Chunks of Sentient Protoplasm (MCSPs, for short) are smart blobs who dream of merging together into one huge blob. But they can only do it following certain rules:
* If two MCSPs have the same mass, or if their masses are $1$ apart, they can merge into a single MCSP, whose mass will be the sum of the original two.
* If an MCSP has even mass, it can split into two MCSPs, each with half the original mass.
Suppose we start with $n$ MCSPs, with masses $1$ through $n$. For what values of $n$ is there a finite sequence of steps that will allow all $n$ MCSPs to merge together into a single MCSP and achieve their dream of unity?
Problem 4 Statement:
Mathematical Chunks of Sentient Protoplasm (MCSPs, for short) are smart blobs who dream of merging together into one huge blob. But they can only do it following certain rules:
* If two MCSPs have the same mass, or if their masses are $1$ apart, they can merge into a single MCSP, whose mass will be the sum of the original two.
* If an MCSP has even mass, it can split into two MCSPs, each with half the original mass.
Suppose we start with $n$ MCSPs, with masses $1$ through $n$. For what values of $n$ is there a finite sequence of steps that will allow all $n$ MCSPs to merge together into a single MCSP and achieve their dream of unity?
etotheipiplus1
2020-05-12 20:44:11
I like problem 4
I like problem 4
violeteagle
2020-05-12 20:44:11
This is my favorite problem!
This is my favorite problem!
KevinCarde
2020-05-12 20:44:15
I'm glad!!
I'm glad!!
KevinCarde
2020-05-12 20:44:30
There are a number of ways to think about this problem -- in the interest of time, we'll just go through one of my favorite ways.
There are a number of ways to think about this problem -- in the interest of time, we'll just go through one of my favorite ways.
KevinCarde
2020-05-12 20:44:31
So let's dive in!
So let's dive in!
KevinCarde
2020-05-12 20:44:32
PROBLEM 4 SOLUTION
PROBLEM 4 SOLUTION
KevinCarde
2020-05-12 20:45:01
As I mentioned, there are lots of approaches. Some people used binary, some people worked very algebraically. We're going to work... backwards!
As I mentioned, there are lots of approaches. Some people used binary, some people worked very algebraically. We're going to work... backwards!
KevinCarde
2020-05-12 20:45:12
If all goes well, we'll be able to solve this problem with almost no computation.
If all goes well, we'll be able to solve this problem with almost no computation.
KevinCarde
2020-05-12 20:45:35
Let's imagine the problem in reverse: given a single MCSP of mass $N$, we're going to try to use our rules backwards to break it into separate pieces of masses $1, 2, 3, \dots$.
Let's imagine the problem in reverse: given a single MCSP of mass $N$, we're going to try to use our rules backwards to break it into separate pieces of masses $1, 2, 3, \dots$.
KevinCarde
2020-05-12 20:45:50
Let's figure out what the new, backwards rules look like:
Let's figure out what the new, backwards rules look like:
KevinCarde
2020-05-12 20:46:05
Old Rule: If two MCSPs have the same mass, or if their masses are $1$ apart, they can merge into a single MCSP, whose mass will be the sum of the original two.
Old Rule: If two MCSPs have the same mass, or if their masses are $1$ apart, they can merge into a single MCSP, whose mass will be the sum of the original two.
KevinCarde
2020-05-12 20:46:16
If we want to run this rule in reverse, what does the new, backwards rule say?
If we want to run this rule in reverse, what does the new, backwards rule say?
KevinCarde
2020-05-12 20:46:58
Lots and lots of answers, great!
Lots and lots of answers, great!
hliu1
2020-05-12 20:47:00
new rule: a MCSP of size $n$ splits into floor and ceiling of $\frac n2$
new rule: a MCSP of size $n$ splits into floor and ceiling of $\frac n2$
Parna
2020-05-12 20:47:00
An MCSP can split into two equally sizen MCSPs or two MCSPs which have sizes that are 1 apart.
An MCSP can split into two equally sizen MCSPs or two MCSPs which have sizes that are 1 apart.
lin8989
2020-05-12 20:47:00
If the mass is 2k, it can be break into k and k, if it's 2k+1, then k and k+1
If the mass is 2k, it can be break into k and k, if it's 2k+1, then k and k+1
violeteagle
2020-05-12 20:47:00
2n can become 2 n's while 2n+1 can become n and n+1
2n can become 2 n's while 2n+1 can become n and n+1
atticus.cull
2020-05-12 20:47:00
any MCSP greater than 1 can split in two
any MCSP greater than 1 can split in two
anagh
2020-05-12 20:47:00
An MSCP can be split into two MSCPs with consecutive masses.
An MSCP can be split into two MSCPs with consecutive masses.
ancientwarrior
2020-05-12 20:47:00
a single mcsp can split into either two blobs of equal mass or two blobs of mass that differ by 1
a single mcsp can split into either two blobs of equal mass or two blobs of mass that differ by 1
mathicorn
2020-05-12 20:47:00
a mass can be split into two equal masses or two masses that are 1 apart?
a mass can be split into two equal masses or two masses that are 1 apart?
KevinCarde
2020-05-12 20:47:12
Here's my favorite way of stating it:
Here's my favorite way of stating it:
KevinCarde
2020-05-12 20:47:14
New Rule: Given any MCSP, we can divide it as evenly as possible into two MCSPs.
New Rule: Given any MCSP, we can divide it as evenly as possible into two MCSPs.
KevinCarde
2020-05-12 20:47:46
In some ways, this backwards rule is more elegant than the original. Before, we had to say "equal masses or $1$ apart"; now, we can simply split any MCSP.
In some ways, this backwards rule is more elegant than the original. Before, we had to say "equal masses or $1$ apart"; now, we can simply split any MCSP.
KevinCarde
2020-05-12 20:48:04
What about the other rule? Old Rule: If an MCSP has even mass, it can split into two MCSPs, each with half the original mass.
What about the other rule? Old Rule: If an MCSP has even mass, it can split into two MCSPs, each with half the original mass.
KevinCarde
2020-05-12 20:48:09
What does this become?
What does this become?
dewdrop
2020-05-12 20:48:40
two MCSPs of the same mass can combine into one with twice the mass of the others
two MCSPs of the same mass can combine into one with twice the mass of the others
PCampbell
2020-05-12 20:48:40
2 blobs of the same mass can merge
2 blobs of the same mass can merge
hliu1
2020-05-12 20:48:40
New rule: two equal MCSP's can join together.
New rule: two equal MCSP's can join together.
atticus.cull
2020-05-12 20:48:40
irrelevant!
irrelevant!
penrose43
2020-05-12 20:48:40
we can merge two MCSPs with the same size into one with the combined mass
we can merge two MCSPs with the same size into one with the combined mass
happyhari
2020-05-12 20:48:40
youi can combine two blobs with the same mass
youi can combine two blobs with the same mass
Speedstorm
2020-05-12 20:48:40
You can combine two MCSPs with equal mass into one MCSP
You can combine two MCSPs with equal mass into one MCSP
MarvelousMasterMark
2020-05-12 20:48:40
Two MCSPs with the same mass can combine into one blob if they have the same mass
Two MCSPs with the same mass can combine into one blob if they have the same mass
piripalah
2020-05-12 20:48:40
Doubling masses?
Doubling masses?
KevinCarde
2020-05-12 20:48:52
Excellent! You might notice an interesting comment that I included here.
Excellent! You might notice an interesting comment that I included here.
KevinCarde
2020-05-12 20:49:07
It will turn out that this rule is not nearly as important to us as the first rule
It will turn out that this rule is not nearly as important to us as the first rule
KevinCarde
2020-05-12 20:49:32
Roughly, our old, original rules were, "split an even MCSP, or combine nearly identical MCSPs" and our new rules are, "split any MCSP, or combine identical MCSPs". Let's now forget about our old rules entirely and focus on the new ones.
Roughly, our old, original rules were, "split an even MCSP, or combine nearly identical MCSPs" and our new rules are, "split any MCSP, or combine identical MCSPs". Let's now forget about our old rules entirely and focus on the new ones.
KevinCarde
2020-05-12 20:49:56
Let's practice using the new rules a bit. Suppose we wanted to investigate the $n=3$ case: whether we could split a single MCSP of size $N$ into one MCSP each of sizes $1$, $2$, and $3$.
Let's practice using the new rules a bit. Suppose we wanted to investigate the $n=3$ case: whether we could split a single MCSP of size $N$ into one MCSP each of sizes $1$, $2$, and $3$.
KevinCarde
2020-05-12 20:50:00
What should $N$ be?
What should $N$ be?
SD2014
2020-05-12 20:50:23
6
6
bluelinfish
2020-05-12 20:50:23
6
6
PCampbell
2020-05-12 20:50:23
$6$
$6$
etotheipiplus1
2020-05-12 20:50:23
6
6
a.y.711
2020-05-12 20:50:23
N = 1+2+3=6
N = 1+2+3=6
Coolpeep
2020-05-12 20:50:23
6
6
anagh
2020-05-12 20:50:23
6
6
iscoconut
2020-05-12 20:50:23
6
6
SilverIntegral
2020-05-12 20:50:23
6
6
hliu1
2020-05-12 20:50:23
6
6
excelguruson
2020-05-12 20:50:23
n(n+1)/2
n(n+1)/2
KevinCarde
2020-05-12 20:50:50
Lots of 6s, and a generalization: if we want to end up with masses $1, 2, \dots, n$, we should start with $N = n(n+1)/2$.
Lots of 6s, and a generalization: if we want to end up with masses $1, 2, \dots, n$, we should start with $N = n(n+1)/2$.
KevinCarde
2020-05-12 20:51:24
So, can we do it? Can we use our rules to split an MCSP of mass $N=6$ into masses $1$ through $3$?
So, can we do it? Can we use our rules to split an MCSP of mass $N=6$ into masses $1$ through $3$?
IceQ
2020-05-12 20:51:51
Yes
Yes
dewdrop
2020-05-12 20:51:51
yes
yes
smartmonkey999
2020-05-12 20:51:51
yes
yes
violeteagle
2020-05-12 20:51:51
Yes
Yes
iscoconut
2020-05-12 20:51:51
yes
yes
etotheipiplus1
2020-05-12 20:51:51
Yes!
Yes!
PCampbell
2020-05-12 20:51:51
{6} -> {3,3} -> {1,2,3}
{6} -> {3,3} -> {1,2,3}
SilverIntegral
2020-05-12 20:51:51
yes, 6=3+3, 3=1+2
yes, 6=3+3, 3=1+2
dewdrop
2020-05-12 20:51:51
split 6 into 2 3s then split one of the threes into a 1 and a 2
split 6 into 2 3s then split one of the threes into a 1 and a 2
violeteagle
2020-05-12 20:51:51
6 --> 3 + 3 --> 3 + 2 + 1
6 --> 3 + 3 --> 3 + 2 + 1
hliu1
2020-05-12 20:51:51
6 --> 3,3 --> 1,2,3
6 --> 3,3 --> 1,2,3
KevinCarde
2020-05-12 20:51:59
Yeses and even some demonstrations! This is great.
Yeses and even some demonstrations! This is great.
KevinCarde
2020-05-12 20:52:20
Notice that we didn't have to use our combination rule here, but if we tried $N=10$ (corresponding to $n=4$), we would need it at the very end:
Notice that we didn't have to use our combination rule here, but if we tried $N=10$ (corresponding to $n=4$), we would need it at the very end:
KevinCarde
2020-05-12 20:52:29
$10 \to 5, 5 \to 2, 3, 2, 3, \to 2, 1, 2, 2, 3 \to 2, 1, 4, 3$
$10 \to 5, 5 \to 2, 3, 2, 3, \to 2, 1, 2, 2, 3 \to 2, 1, 4, 3$
etotheipiplus1
2020-05-12 20:52:32
n=4 is even more interesting!
n=4 is even more interesting!
etotheipiplus1
2020-05-12 20:52:32
because of the combination rule
because of the combination rule
KevinCarde
2020-05-12 20:52:35
KevinCarde
2020-05-12 20:53:06
If you try to do $N=15$ corresponding to $n=5$, you're going to struggle: it doesn't seem to work no matter what we do. Hmm. We'll see if we can explain that later.
If you try to do $N=15$ corresponding to $n=5$, you're going to struggle: it doesn't seem to work no matter what we do. Hmm. We'll see if we can explain that later.
KevinCarde
2020-05-12 20:53:20
But one more bigger practice run: what about $n=6$? What's the corresponding $N$, and does it work?
But one more bigger practice run: what about $n=6$? What's the corresponding $N$, and does it work?
lilcritters
2020-05-12 20:53:41
21
21
violeteagle
2020-05-12 20:53:41
21 and yes?
21 and yes?
goodskate
2020-05-12 20:53:41
Yes
Yes
KevinCarde
2020-05-12 20:53:49
Good; I'll give people a chance to try to write up the sequence of moves.
Good; I'll give people a chance to try to write up the sequence of moves.
hliu1
2020-05-12 20:54:19
21 --> 10,11 --> 10,5,6 - (10--> 1,2,3,4 process) -> 1,2,3,4,5,6
21 --> 10,11 --> 10,5,6 - (10--> 1,2,3,4 process) -> 1,2,3,4,5,6
etotheipiplus1
2020-05-12 20:54:19
21=10+11=5+5+5+6=5+2+3+2+3+6=6+5+3+2+2+2+1=6+5+4+3+2+1
21=10+11=5+5+5+6=5+2+3+2+3+6=6+5+3+2+2+2+1=6+5+4+3+2+1
a.y.711
2020-05-12 20:54:19
corresponding N = 21. 21 -> 10,11 -> 1,2,3,4 (from 10 because of n=4), 5,6
corresponding N = 21. 21 -> 10,11 -> 1,2,3,4 (from 10 because of n=4), 5,6
ancientwarrior
2020-05-12 20:54:19
21 it works 21 to 10,11 to 5,6,5,5 to 5,6,2,3,2,3 to 5,6,2,3,2,1,2 to 5,6,2,3,1,4
21 it works 21 to 10,11 to 5,6,5,5 to 5,6,2,3,2,3 to 5,6,2,3,2,1,2 to 5,6,2,3,1,4
Sross314
2020-05-12 20:54:19
21-> 11,10 -> 10, 6,5 -> 1,2,3,4,5,6 (we showed 10 works
21-> 11,10 -> 10, 6,5 -> 1,2,3,4,5,6 (we showed 10 works
KevinCarde
2020-05-12 20:54:38
Nice, some people noticed we could use what we already did for $N=10$, which is great at saving a little bit of work.
Nice, some people noticed we could use what we already did for $N=10$, which is great at saving a little bit of work.
KevinCarde
2020-05-12 20:55:00
Now that we have a little practice, let's start thinking more generally about what our rules can do for us.
Now that we have a little practice, let's start thinking more generally about what our rules can do for us.
KevinCarde
2020-05-12 20:56:01
(I'm seeing some notes in the chat about using past cases and recursion -- it was helpful here for $N=21$, but it turns out it isn't very productive trying to make it work with larger numbers. We'll see why soon!)
(I'm seeing some notes in the chat about using past cases and recursion -- it was helpful here for $N=21$, but it turns out it isn't very productive trying to make it work with larger numbers. We'll see why soon!)
excelguruson
2020-05-12 20:56:09
we can't combine to get odd numbers
we can't combine to get odd numbers
KevinCarde
2020-05-12 20:56:18
This is a fantastic, fantastic observation.
This is a fantastic, fantastic observation.
KevinCarde
2020-05-12 20:56:34
And it's ultimately going to be why the combination rule is less relevant than the splitting rule.
And it's ultimately going to be why the combination rule is less relevant than the splitting rule.
KevinCarde
2020-05-12 20:56:52
After using our combining rule several times, the only way we could possibly get an MCSP of odd mass is to "undo" the combining by splitting enough times to yield an odd mass.
After using our combining rule several times, the only way we could possibly get an MCSP of odd mass is to "undo" the combining by splitting enough times to yield an odd mass.
KevinCarde
2020-05-12 20:57:08
Therefore, if we start with an MCSP of mass $N$, to figure out what odd masses we could possibly produce, we can entirely ignore our combination rule! All achievable odd masses will arise just by splitting MCSPs over and over.
Therefore, if we start with an MCSP of mass $N$, to figure out what odd masses we could possibly produce, we can entirely ignore our combination rule! All achievable odd masses will arise just by splitting MCSPs over and over.
KevinCarde
2020-05-12 20:57:46
So let's investigate what odd numbers we can get by splitting.
So let's investigate what odd numbers we can get by splitting.
KevinCarde
2020-05-12 20:57:55
Since we potentially split into two different masses each time, we could imagine that applying the splitting rule over and over would produce an unmanageable number of different masses.
Since we potentially split into two different masses each time, we could imagine that applying the splitting rule over and over would produce an unmanageable number of different masses.
etotheipiplus1
2020-05-12 20:58:22
15=7+8=3+4+4+4 and no 5!
15=7+8=3+4+4+4 and no 5!
KevinCarde
2020-05-12 20:58:42
Ooh, good observation! If we never get a $5$ when applying our splitting rule to $15$, well, we're never going to get a $5$ no matter what we do.
Ooh, good observation! If we never get a $5$ when applying our splitting rule to $15$, well, we're never going to get a $5$ no matter what we do.
KevinCarde
2020-05-12 20:58:56
So this observation explains why we had trouble with $N=15$: we can never, ever get $5$.
So this observation explains why we had trouble with $N=15$: we can never, ever get $5$.
KevinCarde
2020-05-12 20:59:23
Let's go back to thinking a little more generally, about what happens as we keep splitting.
Let's go back to thinking a little more generally, about what happens as we keep splitting.
KevinCarde
2020-05-12 21:00:00
Lots of people in chat have excellent ideas!
Lots of people in chat have excellent ideas!
bluelinfish
2020-05-12 21:00:06
n=7: 28=14+14=7+7+7+7=3+4+3+4+3+4+3+4, still no 5
n=7: 28=14+14=7+7+7+7=3+4+3+4+3+4+3+4, still no 5
hliu1
2020-05-12 21:00:06
so we'll aim to prove you can't get 5 and 7?
so we'll aim to prove you can't get 5 and 7?
etotheipiplus1
2020-05-12 21:00:06
All numbers >= n=7 have this complication
All numbers >= n=7 have this complication
etotheipiplus1
2020-05-12 21:00:06
Because a 7 and a 5 can never both occur.
Because a 7 and a 5 can never both occur.
KevinCarde
2020-05-12 21:00:55
We're starting to conjecture something very powerful: if we can't simultaneously get $5$ and $7$, we're never going to be able to succeed for any $n \ge 7$.
We're starting to conjecture something very powerful: if we can't simultaneously get $5$ and $7$, we're never going to be able to succeed for any $n \ge 7$.
KevinCarde
2020-05-12 21:01:44
There are a bunch of good ideas in chat! As I've said, there are a bunch of ways to think about this problem.
There are a bunch of good ideas in chat! As I've said, there are a bunch of ways to think about this problem.
KevinCarde
2020-05-12 21:02:35
Here's an observation: if we only care about the set of possible masses we can split into, then whenever we split an odd mass into an even mass and odd mass, we can in fact ignore the even mass.
Here's an observation: if we only care about the set of possible masses we can split into, then whenever we split an odd mass into an even mass and odd mass, we can in fact ignore the even mass.
KevinCarde
2020-05-12 21:02:54
This is a bit tricky to explain. But imagine that we start with an MCSP of odd mass $4k\pm 1$, and let's think about what happens after we split:
This is a bit tricky to explain. But imagine that we start with an MCSP of odd mass $4k\pm 1$, and let's think about what happens after we split:
KevinCarde
2020-05-12 21:03:05
$4k\pm 1 \to 2k, 2k\pm 1$
$4k\pm 1 \to 2k, 2k\pm 1$
etotheipiplus1
2020-05-12 21:03:08
2k and 2k+1
2k and 2k+1
Bobcats
2020-05-12 21:03:08
2k and 2k+-1
2k and 2k+-1
KevinCarde
2020-05-12 21:03:19
So, why can we ignore $2k$?
So, why can we ignore $2k$?
smartmonkey999
2020-05-12 21:03:42
k, k, k, k+- 1
k, k, k, k+- 1
smartmonkey999
2020-05-12 21:03:42
splits into two k's
splits into two k's
etotheipiplus1
2020-05-12 21:03:42
because it splits into k and 2k+1 splits into k and k+1
because it splits into k and 2k+1 splits into k and k+1
Bobcats
2020-05-12 21:03:42
becomes k,k while 2k+-1 becomes k,k+-1 (has k also)
becomes k,k while 2k+-1 becomes k,k+-1 (has k also)
KevinCarde
2020-05-12 21:04:00
Right: the key here is that, in a sense, $2k\pm 1$ is more "useful" than $2k$: any number $2k$ could split into, $2k\pm 1$ can also split into!
Right: the key here is that, in a sense, $2k\pm 1$ is more "useful" than $2k$: any number $2k$ could split into, $2k\pm 1$ can also split into!
KevinCarde
2020-05-12 21:04:27
Putting all the arguments we've made together, if we want to investigate the set of odd masses we can produce, we can keep splitting MCSPs, ignoring the even mass whenever we split into both an odd and even mass.
Putting all the arguments we've made together, if we want to investigate the set of odd masses we can produce, we can keep splitting MCSPs, ignoring the even mass whenever we split into both an odd and even mass.
KevinCarde
2020-05-12 21:05:16
Rather than branching into a huge number of different masses as we split, there's now a single chain! For example, the odd masses produced in our $15$ example are this single chain:
Rather than branching into a huge number of different masses as we split, there's now a single chain! For example, the odd masses produced in our $15$ example are this single chain:
KevinCarde
2020-05-12 21:05:29
$15 \to 7 \to 3 \to 1$
$15 \to 7 \to 3 \to 1$
KevinCarde
2020-05-12 21:05:55
As you guys pointed out earlier, we don't ever get $5$ in this chain, so we can't ever split $15$ into $1+2+3+4+5$.
As you guys pointed out earlier, we don't ever get $5$ in this chain, so we can't ever split $15$ into $1+2+3+4+5$.
atticus.cull
2020-05-12 21:06:00
It's only a chain if we start with an odd $N$ though
It's only a chain if we start with an odd $N$ though
KevinCarde
2020-05-12 21:06:27
Ah, good point: we might start with even $N$. Then, we'll have to keep splitting until we get to our first odd number, and the chain of odds can start from there.
Ah, good point: we might start with even $N$. Then, we'll have to keep splitting until we get to our first odd number, and the chain of odds can start from there.
KevinCarde
2020-05-12 21:06:34
For example, what happens with $N=28$?
For example, what happens with $N=28$?
dewdrop
2020-05-12 21:06:53
split into 4 7s
split into 4 7s
lilcritters
2020-05-12 21:06:53
28, 14, 7, 3, 1
28, 14, 7, 3, 1
PCampbell
2020-05-12 21:06:53
28 14 7 3 1
28 14 7 3 1
lin8989
2020-05-12 21:06:53
28->14>7>3>1
28->14>7>3>1
atticus.cull
2020-05-12 21:06:53
7 7 7 7
7 7 7 7
Bobcats
2020-05-12 21:06:53
until 7
until 7
SilverIntegral
2020-05-12 21:06:53
7,3,1
7,3,1
MarvelousMasterMark
2020-05-12 21:06:53
28 -> 14 -> 7 -> 3 -> 1
28 -> 14 -> 7 -> 3 -> 1
KevinCarde
2020-05-12 21:07:11
Right: it takes us a while to get to an odd number, but the same logic holds. The only odd numbers we can reach will be $7$, $3$, and $1$.
Right: it takes us a while to get to an odd number, but the same logic holds. The only odd numbers we can reach will be $7$, $3$, and $1$.
KevinCarde
2020-05-12 21:07:42
Incidentally, if $N=28$, what's $n$? What's our goal splitting up $N=28$?
Incidentally, if $N=28$, what's $n$? What's our goal splitting up $N=28$?
dewdrop
2020-05-12 21:07:59
7
7
lilcritters
2020-05-12 21:07:59
7
7
smartmonkey999
2020-05-12 21:07:59
n=7
n=7
PCampbell
2020-05-12 21:07:59
$7$
$7$
KevinCarde
2020-05-12 21:08:13
Right. Can we do it? Can we split $28 = 1 + 2 + 3 + 4 + 5 + 6 + 7$?
Right. Can we do it? Can we split $28 = 1 + 2 + 3 + 4 + 5 + 6 + 7$?
dewdrop
2020-05-12 21:08:28
no
no
excelguruson
2020-05-12 21:08:28
no
no
atticus.cull
2020-05-12 21:08:28
nope
nope
lin8989
2020-05-12 21:08:28
there's no 5
there's no 5
dewdrop
2020-05-12 21:08:28
we can't get 5
we can't get 5
atticus.cull
2020-05-12 21:08:28
no 5
no 5
SilverIntegral
2020-05-12 21:08:38
No, since 5 does not appear in the chain of oddsl
No, since 5 does not appear in the chain of oddsl
KevinCarde
2020-05-12 21:08:50
Right!!
Right!!
etotheipiplus1
2020-05-12 21:08:53
this confirms our proof!
this confirms our proof!
KevinCarde
2020-05-12 21:08:55
Yes!!
Yes!!
KevinCarde
2020-05-12 21:09:20
What we've figured out is that all possible odd numbers appear in one chain, and we've seen several times that once we have $7$, our chain looks like $7\to 3\to 1$.
What we've figured out is that all possible odd numbers appear in one chain, and we've seen several times that once we have $7$, our chain looks like $7\to 3\to 1$.
KevinCarde
2020-05-12 21:09:30
So, as we were conjecturing earlier...
So, as we were conjecturing earlier...
etotheipiplus1
2020-05-12 21:09:33
7 and 5 cannot occur
7 and 5 cannot occur
hliu1
2020-05-12 21:09:43
7 --> no 5
7 --> no 5
KevinCarde
2020-05-12 21:09:49
If we have $7$, we can't have $5$.
If we have $7$, we can't have $5$.
KevinCarde
2020-05-12 21:10:53
There are a couple of questions in chat about why this $5$ and $7$ thing tells us we can't do $n \ge 7$.
There are a couple of questions in chat about why this $5$ and $7$ thing tells us we can't do $n \ge 7$.
KevinCarde
2020-05-12 21:11:13
So remember that we need to get one of each possible mass between $1$ and $n$: if $n \ge 7$, that means we need to have both a $5$ and $7$ simultaneously,.
So remember that we need to get one of each possible mass between $1$ and $n$: if $n \ge 7$, that means we need to have both a $5$ and $7$ simultaneously,.
KevinCarde
2020-05-12 21:11:38
And we can't get ever get them simultaneously!
And we can't get ever get them simultaneously!
KevinCarde
2020-05-12 21:11:50
So, what values of $n$ are possible?
So, what values of $n$ are possible?
Parna
2020-05-12 21:12:03
So that rules out every n that is greater than 6.
So that rules out every n that is greater than 6.
Parna
2020-05-12 21:12:03
1,2,3,4,6
1,2,3,4,6
excelguruson
2020-05-12 21:12:03
1,2,3,4,6
1,2,3,4,6
atticus.cull
2020-05-12 21:12:03
1, 2, 3, 4, 6
1, 2, 3, 4, 6
SilverIntegral
2020-05-12 21:12:03
2,3,4,6
2,3,4,6
lin8989
2020-05-12 21:12:03
<=6
<=6
iscoconut
2020-05-12 21:12:03
1,2,3,4,6
1,2,3,4,6
KevinCarde
2020-05-12 21:12:18
All this is right: and indeed, we already noticed earlier that $n=5$ wasn't going to work for us.
All this is right: and indeed, we already noticed earlier that $n=5$ wasn't going to work for us.
KevinCarde
2020-05-12 21:12:45
I think the problem technically allows for $n=0$, but it's not a very important case.
I think the problem technically allows for $n=0$, but it's not a very important case
.
KevinCarde
2020-05-12 21:13:11
In our warmups, we already checked that $n=3, 4, 6$ all actually work.
In our warmups, we already checked that $n=3, 4, 6$ all actually work.
KevinCarde
2020-05-12 21:13:33
We need to check the smaller $n$ as well.
We need to check the smaller $n$ as well.
etotheipiplus1
2020-05-12 21:13:36
1=1 3=1+2
1=1 3=1+2
etotheipiplus1
2020-05-12 21:13:36
so 1 and 2 work
so 1 and 2 work
KevinCarde
2020-05-12 21:14:27
In summary, we've shown by construction that $n = 1, 2, 3, 4, 6$ (and maybe $0$? chat is getting pretty philosophical!) work, $n = 5$ doesn't work, and $n \ge 7$ is hopeless. So we're done: those are the only possible values of $n$!
In summary, we've shown by construction that $n = 1, 2, 3, 4, 6$ (and maybe $0$? chat is getting pretty philosophical!) work, $n = 5$ doesn't work, and $n \ge 7$ is hopeless. So we're done: those are the only possible values of $n$!
KevinCarde
2020-05-12 21:14:52
That wraps up this problem, with a minimum of algebra and computation.
That wraps up this problem, with a minimum of algebra and computation.
Parna
2020-05-12 21:15:03
We have slain yet another problem.
We have slain yet another problem.
dandan
2020-05-12 21:15:03
Nice solution!
Nice solution!
KevinCarde
2020-05-12 21:15:05
There are other cool ideas that you could use to solve this; I encourage you to keep thinking about this problem!
There are other cool ideas that you could use to solve this; I encourage you to keep thinking about this problem!
KevinCarde
2020-05-12 21:15:15
But next up will be back to Linus for a more algebraic/combinatorial world with Problem 5.
But next up will be back to Linus for a more algebraic/combinatorial world with Problem 5.
Lopsy
2020-05-12 21:15:20
Wow Kevin! I hadn’t solved problem 4 myself. That was such a cool solution!
Wow Kevin! I hadn’t solved problem 4 myself. That was such a cool solution!
Lopsy
2020-05-12 21:15:28
Problem 5 Statement:
Given a sequence of numbers, its head length is the largest integer $m$ for which the first $m$ terms are nondecreasing. For instance, the head length of [1, 1, 2, 4, 3] is 4. Thus, we can compute the average head length for any set of sequences. For example, we can evaluate the head lengths for all six permutations of the sequence [1, 2, 3]:
[2, 1, 3], [3, 1, 2], and [3, 2, 1] each have head length 1,
[1, 3, 2] and [2, 3, 1] have head length 2, and
[1, 2, 3] has head length 3.
Thus, a permutation of [1, 2, 3] has average head length $(1 + 1 + 1 + 2 + 2 + 3)/6 = 5/3$.
Let $n$ be a positive integer. Consider all the permutations of [1, 2, …, n].
Problem 5 Statement:
Given a sequence of numbers, its head length is the largest integer $m$ for which the first $m$ terms are nondecreasing. For instance, the head length of [1, 1, 2, 4, 3] is 4. Thus, we can compute the average head length for any set of sequences. For example, we can evaluate the head lengths for all six permutations of the sequence [1, 2, 3]:
[2, 1, 3], [3, 1, 2], and [3, 2, 1] each have head length 1,
[1, 3, 2] and [2, 3, 1] have head length 2, and
[1, 2, 3] has head length 3.
Thus, a permutation of [1, 2, 3] has average head length $(1 + 1 + 1 + 2 + 2 + 3)/6 = 5/3$.
Let $n$ be a positive integer. Consider all the permutations of [1, 2, …, n].
Lopsy
2020-05-12 21:15:35
Probability and combinatorics! My favorite. Also your favorite.
Probability and combinatorics! My favorite. Also your favorite.
Lopsy
2020-05-12 21:15:48
i. What fraction of them has head length 1?
i. What fraction of them has head length 1?
Lopsy
2020-05-12 21:15:52
Let’s start off by asking: when does a sequence have head length 1?
Let’s start off by asking: when does a sequence have head length 1?
hliu1
2020-05-12 21:16:18
when first term greater than secodn
when first term greater than secodn
atticus.cull
2020-05-12 21:16:18
decreases
decreases
dewdrop
2020-05-12 21:16:18
when the 2nd number is less than the first
when the 2nd number is less than the first
Parna
2020-05-12 21:16:18
when the first number is bigger than the second one.
when the first number is bigger than the second one.
Bobcats
2020-05-12 21:16:18
the first number is greater than the second nubmer
the first number is greater than the second nubmer
atticus.cull
2020-05-12 21:16:18
decreases to begin with
decreases to begin with
bluelinfish
2020-05-12 21:16:18
the first term is greater than the second term
the first term is greater than the second term
Lopsy
2020-05-12 21:16:26
So, how often does a random permutation satisfy this?
So, how often does a random permutation satisfy this?
Parna
2020-05-12 21:16:38
This is exactly 1/2 of the time because of symmetry.
This is exactly 1/2 of the time because of symmetry.
qwerty123456asdfgzxcvb
2020-05-12 21:16:38
so 1/2?
so 1/2?
qwerty123456asdfgzxcvb
2020-05-12 21:16:38
i think 1/2
i think 1/2
Benlovemath2008
2020-05-12 21:16:38
1/2
1/2
Lopsy
2020-05-12 21:17:03
Yep! As Parna observed, by symmetry, it's equally likely for each of the first two terms to be bigger.
Yep! As Parna observed, by symmetry, it's equally likely for each of the first two terms to be bigger.
Lopsy
2020-05-12 21:17:14
ii. Of the permutations of [1,2,...,n], what fraction of them has head length $k$, for $k<n$?
ii. Of the permutations of [1,2,...,n], what fraction of them has head length $k$, for $k<n$?
Lopsy
2020-05-12 21:17:20
First of all, when does a permutation have head length k?
First of all, when does a permutation have head length k?
dewdrop
2020-05-12 21:17:56
when the first k are in order but the k+1th term is smaller than the kth
when the first k are in order but the k+1th term is smaller than the kth
Legolas_LOTR
2020-05-12 21:17:56
when the (k+1)th term is less than the kth term
when the (k+1)th term is less than the kth term
lilcritters
2020-05-12 21:17:56
the first k terms are nondecreasing but the k+1th term is smaller than the kth
the first k terms are nondecreasing but the k+1th term is smaller than the kth
Parna
2020-05-12 21:17:56
when the first k terms are increasing, and k+1-th term decreases.
when the first k terms are increasing, and k+1-th term decreases.
SilverIntegral
2020-05-12 21:17:56
when the first k terms are ascending and the k+1th term is smaller than the kth term
when the first k terms are ascending and the k+1th term is smaller than the kth term
Lopsy
2020-05-12 21:18:02
So, how often does a permutation satisfy this condition?
So, how often does a permutation satisfy this condition?
Lopsy
2020-05-12 21:18:47
Here’s another way to look at it. We want the probability that the first $k$ terms are in order, and the first $k+1$ terms aren’t in order.
Here’s another way to look at it. We want the probability that the first $k$ terms are in order, and the first $k+1$ terms aren’t in order.
excelguruson
2020-05-12 21:19:15
k/(k+1)!
k/(k+1)!
Parna
2020-05-12 21:19:15
k/(k+1)! because if you take any random permutation, there are k different ways that the first k+1 numbers can be in the correct order.
k/(k+1)! because if you take any random permutation, there are k different ways that the first k+1 numbers can be in the correct order.
dandan
2020-05-12 21:19:15
$\frac{k}{(k+1)!}$ because (k+1)! orderings, but the last number cannot be the largest.
$\frac{k}{(k+1)!}$ because (k+1)! orderings, but the last number cannot be the largest.
Lopsy
2020-05-12 21:19:38
Nice. Personally, I would write it as 1/k! - 1/(k+1)!
Nice. Personally, I would write it as 1/k! - 1/(k+1)!
Lopsy
2020-05-12 21:19:41
But that's just me.
But that's just me.
Lopsy
2020-05-12 21:20:07
There's a 1/k! chance the first k terms are in order, and we subtract a 1/(k+1)! chance of the head length being too large.
There's a 1/k! chance the first k terms are in order, and we subtract a 1/(k+1)! chance of the head length being too large.
Lopsy
2020-05-12 21:20:17
iii. What is the average head length of a permutation of [1, 2, …, n]?
iii. What is the average head length of a permutation of [1, 2, …, n]?
Lopsy
2020-05-12 21:20:24
It looks like parts i and ii were there to help you think about this part. In quiz design, this is called “scaffolding.”
Let $x_k$ denote the answer to part ii, i.e. the probability that a permutation has head length $k$. Let’s start by reviewing the definition of the average, or “expected value,” of a random number. In terms of the $x_k$, what is the average head length of a random permutation?
It looks like parts i and ii were there to help you think about this part. In quiz design, this is called “scaffolding.”
Let $x_k$ denote the answer to part ii, i.e. the probability that a permutation has head length $k$. Let’s start by reviewing the definition of the average, or “expected value,” of a random number. In terms of the $x_k$, what is the average head length of a random permutation?
bluelinfish
2020-05-12 21:21:41
$\sum_{k=1}^n (kx_k)
$\sum_{k=1}^n (kx_k)
MarvelousMasterMark
2020-05-12 21:21:41
sum of x_k * k
sum of x_k * k
Legolas_LOTR
2020-05-12 21:21:41
$n!\sum_{n-1}^{k=1}(x_k*k)$
$n!\sum_{n-1}^{k=1}(x_k*k)$
bluelinfish
2020-05-12 21:21:41
$\sum_{k=1}^n (kx_k)$
$\sum_{k=1}^n (kx_k)$
Lopsy
2020-05-12 21:21:57
Yup. (Legolas, I'm taking the average, so dividing out by the n!.)
Yup. (Legolas, I'm taking the average, so dividing out by the n!.)
Lopsy
2020-05-12 21:22:08
We know that $x_k$ fraction of the permutations contribute $k$ to the average. Therefore, the average is the sum over k of $k \cdot x_k$.
We know that $x_k$ fraction of the permutations contribute $k$ to the average. Therefore, the average is the sum over k of $k \cdot x_k$.
Lopsy
2020-05-12 21:22:19
We could now plug in our answer to part ii to evaluate this sum. That's totally valid. However, in my opinion, the scaffolding was slightly misleading -- there’s a more elegant way.
We could now plug in our answer to part ii to evaluate this sum. That's totally valid. However, in my opinion, the scaffolding was slightly misleading -- there’s a more elegant way.
Lopsy
2020-05-12 21:22:35
Let’s look at some example permutation, say 14523. It has three “increasing prefixes”: 1, 14, and 145. How does the head length of a permutation compare to the number of increasing prefixes it has?
Let’s look at some example permutation, say 14523. It has three “increasing prefixes”: 1, 14, and 145. How does the head length of a permutation compare to the number of increasing prefixes it has?
Parna
2020-05-12 21:22:58
it's equal.
it's equal.
PCampbell
2020-05-12 21:22:58
they are equal
they are equal
Lopsy
2020-05-12 21:23:20
Yup. So that's another way to think about this problem. Now, let $p_k$ denote the probability that the first $k$ elements of a permutation are increasing. In other words, $p_k$ is the probability that a random sequence has a length-$k$ increasing prefix. In terms of the $p_k$, what’s the average head length?
Yup. So that's another way to think about this problem. Now, let $p_k$ denote the probability that the first $k$ elements of a permutation are increasing. In other words, $p_k$ is the probability that a random sequence has a length-$k$ increasing prefix. In terms of the $p_k$, what’s the average head length?
Lopsy
2020-05-12 21:23:50
(Equivalently, what's the average number of increasing prefixes?)
(Equivalently, what's the average number of increasing prefixes?)
hliu1
2020-05-12 21:24:35
sum of "fraction of how many permutations have at least k"
sum of "fraction of how many permutations have at least k"
hliu1
2020-05-12 21:24:35
same number
same number
PCampbell
2020-05-12 21:24:35
$p_1 + p_2 + p_3 + \cdots$
$p_1 + p_2 + p_3 + \cdots$
hliu1
2020-05-12 21:24:35
$\sum_{k=1}^n$ fraction of permutations with a prefix of length k?
$\sum_{k=1}^n$ fraction of permutations with a prefix of length k?
Lopsy
2020-05-12 21:24:53
This was tricky -- well done to those who got it! The expected number of length-$k$ increasing prefixes in a random permutation is $p_k$. Totaling over all lengths, the expected number of increasing prefixes total is $p_1 + p_2 + \dots + p_n$.
This was tricky -- well done to those who got it! The expected number of length-$k$ increasing prefixes in a random permutation is $p_k$. Totaling over all lengths, the expected number of increasing prefixes total is $p_1 + p_2 + \dots + p_n$.
Lopsy
2020-05-12 21:25:10
To justify all this, btw, we are implicitly using the most important fact from probability theory: ｡･:*:･ﾟ★,｡･:*:･ﾟ☆ LINEARITY OF EXPECTATION ｡･:*:･ﾟ★,｡･:*:･ﾟ☆. It tells us that the expected value of a sum, here $p_1 + \dots + p_n$, equals the sum of the expected value of each $p_k$.
To justify all this, btw, we are implicitly using the most important fact from probability theory: ｡･:*:･ﾟ★,｡･:*:･ﾟ☆ LINEARITY OF EXPECTATION ｡･:*:･ﾟ★,｡･:*:･ﾟ☆. It tells us that the expected value of a sum, here $p_1 + \dots + p_n$, equals the sum of the expected value of each $p_k$.
Lopsy
2020-05-12 21:25:25
Great, now what’s $p_k$ here?
Great, now what’s $p_k$ here?
hliu1
2020-05-12 21:26:06
$\frac{1}{k!}$
$\frac{1}{k!}$
bluelinfish
2020-05-12 21:26:06
1/k!
1/k!
Lopsy
2020-05-12 21:26:17
Yeah, it’s just the probability that the first $k$ elements are in order: 1/k!. So the answer to the problem is $1/1! + 1/2! + 1/3! + 1/4! + … + 1/n!$.
Yeah, it’s just the probability that the first $k$ elements are in order: 1/k!. So the answer to the problem is $1/1! + 1/2! + 1/3! + 1/4! + … + 1/n!$.
Lopsy
2020-05-12 21:26:21
Or in sigma notation, that’s $\sigma_{1 \leq k \leq n} 1/k!$.
Or in sigma notation, that’s $\sigma_{1 \leq k \leq n} 1/k!$.
Lopsy
2020-05-12 21:26:25
Oops, wrong sigma.
Oops, wrong sigma.
Lopsy
2020-05-12 21:26:29
Or in sigma notation, that’s $\Sigma_{1 \leq k \leq n} 1/k!$.
Or in sigma notation, that’s $\Sigma_{1 \leq k \leq n} 1/k!$.
Lopsy
2020-05-12 21:26:32
There we go.
There we go.
Lopsy
2020-05-12 21:26:45
BTW, we didn’t ask for this, but this sum has a closed form. See, it just so happens that $1 + 1/2! + 1/3! + \dots = e-1$. Our answer is, therefore, so close to $e-1$! So close that the answer is the largest multiple of 1/n! below $e-1$. Or in symbols, $\floor (e-1)n! \rfloor /n!$.
BTW, we didn’t ask for this, but this sum has a closed form. See, it just so happens that $1 + 1/2! + 1/3! + \dots = e-1$. Our answer is, therefore, so close to $e-1$! So close that the answer is the largest multiple of 1/n! below $e-1$. Or in symbols, $\floor (e-1)n! \rfloor /n!$.
Lopsy
2020-05-12 21:27:08
Fun challenge problem for you to think about at home: what’s the average head length of a random series of real numbers uniformly distributed in [0,1]?
Fun challenge problem for you to think about at home: what’s the average head length of a random series of real numbers uniformly distributed in [0,1]?
Lopsy
2020-05-12 21:27:17
Now let's move on.
b. What is the average head length of a permutation of [1, 1, 2, 3, …, n]?
Now let's move on.
b. What is the average head length of a permutation of [1, 1, 2, 3, …, n]?
Lopsy
2020-05-12 21:27:23
Note the repeated 1.
Note the repeated 1.
Lopsy
2020-05-12 21:27:33
One useful technique in problem-solving: look at a similar problem that you already know how to solve.
We just learned about how to handle a random permutation of any set where all the elements are different.
One useful technique in problem-solving: look at a similar problem that you already know how to solve.
We just learned about how to handle a random permutation of any set where all the elements are different.
Lopsy
2020-05-12 21:27:38
What's a set where all the elements are different that's similar to [1, 1, 2, 3, ..., n]?
What's a set where all the elements are different that's similar to [1, 1, 2, 3, ..., n]?
mopmop
2020-05-12 21:28:43
1,2,3,n
1,2,3,n
mopmop
2020-05-12 21:28:43
[1,2,3,...,n]
[1,2,3,...,n]
Bobcats
2020-05-12 21:28:43
[1,2,...,n]
[1,2,...,n]
bluelinfish
2020-05-12 21:28:43
1,2,3,...,n
1,2,3,...,n
SilverIntegral
2020-05-12 21:28:43
(1, 2, 3, ....., n)? we can then insert the remaining 1 later.
(1, 2, 3, ....., n)? we can then insert the remaining 1 later.
Shubhashubha
2020-05-12 21:28:43
${1, 2, 3,..., n}$
${1, 2, 3,..., n}$
Lopsy
2020-05-12 21:28:47
This is one way to do the problem.
This is one way to do the problem.
Lopsy
2020-05-12 21:28:57
Look at the sequences we already know about, and then see what changes when you insert a 1.
Look at the sequences we already know about, and then see what changes when you insert a 1.
hliu1
2020-05-12 21:29:06
0,1,...,n
0,1,...,n
Parna
2020-05-12 21:29:06
[0,1,2,3,....n]
[0,1,2,3,....n]
PCampbell
2020-05-12 21:29:06
[0, 1, 2, ... n]
[0, 1, 2, ... n]
MarvelousMasterMark
2020-05-12 21:29:06
0,1,2,...,n
0,1,2,...,n
Lopsy
2020-05-12 21:29:19
This one is how I did it. Look at these sequences we already know about, and then change the 0 to a 1.
This one is how I did it. Look at these sequences we already know about, and then change the 0 to a 1.
Lopsy
2020-05-12 21:29:48
Important note: the average head length for [0, 1, 2, ..., n] is the same as for [1, 2, 3, ..., n+1]. Why?
Important note: the average head length for [0, 1, 2, ..., n] is the same as for [1, 2, 3, ..., n+1]. Why?
Benlovemath2008
2020-05-12 21:30:13
+1 to every term
+1 to every term
jiaoao
2020-05-12 21:30:13
because we are adding one to every number
because we are adding one to every number
lin8989
2020-05-12 21:30:13
the values don't matter
the values don't matter
SilverIntegral
2020-05-12 21:30:13
we can transform each term by using n --> n+1
we can transform each term by using n --> n+1
Bobcats
2020-05-12 21:30:13
shifting every number +1 doesn't affect head length
shifting every number +1 doesn't affect head length
Lopsy
2020-05-12 21:30:17
Great. Now a multiple-choice quiz. Which is larger? (A) The average head length for a permutation of [0, 1, 2, 3, …, n]. (B) The average head length for a permutation of [1, 1, 2, 3, …, n]. (C) Trick question, they’re the same.
Great. Now a multiple-choice quiz. Which is larger? (A) The average head length for a permutation of [0, 1, 2, 3, …, n]. (B) The average head length for a permutation of [1, 1, 2, 3, …, n]. (C) Trick question, they’re the same.
Bobcats
2020-05-12 21:30:48
C
C
PCampbell
2020-05-12 21:30:48
(B)
(B)
Legolas_LOTR
2020-05-12 21:30:48
a
a
Legolas_LOTR
2020-05-12 21:30:48
b
b
etotheipiplus1
2020-05-12 21:30:48
C
C
goodskate
2020-05-12 21:30:48
A)?
A)?
Lopsy
2020-05-12 21:30:53
Ok, maybe I should ask why.
Ok, maybe I should ask why.
Lopsy
2020-05-12 21:31:01
(Two of you are right!)
(Two of you are right!)
Parna
2020-05-12 21:31:57
Reasoning: The 0 effectively ends the string, while the 1 is not as harsh?
Reasoning: The 0 effectively ends the string, while the 1 is not as harsh?
xuehan24
2020-05-12 21:31:57
the 1s are interchangeable, the 0 and 1 are not?
the 1s are interchangeable, the 0 and 1 are not?
penrose43
2020-05-12 21:31:57
since it's nondecreasing, 0 and 1 are the same
since it's nondecreasing, 0 and 1 are the same
etotheipiplus1
2020-05-12 21:31:57
Because the 1s and 0s can be switched if the 0s are actually 1s
Because the 1s and 0s can be switched if the 0s are actually 1s
Lopsy
2020-05-12 21:32:20
I’m going to call a permutation of [0, 1, 2, 3, …, n] a “type-A sequence”, and a permutation of [1, 1, 2, 3, ,..., n] a “type-B sequence.” To turn a type-A sequence into a type-B sequence, we transform the 0 into a 1. When does this transformation change the head length of the sequence?
I’m going to call a permutation of [0, 1, 2, 3, …, n] a “type-A sequence”, and a permutation of [1, 1, 2, 3, ,..., n] a “type-B sequence.” To turn a type-A sequence into a type-B sequence, we transform the 0 into a 1. When does this transformation change the head length of the sequence?
PCampbell
2020-05-12 21:32:58
it only matters when you change from ...10... to ...11..., in which case the head length increases
it only matters when you change from ...10... to ...11..., in which case the head length increases
smartmonkey999
2020-05-12 21:32:58
I would be concerned if none of the answers were right
I would be concerned if none of the answers were right
dandan
2020-05-12 21:32:58
B, because nondecreasing so 1,1 is 2 but 1,0 is 1
B, because nondecreasing so 1,1 is 2 but 1,0 is 1
Parna
2020-05-12 21:32:58
When the zero is in the second position after the 1 and is changed into a 1, thus extending the head length.
When the zero is in the second position after the 1 and is changed into a 1, thus extending the head length.
hmgebg2000
2020-05-12 21:32:58
1 0 ...
1 0 ...
puppet9
2020-05-12 21:32:58
it starts with 1, 0
it starts with 1, 0
Lopsy
2020-05-12 21:33:12
Yup! It only matters if the sequence starts with 1, 0, ....
Yup! It only matters if the sequence starts with 1, 0, ....
Lopsy
2020-05-12 21:33:34
How often does that happen? What's the probability?
How often does that happen? What's the probability?
Lopsy
2020-05-12 21:33:48
(We'll also need to know how much longer the head gets on average in this case. I'll ask that soon.)
(We'll also need to know how much longer the head gets on average in this case. I'll ask that soon.)
hliu1
2020-05-12 21:34:43
low
low
Parna
2020-05-12 21:34:43
1/(n(n+1))
1/(n(n+1))
bluelinfish
2020-05-12 21:34:43
1/((n)(n-1))
1/((n)(n-1))
PCampbell
2020-05-12 21:34:43
1/(n(n+1))
1/(n(n+1))
bluelinfish
2020-05-12 21:34:43
1/((n+1)(n))
1/((n+1)(n))
Legolas_LOTR
2020-05-12 21:34:43
1/(n(n+1))
1/(n(n+1))
Lopsy
2020-05-12 21:35:05
(My official solution has 1/n(n-1). Oops, editing that now... it's so natural to think n is the number of elements in the sequence.)
(My official solution has 1/n(n-1). Oops, editing that now... it's so natural to think n is the number of elements in the sequence.)
excelguruson
2020-05-12 21:35:19
it gets longer by the average head length of the terms that follow, or [2,3,...,n]
it gets longer by the average head length of the terms that follow, or [2,3,...,n]
Lopsy
2020-05-12 21:35:29
Nice, way ahead of me. And how long is that average head length?
Nice, way ahead of me. And how long is that average head length?
bluelinfish
2020-05-12 21:36:13
1/1!+1/2!+...+1/(n-1)!
1/1!+1/2!+...+1/(n-1)!
lilcritters
2020-05-12 21:36:13
same as [1, 2, ... n-1]
same as [1, 2, ... n-1]
Bobcats
2020-05-12 21:36:13
same as [1,2,...,n-1]
same as [1,2,...,n-1]
atticus.cull
2020-05-12 21:36:13
that is 1.iii
that is 1.iii
PCampbell
2020-05-12 21:36:13
answer to iii (n-1)
answer to iii (n-1)
Lopsy
2020-05-12 21:36:51
Yup! Actually, I think the head gets one longer than that, because it now includes what used to be the 0 in the "1, 0" start.
Yup! Actually, I think the head gets one longer than that, because it now includes what used to be the 0 in the "1, 0" start.
Lopsy
2020-05-12 21:37:02
Let $A_n$ denote the answer to part (a). Then the answer to part (b) is: $a_{A+1}$, plus (the probability that a type-A sequence starts 1, 0, ...) times (the average head length extension in the 1, 0 case).
Let $A_n$ denote the answer to part (a). Then the answer to part (b) is: $a_{A+1}$, plus (the probability that a type-A sequence starts 1, 0, ...) times (the average head length extension in the 1, 0 case).
Lopsy
2020-05-12 21:37:23
Can you take it from here?
Can you take it from here?
Lopsy
2020-05-12 21:38:23
(Okay, $a_{A+1}$ was a terrible typo for $A_{n+1}$.)
(Okay, $a_{A+1}$ was a terrible typo for $A_{n+1}$.)
Lopsy
2020-05-12 21:39:48
I'm not sure whether people are busy LaTeXing or not understanding... in the latter case, y'all should ask some questions.
I'm not sure whether people are busy LaTeXing or not understanding... in the latter case, y'all should ask some questions.
lilcritters
2020-05-12 21:40:42
What does the work we did for 10 and 11 relate to the actual problem?
What does the work we did for 10 and 11 relate to the actual problem?
Lopsy
2020-05-12 21:40:45
Great question.
Great question.
Lopsy
2020-05-12 21:41:02
What we did was look at a question we already knew how to solve -- the average head length of [0, 1, 2, ..., n].
What we did was look at a question we already knew how to solve -- the average head length of [0, 1, 2, ..., n].
Lopsy
2020-05-12 21:41:11
Then we saw how the average head length changes when we turn the 0 into a 1.
Then we saw how the average head length changes when we turn the 0 into a 1.
Lopsy
2020-05-12 21:41:32
It turns out it only changes for the permutations that started with "1, 0, ...".
It turns out it only changes for the permutations that started with "1, 0, ...".
atticus.cull
2020-05-12 21:42:15
$A_{n+1} + \frac{A_{n-1} + 2}{n(n+1)}$
$A_{n+1} + \frac{A_{n-1} + 2}{n(n+1)}$
Lopsy
2020-05-12 21:42:38
Nice!! (I think it might be $A_{n-1} + 1$, not $+2$? Can people check that?)
Nice!! (I think it might be $A_{n-1} + 1$, not $+2$? Can people check that?)
Lopsy
2020-05-12 21:43:15
The point is that turning the 0 into a 1 only changes the head length $1/(n(n+1))$ of the time... and when this happens, the head length increases by something like $A_{n-1}+1$ on average.
The point is that turning the 0 into a 1 only changes the head length $1/(n(n+1))$ of the time... and when this happens, the head length increases by something like $A_{n-1}+1$ on average.
atticus.cull
2020-05-12 21:43:22
it increases twice because it gains both the 1 and 0
it increases twice because it gains both the 1 and 0
Lopsy
2020-05-12 21:43:26
It had the 1 to start with!
It had the 1 to start with!
atticus.cull
2020-05-12 21:43:44
oh right!
oh right!
Lopsy
2020-05-12 21:43:55
Don't worry -- my original solution had off-by-one errors even going into the Math Jam.
Don't worry -- my original solution had off-by-one errors even going into the Math Jam.
Lopsy
2020-05-12 21:44:12
And that was with a full week to type it up.
And that was with a full week to type it up.
Lopsy
2020-05-12 21:44:19
c. What is the average head length of a length-$n$ sequence of random digits {1, 2, 3, 4}?
c. What is the average head length of a length-$n$ sequence of random digits {1, 2, 3, 4}?
Lopsy
2020-05-12 21:44:36
There’s a solution to this using the techniques from part (a) (essentially calculating the $p_k$), which I’ll generously let you discover on your own. (You can also ask on the forums!)
There’s a solution to this using the techniques from part (a) (essentially calculating the $p_k$), which I’ll generously let you discover on your own. (You can also ask on the forums!)
Lopsy
2020-05-12 21:44:44
But there’s also a really elegant solution using generating functions!
But there’s also a really elegant solution using generating functions!
Lopsy
2020-05-12 21:45:09
There’s also a solution using zero insight or thought, in exchange for 100 hours of adding fractions. As a mathematician, this is my favorite type of solution, so this is the one I’ll present.
There’s also a solution using zero insight or thought, in exchange for 100 hours of adding fractions. As a mathematician, this is my favorite type of solution, so this is the one I’ll present.
Lopsy
2020-05-12 21:45:31
The idea is to cast the problem as something called a linear recurrence. We’ll be using a pinch of linear algebra to solve it -- I’ll try my best to keep that self-contained so that the 97% of you who haven’t taken linear algebra can follow the rest of the solution.
The idea is to cast the problem as something called a linear recurrence. We’ll be using a pinch of linear algebra to solve it -- I’ll try my best to keep that self-contained so that the 97% of you who haven’t taken linear algebra can follow the rest of the solution.
Lopsy
2020-05-12 21:45:45
First I’ll define some variables. Let $p_{3,n}$ denote the probability that all $n$ terms of a sequence are nondecreasing and the nth term is 3. Define $p_{1,n}, p_{2,n}, p_{4,n}$ analogously.
My goal is to make a recurrence, so let’s try to do it. Question: what is $p_{3,n+1} in terms of $p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$?
First I’ll define some variables. Let $p_{3,n}$ denote the probability that all $n$ terms of a sequence are nondecreasing and the nth term is 3. Define $p_{1,n}, p_{2,n}, p_{4,n}$ analogously.
My goal is to make a recurrence, so let’s try to do it. Question: what is $p_{3,n+1} in terms of $p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$?
Lopsy
2020-05-12 21:46:08
Oops, LaTeX fail.
Oops, LaTeX fail.
Lopsy
2020-05-12 21:46:23
Question: what is $p_{3,n+1}$ in terms of $p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$?
Question: what is $p_{3,n+1}$ in terms of $p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$?
atticus.cull
2020-05-12 21:47:23
$p_{1,n} + p_{2,n} + p_{3,n}$
$p_{1,n} + p_{2,n} + p_{3,n}$
penrose43
2020-05-12 21:47:23
$p_{3,n+1} = 1/4 \cdot p_{1,n} + 1/3 \cdot p_{2,n} + 1/2 \cdot p_{3,n}$
$p_{3,n+1} = 1/4 \cdot p_{1,n} + 1/3 \cdot p_{2,n} + 1/2 \cdot p_{3,n}$
bluelinfish
2020-05-12 21:47:23
$\frac{1}{4}(p_{1,n}+p_{2,n}+p_{3_n})$
$\frac{1}{4}(p_{1,n}+p_{2,n}+p_{3_n})$
Lopsy
2020-05-12 21:47:49
To get a length-$n+1$ sequence that ends in 3 and is nondecreasing, you need to take a length-$n$ sequence (that ends in 1, 2, or 3) and then plop on a 3.
To get a length-$n+1$ sequence that ends in 3 and is nondecreasing, you need to take a length-$n$ sequence (that ends in 1, 2, or 3) and then plop on a 3.
Lopsy
2020-05-12 21:48:10
Great. But, we sort of care about the answer to the problem, too. Define $a_n$ as that answer, i.e. the average head length of a length-$n$ sequence of digits {1,2,3,4}.
First I claim $a_{n+1}$ is bigger than $a_n$. Why?
Great. But, we sort of care about the answer to the problem, too. Define $a_n$ as that answer, i.e. the average head length of a length-$n$ sequence of digits {1,2,3,4}.
First I claim $a_{n+1}$ is bigger than $a_n$. Why?
Lopsy
2020-05-12 21:48:16
(And... by how much?)
(And... by how much?)
SD2014
2020-05-12 21:48:43
by the fraction of sequences with head length n+1
by the fraction of sequences with head length n+1
Lopsy
2020-05-12 21:49:03
Can we express that in terms of $p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$?
Can we express that in terms of $p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$?
SD2014
2020-05-12 21:50:47
$p_{1,n} + \frac{3}{4}p_{2,n}+\frac{2}{4}p_{3,n}+\frac{1}{4}p_{4,n}$
$p_{1,n} + \frac{3}{4}p_{2,n}+\frac{2}{4}p_{3,n}+\frac{1}{4}p_{4,n}$
atticus.cull
2020-05-12 21:50:47
$\frac{p_{1,n}}{4} + \frac{2p_{1,n}}{4} + \frac{3p_{1,n}}{4} + \frac{4p_{1,n}}{4}$
$\frac{p_{1,n}}{4} + \frac{2p_{1,n}}{4} + \frac{3p_{1,n}}{4} + \frac{4p_{1,n}}{4}$
Lopsy
2020-05-12 21:51:28
Er, those are backwards from each other, but one of them is right. Exercise for the reader which one?
Er, those are backwards from each other, but one of them is right. Exercise for the reader which one?
atticus.cull
2020-05-12 21:51:33
$\frac{p_{1,n}}{4} + \frac{p_{2,n}}{4} + \frac{p_{3,n}}{4}+ \frac{p_{4,n}}{4}$ my mistake
$\frac{p_{1,n}}{4} + \frac{p_{2,n}}{4} + \frac{p_{3,n}}{4}+ \frac{p_{4,n}}{4}$ my mistake
Lopsy
2020-05-12 21:51:36
Ah, phew.
Ah, phew.
Lopsy
2020-05-12 21:52:02
So we have something called a linear recurrence on the five variables $a_n, p_{i,n}$. There exists a technique or two for solving these.
So we have something called a linear recurrence on the five variables $a_n, p_{i,n}$. There exists a technique or two for solving these.
Lopsy
2020-05-12 21:52:34
(Atticus is informing me that their LaTeX was just wrong these times and they meant to type SD2014's answer.)
(Atticus is informing me that their LaTeX was just wrong these times and they meant to type SD2014's answer.)
Lopsy
2020-05-12 21:52:47
(LaTeX is hard to type live.)
(LaTeX is hard to type live.)
Lopsy
2020-05-12 21:52:48
As a prelude to the deep lore that follows, recall everyone’s favorite linear recurrence: the Fibonacci sequence, defined by $F_{n+2} = F_n + F_{n+1}$. The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, ...
Did you know there’s a closed-form formula for the nth Fibonacci number?
As a prelude to the deep lore that follows, recall everyone’s favorite linear recurrence: the Fibonacci sequence, defined by $F_{n+2} = F_n + F_{n+1}$. The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, ...
Did you know there’s a closed-form formula for the nth Fibonacci number?
Elaine_Wang
2020-05-12 21:53:16
Yes
Yes
bluelinfish
2020-05-12 21:53:16
yes
yes
bluelinfish
2020-05-12 21:53:16
Binet's formula
Binet's formula
jiaoao
2020-05-12 21:53:16
really?
really?
Bobcats
2020-05-12 21:53:16
binet's
binet's
Lopsy
2020-05-12 21:53:28
$\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}$.
Frankly, it’s pretty amazing that this is even an integer! Let alone a formula for Fibonacci numbers.
$\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}$.
Frankly, it’s pretty amazing that this is even an integer! Let alone a formula for Fibonacci numbers.
Lopsy
2020-05-12 21:53:37
(I'll speed up because we're low on time.)
(I'll speed up because we're low on time.)
Lopsy
2020-05-12 21:53:43
The recurrence relation for the Fibonacci sequence can be rewritten as a linear transformation. (To the 94% of you who haven’t seen matrices yet: sorry -- I promise you can tune back in in 5 minutes when I say ZAP.)
$\begin{pmatrix}1 & 1\\ 0 & 1 \end{pmatrix}\begin{pmatrix}F_{n+1}\\ F_{n} \end{pmatrix}=\begin{pmatrix}F_{n+2}\\ F_{n+1} \end{pmatrix}$
The recurrence relation for the Fibonacci sequence can be rewritten as a linear transformation. (To the 94% of you who haven’t seen matrices yet: sorry -- I promise you can tune back in in 5 minutes when I say ZAP.)
$\begin{pmatrix}1 & 1\\ 0 & 1 \end{pmatrix}\begin{pmatrix}F_{n+1}\\ F_{n} \end{pmatrix}=\begin{pmatrix}F_{n+2}\\ F_{n+1} \end{pmatrix}$
Lopsy
2020-05-12 21:53:55
The numbers $\frac{1 \pm \sqrt{5}}{2}$ are the “eigenvalues” of that transformation!
The numbers $\frac{1 \pm \sqrt{5}}{2}$ are the “eigenvalues” of that transformation!
Lopsy
2020-05-12 21:54:12
Our problem features a recurrence with a linear transformation mapping $a_n, p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$ to $a_{n+1}, p_{1,n+1}, p_{2,n+1}, p_{3,n+1}, p_{4,n+1}$. Skipping over a decent chunk of computation, it turns out the eigenvalues of that transformation are 1, ¼, ¼, ¼, ¼.
Our problem features a recurrence with a linear transformation mapping $a_n, p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n}$ to $a_{n+1}, p_{1,n+1}, p_{2,n+1}, p_{3,n+1}, p_{4,n+1}$. Skipping over a decent chunk of computation, it turns out the eigenvalues of that transformation are 1, ¼, ¼, ¼, ¼.
Legolas_LOTR
2020-05-12 21:54:24
yay eigenstuff! funn
yay eigenstuff! funn
Lopsy
2020-05-12 21:54:29
The grand theory of linear recurrences -- oh, someone please remind me to link y’all a reference for this at the end of the problem! -- tells us that $a_n$ therefore has a formula that takes the form $P_1(n) \cdot 1^n + P_¼(n) \cdot (\frac{1}{4})^n$... where $P_1$ and $P_¼$ are polynomials, respectively of degree 0 (since 1 appears as an eigenvalue once) and 3 (since ¼ appears as an eigenvalue 4 times).
The grand theory of linear recurrences -- oh, someone please remind me to link y’all a reference for this at the end of the problem! -- tells us that $a_n$ therefore has a formula that takes the form $P_1(n) \cdot 1^n + P_¼(n) \cdot (\frac{1}{4})^n$... where $P_1$ and $P_¼$ are polynomials, respectively of degree 0 (since 1 appears as an eigenvalue once) and 3 (since ¼ appears as an eigenvalue 4 times).
Lopsy
2020-05-12 21:54:48
WOOSH! ZAP! That was scary. Even if you had no idea what just happened, you can come back now. To summarize, we know the answer to the problem has the form $P_1 + P_¼(n) \cdot (\frac{1}{4})^n$ where $P_1$ is a constant and $P_¼$ is a polynomial of degree 3.
Pretend you know absolutely nothing else -- how do you suggest we solve for $P_1$ and $P_¼$?
WOOSH! ZAP! That was scary. Even if you had no idea what just happened, you can come back now. To summarize, we know the answer to the problem has the form $P_1 + P_¼(n) \cdot (\frac{1}{4})^n$ where $P_1$ is a constant and $P_¼$ is a polynomial of degree 3.
Pretend you know absolutely nothing else -- how do you suggest we solve for $P_1$ and $P_¼$?
Lopsy
2020-05-12 21:55:16
(We have five variables to solve for: $P_1$ and the four coefficients of $P_¼$. What do you need to solve for five variables?)
(We have five variables to solve for: $P_1$ and the four coefficients of $P_¼$. What do you need to solve for five variables?)
SD2014
2020-05-12 21:55:39
small values of n
small values of n
lilcritters
2020-05-12 21:55:39
five equations
five equations
Bobcats
2020-05-12 21:55:39
more equatons
more equatons
Lopsy
2020-05-12 21:55:52
Where, oh where, could we ever find five equations? Oh hey, we know the answers for $n=0, 1, 2, 3, 4$!
Where, oh where, could we ever find five equations? Oh hey, we know the answers for $n=0, 1, 2, 3, 4$!
Lopsy
2020-05-12 21:55:58
That gives us a system of 5 linear equations in 5 variables. Fun!!!
That gives us a system of 5 linear equations in 5 variables. Fun!!!
Lopsy
2020-05-12 21:56:09
Well, I was going to make you all solve it yourselves... but it's getting late...
Well, I was going to make you all solve it yourselves... but it's getting late...
Lopsy
2020-05-12 21:56:14
Luckily, I already have this one in the oven. The final answer is $\frac{175}{81}-\left(\frac{175}{81}+\frac{101}{54}n+\frac{5}{9}n^{2}+\frac{1}{18}n^{3}\right)\left(\frac{1}{4}\right)^{n}$.
Luckily, I already have this one in the oven. The final answer is $\frac{175}{81}-\left(\frac{175}{81}+\frac{101}{54}n+\frac{5}{9}n^{2}+\frac{1}{18}n^{3}\right)\left(\frac{1}{4}\right)^{n}$.
Lopsy
2020-05-12 21:56:27
This might have seemed like “the hard way to do it.” But there’s a lesson here. Once you know about linear recurrences, the above approach requires almost no thought. It’s just following a procedure.
This might have seemed like “the hard way to do it.” But there’s a lesson here. Once you know about linear recurrences, the above approach requires almost no thought. It’s just following a procedure.
Lopsy
2020-05-12 21:56:32
Wouldn’t it be great if all problems were like that?
Wouldn’t it be great if all problems were like that?
Lopsy
2020-05-12 21:56:37
There are entire fields of math -- large swaths of Diophantine equations, for example -- where reducing problems to algorithms is a major goal.
There are entire fields of math -- large swaths of Diophantine equations, for example -- where reducing problems to algorithms is a major goal.
Lopsy
2020-05-12 21:56:56
(Don’t worry, we won’t run out of fun math! We’ll be the ones inventing new procedures!)
(Don’t worry, we won’t run out of fun math! We’ll be the ones inventing new procedures!)
Lopsy
2020-05-12 21:57:02
Here’s a link to where you can learn more about linear recurrences: https://en.wikibooks.org/wiki/Linear_Algebra/Topic:_Linear_Recurrences.
And that's a wrap on Problem 5!
Here’s a link to where you can learn more about linear recurrences: https://en.wikibooks.org/wiki/Linear_Algebra/Topic:_Linear_Recurrences.
And that's a wrap on Problem 5!
MarisaD
2020-05-12 21:57:09
Okay folks! We've covered 5 of the 6 Quiz problems, and it's getting late on the East Coast. Would you like to spend another 15-20 minutes talking about Problem #6, or shall we call it a night and leave #6 a mystery? Say "keep going" in the chat if you've got some energy for the last problem, or "I'm tired" if you're ready to be done for the day.
Okay folks! We've covered 5 of the 6 Quiz problems, and it's getting late on the East Coast. Would you like to spend another 15-20 minutes talking about Problem #6, or shall we call it a night and leave #6 a mystery? Say "keep going" in the chat if you've got some energy for the last problem, or "I'm tired" if you're ready to be done for the day.
MarisaD
2020-05-12 21:57:20
(Keep in mind that there will be a transcript, so if some people want to stay but others have had their fill of problems, everybody will be able to read the transcript later.)
(Keep in mind that there will be a transcript, so if some people want to stay but others have had their fill of problems, everybody will be able to read the transcript later.)
MarisaD
2020-05-12 21:57:44
Awww, thanks for the enthusiasm. The "keep going" crew has it! On to Mira for the final problem.
Awww, thanks for the enthusiasm. The "keep going" crew has it! On to Mira for the final problem.
MiraBernstein
2020-05-12 21:58:03
Hi again, everyone! Glad you have so much energy!
Hi again, everyone! Glad you have so much energy!
MiraBernstein
2020-05-12 21:58:19
Problem 6: Harini starts with a quadratic equation, $x^2+p_1x+q_1=0$, with $p_1, q_1$ not both 0.
If the quadratic has two real roots, Harini uses them to create a new quadratic equation,
$$
x^2+p_2x+q_2 = 0,
$$
using the smaller of the two roots as $p_2$ and the larger one as $q_2$.
She keeps going in this way: at each step $n$, if the quadratic
$$
x^2+p_n x+q_n
$$
has two real roots, Harini uses them as the coefficients of the next equation,
$$
x^2+p_{n+1} x+q_{n+1}=0,
$$
always with the smaller root as $p_{n+1}$ and the larger root as $q_{n+1}$.
Harini stops when she gets to a quadratic that does not have real roots.
(A repeated root counts as two equal roots, in which case $p_{n+1} = q_{n+1}$.)
Part a: Prove that Harini’s sequence of equations is finite.
Part b: What is the maximal possible length of Harini's sequence?
Problem 6: Harini starts with a quadratic equation, $x^2+p_1x+q_1=0$, with $p_1, q_1$ not both 0.
If the quadratic has two real roots, Harini uses them to create a new quadratic equation,
$$
x^2+p_2x+q_2 = 0,
$$
using the smaller of the two roots as $p_2$ and the larger one as $q_2$.
She keeps going in this way: at each step $n$, if the quadratic
$$
x^2+p_n x+q_n
$$
has two real roots, Harini uses them as the coefficients of the next equation,
$$
x^2+p_{n+1} x+q_{n+1}=0,
$$
always with the smaller root as $p_{n+1}$ and the larger root as $q_{n+1}$.
Harini stops when she gets to a quadratic that does not have real roots.
(A repeated root counts as two equal roots, in which case $p_{n+1} = q_{n+1}$.)
Part a: Prove that Harini’s sequence of equations is finite.
Part b: What is the maximal possible length of Harini's sequence?
MiraBernstein
2020-05-12 21:58:35
I'll try to make it quick!
I'll try to make it quick!
MiraBernstein
2020-05-12 21:58:48
Problem 6: Solution. We will prove that the answer to Part (b) is 5. This automatically solves Part (a) as well.
We’re going to start by classifying quadratics of the form $x^2+px+q$ (with $p$ and $q$ not both 0) into 10 types, based on the signs and magnitudes of $p$ and $q$:
For example, quadratics of type $\large - \; +$ have $p<0$ and $q>0$.
Problem 6: Solution. We will prove that the answer to Part (b) is 5. This automatically solves Part (a) as well.
We’re going to start by classifying quadratics of the form $x^2+px+q$ (with $p$ and $q$ not both 0) into 10 types, based on the signs and magnitudes of $p$ and $q$:
For example, quadratics of type $\large - \; +$ have $p<0$ and $q>0$.
MiraBernstein
2020-05-12 21:58:58
What’s the big difference between the types in the first line (blue) and the types in the second line (red, in brackets)? Why did I organize my types in this way?
What’s the big difference between the types in the first line (blue) and the types in the second line (red, in brackets)? Why did I organize my types in this way?
bluelinfish
2020-05-12 21:59:51
p<q, p>q
p<q, p>q
penrose43
2020-05-12 21:59:51
the blue types have p <= q, the red types are the other way around
the blue types have p <= q, the red types are the other way around
SilverIntegral
2020-05-12 21:59:51
p>=q in second, q>=p in first
p>=q in second, q>=p in first
MiraBernstein
2020-05-12 22:00:07
Yup, the red, bracketed types in the second row correspond to quadratics with $p>q$, which is problematic for Harini. Can these types of quadratics appear in her sequence?
Yup, the red, bracketed types in the second row correspond to quadratics with $p>q$, which is problematic for Harini. Can these types of quadratics appear in her sequence?
bluelinfish
2020-05-12 22:00:46
only in the starting quadratic
only in the starting quadratic
atticus.cull
2020-05-12 22:00:46
only at the beggining
only at the beggining
SD2014
2020-05-12 22:00:46
only the first term
only the first term
atticus.cull
2020-05-12 22:00:46
only at the beginning
only at the beginning
MiraBernstein
2020-05-12 22:00:56
Right, they can -- but only once! The problem didn’t say that Harini starts with a quadratic where $p<q$. So the red types in brackets can appear, but only as the first term of the sequence.
Right, they can -- but only once! The problem didn’t say that Harini starts with a quadratic where $p<q$. So the red types in brackets can appear, but only as the first term of the sequence.
MiraBernstein
2020-05-12 22:01:04
We now investigate what Harini’s transformation does to each type of quadratic.
For instance, suppose we start with a quadratic of type ${\large - \; -}$ or ${[\large - \; -]}$, i.e. both $p$ and $q$ are negative. If we do Harini’s transformation, what type do we end up with?
We now investigate what Harini’s transformation does to each type of quadratic.
For instance, suppose we start with a quadratic of type ${\large - \; -}$ or ${[\large - \; -]}$, i.e. both $p$ and $q$ are negative. If we do Harini’s transformation, what type do we end up with?
SilverIntegral
2020-05-12 22:01:54
p1 negative, q1 positive
p1 negative, q1 positive
PCampbell
2020-05-12 22:01:54
- +
- +
etotheipiplus1
2020-05-12 22:01:54
I mean -+
I mean -+
bluelinfish
2020-05-12 22:01:54
- +
- +
MiraBernstein
2020-05-12 22:02:01
Wow, you guys are fast!
Wow, you guys are fast!
MiraBernstein
2020-05-12 22:02:11
If $p,q < 0$, then
$$
\sqrt{p^2 - 4q} \;>\; \sqrt{p^2} \;=\; -p,
$$
so we will have one positive and one negative root:
\begin{eqnarray}
\frac{-p - \sqrt{p^2 - 4q}}{2} &<& \frac{-p+p}2 = 0 \\
\\
\frac{-p + \sqrt{p^2 - 4q}}{2}&>& -p > 0.
\end{eqnarray}
So when we apply Harini’s transformation to a quadratic of type ${\large - \; -}$, we get a quadratic of type ${\large - \; +}$.
If $p,q < 0$, then
$$
\sqrt{p^2 - 4q} \;>\; \sqrt{p^2} \;=\; -p,
$$
so we will have one positive and one negative root:
\begin{eqnarray}
\frac{-p - \sqrt{p^2 - 4q}}{2} &<& \frac{-p+p}2 = 0 \\
\\
\frac{-p + \sqrt{p^2 - 4q}}{2}&>& -p > 0.
\end{eqnarray}
So when we apply Harini’s transformation to a quadratic of type ${\large - \; -}$, we get a quadratic of type ${\large - \; +}$.
MiraBernstein
2020-05-12 22:02:34
I’m not going to derive in detail what Harini’s transformation does to the rest of the types. It’s all elementary algebra using the quadratic formula, very similar to what we did above.
I’m not going to derive in detail what Harini’s transformation does to the rest of the types. It’s all elementary algebra using the quadratic formula, very similar to what we did above.
MiraBernstein
2020-05-12 22:02:43
But here’s a summary of the results:
But here’s a summary of the results:
MiraBernstein
2020-05-12 22:03:20
What do you think the red arrows mean?
What do you think the red arrows mean?
PCampbell
2020-05-12 22:03:59
possibility of complex roots
possibility of complex roots
wertiol123
2020-05-12 22:03:59
complex roots?
complex roots?
MiraBernstein
2020-05-12 22:04:03
Right, the types of quadratics with $q>0$ have red arrows coming out of them, because such quadratics might not have any real roots at all. These are the places where Harini’s sequence might potentially stop.
But for a quadratic that does have roots, Harini’s transformation takes it to the type indicated by the arrow.
Right, the types of quadratics with $q>0$ have red arrows coming out of them, because such quadratics might not have any real roots at all. These are the places where Harini’s sequence might potentially stop.
But for a quadratic that does have roots, Harini’s transformation takes it to the type indicated by the arrow.
MiraBernstein
2020-05-12 22:04:20
Note the central loop in the graph:
It looks like Harini could potentially go around this loop forever. On the other hand, two of the lines are dotted, so maybe not...
In fact, we will prove that not. :)
Note the central loop in the graph:
It looks like Harini could potentially go around this loop forever. On the other hand, two of the lines are dotted, so maybe not...
In fact, we will prove that not. :)
MiraBernstein
2020-05-12 22:04:37
(sorry, I switched from red lines to dotted lines)
(sorry, I switched from red lines to dotted lines)
MiraBernstein
2020-05-12 22:04:47
Here’s our key tool:
Lemma: Suppose we apply Harini's procedure to a quadratic of type ${\large - \; -}$.
Then the resulting quadratic will have no real roots, and Harini’s sequence will end there.
Here’s our key tool:
Lemma: Suppose we apply Harini's procedure to a quadratic of type ${\large - \; -}$.
Then the resulting quadratic will have no real roots, and Harini’s sequence will end there.
MiraBernstein
2020-05-12 22:04:56
Proof of lemma: Let the original quadratic be $x^2 + bx + c$, with $b \leq c < 0$.
Let the quadratic obtained after applying Harini’s transformation be $x^2 + px + q$. We showed earlier that it is of type ${\large - \; +}$, i.e. $p < 0 < q$.
Proof of lemma: Let the original quadratic be $x^2 + bx + c$, with $b \leq c < 0$.
Let the quadratic obtained after applying Harini’s transformation be $x^2 + px + q$. We showed earlier that it is of type ${\large - \; +}$, i.e. $p < 0 < q$.
MiraBernstein
2020-05-12 22:05:09
Now what do Vieta’s formulas tell us about $p$, $q$, $b$ and $c$?
Now what do Vieta’s formulas tell us about $p$, $q$, $b$ and $c$?
PCampbell
2020-05-12 22:05:54
$pq=c,p+q=-b$
$pq=c,p+q=-b$
xuehan24
2020-05-12 22:05:54
b=-p-q, c=pq
b=-p-q, c=pq
SD2014
2020-05-12 22:05:54
p+q=-b, pq=c
p+q=-b, pq=c
Shubhashubha
2020-05-12 22:05:54
p+q=-b, pq=c
p+q=-b, pq=c
Potato2017
2020-05-12 22:05:54
p+q=-b
p+q=-b
SilverIntegral
2020-05-12 22:05:54
b = -(p+q), c = pq
b = -(p+q), c = pq
MiraBernstein
2020-05-12 22:06:03
By Vieta's formulas, we have $pq = c$ and $p + q = -b$.
By Vieta's formulas, we have $pq = c$ and $p + q = -b$.
MiraBernstein
2020-05-12 22:06:10
We are given that $b \leq c$, or, equivalently, $-c \leq -b$.
Substituting in Vieta’s formulas, we conclude that
$$
-pq \leq p+q.
$$
We are given that $b \leq c$, or, equivalently, $-c \leq -b$.
Substituting in Vieta’s formulas, we conclude that
$$
-pq \leq p+q.
$$
MiraBernstein
2020-05-12 22:06:28
Now it's a bunch of easy algebra
Now it's a bunch of easy algebra
MiraBernstein
2020-05-12 22:06:37
Rearranging, we get
$$
-p \leq (1+p)q.
$$
Rearranging, we get
$$
-p \leq (1+p)q.
$$
MiraBernstein
2020-05-12 22:06:43
Since $p<0$, we can rewrite this as
$$
|p| \leq (1-|p|)q.
$$
Since $p<0$, we can rewrite this as
$$
|p| \leq (1-|p|)q.
$$
MiraBernstein
2020-05-12 22:06:49
Multiplying both sides by $|p|$, we get
$$
p^2 \leq |p|(1-|p|)q.
$$
Multiplying both sides by $|p|$, we get
$$
p^2 \leq |p|(1-|p|)q.
$$
MiraBernstein
2020-05-12 22:06:57
What can we say about $|p|(1-|p|)$?
What can we say about $|p|(1-|p|)$?
AforApple
2020-05-12 22:07:58
less than 1/4
less than 1/4
PCampbell
2020-05-12 22:07:58
$\le \frac{1}{4}$
$\le \frac{1}{4}$
MiraBernstein
2020-05-12 22:08:11
I got lots of true statements, but this is the relevant one.
I got lots of true statements, but this is the relevant one.
MiraBernstein
2020-05-12 22:08:20
The maximum value of $x(1-x)$ is $\frac14$.
The maximum value of $x(1-x)$ is $\frac14$.
MiraBernstein
2020-05-12 22:08:36
(You can figure that out by plotting the parabola)
(You can figure that out by plotting the parabola)
MiraBernstein
2020-05-12 22:08:46
How does this help us?
How does this help us?
MiraBernstein
2020-05-12 22:09:12
Why is it important that $$
p^2 \leq \frac14q.
$$
Why is it important that $$
p^2 \leq \frac14q.
$$
MiraBernstein
2020-05-12 22:09:22
?
?
wertiol123
2020-05-12 22:09:45
Discriminat is negative
Discriminat is negative
Abra_Kadabra
2020-05-12 22:09:45
discriminant < 0
discriminant < 0
bluelinfish
2020-05-12 22:09:45
discrimanant<0
discrimanant<0
MiraBernstein
2020-05-12 22:09:58
Since $q>0$, we conclude that
$$
p^2 \leq \frac14q < 4q.
$$
Thus the discriminant of $x^2-px+q=0$ is negative, and the equation has no solutions. QED
Since $q>0$, we conclude that
$$
p^2 \leq \frac14q < 4q.
$$
Thus the discriminant of $x^2-px+q=0$ is negative, and the equation has no solutions. QED
MiraBernstein
2020-05-12 22:10:20
In case you’ve forgotten, here’s what we just proved:
Lemma: Suppose we apply Harini's procedure to a quadratic of type ${\large - \; -}$.
Then the resulting quadratic will have no real roots, and Harini’s sequence will end there.
In case you’ve forgotten, here’s what we just proved:
Lemma: Suppose we apply Harini's procedure to a quadratic of type ${\large - \; -}$.
Then the resulting quadratic will have no real roots, and Harini’s sequence will end there.
MiraBernstein
2020-05-12 22:10:33
Here again is our summary of what Harini’s transformation does to the different types of quadratics:
The red arrow is the one mentioned in the lemma. So, how does the lemma help us?
Here again is our summary of what Harini’s transformation does to the different types of quadratics:
The red arrow is the one mentioned in the lemma. So, how does the lemma help us?
MiraBernstein
2020-05-12 22:11:06
(the arrows without guaranteed roots are the dotted arrows. Sorry the picture changed.)
(the arrows without guaranteed roots are the dotted arrows. Sorry the picture changed.)
lilcritters
2020-05-12 22:11:19
the central loop is not infinite
the central loop is not infinite
atticus.cull
2020-05-12 22:11:19
the process has no cycles
the process has no cycles
bluelinfish
2020-05-12 22:11:19
it cannot go in an infinite loop
it cannot go in an infinite loop
Abra_Kadabra
2020-05-12 22:11:19
if we ever reach the red arrow we are done
if we ever reach the red arrow we are done
excelguruson
2020-05-12 22:11:19
it can't go on forever
it can't go on forever
penrose43
2020-05-12 22:11:24
we'll always end up with a finite sequence, so part a is proved
we'll always end up with a finite sequence, so part a is proved
MiraBernstein
2020-05-12 22:11:37
Yup! The lemma says that once you’ve gone on the red arrow, you cannot continue. So you can’t go around the loop forever, and Harini’s sequence must be finite.
Not only that, but we can use our diagram to figure out the longest sequence of types that Harini could possibly make. Actually, she has two options. What are they?
Yup! The lemma says that once you’ve gone on the red arrow, you cannot continue. So you can’t go around the loop forever, and Harini’s sequence must be finite.
Not only that, but we can use our diagram to figure out the longest sequence of types that Harini could possibly make. Actually, she has two options. What are they?
lilcritters
2020-05-12 22:12:29
[0 -] --> - + --> + + --> - - --> - +
[0 -] --> - + --> + + --> - - --> - +
excelguruson
2020-05-12 22:12:29
start at 0- or --
start at 0- or --
penrose43
2020-05-12 22:12:29
starting at [0 -] or [- -]
starting at [0 -] or [- -]
bluelinfish
2020-05-12 22:12:29
Start with 0- or --, p>q
Start with 0- or --, p>q
MiraBernstein
2020-05-12 22:12:41
Yup! Here’s a nicely formatted picture of what you guys have all been saying:
This shows that Harini’s sequence of quadratics cannot be any longer than 5.
Are we done with the proof?
Yup! Here’s a nicely formatted picture of what you guys have all been saying:
This shows that Harini’s sequence of quadratics cannot be any longer than 5.
Are we done with the proof?
lilcritters
2020-05-12 22:13:20
We have to give an example!
We have to give an example!
penrose43
2020-05-12 22:13:20
we need to show that such a quadratic exists
we need to show that such a quadratic exists
Abra_Kadabra
2020-05-12 22:13:20
we have to show this is possible
we have to show this is possible
SD2014
2020-05-12 22:13:20
we have to show that its achievable
we have to show that its achievable
xuehan24
2020-05-12 22:13:20
the other dotted lines need to be proved possible?
the other dotted lines need to be proved possible?
MiraBernstein
2020-05-12 22:13:33
Well done spotting the missing link! All we’ve shown is that Harini’s sequence has length at most 5 .
But some of the arrows in that hypothetical sequence are dotted, which means those equations are not guaranteed to have real roots. Maybe when you actually try to construct a sequence based on our diagram, you run into obstacles similar to the one in the lemma.
Well done spotting the missing link! All we’ve shown is that Harini’s sequence has length at most 5 .
But some of the arrows in that hypothetical sequence are dotted, which means those equations are not guaranteed to have real roots. Maybe when you actually try to construct a sequence based on our diagram, you run into obstacles similar to the one in the lemma.
MiraBernstein
2020-05-12 22:13:44
In other words, for all we know, the true maximal length of Harini’s sequence might be less than 5. So to finish the proof, we have to actually show that a sequence of length 5 exists.
In other words, for all we know, the true maximal length of Harini’s sequence might be less than 5. So to finish the proof, we have to actually show that a sequence of length 5 exists.
MiraBernstein
2020-05-12 22:13:53
The easiest way to do this is by example, which is not hard to construct using our diagram as a guide. For example, here’s a sequence of length 5:
The easiest way to do this is by example, which is not hard to construct using our diagram as a guide. For example, here’s a sequence of length 5:
MiraBernstein
2020-05-12 22:13:59
$$
x^2 - 19x - 330 = (x+11)(x-30)\qquad\qquad\qquad {\large [- \; -]}
$$
$$
x^2 - 19x - 330 = (x+11)(x-30)\qquad\qquad\qquad {\large [- \; -]}
$$
MiraBernstein
2020-05-12 22:14:06
$$
\rightarrow \qquad x^2 - 11x + 30 = (x-5)(x-6)\qquad\qquad\qquad {\large - \; +}
$$
$$
\rightarrow \qquad x^2 - 11x + 30 = (x-5)(x-6)\qquad\qquad\qquad {\large - \; +}
$$
MiraBernstein
2020-05-12 22:14:14
$$
\rightarrow \qquad x^2 +5x + 6 = (x+3)(x+2)\qquad\qquad\qquad {\large + \; +}
$$
$$
\rightarrow \qquad x^2 - 3x - 2 = \left(x-\frac{3-\sqrt{17}}2\right)\left(x-\frac{3+\sqrt{17}}2\right)\qquad\qquad {\large - \; -}
$$
$$
\rightarrow \qquad x^2 + \frac{3-\sqrt{17}}2x + \frac{3+\sqrt{17}}2.\qquad\qquad\qquad\qquad {\large - \; +}
$$
$$
\rightarrow \qquad x^2 +5x + 6 = (x+3)(x+2)\qquad\qquad\qquad {\large + \; +}
$$
$$
\rightarrow \qquad x^2 - 3x - 2 = \left(x-\frac{3-\sqrt{17}}2\right)\left(x-\frac{3+\sqrt{17}}2\right)\qquad\qquad {\large - \; -}
$$
$$
\rightarrow \qquad x^2 + \frac{3-\sqrt{17}}2x + \frac{3+\sqrt{17}}2.\qquad\qquad\qquad\qquad {\large - \; +}
$$
MiraBernstein
2020-05-12 22:14:23
The fact that the final quadratic has no real roots follows from our lemma.
And we have now shown by example that the maximal length of Harini’s sequence is indeed 5. QED problem 6!
The fact that the final quadratic has no real roots follows from our lemma.
And we have now shown by example that the maximal length of Harini’s sequence is indeed 5. QED problem 6!
MarisaD
2020-05-12 22:14:42
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
MiraBernstein
2020-05-12 22:14:45
Sorry I went really fast, but I know people need to get going, since we're over time!
Sorry I went really fast, but I know people need to get going, since we're over time!
MarisaD
2020-05-12 22:15:07
I'm so glad we got through the whole Quiz.
I'm so glad we got through the whole Quiz.
MarisaD
2020-05-12 22:15:09
If we didn't get to your question, you can also post in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too!
If we didn't get to your question, you can also post in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too!
xuehan24
2020-05-12 22:15:17
Thanks
Thanks
SilverIntegral
2020-05-12 22:15:17
Thanks, it was a lot of fun!
Thanks, it was a lot of fun!
atticus.cull
2020-05-12 22:15:17
thank you!
thank you!
lilcritters
2020-05-12 22:15:20
Hooray!!
Hooray!!
MarisaD
2020-05-12 22:15:28
I'll stick around for another five minutes and answer non-Quiz questions about the program and the application process, if anybody has questions about Mathcamp itself.
I'll stick around for another five minutes and answer non-Quiz questions about the program and the application process, if anybody has questions about Mathcamp itself.
LionCodder
2020-05-12 22:15:44
Thank you
Thank you
Shubhashubha
2020-05-12 22:15:44
Thank you!
Thank you!
lilcritters
2020-05-12 22:15:44
Thank you!!!
Thank you!!!
wertiol123
2020-05-12 22:15:44
Thank you
Thank you
penrose43
2020-05-12 22:15:44
thank you!
thank you!
iscoconut
2020-05-12 22:15:44
thank you!
thank you!
Krish2526
2020-05-12 22:15:44
thank you
thank you
happyhari
2020-05-12 22:15:44
thanks so much!!
thanks so much!!
puppet9
2020-05-12 22:15:44
thank you!!
thank you!!
MarisaD
2020-05-12 22:15:49
Aww, thank you all!
Aww, thank you all!
MarisaD
2020-05-12 22:18:48
Thanks again, everybody - good night!
Thanks again, everybody - good night!
dewdrop
2020-05-12 22:18:55
thank you!
thank you!
nia.tatrishvili
2020-05-12 22:18:55
thankssss <3
thankssss <3
Pandayue
2020-05-12 22:18:55
Thank you!
Thank you!
greengrassfield
2020-05-12 22:18:55
Thank you!
Thank you!
MaxwellM
2020-05-12 22:18:55
Thank you!!
Thank you!!
KevinCarde
2020-05-12 22:19:00
Good night everyone, and thank you!
Good night everyone, and thank you!
vapodaca
2020-05-12 22:19:26
Yes, thanks everyone! And thanks to all of our moderators!
Yes, thanks everyone! And thanks to all of our moderators!
vapodaca
2020-05-12 22:19:40
If you have further questions for Mathcamp, you can contact them at https://www.mathcamp.org/contact_us/
If you have further questions for Mathcamp, you can contact them at https://www.mathcamp.org/contact_us/
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
