Art of Problem Solving will be down for scheduled maintenance on Wednesday, June 7, from 1-5 AM ET.

Mathcamp 2020 Qualifying Quiz Math Jam

Go back to the Math Jam Archive

This 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 © 2023 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!
hanakim 2020-05-12 19:30:36
Pixelboboready 2020-05-12 19:30:36
ASTR0N0M3R_11 2020-05-12 19:30:36
oboy 2020-05-12 19:30:36
Pixelboboready 2020-05-12 19:30:36
theodoremui 2020-05-12 19:30:36
sapphire1 2020-05-12 19:30:36
theodoremui 2020-05-12 19:30:36
so excited
eagle702 2020-05-12 19:30:36
Elaine_Wang 2020-05-12 19:30:36
Pixelboboready 2020-05-12 19:30:36
Hi vapodaca
Elaine_Wang 2020-05-12 19:30:36
awesomeguy856 2020-05-12 19:30:36
theodoremui 2020-05-12 19:30:36
hi vapodaca
ancientwarrior 2020-05-12 19:30:36
Parna 2020-05-12 19:30:36
Good afternoon/evening!
smartcookie12 2020-05-12 19:30:36
vapodaca 2020-05-12 19:30:43
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.
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.
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.
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:
vapodaca 2020-05-12 19:31:20
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 . 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.
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.
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!
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.
vapodaca 2020-05-12 19:32:47
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!
MarisaD 2020-05-12 19:33:10
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:
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!).
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!
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}$.
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).
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, or check out the AoPS Jam about the program and the application process from a few months ago:
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!)
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:
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.
Lopsy 2020-05-12 19:34:58
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!)
Lopsy 2020-05-12 19:35:12
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.
Lopsy 2020-05-12 19:35:30
I’ll witness your best efforts at describing your solutions now. >
Elaine_Wang 2020-05-12 19:35:51
hliu1 2020-05-12 19:35:51

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
iscoconut 2020-05-12 19:35:51
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
Parna 2020-05-12 19:36:03
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
Purple_22 2020-05-12 19:36:09
a kind of inside-out star?
Lopsy 2020-05-12 19:36:15
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.
Lopsy 2020-05-12 19:36:41
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?
awang11 2020-05-12 19:37:14
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?!?!
Lopsy 2020-05-12 19:37:34
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$.
etotheipiplus1 2020-05-12 19:37:52
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$.
hliu1 2020-05-12 19:38:36
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
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.
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.”
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.
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.
awang11 2020-05-12 19:39:59
excuse me what
Lopsy 2020-05-12 19:40:02
just kidding
Lopsy 2020-05-12 19:40:04
Now, I’ll hand things off to Marisa’s Modular Mayhem!
MarisaD 2020-05-12 19:40:15
Thanks, Linus! Let's talk fortuitously:
MarisaD 2020-05-12 19:40:25
Problem 2 Statement:
MarisaD 2020-05-12 19:40:34
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} $$
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$.
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.)
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?
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.
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.)
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$?
MarisaD 2020-05-12 19:41:40
Anyway, returning to the main event:
MarisaD 2020-05-12 19:41:47
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.
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:
MarisaD 2020-05-12 19:42:13
$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$.
MarisaD 2020-05-12 19:42:33
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}$
atticus.cull 2020-05-12 19:43:51
$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$
penrose43 2020-05-12 19:43:51
$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$.
MarisaD 2020-05-12 19:44:07
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$?
Parna 2020-05-12 19:44:55
$10^2$ is not congruent to $1 \pmod n$
lin8989 2020-05-12 19:44:55
10^2 \not congruent to 1 mod n
lilcritters 2020-05-12 19:44:55
$10^{k+2} \nequiv 10^k$
Purple_22 2020-05-12 19:44:55
$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}$
hliu1 2020-05-12 19:44:55
$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$.
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$.
MarisaD 2020-05-12 19:45:18
What's a nice way to factor $10^4-1$?
etotheipiplus1 2020-05-12 19:45:45
smartmonkey999 2020-05-12 19:45:45
difference of squares twice
winterrain01 2020-05-12 19:45:45
BakedPotato66 2020-05-12 19:45:45
diff. of squares
Purple_22 2020-05-12 19:45:45
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$$
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?
hliu1 2020-05-12 19:46:43
no, because it divides $10^2$
Purple_22 2020-05-12 19:46:43
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$
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
a.y.711 2020-05-12 19:46:43
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$.
MarisaD 2020-05-12 19:46:51
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
bluelinfish 2020-05-12 19:47:41
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
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$
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$.
MarisaD 2020-05-12 19:48:13
So, what are all possible values for $n$?
Purple_22 2020-05-12 19:49:02
101 times a factor of 99
penrose43 2020-05-12 19:49:02
$101, 303, 909, 1111, 3333, 9999$
hliu1 2020-05-12 19:49:02
atticus.cull 2020-05-12 19:49:02
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*}







MarisaD 2020-05-12 19:49:23
Any questions so far?
anagh 2020-05-12 19:49:34
why times a factor of 99???
MarisaD 2020-05-12 19:49:51
I was hoping someone would ask that!
Purple_22 2020-05-12 19:50:17
Otherwise, it's not a factor of 9999.
dandan 2020-05-12 19:50:17
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.
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.
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?
hliu1 2020-05-12 19:52:20
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}$.
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$.
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:







MarisaD 2020-05-12 19:53:01
Putting it all together: what are the possible values for $m$?
bluelinfish 2020-05-12 19:53:27
any combination of the two
Point142857Repeating 2020-05-12 19:53:27
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.
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} $$
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.
MarisaD 2020-05-12 19:53:50
Any questions on part a?
MarisaD 2020-05-12 19:54:09
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?
MarisaD 2020-05-12 19:54:23
hliu1 2020-05-12 19:54:40
if you thought listing out the answers to part a) was bad...
MarisaD 2020-05-12 19:54:45
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 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.
MarisaD 2020-05-12 19:55:22
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?
Purple_22 2020-05-12 19:56:29
5 and 101 are prime
mathfun2019fortw 2020-05-12 19:56:29
transcendental-number 2020-05-12 19:56:29
101 and 5 are primes
MarvelousMasterMark 2020-05-12 19:56:29
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.
dandan 2020-05-12 19:56:43
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$.)
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?
ancientwarrior 2020-05-12 19:57:20
using the mod 4 part
hliu1 2020-05-12 19:57:20
$2^2$ factor
Purple_22 2020-05-12 19:57:25
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$.
MarisaD 2020-05-12 19:57:33
(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?
MarisaD 2020-05-12 19:59:31
(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$.
MarisaD 2020-05-12 20:01:14
Let's check two cases.
MarisaD 2020-05-12 20:01:20
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?)
ancientwarrior 2020-05-12 20:02:16
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}$.
MarisaD 2020-05-12 20:02:41
So under that assumption for 101, what happens $\mod 5$?
bluelinfish 2020-05-12 20:03:02
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$.
MarisaD 2020-05-12 20:03:15
(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?
Purple_22 2020-05-12 20:03:51
$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}$.
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}$
MarisaD 2020-05-12 20:04:17
How do we solve congruence equation systems in modular arithmetic?
Bobcats 2020-05-12 20:04:34
lilcritters 2020-05-12 20:04:34
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}$$
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
ancientwarrior 2020-05-12 20:05:08
MarisaD 2020-05-12 20:05:12
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?
hliu1 2020-05-12 20:05:55
$10,99$ mod 101
MarisaD 2020-05-12 20:06:04
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$?
Purple_22 2020-05-12 20:06:32
Shouldn't that be 10 and 91?
MarisaD 2020-05-12 20:06:38
yep, that's right
MarisaD 2020-05-12 20:06:47
Purple_22 2020-05-12 20:06:55
Anything would work.
MarisaD 2020-05-12 20:07:02
That's right! Why?
bluelinfish 2020-05-12 20:07:26
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
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$.
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.
MarisaD 2020-05-12 20:07:41
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}$$
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}$$
MarisaD 2020-05-12 20:07:59
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?
etotheipiplus1 2020-05-12 20:08:16
Is this possible to solve without the CRT?
MarisaD 2020-05-12 20:08:22
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!
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.
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.
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.
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.
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.
MiraBernstein 2020-05-12 20:10:06
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.
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:

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

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:

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?
bluelinfish 2020-05-12 20:12:25
adds 1
Th3Numb3rThr33 2020-05-12 20:12:25
changes by 1!
atticus.cull 2020-05-12 20:12:25
Always increases by 1
dandan 2020-05-12 20:12:25
increases by 1
Bobcats 2020-05-12 20:12:25
It is a group A intersection
penrose43 2020-05-12 20:12:25
it increases by 1
SD2014 2020-05-12 20:12:25
increases by 1
dewdrop 2020-05-12 20:12:25
changes by 1
a.y.711 2020-05-12 20:12:25
a-b increases by 1
Purple_22 2020-05-12 20:12:25
It goes up by 1.
violeteagle 2020-05-12 20:12:25
a increases by 1
MiraBernstein 2020-05-12 20:12:37
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.
MiraBernstein 2020-05-12 20:13:02
So what is $a-b$ if the Blue Road starts OUTSIDE the loop and ends INSIDE it?
SD2014 2020-05-12 20:13:50
PCampbell 2020-05-12 20:13:50
atticus.cull 2020-05-12 20:13:50
Th3Numb3rThr33 2020-05-12 20:13:50
bluelinfish 2020-05-12 20:13:50
nia.tatrishvili 2020-05-12 20:13:50
CosmosNebula 2020-05-12 20:13:50
awang11 2020-05-12 20:13:50
dandan 2020-05-12 20:13:50
excelguruson 2020-05-12 20:13:50
Purple_22 2020-05-12 20:13:50
mathfun2019fortw 2020-05-12 20:13:50
hmgebg2000 2020-05-12 20:13:50
a.y.711 2020-05-12 20:13:50
a-b = 1
lilcritters 2020-05-12 20:13:50
MarvelousMasterMark 2020-05-12 20:13:50
natalig 2020-05-12 20:13:50
difference increases by 1
penrose43 2020-05-12 20:13:50
LoveAfrica 2020-05-12 20:13:50
MiraBernstein 2020-05-12 20:14:06
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.
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!
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.
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$.
MiraBernstein 2020-05-12 20:15:03
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!
MiraBernstein 2020-05-12 20:15:32
Me too
MiraBernstein 2020-05-12 20:15:52
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.
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:
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).
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:

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!
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:
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.
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.
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.
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.
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
MiraBernstein 2020-05-12 20:20:02
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?
MiraBernstein 2020-05-12 20:20:29
What an awesome question! Yes, we will, hold that thought!
MiraBernstein 2020-05-12 20:20:34
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
MiraBernstein 2020-05-12 20:20:48
Yup, absolutely
hliu1 2020-05-12 20:20:58
wait isn't each reigon defined with exactly one depth?
MiraBernstein 2020-05-12 20:21:06
Hold that thought
MiraBernstein 2020-05-12 20:21:19
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
MiraBernstein 2020-05-12 20:22:25
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$?
atticus.cull 2020-05-12 20:23:58
smartmonkey999 2020-05-12 20:23:58
k crossings
excelguruson 2020-05-12 20:23:58
a - b will be K
hliu1 2020-05-12 20:23:58
a.y.711 2020-05-12 20:23:58
is it K?
lilcritters 2020-05-12 20:23:58
added $K$ to $a-b$ total
MarvelousMasterMark 2020-05-12 20:23:58
Purple_22 2020-05-12 20:23:58
The Red-Green crossings add $K$ to $a-b$
hmgebg2000 2020-05-12 20:23:58
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.
MiraBernstein 2020-05-12 20:24:33
(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?
MiraBernstein 2020-05-12 20:24:54
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.
MiraBernstein 2020-05-12 20:25:16
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$.
MiraBernstein 2020-05-12 20:25:45
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.
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?
atticus.cull 2020-05-12 20:28:51
increases at B's and decreases at A's
smartmonkey999 2020-05-12 20:28:51
add or subtract 1
bluelinfish 2020-05-12 20:28:51
increases or decreases by 1
hliu1 2020-05-12 20:28:51
plus or minus 1?
violeteagle 2020-05-12 20:28:51
Group A: depth decreases;
penrose43 2020-05-12 20:28:51
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.
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?
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$.
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?
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
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.
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
MiraBernstein 2020-05-12 20:31:57
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$.
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)$.
MiraBernstein 2020-05-12 20:33:05
(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.
etotheipiplus1 2020-05-12 20:33:22
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...
MiraBernstein 2020-05-12 20:34:16
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 .
MiraBernstein 2020-05-12 20:35:08
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?
MiraBernstein 2020-05-12 20:35:35
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$.

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.
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.
MiraBernstein 2020-05-12 20:36:16
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.
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?
MiraBernstein 2020-05-12 20:37:46
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?
hliu1 2020-05-12 20:38:52
outside the loop
PCampbell 2020-05-12 20:38:52
excelguruson 2020-05-12 20:38:52
atticus.cull 2020-05-12 20:38:52
etotheipiplus1 2020-05-12 20:38:52
lin8989 2020-05-12 20:38:52
outside the loop
etotheipiplus1 2020-05-12 20:38:57
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.
MiraBernstein 2020-05-12 20:39:25
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!
bluelinfish 2020-05-12 20:39:53
it goes from outside to inside
lilcritters 2020-05-12 20:39:53
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.
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.
MiraBernstein 2020-05-12 20:40:39
MiraBernstein 2020-05-12 20:40:57
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$.
PCampbell 2020-05-12 20:42:14
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$.
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?
violeteagle 2020-05-12 20:43:00
What happens with four roads?
MiraBernstein 2020-05-12 20:43:07
Good question, I don't know!
MiraBernstein 2020-05-12 20:43:22
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.)
KevinCarde 2020-05-12 20:43:45
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?
etotheipiplus1 2020-05-12 20:44:11
I like problem 4
violeteagle 2020-05-12 20:44:11
This is my favorite problem!
KevinCarde 2020-05-12 20:44:15
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.
KevinCarde 2020-05-12 20:44:31
So let's dive in!
KevinCarde 2020-05-12 20:44:32
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!
KevinCarde 2020-05-12 20:45:12
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$.
KevinCarde 2020-05-12 20:45:50
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.
KevinCarde 2020-05-12 20:46:16
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!
hliu1 2020-05-12 20:47:00
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.
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
violeteagle 2020-05-12 20:47:00
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
anagh 2020-05-12 20:47:00
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
mathicorn 2020-05-12 20:47:00
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:
KevinCarde 2020-05-12 20:47:14
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.
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.
KevinCarde 2020-05-12 20:48:09
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
PCampbell 2020-05-12 20:48:40
2 blobs of the same mass can merge
hliu1 2020-05-12 20:48:40
New rule: two equal MCSP's can join together.
atticus.cull 2020-05-12 20:48:40
penrose43 2020-05-12 20:48:40
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
Speedstorm 2020-05-12 20:48:40
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
piripalah 2020-05-12 20:48:40
Doubling masses?
KevinCarde 2020-05-12 20:48:52
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
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.
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$.
KevinCarde 2020-05-12 20:50:00
What should $N$ be?
SD2014 2020-05-12 20:50:23
bluelinfish 2020-05-12 20:50:23
PCampbell 2020-05-12 20:50:23
etotheipiplus1 2020-05-12 20:50:23
a.y.711 2020-05-12 20:50:23
N = 1+2+3=6
Coolpeep 2020-05-12 20:50:23
anagh 2020-05-12 20:50:23
iscoconut 2020-05-12 20:50:23
SilverIntegral 2020-05-12 20:50:23
hliu1 2020-05-12 20:50:23
excelguruson 2020-05-12 20:50:23
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$.
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$?
IceQ 2020-05-12 20:51:51
dewdrop 2020-05-12 20:51:51
smartmonkey999 2020-05-12 20:51:51
violeteagle 2020-05-12 20:51:51
iscoconut 2020-05-12 20:51:51
etotheipiplus1 2020-05-12 20:51:51
PCampbell 2020-05-12 20:51:51
{6} -> {3,3} -> {1,2,3}
SilverIntegral 2020-05-12 20:51:51
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
violeteagle 2020-05-12 20:51:51
6 --> 3 + 3 --> 3 + 2 + 1
hliu1 2020-05-12 20:51:51
6 --> 3,3 --> 1,2,3
KevinCarde 2020-05-12 20:51:59
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:
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$
etotheipiplus1 2020-05-12 20:52:32
n=4 is even more interesting!
etotheipiplus1 2020-05-12 20:52:32
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.
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?
lilcritters 2020-05-12 20:53:41
violeteagle 2020-05-12 20:53:41
21 and yes?
goodskate 2020-05-12 20:53:41
KevinCarde 2020-05-12 20:53:49
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
etotheipiplus1 2020-05-12 20:54:19
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
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
Sross314 2020-05-12 20:54:19
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.
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.
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!)
excelguruson 2020-05-12 20:56:09
we can't combine to get odd numbers
KevinCarde 2020-05-12 20:56:18
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.
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.
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.
KevinCarde 2020-05-12 20:57:46
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.
etotheipiplus1 2020-05-12 20:58:22
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.
KevinCarde 2020-05-12 20:58:56
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.
KevinCarde 2020-05-12 21:00:00
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
hliu1 2020-05-12 21:00:06
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
etotheipiplus1 2020-05-12 21:00:06
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$.
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.
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.
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:
KevinCarde 2020-05-12 21:03:05
$4k\pm 1 \to 2k, 2k\pm 1$
etotheipiplus1 2020-05-12 21:03:08
2k and 2k+1
Bobcats 2020-05-12 21:03:08
2k and 2k+-1
KevinCarde 2020-05-12 21:03:19
So, why can we ignore $2k$?
smartmonkey999 2020-05-12 21:03:42
k, k, k, k+- 1
smartmonkey999 2020-05-12 21:03:42
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
Bobcats 2020-05-12 21:03:42
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!
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.
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:
KevinCarde 2020-05-12 21:05:29
$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$.
atticus.cull 2020-05-12 21:06:00
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.
KevinCarde 2020-05-12 21:06:34
For example, what happens with $N=28$?
dewdrop 2020-05-12 21:06:53
split into 4 7s
lilcritters 2020-05-12 21:06:53
28, 14, 7, 3, 1
PCampbell 2020-05-12 21:06:53
28 14 7 3 1
lin8989 2020-05-12 21:06:53
atticus.cull 2020-05-12 21:06:53
7 7 7 7
Bobcats 2020-05-12 21:06:53
until 7
SilverIntegral 2020-05-12 21:06:53
MarvelousMasterMark 2020-05-12 21:06:53
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$.
KevinCarde 2020-05-12 21:07:42
Incidentally, if $N=28$, what's $n$? What's our goal splitting up $N=28$?
dewdrop 2020-05-12 21:07:59
lilcritters 2020-05-12 21:07:59
smartmonkey999 2020-05-12 21:07:59
PCampbell 2020-05-12 21:07:59
KevinCarde 2020-05-12 21:08:13
Right. Can we do it? Can we split $28 = 1 + 2 + 3 + 4 + 5 + 6 + 7$?
dewdrop 2020-05-12 21:08:28
excelguruson 2020-05-12 21:08:28
atticus.cull 2020-05-12 21:08:28
lin8989 2020-05-12 21:08:28
there's no 5
dewdrop 2020-05-12 21:08:28
we can't get 5
atticus.cull 2020-05-12 21:08:28
no 5
SilverIntegral 2020-05-12 21:08:38
No, since 5 does not appear in the chain of oddsl
KevinCarde 2020-05-12 21:08:50
etotheipiplus1 2020-05-12 21:08:53
this confirms our proof!
KevinCarde 2020-05-12 21:08:55
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$.
KevinCarde 2020-05-12 21:09:30
So, as we were conjecturing earlier...
etotheipiplus1 2020-05-12 21:09:33
7 and 5 cannot occur
hliu1 2020-05-12 21:09:43
7 --> no 5
KevinCarde 2020-05-12 21:09:49
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$.
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,.
KevinCarde 2020-05-12 21:11:38
And we can't get ever get them simultaneously!
KevinCarde 2020-05-12 21:11:50
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.
Parna 2020-05-12 21:12:03
excelguruson 2020-05-12 21:12:03
atticus.cull 2020-05-12 21:12:03
1, 2, 3, 4, 6
SilverIntegral 2020-05-12 21:12:03
lin8989 2020-05-12 21:12:03
iscoconut 2020-05-12 21:12:03
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.
KevinCarde 2020-05-12 21:12:45
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.
KevinCarde 2020-05-12 21:13:33
We need to check the smaller $n$ as well.
etotheipiplus1 2020-05-12 21:13:36
1=1 3=1+2
etotheipiplus1 2020-05-12 21:13:36
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$!
KevinCarde 2020-05-12 21:14:52
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.
dandan 2020-05-12 21:15:03
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!
KevinCarde 2020-05-12 21:15:15
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!
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].
Lopsy 2020-05-12 21:15:35
Probability and combinatorics! My favorite. Also your favorite.
Lopsy 2020-05-12 21:15:48
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?
hliu1 2020-05-12 21:16:18
when first term greater than secodn
atticus.cull 2020-05-12 21:16:18
dewdrop 2020-05-12 21:16:18
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.
Bobcats 2020-05-12 21:16:18
the first number is greater than the second nubmer
atticus.cull 2020-05-12 21:16:18
decreases to begin with
bluelinfish 2020-05-12 21:16:18
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?
Parna 2020-05-12 21:16:38
This is exactly 1/2 of the time because of symmetry.
qwerty123456asdfgzxcvb 2020-05-12 21:16:38
so 1/2?
qwerty123456asdfgzxcvb 2020-05-12 21:16:38
i think 1/2
Benlovemath2008 2020-05-12 21:16:38
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.
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$?
Lopsy 2020-05-12 21:17:20
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
Legolas_LOTR 2020-05-12 21:17:56
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
Parna 2020-05-12 21:17:56
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
Lopsy 2020-05-12 21:18:02
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.
excelguruson 2020-05-12 21:19:15
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.
dandan 2020-05-12 21:19:15
$\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)!
Lopsy 2020-05-12 21:19:41
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.
Lopsy 2020-05-12 21:20:17
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?
bluelinfish 2020-05-12 21:21:41
$\sum_{k=1}^n (kx_k)
MarvelousMasterMark 2020-05-12 21:21:41
sum of x_k * k
Legolas_LOTR 2020-05-12 21:21:41
bluelinfish 2020-05-12 21:21:41
$\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!.)
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$.
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.
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?
Parna 2020-05-12 21:22:58
it's equal.
PCampbell 2020-05-12 21:22:58
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?
Lopsy 2020-05-12 21:23:50
(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"
hliu1 2020-05-12 21:24:35
same number
PCampbell 2020-05-12 21:24:35
$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?
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$.
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$.
Lopsy 2020-05-12 21:25:25
Great, now what’s $p_k$ here?
hliu1 2020-05-12 21:26:06
bluelinfish 2020-05-12 21:26:06
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!$.
Lopsy 2020-05-12 21:26:21
Or in sigma notation, that’s $\sigma_{1 \leq k \leq n} 1/k!$.
Lopsy 2020-05-12 21:26:25
Oops, wrong sigma.
Lopsy 2020-05-12 21:26:29
Or in sigma notation, that’s $\Sigma_{1 \leq k \leq n} 1/k!$.
Lopsy 2020-05-12 21:26:32
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!$.
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]?
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]?
Lopsy 2020-05-12 21:27:23
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.
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]?
mopmop 2020-05-12 21:28:43
mopmop 2020-05-12 21:28:43
Bobcats 2020-05-12 21:28:43
bluelinfish 2020-05-12 21:28:43
SilverIntegral 2020-05-12 21:28:43
(1, 2, 3, ....., n)? we can then insert the remaining 1 later.
Shubhashubha 2020-05-12 21:28:43
${1, 2, 3,..., n}$
Lopsy 2020-05-12 21:28:47
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.
hliu1 2020-05-12 21:29:06
Parna 2020-05-12 21:29:06
PCampbell 2020-05-12 21:29:06
[0, 1, 2, ... n]
MarvelousMasterMark 2020-05-12 21:29:06
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.
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?
Benlovemath2008 2020-05-12 21:30:13
+1 to every term
jiaoao 2020-05-12 21:30:13
because we are adding one to every number
lin8989 2020-05-12 21:30:13
the values don't matter
SilverIntegral 2020-05-12 21:30:13
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
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.
Bobcats 2020-05-12 21:30:48
PCampbell 2020-05-12 21:30:48
Legolas_LOTR 2020-05-12 21:30:48
Legolas_LOTR 2020-05-12 21:30:48
etotheipiplus1 2020-05-12 21:30:48
goodskate 2020-05-12 21:30:48
Lopsy 2020-05-12 21:30:53
Ok, maybe I should ask why.
Lopsy 2020-05-12 21:31:01
(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?
xuehan24 2020-05-12 21:31:57
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
etotheipiplus1 2020-05-12 21:31:57
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?
PCampbell 2020-05-12 21:32:58
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
dandan 2020-05-12 21:32:58
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.
hmgebg2000 2020-05-12 21:32:58
1 0 ...
puppet9 2020-05-12 21:32:58
it starts with 1, 0
Lopsy 2020-05-12 21:33:12
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?
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.)
hliu1 2020-05-12 21:34:43
Parna 2020-05-12 21:34:43
bluelinfish 2020-05-12 21:34:43
PCampbell 2020-05-12 21:34:43
bluelinfish 2020-05-12 21:34:43
Legolas_LOTR 2020-05-12 21:34:43
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.)
excelguruson 2020-05-12 21:35:19
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?
bluelinfish 2020-05-12 21:36:13
lilcritters 2020-05-12 21:36:13
same as [1, 2, ... n-1]
Bobcats 2020-05-12 21:36:13
same as [1,2,...,n-1]
atticus.cull 2020-05-12 21:36:13
that is 1.iii
PCampbell 2020-05-12 21:36:13
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.
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).
Lopsy 2020-05-12 21:37:23
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}$.)
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.
lilcritters 2020-05-12 21:40:42
What does the work we did for 10 and 11 relate to the actual problem?
Lopsy 2020-05-12 21:40:45
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].
Lopsy 2020-05-12 21:41:11
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, ...".
atticus.cull 2020-05-12 21:42:15
$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?)
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.
atticus.cull 2020-05-12 21:43:22
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!
atticus.cull 2020-05-12 21:43:44
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.
Lopsy 2020-05-12 21:44:12
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}?
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!)
Lopsy 2020-05-12 21:44:44
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.
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.
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}$?
Lopsy 2020-05-12 21:46:08
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}$?
atticus.cull 2020-05-12 21:47:23
$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}$
bluelinfish 2020-05-12 21:47:23
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.
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?
Lopsy 2020-05-12 21:48:16
(And... by how much?)
SD2014 2020-05-12 21:48:43
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}$?
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}$
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}$
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?
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
Lopsy 2020-05-12 21:51:36
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.
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.)
Lopsy 2020-05-12 21:52:47
(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?
Elaine_Wang 2020-05-12 21:53:16
bluelinfish 2020-05-12 21:53:16
bluelinfish 2020-05-12 21:53:16
Binet's formula
jiaoao 2020-05-12 21:53:16
Bobcats 2020-05-12 21:53:16
Lopsy 2020-05-12 21:53:28

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.)
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}$
Lopsy 2020-05-12 21:53:55
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, ¼, ¼, ¼, ¼.
Legolas_LOTR 2020-05-12 21:54:24
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).
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_¼$?
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?)
SD2014 2020-05-12 21:55:39
small values of n
lilcritters 2020-05-12 21:55:39
five equations
Bobcats 2020-05-12 21:55:39
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$!
Lopsy 2020-05-12 21:55:58
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...
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}$.
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.
Lopsy 2020-05-12 21:56:32
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.
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!)
Lopsy 2020-05-12 21:57:02
Here’s a link to where you can learn more about 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.
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.)
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.
MiraBernstein 2020-05-12 21:58:03
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?
MiraBernstein 2020-05-12 21:58:35
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$.
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?
bluelinfish 2020-05-12 21:59:51
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
SilverIntegral 2020-05-12 21:59:51
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?
bluelinfish 2020-05-12 22:00:46
only in the starting quadratic
atticus.cull 2020-05-12 22:00:46
only at the beggining
SD2014 2020-05-12 22:00:46
only the first term
atticus.cull 2020-05-12 22:00:46
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.
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?
SilverIntegral 2020-05-12 22:01:54
p1 negative, q1 positive
PCampbell 2020-05-12 22:01:54
- +
etotheipiplus1 2020-05-12 22:01:54
I mean -+
bluelinfish 2020-05-12 22:01:54
- +
MiraBernstein 2020-05-12 22:02:01
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:


\frac{-p - \sqrt{p^2 - 4q}}{2} &<& \frac{-p+p}2 = 0 \\


\frac{-p + \sqrt{p^2 - 4q}}{2}&>& -p > 0.


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.
MiraBernstein 2020-05-12 22:02:43
But here’s a summary of the results:

MiraBernstein 2020-05-12 22:03:20
What do you think the red arrows mean?
PCampbell 2020-05-12 22:03:59
possibility of complex roots
wertiol123 2020-05-12 22:03:59
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.
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. :)
MiraBernstein 2020-05-12 22:04:37
(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.
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$.
MiraBernstein 2020-05-12 22:05:09
Now what do Vieta’s formulas tell us about $p$, $q$, $b$ and $c$?
PCampbell 2020-05-12 22:05:54
xuehan24 2020-05-12 22:05:54
b=-p-q, c=pq
SD2014 2020-05-12 22:05:54
p+q=-b, pq=c
Shubhashubha 2020-05-12 22:05:54
p+q=-b, pq=c
Potato2017 2020-05-12 22:05:54
SilverIntegral 2020-05-12 22:05:54
b = -(p+q), c = pq
MiraBernstein 2020-05-12 22:06:03
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.

MiraBernstein 2020-05-12 22:06:28
Now it's a bunch of easy algebra
MiraBernstein 2020-05-12 22:06:37
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.

MiraBernstein 2020-05-12 22:06:49
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|)$?
AforApple 2020-05-12 22:07:58
less than 1/4
PCampbell 2020-05-12 22:07:58
$\le \frac{1}{4}$
MiraBernstein 2020-05-12 22:08:11
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$.
MiraBernstein 2020-05-12 22:08:36
(You can figure that out by plotting the parabola)
MiraBernstein 2020-05-12 22:08:46
How does this help us?
MiraBernstein 2020-05-12 22:09:12
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
Abra_Kadabra 2020-05-12 22:09:45
discriminant < 0
bluelinfish 2020-05-12 22:09:45
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
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.
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?
MiraBernstein 2020-05-12 22:11:06
(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
atticus.cull 2020-05-12 22:11:19
the process has no cycles
bluelinfish 2020-05-12 22:11:19
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
excelguruson 2020-05-12 22:11:19
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
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?
lilcritters 2020-05-12 22:12:29
[0 -] --> - + --> + + --> - - --> - +
excelguruson 2020-05-12 22:12:29
start at 0- or --
penrose43 2020-05-12 22:12:29
starting at [0 -] or [- -]
bluelinfish 2020-05-12 22:12:29
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?
lilcritters 2020-05-12 22:13:20
We have to give an example!
penrose43 2020-05-12 22:13:20
we need to show that such a quadratic exists
Abra_Kadabra 2020-05-12 22:13:20
we have to show this is possible
SD2014 2020-05-12 22:13:20
we have to show that its achievable
xuehan24 2020-05-12 22:13:20
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.
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.
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:
MiraBernstein 2020-05-12 22:13:59

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 - \; +}

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 - \; +}

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!
MarisaD 2020-05-12 22:14:42
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!
MarisaD 2020-05-12 22:15:07
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 - the Mathcamp staff will post replies, and you'll get student opinions, too!
xuehan24 2020-05-12 22:15:17
SilverIntegral 2020-05-12 22:15:17
Thanks, it was a lot of fun!
atticus.cull 2020-05-12 22:15:17
thank you!
lilcritters 2020-05-12 22:15:20
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.
LionCodder 2020-05-12 22:15:44
Thank you
Shubhashubha 2020-05-12 22:15:44
Thank you!
lilcritters 2020-05-12 22:15:44
Thank you!!!
wertiol123 2020-05-12 22:15:44
Thank you
penrose43 2020-05-12 22:15:44
thank you!
iscoconut 2020-05-12 22:15:44
thank you!
Krish2526 2020-05-12 22:15:44
thank you
happyhari 2020-05-12 22:15:44
thanks so much!!
puppet9 2020-05-12 22:15:44
thank you!!
MarisaD 2020-05-12 22:15:49
Aww, thank you all!
MarisaD 2020-05-12 22:18:48
Thanks again, everybody - good night!
dewdrop 2020-05-12 22:18:55
thank you!
nia.tatrishvili 2020-05-12 22:18:55
thankssss <3
Pandayue 2020-05-12 22:18:55
Thank you!
greengrassfield 2020-05-12 22:18:55
Thank you!
MaxwellM 2020-05-12 22:18:55
Thank you!!
KevinCarde 2020-05-12 22:19:00
Good night everyone, and thank you!
vapodaca 2020-05-12 22:19:26
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

Copyright © 2023 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.

Invalid username
Sign In