Canada/USA Mathcamp Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveMathcamp admissions committee members discuss the problems from the 2017 Mathcamp Qualifying Quiz.
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: Marisa Debowsky
LauraZed
2017-05-17 19:30:55
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
LauraZed
2017-05-17 19:30:58
Before I introduce our guests, let me briefly explain how our online classroom works.
Before I introduce our guests, let me briefly explain how our online classroom works.
LauraZed
2017-05-17 19:31:07
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
LauraZed
2017-05-17 19:31:30
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
LauraZed
2017-05-17 19:31:42
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
LauraZed
2017-05-17 19:31:53
Many AoPS instructors, assistants, and students are alumni of this outstanding problem, including me! If you're going to Mathcamp 2017, you might actually see me around one weekend – I'm planning to attend the All-Alumni Reunion that will be held during camp this summer.
Many AoPS instructors, assistants, and students are alumni of this outstanding problem, including me! If you're going to Mathcamp 2017, you might actually see me around one weekend – I'm planning to attend the All-Alumni Reunion that will be held during camp this summer.
LauraZed
2017-05-17 19:32:00
Each year, Mathcamp releases a Qualifying Quiz that is the main component of the application process. If you haven't already seen it, you can find the 2017 Qualifying Quiz at http://www.mathcamp.org/prospectiveapplicants/quiz/index.php. In this Math Jam, the following Canada/USA Mathcamp admission committee members will discuss the problems from this year's Qualifying Quiz:
Each year, Mathcamp releases a Qualifying Quiz that is the main component of the application process. If you haven't already seen it, you can find the 2017 Qualifying Quiz at http://www.mathcamp.org/prospectiveapplicants/quiz/index.php. In this Math Jam, the following Canada/USA Mathcamp admission committee members will discuss the problems from this year's Qualifying Quiz:
LauraZed
2017-05-17 19:32:10
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
LauraZed
2017-05-17 19:32:21
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
LauraZed
2017-05-17 19:32:31
Adam Hesterberg (Kamior ? he'll be here later), known as "Pesto" at Mathcamp, is a Mathcamp alum and mentor and MIT math grad student doing computational geometry.
Adam Hesterberg (Kamior ? he'll be here later), known as "Pesto" at Mathcamp, is a Mathcamp alum and mentor and MIT math grad student doing computational geometry.
ItzVineeth
2017-05-17 19:32:44
Hello Ms. Debowsky!
Hello Ms. Debowsky!
ItzVineeth
2017-05-17 19:32:44
Hello Mr. Carde
Hello Mr. Carde
ItzVineeth
2017-05-17 19:32:44
Future hello to Mr. Hesterberg
Future hello to Mr. Hesterberg
LauraZed
2017-05-17 19:32:46
I'll turn the room over to Marisa now!
I'll turn the room over to Marisa now!
MarisaD
2017-05-17 19:32:50
Hi, everybody, and welcome again to the (now annual) Mathcamp Qualifying Quiz Jam!
Hi, everybody, and welcome again to the (now annual) Mathcamp Qualifying Quiz Jam!
MarisaD
2017-05-17 19:32:56
A big thanks as always to @LauraZed, @rrusczyk, and the AoPS team for hosting us.
A big thanks as always to @LauraZed, @rrusczyk, and the AoPS team for hosting us.
MarisaD
2017-05-17 19:33:06
So: Kevin and I are here to talk about the Mathcamp 2017 QQ, and we'll be joined later by our fellow admissions committee member Pesto. To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/2017/qquiz.php
So: Kevin and I are here to talk about the Mathcamp 2017 QQ, and we'll be joined later by our fellow admissions committee member Pesto. To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/2017/qquiz.php
MarisaD
2017-05-17 19:33:20
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
MarisaD
2017-05-17 19:33:29
If you applied this year, I recommend having your solutions open. That way, you can reply more quickly to the questions I ask of the room. And we're expecting you all to pitch in to the solutions!
If you applied this year, I recommend having your solutions open. That way, you can reply more quickly to the questions I ask of the room. And we're expecting you all to pitch in to the solutions!
MarisaD
2017-05-17 19:33:45
Students can use LaTeX in this classroom, just like on the message board. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We know that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We know that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
Students can use LaTeX in this classroom, just like on the message board. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We know that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We know that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
MarisaD
2017-05-17 19:33:55
Also, as @LauraZed pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
Also, as @LauraZed 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).
mochi
2017-05-17 19:34:07
Hello!
Hello!
astroroman
2017-05-17 19:34:07
Hello
Hello
MarisaD
2017-05-17 19:34:11
Hi!
Hi!
MarisaD
2017-05-17 19:34:16
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/ ), or check out the AoPS Jam about the program and the application process from a few months ago: http://www.artofproblemsolving.com/school/mathjams-transcripts?id=431
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/ ), or check out the AoPS Jam about the program and the application process from a few months ago: http://www.artofproblemsolving.com/school/mathjams-transcripts?id=431
MarisaD
2017-05-17 19:34:31
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
MarisaD
2017-05-17 19:34:39
We've got a lot to cover, so let's get started! We've planned this event to last two hours, but of course if we finish sooner, that's great, too...
We've got a lot to cover, so let's get started! We've planned this event to last two hours, but of course if we finish sooner, that's great, too...
MarisaD
2017-05-17 19:35:01
PROBLEM 1: Lotta's Retirement Plan
Lotta is a consulting mathematician who specializes in very large numbers. She runs a business with 100 clients ranked 1 through 100 in order of importance. (The most important client is ranked 1.) Each day, Lotta has time to visit only one of her clients.
A client feels mistreated if Lotta has never visited them, or if Lotta has visited someone less important since the last time she visited them. Every day, Lotta visits the most important client that feels mistreated. On the first day, she visits client 1; on the second day, she visits client 2; on the third day, she goes back to client 1, and so on.
When none of Lotta's clients feel mistreated, she can finally retire.
(a) Prove that Lotta will be able to retire someday.
(b) Over the course of Lotta's career, how many days will the $N^{\text{th}}$ client wake up feeling mistreated?
(c) Describe the set of people that wake up feeling mistreated on the $N^{\text{th}}$ day.
PROBLEM 1: Lotta's Retirement Plan
Lotta is a consulting mathematician who specializes in very large numbers. She runs a business with 100 clients ranked 1 through 100 in order of importance. (The most important client is ranked 1.) Each day, Lotta has time to visit only one of her clients.
A client feels mistreated if Lotta has never visited them, or if Lotta has visited someone less important since the last time she visited them. Every day, Lotta visits the most important client that feels mistreated. On the first day, she visits client 1; on the second day, she visits client 2; on the third day, she goes back to client 1, and so on.
When none of Lotta's clients feel mistreated, she can finally retire.
(a) Prove that Lotta will be able to retire someday.
(b) Over the course of Lotta's career, how many days will the $N^{\text{th}}$ client wake up feeling mistreated?
(c) Describe the set of people that wake up feeling mistreated on the $N^{\text{th}}$ day.
MarisaD
2017-05-17 19:35:28
Ready? Here we got!
Ready? Here we got!
340086
2017-05-17 19:35:44
go*
go*
dawn1729
2017-05-17 19:35:44
Makorn
2017-05-17 19:35:44
Induction is my favorite
Induction is my favorite
MarisaD
2017-05-17 19:35:53
PROBLEM 1 SOLUTION
Before we dive into writing up formal solutions in response to each sub-question, let's start by looking for patterns and understanding what's going on.
PROBLEM 1 SOLUTION
Before we dive into writing up formal solutions in response to each sub-question, let's start by looking for patterns and understanding what's going on.
MarisaD
2017-05-17 19:35:59
Here's the beginning of the pattern: which client Lotta will visit each day?
\[\begin{array}{ccccccccccccccccc}
\rm{Day}
&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\
\hline
\rm{Client}
&1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 &2 & 1 & 3 & 1 & 2 & 1 & 5 \\
\end{array}\]
Here's the beginning of the pattern: which client Lotta will visit each day?
\[\begin{array}{ccccccccccccccccc}
\rm{Day}
&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\
\hline
\rm{Client}
&1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 &2 & 1 & 3 & 1 & 2 & 1 & 5 \\
\end{array}\]
MarisaD
2017-05-17 19:36:13
And for kicks, let's keep going:
\[\begin{array}{ccccccccccccccccc}
\rm{Day}
&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32\\
\hline
\rm{Client}
& 1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 6 \\
\end{array}\]
And for kicks, let's keep going:
\[\begin{array}{ccccccccccccccccc}
\rm{Day}
&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32\\
\hline
\rm{Client}
& 1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 6 \\
\end{array}\]
MarisaD
2017-05-17 19:36:25
A common mistake on this problem was to misunderstand the sequence, e.g. by assuming that Lotta visits one new client, and then all the old ones in a row: $1; 2,1; 3,1,2; 4,1,2,3; 5,1,2,3,4,\ldots$. Why isn't that what happens?
A common mistake on this problem was to misunderstand the sequence, e.g. by assuming that Lotta visits one new client, and then all the old ones in a row: $1; 2,1; 3,1,2; 4,1,2,3; 5,1,2,3,4,\ldots$. Why isn't that what happens?
Makorn
2017-05-17 19:37:07
After $1,2,1,3,1,2$, $1$ will feel mistreated.
After $1,2,1,3,1,2$, $1$ will feel mistreated.
astroroman
2017-05-17 19:37:07
because Lotta always visits the most important mistreated one
because Lotta always visits the most important mistreated one
340086
2017-05-17 19:37:07
after 121312, 1 is mistreated
after 121312, 1 is mistreated
MarisaD
2017-05-17 19:37:17
Right. Every time Lotta visits Client 2, for example, she will make Client 1 unhappy, so rather than moving on to #3, she has to go back to #1 on the next day. That's how we get the alternating pattern we see in the table above.
Right. Every time Lotta visits Client 2, for example, she will make Client 1 unhappy, so rather than moving on to #3, she has to go back to #1 on the next day. That's how we get the alternating pattern we see in the table above.
MarisaD
2017-05-17 19:37:34
So: tell me about this pattern. On what days does Lotta visit Client 1? Client 2? Client 3?
So: tell me about this pattern. On what days does Lotta visit Client 1? Client 2? Client 3?
ProGameXD
2017-05-17 19:38:11
odd days
odd days
Makorn
2017-05-17 19:38:11
She visits Client 1 on odd days
She visits Client 1 on odd days
MathTechFire
2017-05-17 19:38:11
odd - 1
odd - 1
mochi
2017-05-17 19:38:11
Lotta visits Client 1 every 2 days.
Lotta visits Client 1 every 2 days.
mathgirl16
2017-05-17 19:38:20
She visits 1 on every odd day
She visits 1 on every odd day
Thothdragonfly2
2017-05-17 19:38:29
the visit the nth client every n^2 day
the visit the nth client every n^2 day
astroroman
2017-05-17 19:38:29
odd days client 1, every third client 2 client 3 every 4
odd days client 1, every third client 2 client 3 every 4
Makorn
2017-05-17 19:38:29
Client 2 on days $2\mod4$, Client 3 on days $4\mod8$
Client 2 on days $2\mod4$, Client 3 on days $4\mod8$
mochi
2017-05-17 19:38:29
Lotta visits Client 2 every 4 days.
Lotta visits Client 2 every 4 days.
reedmj
2017-05-17 19:38:40
She visits 2 on days $\equiv 2 \pmod{4}$
She visits 2 on days $\equiv 2 \pmod{4}$
futurewriter
2017-05-17 19:38:40
client 1 every other day, client 2 every 4 days, client 3 every 8 days, etc
client 1 every other day, client 2 every 4 days, client 3 every 8 days, etc
340086
2017-05-17 19:38:40
The OEIS sequence if anyone's interested: A001511
The OEIS sequence if anyone's interested: A001511
too_good
2017-05-17 19:38:40
on days that are congruent to 2 mod 4, she visits 2
on days that are congruent to 2 mod 4, she visits 2
MarisaD
2017-05-17 19:38:53
Great, we've got this. It appears that Lotta visits client $1$ every other day starting with day $1$, client $2$ every four days starting with day $2$, client $3$ every eight days starting with day $4$, client $4$ every sixteen days starting with day $8$, and so forth.
Great, we've got this. It appears that Lotta visits client $1$ every other day starting with day $1$, client $2$ every four days starting with day $2$, client $3$ every eight days starting with day $4$, client $4$ every sixteen days starting with day $8$, and so forth.
MarisaD
2017-05-17 19:39:15
And as @Thothdra.. pointed out, we might guess that Lotta visits client $N$ every $2^N$ days starting with day $2^{N-1}$.
And as @Thothdra.. pointed out, we might guess that Lotta visits client $N$ every $2^N$ days starting with day $2^{N-1}$.
mochi
2017-05-17 19:39:19
I see powers of two!
I see powers of two!
Mario2357
2017-05-17 19:39:19
its like binary
its like binary
MarisaD
2017-05-17 19:39:26
Yeah!
Yeah!
MarisaD
2017-05-17 19:39:39
So, let's think about Lotta's retirement for a moment. When none of Lotta's clients feel mistreated, she can finally retire: that is to say, on the day when Clients $1$ - $100$ are happy, and she would theoretically be ready to visit Client $101$ the next day: that's the day she's free to go.
So, let's think about Lotta's retirement for a moment. When none of Lotta's clients feel mistreated, she can finally retire: that is to say, on the day when Clients $1$ - $100$ are happy, and she would theoretically be ready to visit Client $101$ the next day: that's the day she's free to go.
astroroman
2017-05-17 19:39:53
this sequence reminds me of tower of hanoi
this sequence reminds me of tower of hanoi
MarisaD
2017-05-17 19:40:00
Yeah!
Yeah!
MarisaD
2017-05-17 19:40:14
If our guess about this $2^N$ pattern is correct, on what day will she retire?
If our guess about this $2^N$ pattern is correct, on what day will she retire?
futurewriter
2017-05-17 19:40:50
she retires on day 2^100
she retires on day 2^100
astroroman
2017-05-17 19:40:50
on 2^100?
on 2^100?
Makorn
2017-05-17 19:40:50
$2^{100}$
$2^{100}$
MarisaD
2017-05-17 19:41:11
Right: if our guess is correct, then Lotta will retire on day $2^{100}$. (As my colleague Yasha put it: it is therefore possible that Lotta will retire prior to the heat death of the universe.)
Right: if our guess is correct, then Lotta will retire on day $2^{100}$. (As my colleague Yasha put it: it is therefore possible that Lotta will retire prior to the heat death of the universe.)
goodbear
2017-05-17 19:41:13
3.47*(10^27) years after the sun explodes
3.47*(10^27) years after the sun explodes
MarisaD
2017-05-17 19:41:31
Okay, great: Let's justify that pattern!
Okay, great: Let's justify that pattern!
MarisaD
2017-05-17 19:41:48
PROBLEM 1a SOLUTION
PROBLEM 1a SOLUTION
MarisaD
2017-05-17 19:41:53
Let's state clearly what we're trying to prove:
"Lotta visits client $N$ every $2^N$ days starting with day $2^{N-1}$."
Let's state clearly what we're trying to prove:
"Lotta visits client $N$ every $2^N$ days starting with day $2^{N-1}$."
futurewriter
2017-05-17 19:42:20
and we can prove by induction
and we can prove by induction
340086
2017-05-17 19:42:20
Induction time!
Induction time!
astroroman
2017-05-17 19:42:20
induction
induction
lcalvert99
2017-05-17 19:42:20
Induction
Induction
Makorn
2017-05-17 19:42:20
Makorn:Induction is my favorite
Makorn:Induction is my favorite
MarisaD
2017-05-17 19:42:29
This is a great fit for induction. Since this is Problem 1 on the Quiz, I'd like to walk us through an air-tight induction proof, so we'll take this a little slowly. (If you find the pace languishing, don't worry: it'll pick up as the Math Jam goes along!)
This is a great fit for induction. Since this is Problem 1 on the Quiz, I'd like to walk us through an air-tight induction proof, so we'll take this a little slowly. (If you find the pace languishing, don't worry: it'll pick up as the Math Jam goes along!)
MarisaD
2017-05-17 19:42:39
So, what's the base case?
So, what's the base case?
Thothdragonfly2
2017-05-17 19:43:34
client 1 every other day starting on day 1
client 1 every other day starting on day 1
GamerRonay
2017-05-17 19:43:34
For client 1, she is visited every two days starting on the first day.
For client 1, she is visited every two days starting on the first day.
MarisaD
2017-05-17 19:43:51
Right: when $N=1$, we're looking at what happens to Client 1.
Right: when $N=1$, we're looking at what happens to Client 1.
MarisaD
2017-05-17 19:43:55
We need to show that Lotta will visit Client $1$ every other day. Why is this true?
We need to show that Lotta will visit Client $1$ every other day. Why is this true?
astroroman
2017-05-17 19:44:26
because she needs to visit client 1 after any other client
because she needs to visit client 1 after any other client
reedmj
2017-05-17 19:44:26
This happens because whenever Lotta visits a later client she has to visit client 1 the next day since he is most important.
This happens because whenever Lotta visits a later client she has to visit client 1 the next day since he is most important.
Makorn
2017-05-17 19:44:26
Whenever Lotta visits literally anyone else, Client 1 feels mistreated and then Lotta goes back to Client 1
Whenever Lotta visits literally anyone else, Client 1 feels mistreated and then Lotta goes back to Client 1
MarisaD
2017-05-17 19:44:38
Great, yes:
Great, yes:
MarisaD
2017-05-17 19:44:39
If Lotta visited Client $1$ yesterday, then Client $1$ is happy and Lotta will visit someone else today. However, if Lotta did not visit Client $1$ yesterday, she must have visited someone less important, so Client $1$ feels mistreated. Client $1$ is therefore the most important client who feels mistreated, so Lotta will visit them today.
If Lotta visited Client $1$ yesterday, then Client $1$ is happy and Lotta will visit someone else today. However, if Lotta did not visit Client $1$ yesterday, she must have visited someone less important, so Client $1$ feels mistreated. Client $1$ is therefore the most important client who feels mistreated, so Lotta will visit them today.
MarisaD
2017-05-17 19:44:53
...so we have our base case: Lotta visits client $1$ every $2^1=2$ days, starting with day $2^0=1$.
...so we have our base case: Lotta visits client $1$ every $2^1=2$ days, starting with day $2^0=1$.
MarisaD
2017-05-17 19:45:02
Notice that Lotta's odd days are now all booked with Client $1$, so only the even-numbered days are available for other clients.
Notice that Lotta's odd days are now all booked with Client $1$, so only the even-numbered days are available for other clients.
MarisaD
2017-05-17 19:45:07
Can you generalize that pattern? When you add in the visits to Client 2, which days are left?
Can you generalize that pattern? When you add in the visits to Client 2, which days are left?
astroroman
2017-05-17 19:45:26
every fourth day
every fourth day
ChaosImmortal
2017-05-17 19:45:26
Every fourth day
Every fourth day
reedmj
2017-05-17 19:45:26
The days that are multiples of 4
The days that are multiples of 4
EasyAs_Pi
2017-05-17 19:45:26
the multiples of 4 days
the multiples of 4 days
MarisaD
2017-05-17 19:45:37
Right: from the pattern, it looks like Lotta will visit Client 2 on Day 2, and then every four days after that, leaving open only the days that are multiples of 4. (We might think of as $4$ as $2^2$ for our purposes here.)
Right: from the pattern, it looks like Lotta will visit Client 2 on Day 2, and then every four days after that, leaving open only the days that are multiples of 4. (We might think of as $4$ as $2^2$ for our purposes here.)
MarisaD
2017-05-17 19:45:47
In fact, I claim that we can prove a stronger statement than the one we started with:
In fact, I claim that we can prove a stronger statement than the one we started with:
MarisaD
2017-05-17 19:45:52
"Lotta visits client $N$ every $2^N$ days starting with day $2^{N-1}$, and, after scheduling clients $1$ through $N$ in this manner, the only other days available for seeing other clients are multiples of $2^N$."
"Lotta visits client $N$ every $2^N$ days starting with day $2^{N-1}$, and, after scheduling clients $1$ through $N$ in this manner, the only other days available for seeing other clients are multiples of $2^N$."
MarisaD
2017-05-17 19:46:17
We have already proved this claim for $N=1$, so let's move on to the inductive step.
We have already proved this claim for $N=1$, so let's move on to the inductive step.
MarisaD
2017-05-17 19:46:22
Assume that our induction hypothesis holds for $N=k$, and let's use that to show that it is also true for $N=k+1$.
Assume that our induction hypothesis holds for $N=k$, and let's use that to show that it is also true for $N=k+1$.
MarisaD
2017-05-17 19:46:27
When does Lotta visit Client $k+1$?
When does Lotta visit Client $k+1$?
MathPathogen
2017-05-17 19:47:22
on the next open day.
on the next open day.
reedmj
2017-05-17 19:47:22
After clients 1-k are happy
After clients 1-k are happy
astroroman
2017-05-17 19:47:22
on day 2^k
on day 2^k
MathPathogen
2017-05-17 19:47:22
On the next day she isn't visiting another client less than k+1.
On the next day she isn't visiting another client less than k+1.
awesomemaths
2017-05-17 19:47:22
2^k
2^k
MarisaD
2017-05-17 19:47:38
Great. Based on the inductive hypothesis, after scheduling clients $1$ through $k$, the days available for seeing other clients are all the multiples of $2^k$.
Great. Based on the inductive hypothesis, after scheduling clients $1$ through $k$, the days available for seeing other clients are all the multiples of $2^k$.
MarisaD
2017-05-17 19:47:39
We need to determine on which of those days Lotta sees Client $k+1$, and we can use a strategy just like the one we used for Client $1$.
We need to determine on which of those days Lotta sees Client $k+1$, and we can use a strategy just like the one we used for Client $1$.
MarisaD
2017-05-17 19:47:48
If today is a multiple of $2^k$, and on the previous day that was a multiple of $2^k$, Lotta visited Client $k+1$, then Client $k+1$ is happy, because in the intervening time, by the inductive hypothesis, Lotta was only visiting Clients $1$ through $k$, which are more important clients.
If today is a multiple of $2^k$, and on the previous day that was a multiple of $2^k$, Lotta visited Client $k+1$, then Client $k+1$ is happy, because in the intervening time, by the inductive hypothesis, Lotta was only visiting Clients $1$ through $k$, which are more important clients.
MarisaD
2017-05-17 19:48:02
Thus, Lotta will visit someone else today.
Thus, Lotta will visit someone else today.
MarisaD
2017-05-17 19:48:12
However, if on the previous day that was a multiple of $2^k$, Lotta did not visit Client $k+1$, she must have visited someone less important because Clients $1$ through $k$ don't get visited on days that are a multiple of $2^k$.
However, if on the previous day that was a multiple of $2^k$, Lotta did not visit Client $k+1$, she must have visited someone less important because Clients $1$ through $k$ don't get visited on days that are a multiple of $2^k$.
MarisaD
2017-05-17 19:48:38
Thus, Client $k+1$ has been feeling mistreated.
Thus, Client $k+1$ has been feeling mistreated.
MarisaD
2017-05-17 19:48:52
Moreover, Client $k+1$ must be the most important client who feels mistreated by the inductive hypothesis, since we know that Lotta will not visit Clients $1$ through $k$ today.
Moreover, Client $k+1$ must be the most important client who feels mistreated by the inductive hypothesis, since we know that Lotta will not visit Clients $1$ through $k$ today.
MarisaD
2017-05-17 19:49:13
A similar argument holds on day $2^k$ itself. Client $k+1$ has never been visited, and so feels mistreated. We know from the inductive hypothesis that Lotta will not visit Clients $1$ through $k$ today, so she will therefore visit Client $k+1$.
A similar argument holds on day $2^k$ itself. Client $k+1$ has never been visited, and so feels mistreated. We know from the inductive hypothesis that Lotta will not visit Clients $1$ through $k$ today, so she will therefore visit Client $k+1$.
MarisaD
2017-05-17 19:49:21
Thus, Lotta visits Client $k+1$ on every other day that is a multiple of $2^k$. In other words, Lotta visits Client $k+1$ every $2^{k+1}$ days, starting with day $2^k$, as desired.
Thus, Lotta visits Client $k+1$ on every other day that is a multiple of $2^k$. In other words, Lotta visits Client $k+1$ every $2^{k+1}$ days, starting with day $2^k$, as desired.
MarisaD
2017-05-17 19:49:44
(I'm being very very careful here because we're on Problem #1; we'll speed up as we go along.)
(I'm being very very careful here because we're on Problem #1; we'll speed up as we go along.)
MarisaD
2017-05-17 19:49:53
Now let's check the second part of the inductive hypothesis, namely, that after scheduling Clients $1$ through $k+1$, the days available for seeing other clients are the multiples of $2^{k+1}$.
Now let's check the second part of the inductive hypothesis, namely, that after scheduling Clients $1$ through $k+1$, the days available for seeing other clients are the multiples of $2^{k+1}$.
MarisaD
2017-05-17 19:50:09
We know that after scheduling Clients $1$ through $k$, Lotta had the multiples of $2^k$ available. We showed above that Lotta will visit Client $k+1$ on the odd multiples of $2^k$. That leaves the even multiples of $2^k$, that is, the multiples of $2^{k+1}$, available for seeing other clients.
We know that after scheduling Clients $1$ through $k$, Lotta had the multiples of $2^k$ available. We showed above that Lotta will visit Client $k+1$ on the odd multiples of $2^k$. That leaves the even multiples of $2^k$, that is, the multiples of $2^{k+1}$, available for seeing other clients.
MarisaD
2017-05-17 19:50:12
That completes our induction!
That completes our induction!
MarisaD
2017-05-17 19:50:16
And we can conclude that Lotta will retire on Day $2^{100}$.
And we can conclude that Lotta will retire on Day $2^{100}$.
awesomemaths
2017-05-17 19:50:32
induction is really useful
induction is really useful
MarisaD
2017-05-17 19:50:36
Yes!
Yes!
sbudaraj
2017-05-17 19:50:39
part b
part b
MarisaD
2017-05-17 19:50:41
And yes!
And yes!
MarisaD
2017-05-17 19:50:42
PROBLEM 1b SOLUTION
PROBLEM 1b SOLUTION
MarisaD
2017-05-17 19:50:47
Now that we've done all this work understanding the problem, and building ourselves machinery for understanding Lotta's visits, we are well-armed to tackle part b.
Now that we've done all this work understanding the problem, and building ourselves machinery for understanding Lotta's visits, we are well-armed to tackle part b.
MarisaD
2017-05-17 19:50:51
To remind you, the question was: Over the course of Lotta's career, how many days will the $N^{\text{th}}$ client wake up feeling mistreated?
To remind you, the question was: Over the course of Lotta's career, how many days will the $N^{\text{th}}$ client wake up feeling mistreated?
MarisaD
2017-05-17 19:51:00
Just to get a feel for the answer, let's check the first few cases. Between Day $1$ and Day $2^{100}$, how often does Client 1 wake up feeling mistreated?
Just to get a feel for the answer, let's check the first few cases. Between Day $1$ and Day $2^{100}$, how often does Client 1 wake up feeling mistreated?
GamerRonay
2017-05-17 19:51:29
2^99 days
2^99 days
Makorn
2017-05-17 19:51:29
The even days
The even days
ilovemath04
2017-05-17 19:51:29
2^99
2^99
goodbear
2017-05-17 19:51:29
2^99
2^99
richg
2017-05-17 19:51:29
$2^{99}$
$2^{99}$
Littlelachy
2017-05-17 19:51:29
Isn't it just 2^100/2
Isn't it just 2^100/2
MarisaD
2017-05-17 19:51:36
Right: half the time. On Day 1, Client 1 wakes up feeling sad, but Lotta visits that day, so on Day 2, the client will wake up happy. Then later that day, Lotta visits Client 2, irritating our friend Client 1, so on Day 3, Client 1 wakes up feeling sad again. Lather, rinse, repeat.
Right: half the time. On Day 1, Client 1 wakes up feeling sad, but Lotta visits that day, so on Day 2, the client will wake up happy. Then later that day, Lotta visits Client 2, irritating our friend Client 1, so on Day 3, Client 1 wakes up feeling sad again. Lather, rinse, repeat.
MarisaD
2017-05-17 19:51:51
What about Client 2?
What about Client 2?
MarisaD
2017-05-17 19:53:46
Interesting: I'm seeing a lot of incorrect answers, so let's think this out for a minute; I think people might be confused about the "waking up" part.
Interesting: I'm seeing a lot of incorrect answers, so let's think this out for a minute; I think people might be confused about the "waking up" part.
Mario2357
2017-05-17 19:53:53
also $2^99$
also $2^99$
goodbear
2017-05-17 19:53:53
2^99.
2^99.
sorasoratkd7
2017-05-17 19:53:53
2^99 the same
2^99 the same
ChaosImmortal
2017-05-17 19:53:53
2^99
2^99
MarisaD
2017-05-17 19:54:03
That's indeed the correct answer. Unpacking that:
That's indeed the correct answer. Unpacking that:
MarisaD
2017-05-17 19:54:12
Client 2 has more staying power in their moods. Client 2 feels mistreated until their first visit, on Day 2; then Client 2 is happy for a while, until the afternoon of Day 4, when Lotta visits someone less important (Client 3).
Client 2 has more staying power in their moods. Client 2 feels mistreated until their first visit, on Day 2; then Client 2 is happy for a while, until the afternoon of Day 4, when Lotta visits someone less important (Client 3).
MarisaD
2017-05-17 19:54:16
That unhappiness lasts until Client 2 gets a visit again on Day 6, so on the morning of Day 7, they wake up happy.
That unhappiness lasts until Client 2 gets a visit again on Day 6, so on the morning of Day 7, they wake up happy.
MarisaD
2017-05-17 19:54:18
So, Client 2's mornings look like:
Sad, Sad, Happy, Happy, Sad, Sad, Happy, Happy…
So, Client 2's mornings look like:
Sad, Sad, Happy, Happy, Sad, Sad, Happy, Happy…
MarisaD
2017-05-17 19:54:53
(Folks who said $2^{98}$, does it make sense now?)
(Folks who said $2^{98}$, does it make sense now?)
MarisaD
2017-05-17 19:55:12
(Great.)
(Great.)
MarisaD
2017-05-17 19:55:15
Broadly: When does Client $N$ feel mistreated?
Broadly: When does Client $N$ feel mistreated?
skipiano
2017-05-17 19:55:22
client 3 is sad, sad, sad, sad, happy, happy, happy, happy, sad, etc.
client 3 is sad, sad, sad, sad, happy, happy, happy, happy, sad, etc.
ilovemath04
2017-05-17 19:55:27
2^99
2^99
MarisaD
2017-05-17 19:55:45
Yep. First, Client $N$ feels mistreated from the beginning of Lotta's career until day $2^{N-1}$, when Lotta visits them.
Yep. First, Client $N$ feels mistreated from the beginning of Lotta's career until day $2^{N-1}$, when Lotta visits them.
MarisaD
2017-05-17 19:55:58
Then starting with day $2^{N-1}+1$, the client will be happy, and will remain happy for a while, since Lotta will be visiting less important clients until the next multiple of $2^{N-1}$, namely day $2^N$, when Lotta visits someone less important.
Then starting with day $2^{N-1}+1$, the client will be happy, and will remain happy for a while, since Lotta will be visiting less important clients until the next multiple of $2^{N-1}$, namely day $2^N$, when Lotta visits someone less important.
MarisaD
2017-05-17 19:56:07
So: starting with morning $2^N+1$, Client $N$ will feel mistreated, until the next multiple of $2^{N-1}$, namely $3\cdot 2^{N-1}$, when Lotta will visit them.
So: starting with morning $2^N+1$, Client $N$ will feel mistreated, until the next multiple of $2^{N-1}$, namely $3\cdot 2^{N-1}$, when Lotta will visit them.
MarisaD
2017-05-17 19:56:24
We know that this pattern will continue: On even multiples of $2^{N-1}$, Lotta visits someone less important than Client $N$, so Client $N$ will feel mistreated until the next odd multiple of $2^{N-1}$, when Lotta visits client $N$.
We know that this pattern will continue: On even multiples of $2^{N-1}$, Lotta visits someone less important than Client $N$, so Client $N$ will feel mistreated until the next odd multiple of $2^{N-1}$, when Lotta visits client $N$.
MarisaD
2017-05-17 19:56:29
Client $N$ will remain happy until the next even multiple of $2^{N-1}$, because in the intervening time, Lotta will only be visiting more important clients $1$ through $N-1$.
Client $N$ will remain happy until the next even multiple of $2^{N-1}$, because in the intervening time, Lotta will only be visiting more important clients $1$ through $N-1$.
MarisaD
2017-05-17 19:56:45
So in fact, regardless of $N$, Client $N$ will wake up feeling mistreated half of the time. Or, in Lotta's long career, on $2^{99}$ of the mornings.
So in fact, regardless of $N$, Client $N$ will wake up feeling mistreated half of the time. Or, in Lotta's long career, on $2^{99}$ of the mornings.
MarisaD
2017-05-17 19:57:04
We're almost done with #1!
We're almost done with #1!
MarisaD
2017-05-17 19:57:11
PROBLEM 1c SOLUTION
PROBLEM 1c SOLUTION
MarisaD
2017-05-17 19:57:16
This problem asks us to describe the set of people that wake up feeling mistreated on the $N^{\text{th}}$ day.
This problem asks us to describe the set of people that wake up feeling mistreated on the $N^{\text{th}}$ day.
MarisaD
2017-05-17 19:57:22
We've been thinking about this from Lotta's perspective, but let's look at the whole group of clients for a moment. On the first morning, when everybody wakes up, which clients are happy and which feel mistreated?
We've been thinking about this from Lotta's perspective, but let's look at the whole group of clients for a moment. On the first morning, when everybody wakes up, which clients are happy and which feel mistreated?
Littlelachy
2017-05-17 19:57:36
All of them.
All of them.
sbudaraj
2017-05-17 19:57:36
everyone is mistreated
everyone is mistreated
MarisaD
2017-05-17 19:57:43
RIght: before she makes any visits, everyone feels mistreated. That's the miserable state on the first morning. That day, she visits her first client, and when they all wake up on Day 2, the first client is happy and everyone else is still sad.
RIght: before she makes any visits, everyone feels mistreated. That's the miserable state on the first morning. That day, she visits her first client, and when they all wake up on Day 2, the first client is happy and everyone else is still sad.
MarisaD
2017-05-17 19:57:49
Who will be happy on the morning of Day 3?
Who will be happy on the morning of Day 3?
astroroman
2017-05-17 19:58:17
person 2
person 2
Makorn
2017-05-17 19:58:17
Client 2
Client 2
MathPathogen
2017-05-17 19:58:17
only client 2.
only client 2.
richg
2017-05-17 19:58:17
Person 2
Person 2
sbudaraj
2017-05-17 19:58:17
client 2
client 2
MarisaD
2017-05-17 19:58:25
Right: Client 1 will feel mistreated (because less-important 2 was just visited), Client 2 will be happy, and Clients 3 through 100 are still sad.
Right: Client 1 will feel mistreated (because less-important 2 was just visited), Client 2 will be happy, and Clients 3 through 100 are still sad.
MarisaD
2017-05-17 19:58:29
And on the morning of Day 4?
And on the morning of Day 4?
GamerRonay
2017-05-17 19:59:03
clients 1 and 2
clients 1 and 2
Mario2357
2017-05-17 19:59:03
clients 1 and 2
clients 1 and 2
richg
2017-05-17 19:59:03
persons 1 and 2
persons 1 and 2
MarisaD
2017-05-17 19:59:08
Right: Client 1 happy, Client 2 happy, Clients 3 through 100 sad.
Right: Client 1 happy, Client 2 happy, Clients 3 through 100 sad.
MarisaD
2017-05-17 19:59:11
It's taking too long to write this "happy" "sad" business:
It's taking too long to write this "happy" "sad" business:
rafayaashary1
2017-05-17 19:59:17
use the binary representation of N
use the binary representation of N
MathPathogen
2017-05-17 19:59:17
You can read it off the flipped binary representation.
You can read it off the flipped binary representation.
MarisaD
2017-05-17 19:59:25
Yup: a lot of people used binary strings to represent the state of affairs, and that's a much more efficient encoding. Let's use 1 for happy and 0 for feeling mistreated.
Yup: a lot of people used binary strings to represent the state of affairs, and that's a much more efficient encoding. Let's use 1 for happy and 0 for feeling mistreated.
astroroman
2017-05-17 19:59:33
binary use
binary use
GamerRonay
2017-05-17 19:59:33
binary please?
binary please?
MarisaD
2017-05-17 19:59:35
MarisaD
2017-05-17 19:59:38
So the pattern, from the client perspective, that we've described so far:
So the pattern, from the client perspective, that we've described so far:
MarisaD
2017-05-17 19:59:45
\[ \begin{array}{c|ccccccc}
Day \backslash Client& 1 & 2 & 3 & 4 & 5 & 6 & \cdots \\
\hline
1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\
2 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\
3 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\
4 & 1 & 1 & 0 & 0 & 0 & 0 & \cdots \\
5 & 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\
6 & 1 & 0 & 1 & 0 & 0 & 0 & \cdots \\
7 & 0 & 1 & 1 & 0 & 0 & 0 & \cdots \\
8 & 1 & 1 & 1 & 0 & 0 & 0 & \cdots \\
9 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots \\
10 & 1 & 0 & 0 & 1 & 0 & 0 & \cdots \\
11 & 0 & 1 & 0 & 1 & 0 & 0 & \cdots \\
12 & 1 & 1 & 0 & 1 & 0 & 0 & \cdots \\
13 & 0 & 0 & 1 & 1 & 0 & 0 & \cdots \\
14 & 1 & 0 & 1 & 1 & 0 & 0 & \cdots \\
15 & 0 & 1 & 1 & 1 & 0 & 0 & \cdots \\
16 & 1 & 1 & 1 & 1 & 0 & 0 & \cdots \\
17 & 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\
\end{array} \]
\[ \begin{array}{c|ccccccc}
Day \backslash Client& 1 & 2 & 3 & 4 & 5 & 6 & \cdots \\
\hline
1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\
2 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\
3 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\
4 & 1 & 1 & 0 & 0 & 0 & 0 & \cdots \\
5 & 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\
6 & 1 & 0 & 1 & 0 & 0 & 0 & \cdots \\
7 & 0 & 1 & 1 & 0 & 0 & 0 & \cdots \\
8 & 1 & 1 & 1 & 0 & 0 & 0 & \cdots \\
9 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots \\
10 & 1 & 0 & 0 & 1 & 0 & 0 & \cdots \\
11 & 0 & 1 & 0 & 1 & 0 & 0 & \cdots \\
12 & 1 & 1 & 0 & 1 & 0 & 0 & \cdots \\
13 & 0 & 0 & 1 & 1 & 0 & 0 & \cdots \\
14 & 1 & 0 & 1 & 1 & 0 & 0 & \cdots \\
15 & 0 & 1 & 1 & 1 & 0 & 0 & \cdots \\
16 & 1 & 1 & 1 & 1 & 0 & 0 & \cdots \\
17 & 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\
\end{array} \]
MarisaD
2017-05-17 19:59:59
So, our question was: which Clients feel mistreated on Day $N$. What's your guess, from the pattern?
So, our question was: which Clients feel mistreated on Day $N$. What's your guess, from the pattern?
astroroman
2017-05-17 20:00:33
the binary representation of n-1
the binary representation of n-1
goodbear
2017-05-17 20:00:33
binary representation of (Day-1)
binary representation of (Day-1)
MarisaD
2017-05-17 20:00:38
Beautiful. In order to figure out who wakes up feeling mistreated on the $N$th day, we look at the binary representation of the number $N-1$.
Beautiful. In order to figure out who wakes up feeling mistreated on the $N$th day, we look at the binary representation of the number $N-1$.
MarisaD
2017-05-17 20:00:44
Specifically, we claim: Client $k$ feels mistreated that morning if the $k$th digit from the right is a zero.
Specifically, we claim: Client $k$ feels mistreated that morning if the $k$th digit from the right is a zero.
MarisaD
2017-05-17 20:00:59
Let's prove that!
Let's prove that!
MarisaD
2017-05-17 20:01:10
We've already shown that Client $k$'s feeling of mistreatment changes every $2^{k-1}$ days. On the odd multiples of $2^{k-1}$, Lotta visits them, and on the even multiples of $2^{k-1}$, Lotta visits someone inferior and so Client $k$ begins to feel mistreated.
We've already shown that Client $k$'s feeling of mistreatment changes every $2^{k-1}$ days. On the odd multiples of $2^{k-1}$, Lotta visits them, and on the even multiples of $2^{k-1}$, Lotta visits someone inferior and so Client $k$ begins to feel mistreated.
MarisaD
2017-05-17 20:01:20
So: when Client $k$ wakes up on the morning of a day that is one more than a multiple of $2^{k-1}$, they feel differently than on the previous day.
So: when Client $k$ wakes up on the morning of a day that is one more than a multiple of $2^{k-1}$, they feel differently than on the previous day.
MarisaD
2017-05-17 20:01:31
Likewise, the $k$th digit from the right of the binary representation of a number changes at multiples of $2^{k-1}$, so the $k$th digit in the binary representation of $N-1$ will change when $N$ is one more than a multiple of $2^{k-1}$.
Likewise, the $k$th digit from the right of the binary representation of a number changes at multiples of $2^{k-1}$, so the $k$th digit in the binary representation of $N-1$ will change when $N$ is one more than a multiple of $2^{k-1}$.
MarisaD
2017-05-17 20:01:45
Finally, we check that on the morning of day $1$, all clients feel mistreated, and all of the digits of $1-1=0$ are zero.
Finally, we check that on the morning of day $1$, all clients feel mistreated, and all of the digits of $1-1=0$ are zero.
MarisaD
2017-05-17 20:01:54
Since the values of the digits and the corresponding clients' feelings of mistreatement match on day $1$ and change at the same time, they will always match.
Since the values of the digits and the corresponding clients' feelings of mistreatement match on day $1$ and change at the same time, they will always match.
MarisaD
2017-05-17 20:02:08
Whew! Now I think we really understand everything there is to know about Lotta and her strange business.
Whew! Now I think we really understand everything there is to know about Lotta and her strange business.
MarisaD
2017-05-17 20:02:12
Ready? Onto problem 2.
Ready? Onto problem 2.
MarisaD
2017-05-17 20:02:24
PROBLEM 2: Pascal's Oddities
This problem is about some curious relations between the sums of certain entries of Pascal's triangle. I will assume that everybody is familiar with the material in this handout: http://www.mathcamp.org/2017/pascal.pdf
In this problem, we define
\[
\genfrac{\lgroup}{\rgroup}{0pt}{}{{n}}{{k} \bmod {m}} = {n \choose k} + {n \choose k+m} + {n \choose k+2m} + \cdots
\]
where the sum includes every $m^{\text{th}}$ element between $0$ and $n$ inclusive, starting at $k$. For example,
\[
\genfrac{\lgroup}{\rgroup}{0pt}{}{{20}}{{2} \bmod {5}} = {20 \choose 2} + {20 \choose 7} + {20 \choose 12} + {20 \choose 17}.
\]
PROBLEM 2: Pascal's Oddities
This problem is about some curious relations between the sums of certain entries of Pascal's triangle. I will assume that everybody is familiar with the material in this handout: http://www.mathcamp.org/2017/pascal.pdf
In this problem, we define
\[
\genfrac{\lgroup}{\rgroup}{0pt}{}{{n}}{{k} \bmod {m}} = {n \choose k} + {n \choose k+m} + {n \choose k+2m} + \cdots
\]
where the sum includes every $m^{\text{th}}$ element between $0$ and $n$ inclusive, starting at $k$. For example,
\[
\genfrac{\lgroup}{\rgroup}{0pt}{}{{20}}{{2} \bmod {5}} = {20 \choose 2} + {20 \choose 7} + {20 \choose 12} + {20 \choose 17}.
\]
MarisaD
2017-05-17 20:02:42
PROBLEM 2 PREPARATION
PROBLEM 2 PREPARATION
MarisaD
2017-05-17 20:02:46
Let's do just a little exploration first to understand how these sums work.
Let's do just a little exploration first to understand how these sums work.
MarisaD
2017-05-17 20:02:55
Breaking down $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m}$ using Pascal's identity for ${n \choose k}$, let's look for a recurrence.
Breaking down $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m}$ using Pascal's identity for ${n \choose k}$, let's look for a recurrence.
MarisaD
2017-05-17 20:03:01
Starting with our definition,
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = {n \choose k} + {n \choose k+m} + {n \choose k+2m} + \cdots \]
Starting with our definition,
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = {n \choose k} + {n \choose k+m} + {n \choose k+2m} + \cdots \]
MarisaD
2017-05-17 20:03:10
We can rewrite the terms on the right as
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = \left({n-1 \choose k-1} + {n-1 \choose k}\right) + \left({n-1 \choose k+m-1} + {n-1 \choose k+m}\right) + \left({n-1 \choose k+2m-1} + {n-1 \choose k+2m}\right) + \cdots \]
We can rewrite the terms on the right as
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = \left({n-1 \choose k-1} + {n-1 \choose k}\right) + \left({n-1 \choose k+m-1} + {n-1 \choose k+m}\right) + \left({n-1 \choose k+2m-1} + {n-1 \choose k+2m}\right) + \cdots \]
MarisaD
2017-05-17 20:03:14
(There's the Pascal.)
(There's the Pascal.)
MarisaD
2017-05-17 20:03:19
And then regroup terms on the right:
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = \left({n-1 \choose k-1} + {n-1 \choose k+m-1} + {n-1 \choose k+2m-1} + \cdots \right) + \left({n-1 \choose k} + {n-1 \choose k+m} + {n-1 \choose k+2m} + \cdots \right) \]
And then regroup terms on the right:
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = \left({n-1 \choose k-1} + {n-1 \choose k+m-1} + {n-1 \choose k+2m-1} + \cdots \right) + \left({n-1 \choose k} + {n-1 \choose k+m} + {n-1 \choose k+2m} + \cdots \right) \]
MarisaD
2017-05-17 20:03:28
Which now gives us a recurrence, valid for $n\geq 1$:
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{k-1} \bmod {m}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{k} \bmod {m}}. \]
Which now gives us a recurrence, valid for $n\geq 1$:
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod m} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{k-1} \bmod {m}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{k} \bmod {m}}. \]
MarisaD
2017-05-17 20:03:44
Nice that these behave so nicely!
Nice that these behave so nicely!
MarisaD
2017-05-17 20:03:48
What happens when $k=0$?
What happens when $k=0$?
mochi
2017-05-17 20:04:31
$k-1=m-1$
$k-1=m-1$
ChaosImmortal
2017-05-17 20:04:31
then it goes to m-1
then it goes to m-1
MarisaD
2017-05-17 20:04:34
Right: when $k=0$, this identity ``wraps around'' to give instead:
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod m} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{0} \bmod {m}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{m-1} \bmod {m}} \]
Right: when $k=0$, this identity ``wraps around'' to give instead:
\[ \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod m} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{0} \bmod {m}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{m-1} \bmod {m}} \]
MarisaD
2017-05-17 20:04:43
Okay, armed with this nice relation, let's dig into the problem.
Okay, armed with this nice relation, let's dig into the problem.
MarisaD
2017-05-17 20:04:52
PROBLEM 2a STATEMENT
Find, with proof, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2}$ and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2}$.
PROBLEM 2a STATEMENT
Find, with proof, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2}$ and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2}$.
MarisaD
2017-05-17 20:05:06
PROBLEM 2a SOLUTION
To get us started: what's the answer?
PROBLEM 2a SOLUTION
To get us started: what's the answer?
goodbear
2017-05-17 20:05:33
2^(n-1)
2^(n-1)
Makorn
2017-05-17 20:05:33
$2^{n-1}$ each
$2^{n-1}$ each
GamerRonay
2017-05-17 20:05:33
2^n-1 for both
2^n-1 for both
awesomemaths
2017-05-17 20:05:33
2^n-1
2^n-1
MarisaD
2017-05-17 20:05:38
Correct!
Correct!
MarisaD
2017-05-17 20:05:44
We saw lots of different approaches to proving this statement, but here's one approach: first prove that the two quantities are equal, and then prove that that the two quantities sum to $2^n$.
We saw lots of different approaches to proving this statement, but here's one approach: first prove that the two quantities are equal, and then prove that that the two quantities sum to $2^n$.
MarisaD
2017-05-17 20:05:53
Why is it true that $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2} $?
Why is it true that $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2} $?
goodbear
2017-05-17 20:06:15
recurrence
recurrence
MarisaD
2017-05-17 20:06:22
Right: we can use our recurrence!
Right: we can use our recurrence!
MarisaD
2017-05-17 20:06:29
For all $n \ge 1$, the recurrence above gives us the identities
$$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{0} \bmod {2}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{1} \bmod {2}}$$
and
$$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{0} \bmod {2}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{1} \bmod {2}},$$
For all $n \ge 1$, the recurrence above gives us the identities
$$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{0} \bmod {2}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{1} \bmod {2}}$$
and
$$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{0} \bmod {2}} + \genfrac{\lgroup}{\rgroup}{0pt}{}{{n-1}}{{1} \bmod {2}},$$
MarisaD
2017-05-17 20:06:42
so as we hoped: $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2}$.
so as we hoped: $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2}$.
MarisaD
2017-05-17 20:06:46
And why do our two quantities sum to $2^n$?
And why do our two quantities sum to $2^n$?
astroroman
2017-05-17 20:07:11
because rows of pscal's triangle
because rows of pscal's triangle
awesomemaths
2017-05-17 20:07:11
because thats the sum of a row of pascals triangle
because thats the sum of a row of pascals triangle
MarisaD
2017-05-17 20:07:17
Right, Pascal. This is just a sum over all entries of the $n$th row of Pascal's triangle: $$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} + \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2} = 2^n.$$
Right, Pascal. This is just a sum over all entries of the $n$th row of Pascal's triangle: $$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2} + \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2} = 2^n.$$
MarisaD
2017-05-17 20:07:25
Therefore, both $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2}$ and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2}$ must be equal to $2^{n-1}$.
Therefore, both $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 2}$ and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 2}$ must be equal to $2^{n-1}$.
goodbear
2017-05-17 20:07:32
binomial expansion
binomial expansion
ChaosImmortal
2017-05-17 20:07:32
Because the binomial theorem
Because the binomial theorem
MarisaD
2017-05-17 20:07:37
Another great approach.
Another great approach.
MathPathogen
2017-05-17 20:07:40
A.These two expressions are both equal to 2^(n-1). Moving up a row and finding the constituent parts, each item in row n-1 is hit as a constituent of both expressions. As a row sum is equal to 2^x, each of the expressions are equal to 2^(n-1).
A.These two expressions are both equal to 2^(n-1). Moving up a row and finding the constituent parts, each item in row n-1 is hit as a constituent of both expressions. As a row sum is equal to 2^x, each of the expressions are equal to 2^(n-1).
MarisaD
2017-05-17 20:07:45
And a nice concise version!
And a nice concise version!
MarisaD
2017-05-17 20:07:47
Great. Onto the next part.
Great. Onto the next part.
MarisaD
2017-05-17 20:07:58
PROBLEM 2b STATEMENT
Show that $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is always one of the two integers closest to $\frac{2^n}{3}$. For which values of $n$ is it larger than $\frac{2^n}{3}$, and for which values of $n$ is it smaller?
PROBLEM 2b STATEMENT
Show that $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is always one of the two integers closest to $\frac{2^n}{3}$. For which values of $n$ is it larger than $\frac{2^n}{3}$, and for which values of $n$ is it smaller?
MarisaD
2017-05-17 20:08:08
PROBLEM 2b SOLUTION
We saw a lot of solutions here using roots of unity, which is a great way to solve the problem; since we weren't expecting a lot of familiarity with complex numbers as background for the Quiz, I'll walk through a straightforward solution that just uses the material from the background handout.
PROBLEM 2b SOLUTION
We saw a lot of solutions here using roots of unity, which is a great way to solve the problem; since we weren't expecting a lot of familiarity with complex numbers as background for the Quiz, I'll walk through a straightforward solution that just uses the material from the background handout.
MarisaD
2017-05-17 20:08:20
First, what's the answer?
First, what's the answer?
goodbear
2017-05-17 20:09:28
larger for 0, 1, or 5 (mod 6)
larger for 0, 1, or 5 (mod 6)
MarisaD
2017-05-17 20:09:38
Yes! The answer is: $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is $\frac{2^n}{3}$ rounded down when $n \equiv 2, 3, 4 \pmod 6$, and rounded up otherwise.
Yes! The answer is: $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is $\frac{2^n}{3}$ rounded down when $n \equiv 2, 3, 4 \pmod 6$, and rounded up otherwise.
MarisaD
2017-05-17 20:09:49
(We saw many incorrect solutions counting mod 3 instead of mod 6, but we'll see as we work through the solution why the pattern actually repeats in groups of 6.)
(We saw many incorrect solutions counting mod 3 instead of mod 6, but we'll see as we work through the solution why the pattern actually repeats in groups of 6.)
MarisaD
2017-05-17 20:09:56
Lots of students started by observing patterns here, so I'll start with a big table of $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$, and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$ for small $n$:
Lots of students started by observing patterns here, so I'll start with a big table of $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$, and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$ for small $n$:
MarisaD
2017-05-17 20:10:00
(Make your window wide for this!)
(Make your window wide for this!)
MarisaD
2017-05-17 20:10:07
\begin{array}{c|cccccccccc}
& n=0 & n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 & n=9 \\
\hline \\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3} & \boxed{1} & 1 & 1 & \boxed{2} & 5 & 11 & \boxed{22} & 43 & 85 & \boxed{170} \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3} & 0 & 1 & \boxed{2} & 3 & 5 & \boxed{10} & 21 & 43 & \boxed{86} & 171 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3} & 0 & \boxed{0} & 1 & 3 & \boxed{6} & 11 & 21 & \boxed{42} & 85 & 171
\end{array}
\begin{array}{c|cccccccccc}
& n=0 & n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 & n=9 \\
\hline \\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3} & \boxed{1} & 1 & 1 & \boxed{2} & 5 & 11 & \boxed{22} & 43 & 85 & \boxed{170} \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3} & 0 & 1 & \boxed{2} & 3 & 5 & \boxed{10} & 21 & 43 & \boxed{86} & 171 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3} & 0 & \boxed{0} & 1 & 3 & \boxed{6} & 11 & 21 & \boxed{42} & 85 & 171
\end{array}
MarisaD
2017-05-17 20:10:16
What pattern do you see for each $n$?
What pattern do you see for each $n$?
mochi
2017-05-17 20:11:16
This diagonal pattern.
This diagonal pattern.
ChaosImmortal
2017-05-17 20:11:16
repeats every 3
repeats every 3
sbudaraj
2017-05-17 20:11:16
the difference between the numbers in the row below is the same is the numbers in the roq above
the difference between the numbers in the row below is the same is the numbers in the roq above
astroroman
2017-05-17 20:11:35
all columns have one that is either greater or less
all columns have one that is either greater or less
MarisaD
2017-05-17 20:11:45
Great, lots of good info here. To summarize: for each $n$, two out of the values agree, and the third is either one lower or one higher. The exceptional value alternates being lower and higher, and cycles between the rows: it is $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 3}$ for $k=0, 2, 1, 0, 2, 1, \dots$.
Great, lots of good info here. To summarize: for each $n$, two out of the values agree, and the third is either one lower or one higher. The exceptional value alternates being lower and higher, and cycles between the rows: it is $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 3}$ for $k=0, 2, 1, 0, 2, 1, \dots$.
MarisaD
2017-05-17 20:12:01
Of course, it's not enough to observe a pattern: we have to prove it. Let's use some good old induction again.
Of course, it's not enough to observe a pattern: we have to prove it. Let's use some good old induction again.
MarisaD
2017-05-17 20:12:05
The table above takes care of the base case; we just need to verify that it keeps repeating.
The table above takes care of the base case; we just need to verify that it keeps repeating.
MarisaD
2017-05-17 20:12:09
Ready? I'll walk you through the inductive step (a little faster than the induction from Problem 1).
Ready? I'll walk you through the inductive step (a little faster than the induction from Problem 1).
MarisaD
2017-05-17 20:12:14
First, let's start by checking that the exceptional value alternates between high and low.
First, let's start by checking that the exceptional value alternates between high and low.
MarisaD
2017-05-17 20:12:20
Whenever the values of $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$, and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$ are $\{x, x, x+1\}$ in some order (the exceptional value is one higher),
Whenever the values of $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$, and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$ are $\{x, x, x+1\}$ in some order (the exceptional value is one higher),
MarisaD
2017-05-17 20:12:24
the next three values are $\{x+(x+1), x+(x+1), x+x\}$ in some order.
the next three values are $\{x+(x+1), x+(x+1), x+x\}$ in some order.
MarisaD
2017-05-17 20:12:37
(Grab scratch paper if you don't have it already!)
(Grab scratch paper if you don't have it already!)
MarisaD
2017-05-17 20:12:38
You can think of that as $\{y, y, y-1\}$ for $y=2x+1$: namely, the exceptional value is one lower.
You can think of that as $\{y, y, y-1\}$ for $y=2x+1$: namely, the exceptional value is one lower.
MarisaD
2017-05-17 20:12:43
After that, the next three values are $\{y+(y-1), y+(y-1), y+y\}$ in some order, which are $\{z, z, z+1\}$ for $z = 2y-1$: the exceptional value is one higher again.
After that, the next three values are $\{y+(y-1), y+(y-1), y+y\}$ in some order, which are $\{z, z, z+1\}$ for $z = 2y-1$: the exceptional value is one higher again.
MarisaD
2017-05-17 20:12:50
So if this part of the pattern holds for $n$, it holds for $n+1$.
So if this part of the pattern holds for $n$, it holds for $n+1$.
goodbear
2017-05-17 20:12:59
high, high, low
high, high, low
MarisaD
2017-05-17 20:13:04
Yep.
Yep.
MarisaD
2017-05-17 20:13:05
Now, let's investigate what happens when each of 0, 1, and 2 take on the exceptional role.
Now, let's investigate what happens when each of 0, 1, and 2 take on the exceptional role.
MarisaD
2017-05-17 20:13:14
Suppose that for some $n$, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is the exceptional value: one higher or one lower than $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$ and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$, which are equal.
Suppose that for some $n$, $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is the exceptional value: one higher or one lower than $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$ and $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$, which are equal.
MarisaD
2017-05-17 20:13:33
Then in the next step, $$\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{0 \bmod 3} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3} + \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3},$$
Then in the next step, $$\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{0 \bmod 3} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3} + \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3},$$
MarisaD
2017-05-17 20:13:50
which is equal to $$\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{1 \bmod 3} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3} + \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$$
which is equal to $$\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{1 \bmod 3} = \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3} + \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$$
MarisaD
2017-05-17 20:14:06
...so the exceptional value is $\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{2 \bmod 3}$.
...so the exceptional value is $\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{2 \bmod 3}$.
MarisaD
2017-05-17 20:14:19
I'll leave you to check the details of the other two cases:
I'll leave you to check the details of the other two cases:
MarisaD
2017-05-17 20:14:29
you'll find that if $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$ is the exceptional value, the next exceptional value will be $\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{1 \bmod 3}$,
you'll find that if $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 3}$ is the exceptional value, the next exceptional value will be $\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{1 \bmod 3}$,
MarisaD
2017-05-17 20:14:32
and if $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$ is the exceptional value, the next exceptional value will be $\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{0 \bmod 3}$.
and if $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 3}$ is the exceptional value, the next exceptional value will be $\genfrac{\lgroup}{\rgroup}{0pt}{}{{n+1}}{0 \bmod 3}$.
MarisaD
2017-05-17 20:14:44
Putting the pieces together:
Putting the pieces together:
MarisaD
2017-05-17 20:14:50
$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ will be $\frac{2^n}{3}$ rounded down when it is either the exceptional value and one lower than the others (as for $n=3$ or $n=9$) or one of the other values and one lower than the exceptional value (as for $n=2$ or $n=4$ or $n=8$).
$\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ will be $\frac{2^n}{3}$ rounded down when it is either the exceptional value and one lower than the others (as for $n=3$ or $n=9$) or one of the other values and one lower than the exceptional value (as for $n=2$ or $n=4$ or $n=8$).
MarisaD
2017-05-17 20:15:33
Finally: since $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is the exceptional value when $n$ is a multiple of 3, and the exceptional value is lower than the others when $n$ is odd,
Finally: since $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 3}$ is the exceptional value when $n$ is a multiple of 3, and the exceptional value is lower than the others when $n$ is odd,
MarisaD
2017-05-17 20:15:38
we round down when $n$ is either an odd multiple of 3 or an even non-multiple of 3.
we round down when $n$ is either an odd multiple of 3 or an even non-multiple of 3.
MarisaD
2017-05-17 20:15:50
So: the pattern of rounding up, up, down, down, down, up will repeat every six steps.
So: the pattern of rounding up, up, down, down, down, up will repeat every six steps.
MarisaD
2017-05-17 20:15:57
And there's the pattern we were looking to justify; QED!
And there's the pattern we were looking to justify; QED!
MarisaD
2017-05-17 20:16:17
(And now we see why it's a six-unit pattern instead of a three-unit pattern.)
(And now we see why it's a six-unit pattern instead of a three-unit pattern.)
MarisaD
2017-05-17 20:16:31
Questions before we head to part c?
Questions before we head to part c?
leum22
2017-05-17 20:16:49
What does QED mean?
What does QED mean?
MarisaD
2017-05-17 20:17:21
Ooh! It literally stands for "quod erat demonstrandum", which means "that which was to be demonstrated" -
Ooh! It literally stands for "quod erat demonstrandum", which means "that which was to be demonstrated" -
MarisaD
2017-05-17 20:17:32
or in other words, "...and that's what we wanted to prove all along."
or in other words, "...and that's what we wanted to prove all along."
MarisaD
2017-05-17 20:17:58
(Pesto is really the Latin expert among us, but Kevin and I have been known to dabble, and that particular one is a favorite among mathematicians.)
(Pesto is really the Latin expert among us, but Kevin and I have been known to dabble, and that particular one is a favorite among mathematicians.)
MarisaD
2017-05-17 20:18:06
Okay, on to part c:
Okay, on to part c:
MarisaD
2017-05-17 20:18:07
PROBLEM 2c STATEMENT
Let $D_n$ be the difference between the largest and the smallest among the numbers
\[
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 5}, \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 5}, \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 5}, \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{3 \bmod 5}, \text{ and }\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{4 \bmod 5}.
\]
Find $D_n$.
PROBLEM 2c STATEMENT
Let $D_n$ be the difference between the largest and the smallest among the numbers
\[
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 5}, \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 5}, \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 5}, \genfrac{\lgroup}{\rgroup}{0pt}{}{n}{3 \bmod 5}, \text{ and }\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{4 \bmod 5}.
\]
Find $D_n$.
MarisaD
2017-05-17 20:18:20
Almost there! So, what's the answer to part c?
Almost there! So, what's the answer to part c?
MarisaD
2017-05-17 20:18:43
PROBLEM 2c SOLUTION
PROBLEM 2c SOLUTION
sorasoratkd7
2017-05-17 20:18:47
Fibonacci numbers
Fibonacci numbers
MathPathogen
2017-05-17 20:18:47
Fibonaccis!
Fibonaccis!
MarisaD
2017-05-17 20:18:51
Yeah!
Yeah!
MarisaD
2017-05-17 20:19:01
Precisely: $D_n = F_{n+1}$, where $F_n$ is the $n$th Fibonacci number. (Cool, right?)
Precisely: $D_n = F_{n+1}$, where $F_n$ is the $n$th Fibonacci number. (Cool, right?)
mochi
2017-05-17 20:19:06
The n+1th Fibonacci number.
The n+1th Fibonacci number.
MarisaD
2017-05-17 20:19:09
Exactly.
Exactly.
MarisaD
2017-05-17 20:19:17
So, once again, let's start by looking at patterns, and this is where our recurrence relation is going to come in very handy.
So, once again, let's start by looking at patterns, and this is where our recurrence relation is going to come in very handy.
MarisaD
2017-05-17 20:19:24
For $m=5$, our recurrence tells us that the 5-tuple of values $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 5}$, $0 \le k \le 4$, is updated by the rule
\[
(a,b,c,d,e) \qquad \Rightarrow \qquad (e+a, a+b, b+c, c+d, d+e).
\]
For $m=5$, our recurrence tells us that the 5-tuple of values $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 5}$, $0 \le k \le 4$, is updated by the rule
\[
(a,b,c,d,e) \qquad \Rightarrow \qquad (e+a, a+b, b+c, c+d, d+e).
\]
MarisaD
2017-05-17 20:19:44
(I'll give you a moment to check this.)
(I'll give you a moment to check this.)
MarisaD
2017-05-17 20:19:55
Meanwhile, here's our big table of the first few values $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 5}$:
Meanwhile, here's our big table of the first few values $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 5}$:
MarisaD
2017-05-17 20:20:02
\begin{array}{c|cccccccccc}
& n=0 & n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 & n=9 \\
\hline \\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 5} & \boxed{1} & 1 & 1 & 1 & 1 & \boxed{2} & 7 & 22 & 57 & 127 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 5} & 0 & 1 & \boxed{2} & 3 & 4 & 5 & 7 & \boxed{14} & 36 & 93 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 5} & 0 & 0 & 1 & 3 & \boxed{6} & 10 & 15 & 22 & 36 & \boxed{72} \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{3 \bmod 5} & 0 & \boxed{0} & 0 & 1 & 4 & 10 & \boxed{20} & 35 & 57 & 93 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{4 \bmod 5} & 0 & 0 & 0 & \boxed{0} & 1 & 5 & 15 & 35 & \boxed{70} & 127 \\
\\
\end{array}
\begin{array}{c|cccccccccc}
& n=0 & n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 & n=9 \\
\hline \\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{0 \bmod 5} & \boxed{1} & 1 & 1 & 1 & 1 & \boxed{2} & 7 & 22 & 57 & 127 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{1 \bmod 5} & 0 & 1 & \boxed{2} & 3 & 4 & 5 & 7 & \boxed{14} & 36 & 93 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{2 \bmod 5} & 0 & 0 & 1 & 3 & \boxed{6} & 10 & 15 & 22 & 36 & \boxed{72} \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{3 \bmod 5} & 0 & \boxed{0} & 0 & 1 & 4 & 10 & \boxed{20} & 35 & 57 & 93 \\
\\
\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{4 \bmod 5} & 0 & 0 & 0 & \boxed{0} & 1 & 5 & 15 & 35 & \boxed{70} & 127 \\
\\
\end{array}
MarisaD
2017-05-17 20:20:15
What pattern do you see this time?
What pattern do you see this time?
340086
2017-05-17 20:20:45
stranger diagonals
stranger diagonals
mochi
2017-05-17 20:20:45
There's many diagonals that have a slope of -2/3.
There's many diagonals that have a slope of -2/3.
MarisaD
2017-05-17 20:21:26
Ooh, I see lots of interesting observations in the chat; these are great. Let me summarize:
Ooh, I see lots of interesting observations in the chat; these are great. Let me summarize:
MarisaD
2017-05-17 20:21:34
For each $n$, there is an exceptional value alternating between lowest and highest, flanked by a pair of equal values, and opposite another pair of equal values. (E.g., for $n=5$, 2 is flanked by 5 and 5, and opposite 10 and 10.)
For each $n$, there is an exceptional value alternating between lowest and highest, flanked by a pair of equal values, and opposite another pair of equal values. (E.g., for $n=5$, 2 is flanked by 5 and 5, and opposite 10 and 10.)
MarisaD
2017-05-17 20:21:43
And: if the exceptional value is $x$, then the two adjacent values are $x \pm F_{n-1}$, and the two opposite values are $x \pm F_{n+1}$, where $F_n$ is the $n$th Fibonacci number.
And: if the exceptional value is $x$, then the two adjacent values are $x \pm F_{n-1}$, and the two opposite values are $x \pm F_{n+1}$, where $F_n$ is the $n$th Fibonacci number.
MarisaD
2017-05-17 20:21:56
(For the initial portion of the sequence, we're starting with $F_{-1}=1$ and $F_0 = 0$).
(For the initial portion of the sequence, we're starting with $F_{-1}=1$ and $F_0 = 0$).
MarisaD
2017-05-17 20:22:12
One last time: we can prove that this pattern holds by induction on $n$. (Are you surprised?)
One last time: we can prove that this pattern holds by induction on $n$. (Are you surprised?)
MarisaD
2017-05-17 20:22:22
Ready?
Ready?
MarisaD
2017-05-17 20:22:32
Suppose that, for some $n$, the 5-tuple of values of $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 5}$ is a cyclic shift of
\[ (x - F_{n+1}, x - F_{n-1}, x, x - F_{n-1}, x - F_{n+1}).\]
Suppose that, for some $n$, the 5-tuple of values of $\genfrac{\lgroup}{\rgroup}{0pt}{}{n}{k \bmod 5}$ is a cyclic shift of
\[ (x - F_{n+1}, x - F_{n-1}, x, x - F_{n-1}, x - F_{n+1}).\]
MarisaD
2017-05-17 20:22:41
Let's write down what happens when we move from $n$ to $n+1$.
Let's write down what happens when we move from $n$ to $n+1$.
goodbear
2017-05-17 20:22:47
sure
sure
astroroman
2017-05-17 20:22:47
strap in, it's math time!
strap in, it's math time!
MarisaD
2017-05-17 20:22:49
MarisaD
2017-05-17 20:22:53
The next value of the 5-tuple is
\[ (2x - 2F_{n+1}, 2x - F_{n+1} - F_{n-1}, 2x - F_{n-1}, 2x - F_{n-1}, 2x - F_{n+1} - F_{n-1})\]
The next value of the 5-tuple is
\[ (2x - 2F_{n+1}, 2x - F_{n+1} - F_{n-1}, 2x - F_{n-1}, 2x - F_{n-1}, 2x - F_{n+1} - F_{n-1})\]
MarisaD
2017-05-17 20:23:00
which can be written as \[ (y, y + F_n, y + F_{n+2}, y + F_{n+2}, y + F_n) \] where $y = 2x - 2 F_{n+1}$.
which can be written as \[ (y, y + F_n, y + F_{n+2}, y + F_{n+2}, y + F_n) \] where $y = 2x - 2 F_{n+1}$.
MarisaD
2017-05-17 20:23:19
You can also check: the case where the exceptional value $x$ is the lowest value is identical, but with $-$ and $+$ switched.
You can also check: the case where the exceptional value $x$ is the lowest value is identical, but with $-$ and $+$ switched.
MarisaD
2017-05-17 20:23:38
Now we see that the difference between the highest value and the lowest value in the 5-tuple is always $F_{n+1}$ - namely, the absolute difference between the exceptional value and one of the opposite values.
Now we see that the difference between the highest value and the lowest value in the 5-tuple is always $F_{n+1}$ - namely, the absolute difference between the exceptional value and one of the opposite values.
MarisaD
2017-05-17 20:24:21
(I will leave you to do the details of the induction, because it's already 5:24.)
(I will leave you to do the details of the induction, because it's already 5:24.)
MarisaD
2017-05-17 20:24:36
That wraps up Problem 2!
That wraps up Problem 2!
MarisaD
2017-05-17 20:24:48
I did see complete and correct solutions submitted for this problem using fifth roots of unity, but it's very tricky to get that right.
I did see complete and correct solutions submitted for this problem using fifth roots of unity, but it's very tricky to get that right.
MarisaD
2017-05-17 20:25:11
Onwards to Problem 3! That one will be much shorter.
Onwards to Problem 3! That one will be much shorter.
MarisaD
2017-05-17 20:25:30
====== PROBLEM 3 =======
PROBLEM 3: Mentors in the Library
It's the week before Mathcamp, and the $N$ mentors are frantically preparing their classes. The Mathcamp library is open around the clock, and each mentor visits it once in every 24 hour period. They follow a strict schedule: each mentor has a set time when they enter the library and a set time when they leave. (Some mentors work through the night, arriving in the evening and leaving in the morning.) No mentor arrives or departs at the exact same time as another: all $2N$ times are different.
It so happens that:
- There are 47 pairs of distinct mentors that sometimes see each other in the library. (All other pairs of mentors visit the library at non-overlapping times.)
- One day, the mentors decide to estimate the typical number of mentors in the library. That day, each mentor writes down the number of other mentors in the library when they arrive and again when they leave (not counting themselves). The average of these $2N$ numbers is $4$.
- Two of the mentors, Jane and Sam, are so dedicated that at any time of day or night, at least one of them is in the library. (They are the only pair of mentors with this property.)
a) What is $N$, the number of mentors at Mathcamp?
b) Suppose we vary $A=47$ (the number of pairs of mentors that see each other), $B=4$ (the average computed by the mentors), and $C=1$ (the number of mentor pairs like Jane and Sam). Find an equation for $N$ in terms of $A$, $B$, and $C$.
====== PROBLEM 3 =======
PROBLEM 3: Mentors in the Library
It's the week before Mathcamp, and the $N$ mentors are frantically preparing their classes. The Mathcamp library is open around the clock, and each mentor visits it once in every 24 hour period. They follow a strict schedule: each mentor has a set time when they enter the library and a set time when they leave. (Some mentors work through the night, arriving in the evening and leaving in the morning.) No mentor arrives or departs at the exact same time as another: all $2N$ times are different.
It so happens that:
- There are 47 pairs of distinct mentors that sometimes see each other in the library. (All other pairs of mentors visit the library at non-overlapping times.)
- One day, the mentors decide to estimate the typical number of mentors in the library. That day, each mentor writes down the number of other mentors in the library when they arrive and again when they leave (not counting themselves). The average of these $2N$ numbers is $4$.
- Two of the mentors, Jane and Sam, are so dedicated that at any time of day or night, at least one of them is in the library. (They are the only pair of mentors with this property.)
a) What is $N$, the number of mentors at Mathcamp?
b) Suppose we vary $A=47$ (the number of pairs of mentors that see each other), $B=4$ (the average computed by the mentors), and $C=1$ (the number of mentor pairs like Jane and Sam). Find an equation for $N$ in terms of $A$, $B$, and $C$.
MarisaD
2017-05-17 20:25:51
PROBLEM 3 SOLUTION
PROBLEM 3 SOLUTION
MarisaD
2017-05-17 20:25:59
Let's work this problem backwards, starting by trying to understand the general situation (part b). The solution I'll guide us through is a short one; lots of applicants submitted complicated arguments with pretty diagrams (many of which were also correct!).
Let's work this problem backwards, starting by trying to understand the general situation (part b). The solution I'll guide us through is a short one; lots of applicants submitted complicated arguments with pretty diagrams (many of which were also correct!).
MarisaD
2017-05-17 20:26:25
Alright, starting simple. If the average of the $2N$ numbers is $B$, then how many total instances are there of one mentor seeing another upon arriving or leaving?
Alright, starting simple. If the average of the $2N$ numbers is $B$, then how many total instances are there of one mentor seeing another upon arriving or leaving?
MathPathogen
2017-05-17 20:27:24
yeah, b does it trivially.
yeah, b does it trivially.
mathgirl16
2017-05-17 20:27:24
2N*B
2N*B
MarisaD
2017-05-17 20:27:40
Yep, starting with part (b) is the slicker stragy.
Yep, starting with part (b) is the slicker stragy.
MarisaD
2017-05-17 20:27:44
*strategy
*strategy
MarisaD
2017-05-17 20:27:51
And yes, right: the total number of "I spy another mentor" instances is $2NB$.
And yes, right: the total number of "I spy another mentor" instances is $2NB$.
MarisaD
2017-05-17 20:28:00
The contribution of one overlap: For each interval of time that a pair of mentors overlaps, how many instances do they contribute to the "I spy" count?
The contribution of one overlap: For each interval of time that a pair of mentors overlaps, how many instances do they contribute to the "I spy" count?
340086
2017-05-17 20:28:33
2
2
mochi
2017-05-17 20:28:33
2
2
goodbear
2017-05-17 20:28:33
2
2
astroroman
2017-05-17 20:28:33
every time a mentor enters or leaves
every time a mentor enters or leaves
MarisaD
2017-05-17 20:28:40
Yes! They contribute 2 to the total number of instances: 1 when a mentor arrives at the beginning of the interval and counts the other one as being there, and 1 when a mentor leaves at the end of the interval and counts the other.
Yes! They contribute 2 to the total number of instances: 1 when a mentor arrives at the beginning of the interval and counts the other one as being there, and 1 when a mentor leaves at the end of the interval and counts the other.
MarisaD
2017-05-17 20:28:50
The number of overlaps per pair: How many times does each pair overlap?
The number of overlaps per pair: How many times does each pair overlap?
MarisaD
2017-05-17 20:28:59
Since each mentor comes and goes only once per day, each has some interval of time that they're in the library. For each pair of mentors who do see each other, one mentor's interval overlaps the other at its start, end, middle, or both the start and end but not the middle.
Since each mentor comes and goes only once per day, each has some interval of time that they're in the library. For each pair of mentors who do see each other, one mentor's interval overlaps the other at its start, end, middle, or both the start and end but not the middle.
goodbear
2017-05-17 20:29:29
1 or 2
1 or 2
MarisaD
2017-05-17 20:29:31
Exactly.
Exactly.
MarisaD
2017-05-17 20:29:32
How often overlapping pairs count one another: If a pair overlaps at the start or end or middle, there is one overlap, so the pair contributes $2$ to the "I spy" count.
How often overlapping pairs count one another: If a pair overlaps at the start or end or middle, there is one overlap, so the pair contributes $2$ to the "I spy" count.
MarisaD
2017-05-17 20:29:56
If it overlaps at both the start and end, then the two mentors' intervals must cover the entire day, like Jane and Sam did in our example.
If it overlaps at both the start and end, then the two mentors' intervals must cover the entire day, like Jane and Sam did in our example.
MarisaD
2017-05-17 20:30:00
So: that pair is one of the $C$ pairs that always have someone in the library, and the pair contributes $4$ to the number of instances counted.
So: that pair is one of the $C$ pairs that always have someone in the library, and the pair contributes $4$ to the number of instances counted.
340086
2017-05-17 20:30:07
Once, except for Jane and Sam (twice)
Once, except for Jane and Sam (twice)
MathPathogen
2017-05-17 20:30:07
If two overlaps, the contribute 4.
If two overlaps, the contribute 4.
MarisaD
2017-05-17 20:30:15
Exactly.
Exactly.
MarisaD
2017-05-17 20:30:23
So, let's count:
So, let's count:
MarisaD
2017-05-17 20:30:43
Exactly $A-C$ of the pairs contribute $2$ sightings each, and $C$ pairs contribute $4$ each,
Exactly $A-C$ of the pairs contribute $2$ sightings each, and $C$ pairs contribute $4$ each,
MarisaD
2017-05-17 20:30:46
for a total of $2(A-C)+4C$ times that one mentor counts another upon leaving or arriving.
for a total of $2(A-C)+4C$ times that one mentor counts another upon leaving or arriving.
MarisaD
2017-05-17 20:30:51
Now we can put it all together!
Now we can put it all together!
MarisaD
2017-05-17 20:30:56
We have $2(A-C) + 4C = 2NB$,
We have $2(A-C) + 4C = 2NB$,
MarisaD
2017-05-17 20:31:01
so $A+C = NB$,
so $A+C = NB$,
MarisaD
2017-05-17 20:31:05
and $N = \frac{A+C}{B}$.
and $N = \frac{A+C}{B}$.
MarisaD
2017-05-17 20:31:10
This is the answer to part (b)!
This is the answer to part (b)!
MarisaD
2017-05-17 20:31:31
And, as a few people suggested earlier, we can use (b) to finish (a):
And, as a few people suggested earlier, we can use (b) to finish (a):
MarisaD
2017-05-17 20:31:35
For part (a), we substitute $A=47$, $B=4$, and $C=1$ to get $N=12$.
For part (a), we substitute $A=47$, $B=4$, and $C=1$ to get $N=12$.
awesomemaths
2017-05-17 20:31:38
substitute for part a
substitute for part a
MarisaD
2017-05-17 20:31:40
Exactly.
Exactly.
MarisaD
2017-05-17 20:31:44
And as one applicant helpfully noted: "On a side note, Jane and Sam really need to take more time off."
And as one applicant helpfully noted: "On a side note, Jane and Sam really need to take more time off."
MarisaD
2017-05-17 20:32:06
Any questions before we move on?
Any questions before we move on?
awesomemaths
2017-05-17 20:32:30
part a is 12 right???
part a is 12 right???
MarisaD
2017-05-17 20:32:33
Sure is!
Sure is!
MarisaD
2017-05-17 20:32:36
Okay, great: that wraps up Problem 3. Over to Kevin for Problem 4!
Okay, great: that wraps up Problem 3. Over to Kevin for Problem 4!
KevinCarde
2017-05-17 20:33:00
Thanks Marisa, and hi everyone!
Thanks Marisa, and hi everyone!
awesomemaths
2017-05-17 20:33:03
hi kevin
hi kevin
Mario2357
2017-05-17 20:33:11
hey
hey
goodbear
2017-05-17 20:33:11
Hello
Hello
KevinCarde
2017-05-17 20:33:25
I'm going to try to keep things moving briskly, since there's a lot more to do
I'm going to try to keep things moving briskly, since there's a lot more to do
KevinCarde
2017-05-17 20:33:41
As a reminder, though, the transcript will be available afterward, so you can work through everything on your own time!
As a reminder, though, the transcript will be available afterward, so you can work through everything on your own time!
KevinCarde
2017-05-17 20:33:48
Let's dive in to Problem 4 now.
Let's dive in to Problem 4 now.
KevinCarde
2017-05-17 20:34:10
====== PROBLEM 4a STATEMENT =======
PROBLEM 4a: $\mathcal E_k$
Let $k$ be a positive integer, and let $\mathcal E_k$ be the equation
\[
m(m+1) = n(n+k).
\]
A solution to $\mathcal E_k$ is a pair of positive integers $m$ and $n$ that satisfy the equation. For example, solutions to $\mathcal E_{2017}$ include $m=3459, n=2595$ and $m=4484, n=3588$. (There are others as well.)
For what positive integers $k$ does $\mathcal E_k$ have no solutions? Be sure to prove your answer, including showing that $\mathcal E_k$ does have a solution for all other values of $k$.
====== PROBLEM 4a STATEMENT =======
PROBLEM 4a: $\mathcal E_k$
Let $k$ be a positive integer, and let $\mathcal E_k$ be the equation
\[
m(m+1) = n(n+k).
\]
A solution to $\mathcal E_k$ is a pair of positive integers $m$ and $n$ that satisfy the equation. For example, solutions to $\mathcal E_{2017}$ include $m=3459, n=2595$ and $m=4484, n=3588$. (There are others as well.)
For what positive integers $k$ does $\mathcal E_k$ have no solutions? Be sure to prove your answer, including showing that $\mathcal E_k$ does have a solution for all other values of $k$.
KevinCarde
2017-05-17 20:34:39
PROBLEM 4a SOLUTION
PROBLEM 4a SOLUTION
KevinCarde
2017-05-17 20:34:49
First, notice that if $k=1$, then the equation holds whenever $m=n$, and we have infinitely many solutions.
First, notice that if $k=1$, then the equation holds whenever $m=n$, and we have infinitely many solutions.
KevinCarde
2017-05-17 20:35:00
So $k=1$ has solutions.
So $k=1$ has solutions.
KevinCarde
2017-05-17 20:35:11
Now suppose $k > 1$. We don't have any solution if $m \le n$, as $m(m+1) \le n(n+1) < n(n+k)$, so equality cannot hold.
Now suppose $k > 1$. We don't have any solution if $m \le n$, as $m(m+1) \le n(n+1) < n(n+k)$, so equality cannot hold.
KevinCarde
2017-05-17 20:35:25
So to have any chance at a solution, $m > n$, so we can write $m = n+a$ for some integer $a \ge 1$.
So to have any chance at a solution, $m > n$, so we can write $m = n+a$ for some integer $a \ge 1$.
KevinCarde
2017-05-17 20:35:40
Plugging this into the original equation and solving for $n$ yields \[n = \frac{a(a+1)}{k-2a-1}.\]
Plugging this into the original equation and solving for $n$ yields \[n = \frac{a(a+1)}{k-2a-1}.\]
KevinCarde
2017-05-17 20:35:55
This is the equation we'll be focusing on from now on: if we can find positive integer values of $a$ that make $n$ a positive integer, then $m=n+a$ provides a solution to the original equation!
This is the equation we'll be focusing on from now on: if we can find positive integer values of $a$ that make $n$ a positive integer, then $m=n+a$ provides a solution to the original equation!
KevinCarde
2017-05-17 20:36:09
So, quick question: What goes wrong if $k=2$ or $k=3$?
So, quick question: What goes wrong if $k=2$ or $k=3$?
astroroman
2017-05-17 20:36:53
divides by 0z?
divides by 0z?
ChaosImmortal
2017-05-17 20:36:53
Denominator is 0
Denominator is 0
rafayaashary1
2017-05-17 20:36:53
very few possibilities for a
very few possibilities for a
BobaFett101
2017-05-17 20:36:53
denominator is negative or 0
denominator is negative or 0
Mario2357
2017-05-17 20:36:53
n is negative or undefined
n is negative or undefined
KevinCarde
2017-05-17 20:37:07
Right. So there is no hope in this case: $k=2$ and $k=3$ have no solutions.
Right. So there is no hope in this case: $k=2$ and $k=3$ have no solutions.
KevinCarde
2017-05-17 20:37:20
Now assume $k\ge 4$, and let's divide into cases based on whether $k$ is even or odd.
Now assume $k\ge 4$, and let's divide into cases based on whether $k$ is even or odd.
KevinCarde
2017-05-17 20:37:29
CASE 1: $k$ is even.
CASE 1: $k$ is even.
KevinCarde
2017-05-17 20:37:39
Since $k$ is even, $k-2a-1$ will be odd. In fact, by varying $a$, it can be any odd number less than or equal to $k-3$.
Since $k$ is even, $k-2a-1$ will be odd. In fact, by varying $a$, it can be any odd number less than or equal to $k-3$.
KevinCarde
2017-05-17 20:37:55
In particular, by taking $a = (k-2)/2$, we get $k-2a-1 = 1$, yielding the solution $n = a(a+1)$.
In particular, by taking $a = (k-2)/2$, we get $k-2a-1 = 1$, yielding the solution $n = a(a+1)$.
Mario2357
2017-05-17 20:38:03
k=(2a+2)
k=(2a+2)
KevinCarde
2017-05-17 20:38:10
That's an equivalent way to write it!
That's an equivalent way to write it!
KevinCarde
2017-05-17 20:38:23
So, for any even $k$, taking $a = (k-2)/2$, $n = a(a+1)$, and $m = n+a$ is a solution to the original equation.
So, for any even $k$, taking $a = (k-2)/2$, $n = a(a+1)$, and $m = n+a$ is a solution to the original equation.
KevinCarde
2017-05-17 20:38:28
(You can expand out what $n$ and $m$ equal solely in terms of $k$, if you'd like, but it's not necessary.)
(You can expand out what $n$ and $m$ equal solely in terms of $k$, if you'd like, but it's not necessary.)
KevinCarde
2017-05-17 20:38:50
That's the even case.
That's the even case.
KevinCarde
2017-05-17 20:38:51
CASE 2: $k$ is odd.
CASE 2: $k$ is odd.
KevinCarde
2017-05-17 20:39:03
Now $k-2a-1$ is always even, and as before, by varying $a$, it can be any even number less than or equal to $k-3$.
Now $k-2a-1$ is always even, and as before, by varying $a$, it can be any even number less than or equal to $k-3$.
KevinCarde
2017-05-17 20:39:13
What's a good value of $a$ that guarantees $n$ is an integer?
What's a good value of $a$ that guarantees $n$ is an integer?
Mario2357
2017-05-17 20:40:05
top must be even (2 consecutive integers) k=2a+1
top must be even (2 consecutive integers) k=2a+1
KevinCarde
2017-05-17 20:40:43
If we have $k=2a+3$, the denominator becomes $2$
If we have $k=2a+3$, the denominator becomes $2$
Mario2357
2017-05-17 20:40:47
k=2a+3
k=2a+3
KevinCarde
2017-05-17 20:40:52
Good fix
Good fix
KevinCarde
2017-05-17 20:41:06
And since $a(a+1)$ is always even, we get an integer value for $n$.
And since $a(a+1)$ is always even, we get an integer value for $n$.
KevinCarde
2017-05-17 20:41:18
Thus we yet again get a solution to the original equation!
Thus we yet again get a solution to the original equation!
KevinCarde
2017-05-17 20:41:25
So: $k\ge 4$ always has solutions.
So: $k\ge 4$ always has solutions.
KevinCarde
2017-05-17 20:41:32
Putting it all together, we see that only $\mathcal E_2$ and $\mathcal E_3$ have no solutions.
Putting it all together, we see that only $\mathcal E_2$ and $\mathcal E_3$ have no solutions.
KevinCarde
2017-05-17 20:41:51
That wraps up Part (a)!
That wraps up Part (a)!
KevinCarde
2017-05-17 20:42:00
PROBLEM 4b: $\mathcal E_{2017}$
Find, with proof, the solutions to $\mathcal E_{2017}$ with the smallest and the largest possible values of $m$.
PROBLEM 4b: $\mathcal E_{2017}$
Find, with proof, the solutions to $\mathcal E_{2017}$ with the smallest and the largest possible values of $m$.
KevinCarde
2017-05-17 20:42:12
Now we get to get our hands dirty with a specific equation!
Now we get to get our hands dirty with a specific equation!
KevinCarde
2017-05-17 20:42:19
First, from glancing at the original equation $m(m+1) = n(n+k)$, we see that larger values of $n$ correspond to larger values of $m$, so to maximize or minimize $m$, we can instead maximize or minimize $n$. So we'll focus on $n$ instead.
First, from glancing at the original equation $m(m+1) = n(n+k)$, we see that larger values of $n$ correspond to larger values of $m$, so to maximize or minimize $m$, we can instead maximize or minimize $n$. So we'll focus on $n$ instead.
KevinCarde
2017-05-17 20:42:33
Now let's go back to our rearranged form: plugging $k=2017$ into $n = \frac{a(a+1)}{k-2a-1}$ yields \[n = \frac{a(a+1)}{2(1008-a)}.\]
Now let's go back to our rearranged form: plugging $k=2017$ into $n = \frac{a(a+1)}{k-2a-1}$ yields \[n = \frac{a(a+1)}{2(1008-a)}.\]
KevinCarde
2017-05-17 20:42:45
Note that increasing $a$ increases the numerator and decreases the denominator, and hence larger $a$ values yield larger $n$ values.
Note that increasing $a$ increases the numerator and decreases the denominator, and hence larger $a$ values yield larger $n$ values.
KevinCarde
2017-05-17 20:42:55
To summarize where we are so far, largest $a$ implies largest $n$ implies largest $m$ and similarly for smallest.
To summarize where we are so far, largest $a$ implies largest $n$ implies largest $m$ and similarly for smallest.
KevinCarde
2017-05-17 20:43:05
What's the largest value of $a$ we can plug in to get a positive integer value for $n$?
What's the largest value of $a$ we can plug in to get a positive integer value for $n$?
Ninja531
2017-05-17 20:43:49
1007
1007
rafayaashary1
2017-05-17 20:43:49
1007
1007
KevinCarde
2017-05-17 20:43:55
Right. If $a=1008$, we divide by $0$ (very bad!), and if $a > 1008$, then $n$ is negative. So the largest value of $a$ we can pick is $a=1007$, yielding $n = 1007(1007+1)/2 = 507528$.
Right. If $a=1008$, we divide by $0$ (very bad!), and if $a > 1008$, then $n$ is negative. So the largest value of $a$ we can pick is $a=1007$, yielding $n = 1007(1007+1)/2 = 507528$.
KevinCarde
2017-05-17 20:44:11
Recalling that $m = n+a = 507528 + 1007$, we have $m=508535, n=507528$ is the solution to $\mathcal E_{2017}$ with largest $m$.
Recalling that $m = n+a = 507528 + 1007$, we have $m=508535, n=507528$ is the solution to $\mathcal E_{2017}$ with largest $m$.
KevinCarde
2017-05-17 20:44:32
Whew! Big numbers, but nothing like Lotta had to deal with.
Whew! Big numbers, but nothing like Lotta had to deal with
.
KevinCarde
2017-05-17 20:44:41
Now to minimize, we want to pick the smallest positive integer value of $a$ such that $\frac{a(a+1)}{2(1008-a)}$ is an integer.
Now to minimize, we want to pick the smallest positive integer value of $a$ such that $\frac{a(a+1)}{2(1008-a)}$ is an integer.
KevinCarde
2017-05-17 20:44:51
(If, say, we picked $a=1$, then $n=1/1007$ is not an integer, so that doesn't work!)
(If, say, we picked $a=1$, then $n=1/1007$ is not an integer, so that doesn't work!)
KevinCarde
2017-05-17 20:45:07
To be an integer, we need $1008-a$ to divide the numerator. Hence every prime factor $p$ of $1008-a$ must also divide $a$ or $a+1$.
To be an integer, we need $1008-a$ to divide the numerator. Hence every prime factor $p$ of $1008-a$ must also divide $a$ or $a+1$.
KevinCarde
2017-05-17 20:45:19
But if $p$ divides $a+1$, then it divides $(1008-a)+(a+1) = 1009$.
But if $p$ divides $a+1$, then it divides $(1008-a)+(a+1) = 1009$.
KevinCarde
2017-05-17 20:45:24
What are the possibilities for $p$ in this case?
What are the possibilities for $p$ in this case?
mochi
2017-05-17 20:46:14
$1009$ is a prime number
$1009$ is a prime number
KevinCarde
2017-05-17 20:46:33
Aha! This is good news -- there aren't very many factors of primes.
Aha! This is good news -- there aren't very many factors of primes.
mochi
2017-05-17 20:46:39
$1$ or $1009$
$1$ or $1009$
astroroman
2017-05-17 20:46:39
1,1009
1,1009
KevinCarde
2017-05-17 20:46:55
Since $p$ is a prime factor, $p$ must be $1009$, but at the same time, $p$ has to divide $1008-a < 1009$, contradiction.
Since $p$ is a prime factor, $p$ must be $1009$, but at the same time, $p$ has to divide $1008-a < 1009$, contradiction.
KevinCarde
2017-05-17 20:47:13
Since $p$ cannot divide $a+1$, we see that $a+1$ and $1008-a$ are relatively prime, and hence $a$ is divisible by $1008-a$.
Since $p$ cannot divide $a+1$, we see that $a+1$ and $1008-a$ are relatively prime, and hence $a$ is divisible by $1008-a$.
KevinCarde
2017-05-17 20:47:52
By juggling these pieces a little bit, this implies that $1008$ itself is divisible by $1008-a$.
By juggling these pieces a little bit, this implies that $1008$ itself is divisible by $1008-a$.
KevinCarde
2017-05-17 20:48:04
Some of you have already given the prime factors of $1008$ already
Some of you have already given the prime factors of $1008$ already
mathgirl16
2017-05-17 20:48:06
2, 3, 7
2, 3, 7
KevinCarde
2017-05-17 20:48:18
but this severely limits what the possibilities are for $1008-a$
but this severely limits what the possibilities are for $1008-a$
astroroman
2017-05-17 20:48:22
2,3,7
2,3,7
chemdude
2017-05-17 20:48:22
2, 3 , 7?
2, 3 , 7?
KevinCarde
2017-05-17 20:48:32
Since we want $a$ to be as small as possible, we want $1008-a$ to be as large as possible.
Since we want $a$ to be as small as possible, we want $1008-a$ to be as large as possible.
KevinCarde
2017-05-17 20:48:48
So we want $1008-a$ to be the biggest factor of $1008$ possible.
So we want $1008-a$ to be the biggest factor of $1008$ possible.
goodbear
2017-05-17 20:48:57
504
504
MathPathogen
2017-05-17 20:48:57
504.
504.
KevinCarde
2017-05-17 20:49:12
Unfortunately, if we plug this in to our equation for $n$, $1008-a = 504 \implies a = 504 \implies n = 505/2$ is not an integer.
Unfortunately, if we plug this in to our equation for $n$, $1008-a = 504 \implies a = 504 \implies n = 505/2$ is not an integer.
MathPathogen
2017-05-17 20:49:17
But that fails.
But that fails.
KevinCarde
2017-05-17 20:49:26
(The pesky $2$ in the denominator gets us in trouble!)
(The pesky $2$ in the denominator gets us in trouble!)
KevinCarde
2017-05-17 20:49:32
What's the next biggest factor?
What's the next biggest factor?
mochi
2017-05-17 20:50:02
$336$
$336$
awesomemaths
2017-05-17 20:50:02
336
336
mathgirl16
2017-05-17 20:50:02
336
336
MathPathogen
2017-05-17 20:50:02
Next largest is 336.
Next largest is 336.
Ninja531
2017-05-17 20:50:02
1008/3 = 336
1008/3 = 336
KevinCarde
2017-05-17 20:50:09
The next largest proper divisor is $336$, and now everything's fine: $1008-a = 336 \implies a = 672 \implies n = 673 \implies m = 1345$.
The next largest proper divisor is $336$, and now everything's fine: $1008-a = 336 \implies a = 672 \implies n = 673 \implies m = 1345$.
goodbear
2017-05-17 20:50:23
works
works
mathgirl16
2017-05-17 20:50:23
it works!
it works!
KevinCarde
2017-05-17 20:50:27
Hooray!
Hooray
!
awesomemaths
2017-05-17 20:50:32
yay
yay
mochi
2017-05-17 20:50:33
We have our two values!
We have our two values!
KevinCarde
2017-05-17 20:50:43
Indeed! We got the biggest one before, and now we conclude that $m=1345, n=673$ is the solution to $\mathcal E_{2017}$ with the smallest $m$.
Indeed! We got the biggest one before, and now we conclude that $m=1345, n=673$ is the solution to $\mathcal E_{2017}$ with the smallest $m$.
KevinCarde
2017-05-17 20:51:02
Whew! Onward to Part (c).
Whew! Onward to Part (c).
KevinCarde
2017-05-17 20:51:10
PROBLEM 4c: $\mathcal E_k$ and $\mathcal E_{k+1}$
Show that, with a few exceptions, it is impossible for both $\mathcal E_k$ and $\mathcal E_{k+1}$ to have exactly one solution. What are the exceptions?
PROBLEM 4c: $\mathcal E_k$ and $\mathcal E_{k+1}$
Show that, with a few exceptions, it is impossible for both $\mathcal E_k$ and $\mathcal E_{k+1}$ to have exactly one solution. What are the exceptions?
KevinCarde
2017-05-17 20:51:39
PROBLEM 4c SOLUTION
PROBLEM 4c SOLUTION
KevinCarde
2017-05-17 20:51:43
Let's call $k$ groovy if $\mathcal E_k$ has a unique solution.
Let's call $k$ groovy if $\mathcal E_k$ has a unique solution.
awesomemaths
2017-05-17 20:51:49
funny name
funny name
KevinCarde
2017-05-17 20:51:51
(This terminology comes from Mira, another admissions committee member!)
(This terminology comes from Mira, another admissions committee member!)
KevinCarde
2017-05-17 20:52:23
Let's think about the first few values. Are $k=1$, $2$, or $3$ groovy?
Let's think about the first few values. Are $k=1$, $2$, or $3$ groovy?
goodbear
2017-05-17 20:52:56
no
no
mathgirl16
2017-05-17 20:52:56
nope
nope
astroroman
2017-05-17 20:52:56
not 2 or 3
not 2 or 3
MathPathogen
2017-05-17 20:52:56
They either have infinity or 0 solutions
They either have infinity or 0 solutions
KevinCarde
2017-05-17 20:53:09
Exactly -- we saw that $k=1$ has too many solutions, and $k=2$ and $3$ have none. Not cool!
Exactly -- we saw that $k=1$ has too many solutions, and $k=2$ and $3$ have none. Not cool!
KevinCarde
2017-05-17 20:53:11
Err, not groovy!
Err, not groovy!
KevinCarde
2017-05-17 20:53:23
What about the next values of $k$? Let's see what $n = \frac{a(a+1)}{k-2a-1}$ looks like for some values of $k$.
What about the next values of $k$? Let's see what $n = \frac{a(a+1)}{k-2a-1}$ looks like for some values of $k$.
KevinCarde
2017-05-17 20:53:36
$k=4$: We have $n = \frac{a(a+1)}{3-2a}$. In order for the denominator to be positive, $a$ must be $1$, so there is only the one solution $n=2$ corresponding to $a=1$: $k=4$ is groovy!
$k=4$: We have $n = \frac{a(a+1)}{3-2a}$. In order for the denominator to be positive, $a$ must be $1$, so there is only the one solution $n=2$ corresponding to $a=1$: $k=4$ is groovy!
KevinCarde
2017-05-17 20:54:06
What about $k=5$, $6$, or $7$? (Feel free to think about just one at a time!)
What about $k=5$, $6$, or $7$? (Feel free to think about just one at a time!)
mochi
2017-05-17 20:54:46
k=5 is groovy!
k=5 is groovy!
mathgirl16
2017-05-17 20:54:53
5
5
mathgirl16
2017-05-17 20:55:03
6
6
MathPathogen
2017-05-17 20:55:13
7 is too
7 is too
KevinCarde
2017-05-17 20:55:28
All true! We can do something similar to $k=4$ to conclude there's only one possibility.
All true! We can do something similar to $k=4$ to conclude there's only one possibility.
MathPathogen
2017-05-17 20:55:31
8 is not.
8 is not.
KevinCarde
2017-05-17 20:55:37
Aha! Let's start studying these systematically.
Aha! Let's start studying these systematically.
KevinCarde
2017-05-17 20:55:42
Lemma 1: Let $k \ge 4$ be an even integer. If $k$ is groovy, then $k-1$ and $k+1$ are both prime.
Lemma 1: Let $k \ge 4$ be an even integer. If $k$ is groovy, then $k-1$ and $k+1$ are both prime.
KevinCarde
2017-05-17 20:56:04
(These are called twin primes, and this lemma proves that they're a pretty groovy topic!)
(These are called twin primes, and this lemma proves that they're a pretty groovy topic!)
KevinCarde
2017-05-17 20:56:19
Proof: Write $k=2r$, and let $p$ be a proper factor of $2r-1$ or $2r+1$. Note that these are both odd, so $p$ must be an odd prime.
Proof: Write $k=2r$, and let $p$ be a proper factor of $2r-1$ or $2r+1$. Note that these are both odd, so $p$ must be an odd prime.
KevinCarde
2017-05-17 20:56:34
We claim that $a = (2r-1-p)/2$ yields a solution (which is an integer since $p$ is odd). Let's plug it in:
\[n = \frac{((2r-p-1)/2)((2r-p-1)/2 + 1)}{2r-2((2r-p-1)/2)-1} = \frac{(2r-1-p)(2r+1-p)}{4p}\]
We claim that $a = (2r-1-p)/2$ yields a solution (which is an integer since $p$ is odd). Let's plug it in:
\[n = \frac{((2r-p-1)/2)((2r-p-1)/2 + 1)}{2r-2((2r-p-1)/2)-1} = \frac{(2r-1-p)(2r+1-p)}{4p}\]
KevinCarde
2017-05-17 20:56:48
Recall that $p$ divides either $2r-1$ or $2r+1$, and both $2r-1-p$ and $2r+1-p$ are even. Therefore, this is an integer!
Recall that $p$ divides either $2r-1$ or $2r+1$, and both $2r-1-p$ and $2r+1-p$ are even. Therefore, this is an integer!
KevinCarde
2017-05-17 20:57:01
Thus every proper factor of $2r-1$ or $2r+1$ yields a solution to $\mathcal E_{2r}$.
Thus every proper factor of $2r-1$ or $2r+1$ yields a solution to $\mathcal E_{2r}$.
pyaops
2017-05-17 20:57:14
that copy and paste tho
that copy and paste tho
KevinCarde
2017-05-17 20:57:20
Gotta forgive me for not writing latex on the fly.
Gotta forgive me for not writing latex on the fly
.
KevinCarde
2017-05-17 20:57:37
But since $k=2r$ is groovy, we can't have any more solutions, and therefore we have no other proper factors: $2r-1$ and $2r+1$ must both be prime!
But since $k=2r$ is groovy, we can't have any more solutions, and therefore we have no other proper factors: $2r-1$ and $2r+1$ must both be prime!
KevinCarde
2017-05-17 20:58:00
That does it for Lemma 1 (with a slight digression!).
That does it for Lemma 1 (with a slight digression!).
mochi
2017-05-17 20:58:07
Word of the day (night): groovy!
Word of the day (night): groovy!
astroroman
2017-05-17 20:58:07
twin primes = groovy!
twin primes = groovy!
KevinCarde
2017-05-17 20:58:11
True on both counts!
True on both counts!
KevinCarde
2017-05-17 20:58:23
Let's now think about odd numbers.
Let's now think about odd numbers.
KevinCarde
2017-05-17 20:58:27
Lemma 2: Let $k \ge 9$ be an odd integer. If $k$ is groovy, then $k$ is divisible by $3$.
Lemma 2: Let $k \ge 9$ be an odd integer. If $k$ is groovy, then $k$ is divisible by $3$.
KevinCarde
2017-05-17 20:58:43
Proof: Write $k=2r+1$, with $r\ge 4$. Let $p$ be an odd proper factor of $r$ or $r+1$. We claim $a = r-p$ is a solution. Let's plug it in:
\[n = \frac{(r-p)(r-p+1)}{2r+1-2(r-p)-1} = \frac{(r-p)(r+1-p)}{2p}\]
Proof: Write $k=2r+1$, with $r\ge 4$. Let $p$ be an odd proper factor of $r$ or $r+1$. We claim $a = r-p$ is a solution. Let's plug it in:
\[n = \frac{(r-p)(r-p+1)}{2r+1-2(r-p)-1} = \frac{(r-p)(r+1-p)}{2p}\]
KevinCarde
2017-05-17 20:59:02
By definition, $p$ divides either $r-p$ or $r+1-p$, and since one of those numbers is even, $2$ divides the numerator as well.
By definition, $p$ divides either $r-p$ or $r+1-p$, and since one of those numbers is even, $2$ divides the numerator as well.
KevinCarde
2017-05-17 20:59:10
(And since $p$ was picked to be odd, we're not dividing by too many powers of $2$!)
(And since $p$ was picked to be odd, we're not dividing by too many powers of $2$!)
KevinCarde
2017-05-17 20:59:21
Therefore, every odd proper factor of $r$ or $r+1$ gives us a solution. Since we always have the possibility of $p=1$, we must have no other odd proper factors.
Therefore, every odd proper factor of $r$ or $r+1$ gives us a solution. Since we always have the possibility of $p=1$, we must have no other odd proper factors.
KevinCarde
2017-05-17 20:59:33
In particular, we can't have $r$ or $r+1$ divisible by $3$, and hence $r\equiv 1 \pmod3$ and $r+1\equiv 2 \pmod3$.
In particular, we can't have $r$ or $r+1$ divisible by $3$, and hence $r\equiv 1 \pmod3$ and $r+1\equiv 2 \pmod3$.
KevinCarde
2017-05-17 20:59:54
We conclude that $k = 2r+1 \equiv 0 \pmod3$, as desired.
We conclude that $k = 2r+1 \equiv 0 \pmod3$, as desired.
Buddy03
2017-05-17 21:00:00
It's the same equation but with r instead of 2r and 2p instead of 4p!
It's the same equation but with r instead of 2r and 2p instead of 4p!
KevinCarde
2017-05-17 21:00:17
Yeah! The cases are very similar: we just have to be careful of $+1$s and $-1$s and dividing by $2$ in the even and odd cases.
Yeah! The cases are very similar: we just have to be careful of $+1$s and $-1$s and dividing by $2$ in the even and odd cases.
KevinCarde
2017-05-17 21:00:29
OK, we're ready to wrap this up.
OK, we're ready to wrap this up.
KevinCarde
2017-05-17 21:00:35
We claim that the only consecutive pairs of groovy integers are $\{4, 5\}$, $\{5, 6\}$, and $\{6, 7\}$.
We claim that the only consecutive pairs of groovy integers are $\{4, 5\}$, $\{5, 6\}$, and $\{6, 7\}$.
KevinCarde
2017-05-17 21:00:54
First: Some of you already said it before, but our Lemmas now tell us about whether $k=8$ is groovy.
First: Some of you already said it before, but our Lemmas now tell us about whether $k=8$ is groovy.
KevinCarde
2017-05-17 21:01:06
Is $k=8$ groovy, and which lemma tells us that?
Is $k=8$ groovy, and which lemma tells us that?
MathPathogen
2017-05-17 21:01:33
7 and 9 are not twin primes.
7 and 9 are not twin primes.
astroroman
2017-05-17 21:01:33
lemma 1 says not groovy because 9
lemma 1 says not groovy because 9
Buddy03
2017-05-17 21:01:38
No it is not
No it is not
mochi
2017-05-17 21:01:38
$k=8$ is not groovy, and Lemma 1 tells us that.
$k=8$ is not groovy, and Lemma 1 tells us that.
KevinCarde
2017-05-17 21:01:43
Excellent.
Excellent.
KevinCarde
2017-05-17 21:01:49
Now suppose $k > 8$ and both $k$ and $k+1$ are groovy.
Now suppose $k > 8$ and both $k$ and $k+1$ are groovy.
KevinCarde
2017-05-17 21:02:04
One of $k$ and $k+1$ is odd.
One of $k$ and $k+1$ is odd.
KevinCarde
2017-05-17 21:02:09
What does Lemma 1 say about the odd one?
What does Lemma 1 say about the odd one?
mochi
2017-05-17 21:02:39
Do you mean Lemma 2?
Do you mean Lemma 2?
KevinCarde
2017-05-17 21:02:51
Ah, the key here is that both Lemmas tell us about the odd number!
Ah, the key here is that both Lemmas tell us about the odd number!
KevinCarde
2017-05-17 21:03:05
Lemma 2 tells us the odd one must be divisible by $3$.
Lemma 2 tells us the odd one must be divisible by $3$.
Buddy03
2017-05-17 21:03:14
K=2r+1=0 mod3
K=2r+1=0 mod3
KevinCarde
2017-05-17 21:03:22
And then Lemma 1
And then Lemma 1
MathPathogen
2017-05-17 21:03:24
It must be part of a twin primes, but it cannot be.
It must be part of a twin primes, but it cannot be.
KevinCarde
2017-05-17 21:03:36
So we have a number $> 8$ which is a prime divisible by $3$. Contradiction!
So we have a number $> 8$ which is a prime divisible by $3$. Contradiction!
KevinCarde
2017-05-17 21:03:44
Therefore, there can be no other pairs of consecutive groovy numbers!
Therefore, there can be no other pairs of consecutive groovy numbers!
Buddy03
2017-05-17 21:03:57
Groovy!
Groovy!
KevinCarde
2017-05-17 21:04:20
That does it for Problem 4, and now that "groovy" isn't a technical term, we can use it whenever we want to say something's cool.
That does it for Problem 4, and now that "groovy" isn't a technical term, we can use it whenever we want to say something's cool
.
KevinCarde
2017-05-17 21:04:25
Onwards to Problem 5!
Onwards to Problem 5!
KevinCarde
2017-05-17 21:04:44
PROBLEM 5: Wizards in a Tower
Wizards live in towers that have infinitely many floors, numbered $1, 2, 3, \dots$. The floors are not connected by staircases or any other mundane means. Instead, for every positive integer $N$, there is a red magic portal connecting floor $N$ to floor $N+10$, and a blue magic portal connecting floor $N$ to floor $3N+1$. The portals go both ways; for example, starting at floor $26$, you could descend to floor $16$ by a red portal, descend to floor $5$ by a blue portal, and ascend to floor $15$ by a red portal.
Of course, an infinitely tall tower would have enough room for multiple wizards. But wizards refuse to share: two wizards refuse to both live in the tower if it's possible to get from one wizard's floor to the other wizard's floor using the magic portals.
PROBLEM 5: Wizards in a Tower
Wizards live in towers that have infinitely many floors, numbered $1, 2, 3, \dots$. The floors are not connected by staircases or any other mundane means. Instead, for every positive integer $N$, there is a red magic portal connecting floor $N$ to floor $N+10$, and a blue magic portal connecting floor $N$ to floor $3N+1$. The portals go both ways; for example, starting at floor $26$, you could descend to floor $16$ by a red portal, descend to floor $5$ by a blue portal, and ascend to floor $15$ by a red portal.
Of course, an infinitely tall tower would have enough room for multiple wizards. But wizards refuse to share: two wizards refuse to both live in the tower if it's possible to get from one wizard's floor to the other wizard's floor using the magic portals.
KevinCarde
2017-05-17 21:04:55
PROBLEM 5a: $N+10$ and $3N+1$
How many wizards could live together in such a tower?
PROBLEM 5a: $N+10$ and $3N+1$
How many wizards could live together in such a tower?
KevinCarde
2017-05-17 21:05:17
PROBLEM 5a SOLUTION
PROBLEM 5a SOLUTION
mochi
2017-05-17 21:05:22
$3$!
$3$!
KevinCarde
2017-05-17 21:05:25
(excitement, not factorial)
(excitement, not factorial)
goodbear
2017-05-17 21:05:29
3
3
astroroman
2017-05-17 21:05:29
3
3
mochi
2017-05-17 21:05:39
3 wizards only! These are some very picky wizards!
3 wizards only! These are some very picky wizards!
astroroman
2017-05-17 21:05:39
but only 3
but only 3
Buddy03
2017-05-17 21:05:39
3
3
acegikmoqsuwy2000
2017-05-17 21:05:39
$\lfloor \pi\rfloor$
$\lfloor \pi\rfloor$
KevinCarde
2017-05-17 21:05:43
All true.
All true
.
KevinCarde
2017-05-17 21:05:57
Note that we can travel between two floors $a$ and $b$ using red portals if and only if $a\equiv b \pmod{10}$. So at most, we have $10$ wizards, one per residue class mod $10$. Let's see how that pares down to $3$.
Note that we can travel between two floors $a$ and $b$ using red portals if and only if $a\equiv b \pmod{10}$. So at most, we have $10$ wizards, one per residue class mod $10$. Let's see how that pares down to $3$.
KevinCarde
2017-05-17 21:06:12
How does the $3N+1$ operation affect residues mod $10$?
How does the $3N+1$ operation affect residues mod $10$?
340086
2017-05-17 21:06:36
some things can connect to others
some things can connect to others
KevinCarde
2017-05-17 21:06:53
Right. For example, starting at $1 \pmod{10}$, we next move to $3\cdot 1+1 \equiv 4 \pmod{10}$, then $3\cdot 4 + 1 \equiv 3 \pmod{10}$, then $3\cdot 3 + 1 \equiv 0 \pmod{10}$, then finally back to $3\cdot 0 + 1 \equiv 1 \pmod{10}$.
Right. For example, starting at $1 \pmod{10}$, we next move to $3\cdot 1+1 \equiv 4 \pmod{10}$, then $3\cdot 4 + 1 \equiv 3 \pmod{10}$, then $3\cdot 3 + 1 \equiv 0 \pmod{10}$, then finally back to $3\cdot 0 + 1 \equiv 1 \pmod{10}$.
340086
2017-05-17 21:07:00
e.g. 2 mod 10 goes to 7 mod 10
e.g. 2 mod 10 goes to 7 mod 10
KevinCarde
2017-05-17 21:07:07
Where does $7$ go next?
Where does $7$ go next?
Buddy03
2017-05-17 21:07:14
2
2
hilarious
2017-05-17 21:07:18
back to 2
back to 2
Mario2357
2017-05-17 21:07:20
but 7 goes back to 2 and ur done with the loop
but 7 goes back to 2 and ur done with the loop
astroroman
2017-05-17 21:07:20
2
2
KevinCarde
2017-05-17 21:07:26
Right. We're getting cycles!
Right. We're getting cycles!
Mario2357
2017-05-17 21:07:28
1,4,3,0
2,7
5,6,9,8
1,4,3,0
2,7
5,6,9,8
MathPathogen
2017-05-17 21:07:32
congruence class 1-->4-->3-->0-->1, class 2-->7-->2, and class 5-->6-->9-->8-->5.
congruence class 1-->4-->3-->0-->1, class 2-->7-->2, and class 5-->6-->9-->8-->5.
KevinCarde
2017-05-17 21:07:41
We get these three cycles, and no two wizards can share a cycle.
We get these three cycles, and no two wizards can share a cycle.
KevinCarde
2017-05-17 21:07:51
So we can only have one wizard per cycle: 3 wizards total!
So we can only have one wizard per cycle: 3 wizards total!
KevinCarde
2017-05-17 21:08:10
Let's move on to 5b and hopefully find some less picky wizards.
Let's move on to 5b and hopefully find some less picky wizards.
KevinCarde
2017-05-17 21:08:19
PROBLEM 5b: $2N+1$ and $8N+1$
If the red portals instead connected floor $N$ to floor $2N + 1$, and the blue portals instead connected floor $N$ to floor $8N + 1$, how many wizards could live in the tower?
PROBLEM 5b: $2N+1$ and $8N+1$
If the red portals instead connected floor $N$ to floor $2N + 1$, and the blue portals instead connected floor $N$ to floor $8N + 1$, how many wizards could live in the tower?
MathPathogen
2017-05-17 21:08:32
infinitely less icky.
infinitely less icky.
MathPathogen
2017-05-17 21:08:32
*picky
*picky
KevinCarde
2017-05-17 21:08:40
Maybe if they're less icky, that's why they're willing to live together.
Maybe if they're less icky, that's why they're willing to live together
.
KevinCarde
2017-05-17 21:08:51
The most popular strategy we saw is to consider floor numbers in binary: then $2N+1$ appends a $1$ to the binary representation, and $8N+1$ appends $001$ to the binary representation. This can lead pretty quickly to a proof, as long as you're careful about details -- give it some thought on your own time if you haven't already!
The most popular strategy we saw is to consider floor numbers in binary: then $2N+1$ appends a $1$ to the binary representation, and $8N+1$ appends $001$ to the binary representation. This can lead pretty quickly to a proof, as long as you're careful about details -- give it some thought on your own time if you haven't already!
KevinCarde
2017-05-17 21:09:01
Here, though, I want to present another strategy that we saw much less in Quiz submissions!
Here, though, I want to present another strategy that we saw much less in Quiz submissions!
KevinCarde
2017-05-17 21:09:13
Let $a$ and $b$ be two distinct floors which are connected by portals. Call a path between them reduced if we never visit the same floor more than once.
Let $a$ and $b$ be two distinct floors which are connected by portals. Call a path between them reduced if we never visit the same floor more than once.
KevinCarde
2017-05-17 21:09:24
Note that any path can be turned into a reduced path just by removing the portion between two identical floors. So to determine whether two floors are connected, we can focus on whether there's a reduced path between them.
Note that any path can be turned into a reduced path just by removing the portion between two identical floors. So to determine whether two floors are connected, we can focus on whether there's a reduced path between them.
KevinCarde
2017-05-17 21:09:36
Suppose we have a reduced path between $a$ and $b$. Then there is a unique highest floor along this path; call it $c$.
Suppose we have a reduced path between $a$ and $b$. Then there is a unique highest floor along this path; call it $c$.
KevinCarde
2017-05-17 21:09:50
Note that we must go up to reach $c$ (or else it wouldn't be highest!), so $c$ is an odd number.
Note that we must go up to reach $c$ (or else it wouldn't be highest!), so $c$ is an odd number.
KevinCarde
2017-05-17 21:10:00
There are two possibilities:
There are two possibilities:
KevinCarde
2017-05-17 21:10:06
CASE 1: $c$ is one of the endpoints $a$ or $b$. Since $c$ is odd, that means one of the endpoints is odd.
CASE 1: $c$ is one of the endpoints $a$ or $b$. Since $c$ is odd, that means one of the endpoints is odd.
KevinCarde
2017-05-17 21:10:15
Or...
Or...
Buddy03
2017-05-17 21:10:23
Because 8n+1 mod 2=1
Because 8n+1 mod 2=1
KevinCarde
2017-05-17 21:10:35
Exactly -- both $8n+1$ and $2n+1$ are $1$ mod $2$ and hence odd.
Exactly -- both $8n+1$ and $2n+1$ are $1$ mod $2$ and hence odd.
KevinCarde
2017-05-17 21:10:38
CASE 2: $c$ appears in the interior of the path. Then we must go up one kind of portal to reach $c$ and down the other to leave $c$. Hence $c$ must be at the top of an $8N+1$ portal, so we can write $c = 8n+1$ for some $n$.
CASE 2: $c$ appears in the interior of the path. Then we must go up one kind of portal to reach $c$ and down the other to leave $c$. Hence $c$ must be at the top of an $8N+1$ portal, so we can write $c = 8n+1$ for some $n$.
KevinCarde
2017-05-17 21:10:47
The floors adjacent to $c$ are thus $n$ (connected to $c$ via the $8N+1$ portal) and $4n$ (connected to $c$ via the $2N+1$ portal).
The floors adjacent to $c$ are thus $n$ (connected to $c$ via the $8N+1$ portal) and $4n$ (connected to $c$ via the $2N+1$ portal).
KevinCarde
2017-05-17 21:10:59
What can we do from floor $4n$?
What can we do from floor $4n$?
KevinCarde
2017-05-17 21:11:05
Where can we go next?
Where can we go next?
MathPathogen
2017-05-17 21:11:24
why not up 2n+1 and down 8n+1?
why not up 2n+1 and down 8n+1?
KevinCarde
2017-05-17 21:11:39
Even if our path takes us down the $8N+1$ portal, $c$ is still sitting at the top and will have the form $8n+1$ -- good question!
Even if our path takes us down the $8N+1$ portal, $c$ is still sitting at the top and will have the form $8n+1$ -- good question!
340086
2017-05-17 21:11:48
nowhere
nowhere
340086
2017-05-17 21:11:48
can't go up b/c contradiction of c
can't go up b/c contradiction of c
KevinCarde
2017-05-17 21:11:56
Interesting -- let's flesh this out a bit.
Interesting -- let's flesh this out a bit.
KevinCarde
2017-05-17 21:12:06
From $4n$, we can't go down, because $4n$ isn't odd.
From $4n$, we can't go down, because $4n$ isn't odd.
KevinCarde
2017-05-17 21:12:13
We can go up via $2N+1$, but then we reach $c = 8n+1$ again.
We can go up via $2N+1$, but then we reach $c = 8n+1$ again.
KevinCarde
2017-05-17 21:12:20
We can go up via $8N+1$, but then we reach $32n+1 > c = 8n+1$, contradicting that $c$ is the largest floor in the path.
We can go up via $8N+1$, but then we reach $32n+1 > c = 8n+1$, contradicting that $c$ is the largest floor in the path.
KevinCarde
2017-05-17 21:12:26
Therefore, $4n$ must be one of the endpoints of the path, as we can't go any further without breaking our assumptions!
Therefore, $4n$ must be one of the endpoints of the path, as we can't go any further without breaking our assumptions!
KevinCarde
2017-05-17 21:12:43
So: in Case 1, we have an odd endpoint; in Case 2, we have an endpoint divisible by $4$.
So: in Case 1, we have an odd endpoint; in Case 2, we have an endpoint divisible by $4$.
KevinCarde
2017-05-17 21:12:45
Combining the two possibilities, we see that in any reduced path between distinct floors, either an endpoint is odd or an endpoint is divisible by $4$.
Combining the two possibilities, we see that in any reduced path between distinct floors, either an endpoint is odd or an endpoint is divisible by $4$.
KevinCarde
2017-05-17 21:12:59
We conclude that distinct floors that are $2 \pmod4$ cannot be connected!
We conclude that distinct floors that are $2 \pmod4$ cannot be connected!
astroroman
2017-05-17 21:13:25
so infinite wizards?
so infinite wizards?
Mario2357
2017-05-17 21:13:35
there are an infinite number of 2 mod 4 numbers
there are an infinite number of 2 mod 4 numbers
KevinCarde
2017-05-17 21:13:39
Yes! By putting a wizard on each such floor, infinitely many wizards can live in the tower.
Yes! By putting a wizard on each such floor, infinitely many wizards can live in the tower.
KevinCarde
2017-05-17 21:14:04
Let's see if the tower in Part (c) is as welcoming.
Let's see if the tower in Part (c) is as welcoming.
KevinCarde
2017-05-17 21:14:10
PROBLEM 5c: $2N+1$ and $3N+1$
If the red portals instead connected floor $N$ to floor $2N + 1$, and the blue portals instead connected floor $N$ to floor $3N + 1$, how many wizards could live in the tower?
PROBLEM 5c: $2N+1$ and $3N+1$
If the red portals instead connected floor $N$ to floor $2N + 1$, and the blue portals instead connected floor $N$ to floor $3N + 1$, how many wizards could live in the tower?
KevinCarde
2017-05-17 21:14:21
PROBLEM 5c SOLUTION
PROBLEM 5c SOLUTION
KevinCarde
2017-05-17 21:14:43
I'm seeing a range of responses -- we'll see how this one turns out!
I'm seeing a range of responses -- we'll see how this one turns out!
KevinCarde
2017-05-17 21:14:47
We will show that every floor $a > 1$ can reach a smaller floor. Therefore, every floor is connected to floor $1$, and hence all floors are connected, and only one wizard can live in the tower.
We will show that every floor $a > 1$ can reach a smaller floor. Therefore, every floor is connected to floor $1$, and hence all floors are connected, and only one wizard can live in the tower.
MathPathogen
2017-05-17 21:15:02
Now on to the super picky wizard.
Now on to the super picky wizard.
BobaFett101
2017-05-17 21:15:02
1
1
goodbear
2017-05-17 21:15:02
1 fat wizard
1 fat wizard
Mario2357
2017-05-17 21:15:02
1
1
dawn1729
2017-05-17 21:15:02
1
1
astroroman
2017-05-17 21:15:02
only one?
only one?
KevinCarde
2017-05-17 21:15:11
All true!
All true!
KevinCarde
2017-05-17 21:15:22
So, showing that every floor can reach a lower floor. Many students set this problem up as strong induction, and that's a fine way to write up this idea.
So, showing that every floor can reach a lower floor. Many students set this problem up as strong induction, and that's a fine way to write up this idea.
KevinCarde
2017-05-17 21:15:34
I'm not going to go into the details of an inductive proof like Marisa did though.
I'm not going to go into the details of an inductive proof like Marisa did though.
KevinCarde
2017-05-17 21:15:45
Anyway, like the previous part, there are multiple strategies towards a proof.
Anyway, like the previous part, there are multiple strategies towards a proof.
KevinCarde
2017-05-17 21:15:52
There is a lovely strategy involving changing powers of $2$ in the starting floor to powers of $3$, going down a $2N+1$ portal, then going down many $3N+1$ portals to reach a lower floor. Try filling in the details of this method on your own time if it's new to you!
There is a lovely strategy involving changing powers of $2$ in the starting floor to powers of $3$, going down a $2N+1$ portal, then going down many $3N+1$ portals to reach a lower floor. Try filling in the details of this method on your own time if it's new to you!
KevinCarde
2017-05-17 21:15:57
In the interest of time, however, we're going to present a very direct proof.
In the interest of time, however, we're going to present a very direct proof.
KevinCarde
2017-05-17 21:16:03
Let $a > 1$ be any floor. There are three cases based on the residue mod $3$.
Let $a > 1$ be any floor. There are three cases based on the residue mod $3$.
KevinCarde
2017-05-17 21:16:08
$a = 3r$: How do we descend to a lower floor?
$a = 3r$: How do we descend to a lower floor?
Mario2357
2017-05-17 21:16:42
6r+1 then 2r
6r+1 then 2r
acegikmoqsuwy2000
2017-05-17 21:16:42
up to $6n+1$ and down to $2n$
up to $6n+1$ and down to $2n$
340086
2017-05-17 21:16:42
go to 6r + 1, then go to 2r
go to 6r + 1, then go to 2r
KevinCarde
2017-05-17 21:16:49
Going up $2N+1$ and down $3N+1$ takes us along the path $3r \to 6r+1 \to 2r$. Since $2r < 3r$, we have successfully reached a smaller floor.
Going up $2N+1$ and down $3N+1$ takes us along the path $3r \to 6r+1 \to 2r$. Since $2r < 3r$, we have successfully reached a smaller floor.
KevinCarde
2017-05-17 21:16:57
Next case, $a = 3r+1$: How do we descend to a lower floor?
Next case, $a = 3r+1$: How do we descend to a lower floor?
acegikmoqsuwy2000
2017-05-17 21:17:22
directly down to $r$
directly down to $r$
Mario2357
2017-05-17 21:17:22
r
r
hilarious
2017-05-17 21:17:22
3n+1
3n+1
MathPathogen
2017-05-17 21:17:22
take a blue portal downstairs.
take a blue portal downstairs.
duck_master
2017-05-17 21:17:22
down the 3n+1 portal
down the 3n+1 portal
BobaFett101
2017-05-17 21:17:22
go to r
go to r
PhoneChargers
2017-05-17 21:17:22
3r+1 to r
3r+1 to r
KevinCarde
2017-05-17 21:17:27
We have a portal precisely for this purpose!
We have a portal precisely for this purpose!
KevinCarde
2017-05-17 21:17:33
We simply go down the $3N+1$ portal to reach floor $r < 3r+1$.
We simply go down the $3N+1$ portal to reach floor $r < 3r+1$.
MathPathogen
2017-05-17 21:17:41
Now, on to the case that cost me days to do...
Now, on to the case that cost me days to do...
KevinCarde
2017-05-17 21:17:43
Uh oh
Uh oh
KevinCarde
2017-05-17 21:17:44
$a = 3r+2$: How do we descend to a lower floor?
$a = 3r+2$: How do we descend to a lower floor?
KevinCarde
2017-05-17 21:18:19
This is a tough case -- apologies that I didn't give you much time to think about it! Here's a sequence of portals that works.
This is a tough case -- apologies that I didn't give you much time to think about it! Here's a sequence of portals that works.
KevinCarde
2017-05-17 21:18:33
(Some of you might want to subdivide further, mod $6$ or even $12$, but we can do all cases at once!)
(Some of you might want to subdivide further, mod $6$ or even $12$, but we can do all cases at once!)
KevinCarde
2017-05-17 21:18:38
\[3r+2 \to 9r+7 \to 18r+15 \to 36r+31 \to 12r+10 \to 4r+3\to 2r+1\]
\[3r+2 \to 9r+7 \to 18r+15 \to 36r+31 \to 12r+10 \to 4r+3\to 2r+1\]
KevinCarde
2017-05-17 21:19:02
Whew!! I can see what that might take a while to discover.
Whew!! I can see what that might take a while to discover.
astroroman
2017-05-17 21:19:05
good thing this tower is infinite!
good thing this tower is infinite!
KevinCarde
2017-05-17 21:19:11
Yeah! We have to go up a long ways to get down.
Yeah! We have to go up a long ways to get down.
hilarious
2017-05-17 21:19:16
How does one find this? Guess and check?
How does one find this? Guess and check?
KevinCarde
2017-05-17 21:19:25
That's an excellent question! A lot of playing with portals can get you there.
That's an excellent question! A lot of playing with portals can get you there.
KevinCarde
2017-05-17 21:19:39
The other strategy that I outlined at the beginning of 5c is a little more motivated, so you might want to think about that.
The other strategy that I outlined at the beginning of 5c is a little more motivated, so you might want to think about that.
KevinCarde
2017-05-17 21:19:55
I believe that this is the shortest path that works for all numbers $2$ mod $3$, however.
I believe that this is the shortest path that works for all numbers $2$ mod $3$, however.
KevinCarde
2017-05-17 21:20:14
Anyway, we've successfully reduced every floor to a lower one, as desired.
Anyway, we've successfully reduced every floor to a lower one, as desired.
KevinCarde
2017-05-17 21:20:27
And that justifies only $1$ wizard in the tower!
And that justifies only $1$ wizard in the tower!
Buddy03
2017-05-17 21:20:36
Can that be proven
Can that be proven
KevinCarde
2017-05-17 21:20:52
I think the question is about this being the shortest path working for all $2$ mod $3$ floors, and yes, we could prove it!
I think the question is about this being the shortest path working for all $2$ mod $3$ floors, and yes, we could prove it!
KevinCarde
2017-05-17 21:21:00
There are only finitely many paths this length or shorter, so we could check them all.
There are only finitely many paths this length or shorter, so we could check them all.
KevinCarde
2017-05-17 21:21:13
If we find a shorter one, great, and if not, the one we used must be shortest!
If we find a shorter one, great, and if not, the one we used must be shortest!
MathPathogen
2017-05-17 21:21:17
yay for brute force!
yay for brute force!
KevinCarde
2017-05-17 21:21:22
It has its place sometimes.
It has its place sometimes
.
KevinCarde
2017-05-17 21:21:28
OK, onwards to Problem 6, something very different!
OK, onwards to Problem 6, something very different!
KevinCarde
2017-05-17 21:21:41
(Ready for a big copy and paste?)
(Ready for a big copy and paste?)
KevinCarde
2017-05-17 21:21:48
PROBLEM 6: Triangles
A triangle function assigns a nonnegative real number to all nondegenerate triangles. We call a triangle function $f$ consistent if any two congruent triangles are assigned the same value: $f(\triangle ABC) = f(\triangle DEF)$ whenever $\triangle ABC \cong \triangle DEF$.
Suppose that for some $\triangle ABC$, points $X$, $Y$, and $Z$ are chosen in the interior of sides $AB$, $AC$, and $BC$, respectively. If a triangle function $f$ satisfies
\[f(\triangle AXY) + f(\triangle BXZ) + f(\triangle CYZ) = f(\triangle ABC)\]
for all choices of $\triangle ABC$, $X$, $Y$, and $Z$, we say that $f$ has the triforce property. (In the diagram below, the function's values for each of the shaded triangles must add up to the function's value for the large triangle.)
Figure 1: $f$'s values at $\triangle AXY$ (red), $\triangle BXZ$ (cyan), and $\triangle CYZ$ (teal) must add up to $f$'s value at $\triangle ABC$.
Is there a consistent triangle function with the triforce property, other than the trivial function assigning the value $0$ to every triangle?
PROBLEM 6: Triangles
A triangle function assigns a nonnegative real number to all nondegenerate triangles. We call a triangle function $f$ consistent if any two congruent triangles are assigned the same value: $f(\triangle ABC) = f(\triangle DEF)$ whenever $\triangle ABC \cong \triangle DEF$.
Suppose that for some $\triangle ABC$, points $X$, $Y$, and $Z$ are chosen in the interior of sides $AB$, $AC$, and $BC$, respectively. If a triangle function $f$ satisfies
\[f(\triangle AXY) + f(\triangle BXZ) + f(\triangle CYZ) = f(\triangle ABC)\]
for all choices of $\triangle ABC$, $X$, $Y$, and $Z$, we say that $f$ has the triforce property. (In the diagram below, the function's values for each of the shaded triangles must add up to the function's value for the large triangle.)
Figure 1: $f$'s values at $\triangle AXY$ (red), $\triangle BXZ$ (cyan), and $\triangle CYZ$ (teal) must add up to $f$'s value at $\triangle ABC$.
Is there a consistent triangle function with the triforce property, other than the trivial function assigning the value $0$ to every triangle?
KevinCarde
2017-05-17 21:22:12
PROBLEM 6 SOLUTION
PROBLEM 6 SOLUTION
KevinCarde
2017-05-17 21:22:26
Whew! This sounds intimidating -- this is the problem on the Qualifying Quiz that I was most intimidated by.
Whew! This sounds intimidating -- this is the problem on the Qualifying Quiz that I was most intimidated by.
KevinCarde
2017-05-17 21:22:42
But it turns out it's not going to be very nice -- hang in there!
But it turns out it's not going to be very nice -- hang in there!
MathPathogen
2017-05-17 21:22:51
No?
No?
PhoneChargers
2017-05-17 21:22:51
No, no such function exists
No, no such function exists
KevinCarde
2017-05-17 21:22:57
We claim that there is no nontrivial consistent triangle function with the triforce property.
We claim that there is no nontrivial consistent triangle function with the triforce property.
KevinCarde
2017-05-17 21:23:09
Let $f$ be a consistent triangle function with the triforce property. We will show that $f$ takes the value $0$ on every triangle.
Let $f$ be a consistent triangle function with the triforce property. We will show that $f$ takes the value $0$ on every triangle.
KevinCarde
2017-05-17 21:23:22
Note that we can iterate the triforce property to write the value of $f$ on a big triangle as a sum of more than three pieces.
Note that we can iterate the triforce property to write the value of $f$ on a big triangle as a sum of more than three pieces.
KevinCarde
2017-05-17 21:23:28
For example, consider the following situation:
For example, consider the following situation:
KevinCarde
2017-05-17 21:23:32
KevinCarde
2017-05-17 21:23:40
Here, we've made a triforce out of the big equilateral triangle, then we've further triforced the bottom left piece into three even smaller triangles.
Here, we've made a triforce out of the big equilateral triangle, then we've further triforced the bottom left piece into three even smaller triangles.
KevinCarde
2017-05-17 21:23:46
(And yes, I just verbed "triforce".)
(And yes, I just verbed "triforce".)
acegikmoqsuwy2000
2017-05-17 21:24:04
and you also verbed "verb"
and you also verbed "verb"
KevinCarde
2017-05-17 21:24:07
Well, so did you!
Well, so did you
!
KevinCarde
2017-05-17 21:24:14
Back to triangles: The value of $f$ on the big triangle equals the sum of the values of $f$ on all five pieces (the top and right triforce pieces plus the three sub-triforce pieces on the left).
Back to triangles: The value of $f$ on the big triangle equals the sum of the values of $f$ on all five pieces (the top and right triforce pieces plus the three sub-triforce pieces on the left).
KevinCarde
2017-05-17 21:24:31
You can check this by applying the triforce property twice.
You can check this by applying the triforce property twice.
mochi
2017-05-17 21:24:34
There should be a dictionary on improper words used in this Math Jam.
There should be a dictionary on improper words used in this Math Jam.
KevinCarde
2017-05-17 21:24:37
Groovy idea!
Groovy idea!
KevinCarde
2017-05-17 21:24:51
By nonnegativity of triangle functions, we have our first important observation.
By nonnegativity of triangle functions, we have our first important observation.
KevinCarde
2017-05-17 21:24:56
OBSERVATION 1: If $f$ takes the value $0$ on the big triangle, then it must equal $0$ on every piece as well.
OBSERVATION 1: If $f$ takes the value $0$ on the big triangle, then it must equal $0$ on every piece as well.
KevinCarde
2017-05-17 21:25:15
Let's look at our picture above of the big subdivided equilateral triangle. It takes some thinking and justification, but any triangle can be used in place of the red triangle (the one marked with a star in the picture).
Let's look at our picture above of the big subdivided equilateral triangle. It takes some thinking and justification, but any triangle can be used in place of the red triangle (the one marked with a star in the picture).
KevinCarde
2017-05-17 21:25:30
(There are some details to be careful of: if the red triangle has an angle of at least $120^\circ$, we must be sure not use that as the rightmost angle in this construction!)
(There are some details to be careful of: if the red triangle has an angle of at least $120^\circ$, we must be sure not use that as the rightmost angle in this construction!)
KevinCarde
2017-05-17 21:25:41
This gives us our second observation.
This gives us our second observation.
KevinCarde
2017-05-17 21:25:45
OBSERVATION 2: Any triangle can be used as a triforce piece in an equilateral triangle.
OBSERVATION 2: Any triangle can be used as a triforce piece in an equilateral triangle.
KevinCarde
2017-05-17 21:25:53
Combining the above observations, we've shown something very important:
Combining the above observations, we've shown something very important:
KevinCarde
2017-05-17 21:26:00
If $f$ is $0$ on all equilateral triangles, then $f$ is $0$ on all triangles.
If $f$ is $0$ on all equilateral triangles, then $f$ is $0$ on all triangles.
KevinCarde
2017-05-17 21:26:12
So now we focus on equilateral triangles! Here's one set of useful triforces.
So now we focus on equilateral triangles! Here's one set of useful triforces.
MathPathogen
2017-05-17 21:26:23
what about a degenerate triangle?
what about a degenerate triangle?
KevinCarde
2017-05-17 21:26:27
Good question!
Good question!
KevinCarde
2017-05-17 21:26:39
The problem writers were careful enough to put this in the original problem statement.
The problem writers were careful enough to put this in the original problem statement
.
KevinCarde
2017-05-17 21:27:16
We're only considering triangle functions as taking nondegenerate triangles as input.
We're only considering triangle functions as taking nondegenerate triangles as input.
KevinCarde
2017-05-17 21:27:29
(And I've been a bit sloppy in my solution -- whenever I say "triangle", I mean nondegenerate)
(And I've been a bit sloppy in my solution -- whenever I say "triangle", I mean nondegenerate)
KevinCarde
2017-05-17 21:27:37
OK, here are those useful triforces I promised:
OK, here are those useful triforces I promised:
KevinCarde
2017-05-17 21:27:38
KevinCarde
2017-05-17 21:27:51
We've written the value of $f$ on an arbitrary equilateral triangle in four different ways:
We've written the value of $f$ on an arbitrary equilateral triangle in four different ways:
KevinCarde
2017-05-17 21:28:06
\[9f(\triangle_1) = 5f(\triangle_2) = 3f(\triangle_3) = f(\triangle_1) + 3f(\triangle_2) + f(\triangle_3)\]
\[9f(\triangle_1) = 5f(\triangle_2) = 3f(\triangle_3) = f(\triangle_1) + 3f(\triangle_2) + f(\triangle_3)\]
mochi
2017-05-17 21:28:34
Pretty triangles!
Pretty triangles!
mochi
2017-05-17 21:28:34
Love the color combos!
Love the color combos!
KevinCarde
2017-05-17 21:28:48
I take no credit for the color choices -- I made another Mathcamp staff member make the diagrams for me.
I take no credit for the color choices -- I made another Mathcamp staff member make the diagrams for me
.
KevinCarde
2017-05-17 21:29:06
With a little algebra, we can see that these equalities are only possible if $f(\triangle_1) = f(\triangle_2) = f(\triangle_3) = 0$, and hence $f$ is $0$ on the big equilateral triangle.
With a little algebra, we can see that these equalities are only possible if $f(\triangle_1) = f(\triangle_2) = f(\triangle_3) = 0$, and hence $f$ is $0$ on the big equilateral triangle.
KevinCarde
2017-05-17 21:29:17
Since the equilateral triangle was arbitrary, we've successfully shown that $f$ is $0$ on all equilateral triangles, as desired. QED!
Since the equilateral triangle was arbitrary, we've successfully shown that $f$ is $0$ on all equilateral triangles, as desired. QED!
340086
2017-05-17 21:29:21
QED
QED
PhoneChargers
2017-05-17 21:29:24
What's the motivation behind this?
What's the motivation behind this?
KevinCarde
2017-05-17 21:29:45
Good question again. A lot of fiddling with triangles can get you here.
Good question again. A lot of fiddling with triangles can get you here.
KevinCarde
2017-05-17 21:30:11
But if you're trying to prove that no nontrivial consistent triangle functions exist, it's reasonable to hope that you can do so by getting contradictory subdivisions of the same big triangle.
But if you're trying to prove that no nontrivial consistent triangle functions exist, it's reasonable to hope that you can do so by getting contradictory subdivisions of the same big triangle.
KevinCarde
2017-05-17 21:30:32
So then you try to get the same triforce pieces involved in multiple different subdivisions.
So then you try to get the same triforce pieces involved in multiple different subdivisions.
KevinCarde
2017-05-17 21:30:41
There are many constructions that work for the proof -- this is just one of them!
There are many constructions that work for the proof -- this is just one of them!
KevinCarde
2017-05-17 21:30:54
One final note. It's possible to remove the nonnegativity condition on triangle functions, and the result that there is no nontrivial consistent triangle function with the triforce property still holds -- you might enjoy thinking about this on your own time!
One final note. It's possible to remove the nonnegativity condition on triangle functions, and the result that there is no nontrivial consistent triangle function with the triforce property still holds -- you might enjoy thinking about this on your own time!
astroroman
2017-05-17 21:31:01
Next problem!
Next problem!
KevinCarde
2017-05-17 21:31:10
But yes -- over to Pesto for the last problem!
But yes -- over to Pesto for the last problem!
Kamior
2017-05-17 21:31:54
PROBLEM 7: Waldo and Carmen
Waldo and Carmen play a guessing game played in $N$ cities located on a large ring around the earth. Two cities that are next to each other in the ring are chosen uniformly at random. Waldo is sent to one of them and Carmen is sent to the other. Neither player knows which of the adjacent cities the other is in.
Starting with Waldo, the players take turns guessing where the other is. Each player hears the other's guesses and can use that information when making future guesses. The first player to guess correctly wins.
If $N=3$, find a strategy for Waldo that wins him the game with probability at least $\frac23$, no matter what strategy Carmen uses.
If $N=3$, find a strategy for Carmen that wins her the game with probability at least $\frac13$, no matter what strategy Waldo uses.
What are Waldo and Carmen's optimal strategies in the general case? (You might want to try $N=6$ and $N=8$ to begin with.)
PROBLEM 7: Waldo and Carmen
Waldo and Carmen play a guessing game played in $N$ cities located on a large ring around the earth. Two cities that are next to each other in the ring are chosen uniformly at random. Waldo is sent to one of them and Carmen is sent to the other. Neither player knows which of the adjacent cities the other is in.
Starting with Waldo, the players take turns guessing where the other is. Each player hears the other's guesses and can use that information when making future guesses. The first player to guess correctly wins.
If $N=3$, find a strategy for Waldo that wins him the game with probability at least $\frac23$, no matter what strategy Carmen uses.
If $N=3$, find a strategy for Carmen that wins her the game with probability at least $\frac13$, no matter what strategy Waldo uses.
What are Waldo and Carmen's optimal strategies in the general case? (You might want to try $N=6$ and $N=8$ to begin with.)
Kamior
2017-05-17 21:32:18
PROBLEM 7 SOLUTION
Before we dive in, it will be helpful to introduce a couple concepts.
PROBLEM 7 SOLUTION
Before we dive in, it will be helpful to introduce a couple concepts.
Kamior
2017-05-17 21:32:31
Pure vs. mixed strategies: A pure strategy for Waldo is basically a rulebook that describes exactly what Waldo should do in every possible situation. A pure strategy cannot involve making any choice that is random or depends on something outside the game. If Waldo plays with a mixed strategy, then he chooses randomly from a number of pure strategies (each with a particular probability). Alternatively, a mixed strategy is like a rulebook that can also tell Waldo to, say, flip a coin or roll a die.
Pure vs. mixed strategies: A pure strategy for Waldo is basically a rulebook that describes exactly what Waldo should do in every possible situation. A pure strategy cannot involve making any choice that is random or depends on something outside the game. If Waldo plays with a mixed strategy, then he chooses randomly from a number of pure strategies (each with a particular probability). Alternatively, a mixed strategy is like a rulebook that can also tell Waldo to, say, flip a coin or roll a die.
Kamior
2017-05-17 21:32:50
In part (a), when we come up with a strategy for Waldo, it's going to be a mixed strategy. We'll show that it beats any pure strategy for Carmen with probability at least $\frac23$. But that implies that it also beats any mixed strategy for Carmen with probability at least $\frac23$. Similarly in the other parts of the problem, we'll describe a mixed strategy for one player and talk about how it competes against any pure strategy for the other player.
In part (a), when we come up with a strategy for Waldo, it's going to be a mixed strategy. We'll show that it beats any pure strategy for Carmen with probability at least $\frac23$. But that implies that it also beats any mixed strategy for Carmen with probability at least $\frac23$. Similarly in the other parts of the problem, we'll describe a mixed strategy for one player and talk about how it competes against any pure strategy for the other player.
Kamior
2017-05-17 21:33:05
In fact, even before solving anything, we can see that Waldo's and Carmen's strategies must not be pure:
In fact, even before solving anything, we can see that Waldo's and Carmen's strategies must not be pure:
Kamior
2017-05-17 21:33:20
-If Waldo's strategy is to always guess a city next to him on the first turn, he wins on that turn with probability $\frac12$. But if he doesn't win immediately following that strategy, he must've guessed the empty city, so Carmen's strategy of “guess whichever adjacent city Waldo didn't guess” wins with probability $\frac12$. But we want a strategy for Waldo that wins with probability greater than $\frac12$ no matter what Carmen's strategy is, so this can't be it.
-If Waldo's strategy is to always guess a city next to him on the first turn, he wins on that turn with probability $\frac12$. But if he doesn't win immediately following that strategy, he must've guessed the empty city, so Carmen's strategy of “guess whichever adjacent city Waldo didn't guess” wins with probability $\frac12$. But we want a strategy for Waldo that wins with probability greater than $\frac12$ no matter what Carmen's strategy is, so this can't be it.
Kamior
2017-05-17 21:33:35
-If Carmen's strategy is to always guess her own city on her first guess, then Waldo's strategy of “Guess my own city, then guess whichever city Carmen guessed” wins with probability $1$. But we want a strategy for Waldo that wins with probability greater than $0$ no matter what Carmen's strategy is, so this can't be it.
-If Carmen's strategy is to always guess her own city on her first guess, then Waldo's strategy of “Guess my own city, then guess whichever city Carmen guessed” wins with probability $1$. But we want a strategy for Waldo that wins with probability greater than $0$ no matter what Carmen's strategy is, so this can't be it.
Kamior
2017-05-17 21:33:41
There are two more cases for Carmen's first guess to be pure; can you rule them out similarly?
There are two more cases for Carmen's first guess to be pure; can you rule them out similarly?
Kamior
2017-05-17 21:36:12
In the interest of time, we won't go over those two cases here. (Speaking of time, we're over our originally stated end time, and we have another ~20 minutes to go. You're welcome to leave and read the transcript later if, say, it's bedtime.)
In the interest of time, we won't go over those two cases here. (Speaking of time, we're over our originally stated end time, and we have another ~20 minutes to go. You're welcome to leave and read the transcript later if, say, it's bedtime.)
Kamior
2017-05-17 21:36:33
If the problem statement is correct, Carmen can't win with probability better than $\frac13$ against all strategies of Waldo's (because then her strategy would be one against which Waldo couldn't win $\frac23$ of the time), and Waldo can't win with probability better than $\frac23$ against all strategies of Carmen's (because then his strategy would be one against which Carmen couldn't win $\frac13$ of the time). One of the most amusing things to see in admissions was how many people “proved” both that, say, Carmen could guarantee a win with probability at least $\frac12$ and that Waldo could guarantee a win with probability at least $\frac56$.
If the problem statement is correct, Carmen can't win with probability better than $\frac13$ against all strategies of Waldo's (because then her strategy would be one against which Waldo couldn't win $\frac23$ of the time), and Waldo can't win with probability better than $\frac23$ against all strategies of Carmen's (because then his strategy would be one against which Carmen couldn't win $\frac13$ of the time). One of the most amusing things to see in admissions was how many people “proved” both that, say, Carmen could guarantee a win with probability at least $\frac12$ and that Waldo could guarantee a win with probability at least $\frac56$.
Kamior
2017-05-17 21:37:27
(Note that the other possibility where those probabilities add up to less than 1 is hard to rule out: you might imagine there's some rock-paper-scissors going on, where some of Carmen's strategies do better against some of Waldo's, and Carmen can't come up with a strategy that wins with probability more than, say, $\frac14$ against all strategies of Waldo's and Waldo can't come up with a strategy that wins with probability more than, say, $\frac12$ against all strategies of Carmen's, where $\frac14+\frac12 < 1$. There's a theorem called von Neumann's minimax theorem that states this is never the case.)
(Note that the other possibility where those probabilities add up to less than 1 is hard to rule out: you might imagine there's some rock-paper-scissors going on, where some of Carmen's strategies do better against some of Waldo's, and Carmen can't come up with a strategy that wins with probability more than, say, $\frac14$ against all strategies of Waldo's and Waldo can't come up with a strategy that wins with probability more than, say, $\frac12$ against all strategies of Carmen's, where $\frac14+\frac12 < 1$. There's a theorem called von Neumann's minimax theorem that states this is never the case.)
Kamior
2017-05-17 21:38:08
Dominance: Sometimes a player will have several different options, but some of them they should never take, because another option is always better. For example, if Waldo figures out what city Carmen is in, his only ``reasonable'' next guess is that city. No other choice would be better for Waldo, regardless of what strategy Carmen is using, because the strategy of ?guess Carmen's city if you know it? wins with probability 1 whenever it comes up, and every other strategy wins with probability at most 1. If we're trying prove that Carmen's strategy beats every pure strategy for Waldo, it's actually enough for us to prove that it beats every ``reasonable'' strategy for Waldo. This is a rephrasing of what is usually called the principle of iterated removal of dominated strategies. We'll use this principle repeatedly to narrow down the strategies that we have to consider.
Dominance: Sometimes a player will have several different options, but some of them they should never take, because another option is always better. For example, if Waldo figures out what city Carmen is in, his only ``reasonable'' next guess is that city. No other choice would be better for Waldo, regardless of what strategy Carmen is using, because the strategy of ?guess Carmen's city if you know it? wins with probability 1 whenever it comes up, and every other strategy wins with probability at most 1. If we're trying prove that Carmen's strategy beats every pure strategy for Waldo, it's actually enough for us to prove that it beats every ``reasonable'' strategy for Waldo. This is a rephrasing of what is usually called the principle of iterated removal of dominated strategies. We'll use this principle repeatedly to narrow down the strategies that we have to consider.
Kamior
2017-05-17 21:38:16
Let's start doing that right now!
Let's start doing that right now!
Kamior
2017-05-17 21:38:58
Can anyone tell me any strategies (for either Waldo or Carmen) that dominate other strategies?
Can anyone tell me any strategies (for either Waldo or Carmen) that dominate other strategies?
MathPathogen
2017-05-17 21:40:24
Choosing randomly for Waldo dominates all Carmen strategies.
Choosing randomly for Waldo dominates all Carmen strategies.
Kamior
2017-05-17 21:40:35
A strategy for Waldo dominates other strategies for Waldo, showing that one should never use the latter.
A strategy for Waldo dominates other strategies for Waldo, showing that one should never use the latter.
Kamior
2017-05-17 21:40:49
Let's see an example:
Let's see an example:
Kamior
2017-05-17 21:40:56
Lemma: Carmen should never guess her own city.
Lemma: Carmen should never guess her own city.
Kamior
2017-05-17 21:41:03
This lemma sort of makes sense, because Carmen already knows Waldo isn't there. On the other hand, Carmen could in theory guess wrong on purpose to confuse Waldo (in fact, Waldo will sometimes try to confuse Carmen this way).
This lemma sort of makes sense, because Carmen already knows Waldo isn't there. On the other hand, Carmen could in theory guess wrong on purpose to confuse Waldo (in fact, Waldo will sometimes try to confuse Carmen this way).
Kamior
2017-05-17 21:41:17
To prove it, we'll show that Carmen can always do at least as well by not guessing her own city.
To prove it, we'll show that Carmen can always do at least as well by not guessing her own city.
Kamior
2017-05-17 21:41:35
(Incidentally, strategies where Carmen guesses her own city may be only weakly dominated: in fact, Carmen can win with probability $\frac13$ even if she guesses her own city.)
(Incidentally, strategies where Carmen guesses her own city may be only weakly dominated: in fact, Carmen can win with probability $\frac13$ even if she guesses her own city.)
Kamior
2017-05-17 21:41:46
We'll show that it's at least as good for Carmen to guess the same city Waldo guessed instead. There's two cases to consider:
We'll show that it's at least as good for Carmen to guess the same city Waldo guessed instead. There's two cases to consider:
Kamior
2017-05-17 21:41:51
Case 1: Waldo didn't guess his own city. In this case, he guessed an adjacent city and will win on his second turn. So there's no use to Carmen purposefully guessing wrong.
Case 1: Waldo didn't guess his own city. In this case, he guessed an adjacent city and will win on his second turn. So there's no use to Carmen purposefully guessing wrong.
Kamior
2017-05-17 21:41:58
Case 2: Waldo guessed his own city. In this case, Carmen wins by guessing the same city as Waldo.
Case 2: Waldo guessed his own city. In this case, Carmen wins by guessing the same city as Waldo.
Kamior
2017-05-17 21:43:11
With that as an example, can anyone find any other pieces of strategy for either Waldo or Carmen that dominate any other pieces of their strategy?
With that as an example, can anyone find any other pieces of strategy for either Waldo or Carmen that dominate any other pieces of their strategy?
Kamior
2017-05-17 21:45:54
(This is a sort of thing that it's easy to mess up on, and accidentally think you've proven something that's actually false.)
(This is a sort of thing that it's easy to mess up on, and accidentally think you've proven something that's actually false.)
Kamior
2017-05-17 21:46:03
The above observations are useful for finding a solution. The following would suffice as a complete solution to the problem (although if you try to do just this and get something wrong, we'd have less evidence that you understood anything):
The above observations are useful for finding a solution. The following would suffice as a complete solution to the problem (although if you try to do just this and get something wrong, we'd have less evidence that you understood anything):
MarisaD
2017-05-17 21:47:59
[Elevator music plays during a brief pause while Pesto's computer restarts.]
[Elevator music plays during a brief pause while Pesto's computer restarts.]
duck_master
2017-05-17 21:48:29
this is a strange game
this is a strange game
MarisaD
2017-05-17 21:48:38
It sure is! But a mathematically interesting one.
It sure is! But a mathematically interesting one.
Ninja531
2017-05-17 21:48:42
[Gentle watered down jazz slowly starts]
[Gentle watered down jazz slowly starts]
340086
2017-05-17 21:48:42
some elevator music
some elevator music
MathPathogen
2017-05-17 21:49:32
[Jeopardy music begins]
[Jeopardy music begins]
mochi
2017-05-17 21:49:37
[Music that plays in Gym to make it less awkward while you're running)
[Music that plays in Gym to make it less awkward while you're running)
340086
2017-05-17 21:50:08
in the meantime
in the meantime
340086
2017-05-17 21:50:08
would anybody be interested in actually playing this game at mathcamp
would anybody be interested in actually playing this game at mathcamp
MarisaD
2017-05-17 21:50:15
I bet we'll get some takers.
I bet we'll get some takers.
IvantheKingIII
2017-05-17 21:52:26
[Kahoot music begins]
[Kahoot music begins]
Ninja531
2017-05-17 21:54:12
[song remixes from 2012] ]
[song remixes from 2012] ]
340086
2017-05-17 21:54:12
*lightly tapping foot*
*lightly tapping foot*
KevinCarde
2017-05-17 21:54:20
OK, while we try to get Pesto back, let's try to push forward.
OK, while we try to get Pesto back, let's try to push forward.
KevinCarde
2017-05-17 21:54:40
Pesto was having you do some good exploration, and let's now dive into a solution.
Pesto was having you do some good exploration, and let's now dive into a solution.
KevinCarde
2017-05-17 21:54:42
A solution to (a)
A solution to (a)
KevinCarde
2017-05-17 21:55:15
On Waldo's first turn, he guesses each city with probability $\frac13$. What he does on his second turn (if he gets one) depends on whether he guessed his own city on his first turn. If he did, then on his second turn he guesses the one city that neither he nor Carmen has guessed yet. If he started by guessing a city not his own, then he guesses the other city that isn't his.
On Waldo's first turn, he guesses each city with probability $\frac13$. What he does on his second turn (if he gets one) depends on whether he guessed his own city on his first turn. If he did, then on his second turn he guesses the one city that neither he nor Carmen has guessed yet. If he started by guessing a city not his own, then he guesses the other city that isn't his.
KevinCarde
2017-05-17 21:55:29
To check that Waldo wins with probability at least $\frac23$, let $p$ be the probability that Carmen guesses neither her own city nor Waldo's guess on her turn. Then we split into three cases, based on Waldo's first guess:
To check that Waldo wins with probability at least $\frac23$, let $p$ be the probability that Carmen guesses neither her own city nor Waldo's guess on her turn. Then we split into three cases, based on Waldo's first guess:
KevinCarde
2017-05-17 21:55:39
With probability $\frac13$, Waldo guesses Carmen's city first and wins. Hooray!
With probability $\frac13$, Waldo guesses Carmen's city first and wins. Hooray!
KevinCarde
2017-05-17 21:55:56
With probability $\frac13$, Waldo guesses the empty city first. Then with probability $p$, Carmen guesses Waldo's city; if not, Waldo's next guess is correct, so he wins with probability $\frac13(1-p)$ this way.
With probability $\frac13$, Waldo guesses the empty city first. Then with probability $p$, Carmen guesses Waldo's city; if not, Waldo's next guess is correct, so he wins with probability $\frac13(1-p)$ this way.
KevinCarde
2017-05-17 21:56:28
With probability $\frac13$, Waldo guesses his own city first. Then with probability $p$, Carmen guesses the empty city and Waldo wins on his next guess, so Waldo wins with probability at least $\frac13p$ in this case.
With probability $\frac13$, Waldo guesses his own city first. Then with probability $p$, Carmen guesses the empty city and Waldo wins on his next guess, so Waldo wins with probability at least $\frac13p$ in this case.
KevinCarde
2017-05-17 21:56:35
So Waldo's total chance of winning with this strategy is at least $\frac13 + \frac13(1-p) + \frac13p = \frac23$.
So Waldo's total chance of winning with this strategy is at least $\frac13 + \frac13(1-p) + \frac13p = \frac23$.
KevinCarde
2017-05-17 21:57:04
Now let's see what Carmen can do.
Now let's see what Carmen can do.
KevinCarde
2017-05-17 21:57:05
A solution to (b)
A solution to (b)
KevinCarde
2017-05-17 21:57:17
Carmen never guesses her own city. With probability $\frac13$, she guesses the same city as Waldo did on his first guess, and with probability $\frac23$, she guesses the other city that is not her own.
Carmen never guesses her own city. With probability $\frac13$, she guesses the same city as Waldo did on his first guess, and with probability $\frac23$, she guesses the other city that is not her own.
KevinCarde
2017-05-17 21:57:27
To check that Carmen wins with probability at least $\frac13$, we consider two cases: either Waldo guesses his own city on his first turn, or he doesn't.
To check that Carmen wins with probability at least $\frac13$, we consider two cases: either Waldo guesses his own city on his first turn, or he doesn't.
KevinCarde
2017-05-17 21:57:47
Case 1: Waldo's first guess is his own city. Waldo is wrong on his first turn, and then one third of the time, Carmen guesses the same city as Waldo, and she wins.
Case 1: Waldo's first guess is his own city. Waldo is wrong on his first turn, and then one third of the time, Carmen guesses the same city as Waldo, and she wins.
KevinCarde
2017-05-17 21:58:11
Case 2: Waldo's first guess is not his own city. From Waldo's perspective, each of the other two cities is equally likely to be Carmen's, so his first guess is a winner half the time. The other half of the time, Carmen wins when she doesn't make the same guess as Waldo, which is a choice she makes with probability two thirds. So, she wins with probability at least $\frac12 \cdot \frac23 = \frac13$.
Case 2: Waldo's first guess is not his own city. From Waldo's perspective, each of the other two cities is equally likely to be Carmen's, so his first guess is a winner half the time. The other half of the time, Carmen wins when she doesn't make the same guess as Waldo, which is a choice she makes with probability two thirds. So, she wins with probability at least $\frac12 \cdot \frac23 = \frac13$.
KevinCarde
2017-05-17 21:58:44
So whichever case we're in, Carmen wins with probability at least $\frac13$!
So whichever case we're in, Carmen wins with probability at least $\frac13$!
KevinCarde
2017-05-17 21:59:07
OK, those were just warm ups... ...
OK, those were just warm ups... ...
KevinCarde
2017-05-17 21:59:08
A solution to (c)
A solution to (c)
KevinCarde
2017-05-17 21:59:52
The following solution to problem (c) comes from Mathcamp applicant Mariusz Trela, whose solution was better than ours. (Typos are definitely mine, though -- I'm not an expert on this problem!)
The following solution to problem (c) comes from Mathcamp applicant Mariusz Trela, whose solution was better than ours. (Typos are definitely mine, though -- I'm not an expert on this problem!)
KevinCarde
2017-05-17 22:00:17
Let's number the cities from $0$ to $N-1$ counterclockwise -- we will treat cities' numbers as remainders modulo $N$. Also, let's assume that $N$ is even (we will consider the case of odd $N$ later), so let the number of cities be $2M$ for some natural number $M$. We will show a strategy that gives Waldo a probability at least $\frac{N+2}{2N} = \frac{M+1}{2M}$ of winning regardless of Carmen's strategy. Let 0 be Waldo's city. Then he uses the following strategy:
Let's number the cities from $0$ to $N-1$ counterclockwise -- we will treat cities' numbers as remainders modulo $N$. Also, let's assume that $N$ is even (we will consider the case of odd $N$ later), so let the number of cities be $2M$ for some natural number $M$. We will show a strategy that gives Waldo a probability at least $\frac{N+2}{2N} = \frac{M+1}{2M}$ of winning regardless of Carmen's strategy. Let 0 be Waldo's city. Then he uses the following strategy:
KevinCarde
2017-05-17 22:00:30
In his first guess, he guesses randomly among the cities with an odd index, each with the same probability of $\frac1M$. Let Waldo's guess be $X$.
In his first guess, he guesses randomly among the cities with an odd index, each with the same probability of $\frac1M$. Let Waldo's guess be $X$.
KevinCarde
2017-05-17 22:01:05
If $X$ isn't Carmen's city and Carmen guesses some city $Y \neq 0$, then Waldo guesses $1$ if $Y < X$ and $2M-1$ otherwise.
If $X$ isn't Carmen's city and Carmen guesses some city $Y \neq 0$, then Waldo guesses $1$ if $Y < X$ and $2M-1$ otherwise.
KevinCarde
2017-05-17 22:01:23
We will show these two guesses are enough for $\frac{M+1}{2M}$ probability.
We will show these two guesses are enough for $\frac{M+1}{2M}$ probability.
KevinCarde
2017-05-17 22:01:44
Let C be Carmen's city, and let $c_l(X - C)$ and $c_r(X - C)$ be the probabilities that Carmen guesses in the intervals $[X, C - 1]$ and $[C, X - 1]$ respectively after Waldo's guessing $X$ (note that those probabilities aren't dependent on anything but the position of $X$ with respect to $C$, because that's all Carmen knows). We have $c_l(i) + c_r(i) = 1$ for each nonzero $i$ (mod 2M).
Let C be Carmen's city, and let $c_l(X - C)$ and $c_r(X - C)$ be the probabilities that Carmen guesses in the intervals $[X, C - 1]$ and $[C, X - 1]$ respectively after Waldo's guessing $X$ (note that those probabilities aren't dependent on anything but the position of $X$ with respect to $C$, because that's all Carmen knows). We have $c_l(i) + c_r(i) = 1$ for each nonzero $i$ (mod 2M).
KevinCarde
2017-05-17 22:02:04
Now, we have two cases: either Carmen's in city 1 or she's in city $2M-1$.
Now, we have two cases: either Carmen's in city 1 or she's in city $2M-1$.
KevinCarde
2017-05-17 22:02:33
If she's in city 1:
If she's in city 1:
KevinCarde
2017-05-17 22:02:47
If Waldo guesses $X$, the probability that Carmen guesses in the interval $[1, X - 1]$ is
$c_r(X - 1)$, and then Waldo wins according to his strategy. So the probability of Waldo's winning in this case is at least
$$\frac1M + \frac1M\sum_{i=1}^{M-1} c_r(2i),$$
where the initial $\frac1M$ comes from the possibility that Waldo wins the game in his first guess.
If Waldo guesses $X$, the probability that Carmen guesses in the interval $[1, X - 1]$ is
$c_r(X - 1)$, and then Waldo wins according to his strategy. So the probability of Waldo's winning in this case is at least
$$\frac1M + \frac1M\sum_{i=1}^{M-1} c_r(2i),$$
where the initial $\frac1M$ comes from the possibility that Waldo wins the game in his first guess.
KevinCarde
2017-05-17 22:03:01
If Carmen's in city $2M-1$:
If Carmen's in city $2M-1$:
KevinCarde
2017-05-17 22:03:14
If Waldo guesses $X$, the probability that Carmen guesses in the
interval $[X, 2M - 2]$ is $c_l(X - (2M - 1)) = c_l(X + 1)$, and then Waldo wins. So the probability
of Waldo's winning in this case is at least
$$\frac1M + \frac1M\sum_{i=1}^{M-1} c_l(2i),$$
as it was in the previous case. Each case is equally likely, so the total probability is
$$\frac12(\frac1M + \frac1M + \frac1M\sum_{i=1}^{M-1} c_r(2i)+\frac1M\sum_{i=1}^{M-1} c_l(2i) = \frac12(\frac2M + \frac1M(M-1)) = \frac{M+1}{2M},$$
which is what we wanted to prove.
If Waldo guesses $X$, the probability that Carmen guesses in the
interval $[X, 2M - 2]$ is $c_l(X - (2M - 1)) = c_l(X + 1)$, and then Waldo wins. So the probability
of Waldo's winning in this case is at least
$$\frac1M + \frac1M\sum_{i=1}^{M-1} c_l(2i),$$
as it was in the previous case. Each case is equally likely, so the total probability is
$$\frac12(\frac1M + \frac1M + \frac1M\sum_{i=1}^{M-1} c_r(2i)+\frac1M\sum_{i=1}^{M-1} c_l(2i) = \frac12(\frac2M + \frac1M(M-1)) = \frac{M+1}{2M},$$
which is what we wanted to prove.
KevinCarde
2017-05-17 22:03:55
Whew! Carmen's side of the story now.
Whew! Carmen's side of the story now.
KevinCarde
2017-05-17 22:04:08
Now we will show a strategy that gives Carmen a probability at least $\frac{N-2}{2N} = \frac{M-1}{2M}$ of winning regardless of Waldo's strategy.
Now we will show a strategy that gives Carmen a probability at least $\frac{N-2}{2N} = \frac{M-1}{2M}$ of winning regardless of Waldo's strategy.
KevinCarde
2017-05-17 22:04:16
This time let 0 be Carmen's city. Then, if Waldo's first guess is $X \neq 0$, she guesses $2M - 1$ with probability $\frac{X}{2M}$ and 1 with probability $1 - \frac{X}{2M}$.
This time let 0 be Carmen's city. Then, if Waldo's first guess is $X \neq 0$, she guesses $2M - 1$ with probability $\frac{X}{2M}$ and 1 with probability $1 - \frac{X}{2M}$.
KevinCarde
2017-05-17 22:04:26
We will show that after this one guess Carmen has won with probability at least $\frac{M-1}{2M}$.
We will show that after this one guess Carmen has won with probability at least $\frac{M-1}{2M}$.
KevinCarde
2017-05-17 22:04:45
Let $W$ be Waldo's city, and let $w(X - W)$ be the probability of his guessing $X$ in the first guess (note that this probability isn't dependent on anything but the relative position of $W$ and $X$, because that's all Waldo knows).
Let $W$ be Waldo's city, and let $w(X - W)$ be the probability of his guessing $X$ in the first guess (note that this probability isn't dependent on anything but the relative position of $W$ and $X$, because that's all Waldo knows).
KevinCarde
2017-05-17 22:05:00
Suppose $W = 2M - 1$. Then if Waldo guesses $X$, the probability of Carmen winning is $\frac{X}{2M}$ (even if $X = 0$, because then Carmen loses immediately). So, the probability of Carmen's winning is at least
$$\sum_{i=0}^{2M-1} w(i+1)\frac{i}{2M} = \sum_{i=1}^{2M}w(i)\frac{i-1}{2M}.$$
Suppose $W = 2M - 1$. Then if Waldo guesses $X$, the probability of Carmen winning is $\frac{X}{2M}$ (even if $X = 0$, because then Carmen loses immediately). So, the probability of Carmen's winning is at least
$$\sum_{i=0}^{2M-1} w(i+1)\frac{i}{2M} = \sum_{i=1}^{2M}w(i)\frac{i-1}{2M}.$$
KevinCarde
2017-05-17 22:05:13
Now suppose $W = 1$. Then if Waldo guesses $X$, the probability of Carmen winning is $1-\frac{X} {2M}$ (unless $X = 0$, because then Carmen loses immediately). So, the probability of Carmen's winning in this case is at least
$$\sum_{i=1}^{2M}w(i-1)(1-\frac{i}{2M} = \sum_{i=0}^{2M-1} w(i)(1-\frac{i+1}{2M}).$$
Now suppose $W = 1$. Then if Waldo guesses $X$, the probability of Carmen winning is $1-\frac{X} {2M}$ (unless $X = 0$, because then Carmen loses immediately). So, the probability of Carmen's winning in this case is at least
$$\sum_{i=1}^{2M}w(i-1)(1-\frac{i}{2M} = \sum_{i=0}^{2M-1} w(i)(1-\frac{i+1}{2M}).$$
KevinCarde
2017-05-17 22:05:27
Each case is equally likely, so the total probability is at least
$$\frac12\left(w(0)(1-\frac{1}{2M}) + w(2M)(1-\frac{1}{2M}) + \sum_{i=1}^{2M-1} w(i)(1-\frac{2}{2M})\right).$$
That’s
$$\frac12(w(0) + 1 - \frac{2}{2M}) \ge \frac{M-1}{2M},$$
which is what we wanted to prove.
Each case is equally likely, so the total probability is at least
$$\frac12\left(w(0)(1-\frac{1}{2M}) + w(2M)(1-\frac{1}{2M}) + \sum_{i=1}^{2M-1} w(i)(1-\frac{2}{2M})\right).$$
That’s
$$\frac12(w(0) + 1 - \frac{2}{2M}) \ge \frac{M-1}{2M},$$
which is what we wanted to prove.
KevinCarde
2017-05-17 22:06:00
Because Waldo has a strategy to win the game with probability at least $\frac{M+1}{2M}$, Carmen can't have a strategy which gives her higher probability than $\frac{M-1}{2M}$, and vice versa. Therefore both strategies are optimal.
Because Waldo has a strategy to win the game with probability at least $\frac{M+1}{2M}$, Carmen can't have a strategy which gives her higher probability than $\frac{M-1}{2M}$, and vice versa. Therefore both strategies are optimal.
KevinCarde
2017-05-17 22:06:21
Great! We're completely done... with the case where $N$ is even.
Great! We're completely done... with the case where $N$ is even.
KevinCarde
2017-05-17 22:06:42
Now let's solve the case of odd $N$!
Now let's solve the case of odd $N$!
340086
2017-05-17 22:07:02
...
...
mochi
2017-05-17 22:07:02
Done...almost.
Done...almost.
KevinCarde
2017-05-17 22:07:05
We're getting there
We're getting there
KevinCarde
2017-05-17 22:07:26
Let $G$ be the game with $N$ cities, and $G'$ be the game with $2N$ cities.
Let $G$ be the game with $N$ cities, and $G'$ be the game with $2N$ cities.
KevinCarde
2017-05-17 22:07:40
Also, let 0 be Waldo's city in both these games.
Also, let 0 be Waldo's city in both these games.
KevinCarde
2017-05-17 22:07:53
If Carmen's city in $G$ is 1, then
in $G'$ it's 1 too, otherwise it's $N - 1$ in $G$ and $2N - 1$ in $G'$.
If Carmen's city in $G$ is 1, then
in $G'$ it's 1 too, otherwise it's $N - 1$ in $G$ and $2N - 1$ in $G'$.
KevinCarde
2017-05-17 22:08:00
Let's map the moves in $G$ to $G'$:
Let's map the moves in $G$ to $G'$:
KevinCarde
2017-05-17 22:08:20
Waldo's guess $X$ is mapped to odd $X'$ such that $X \equiv X'$ (mod $N$), and Carmen's guess $Y$ is mapped to even $Y'$ such that $Y \equiv Y'$ (mod N).
Waldo's guess $X$ is mapped to odd $X'$ such that $X \equiv X'$ (mod $N$), and Carmen's guess $Y$ is mapped to even $Y'$ such that $Y \equiv Y'$ (mod N).
KevinCarde
2017-05-17 22:08:34
Because $N$ is odd, the definition determines unique $X'$ and $Y'$ modulo $2N$.
Because $N$ is odd, the definition determines unique $X'$ and $Y'$ modulo $2N$.
KevinCarde
2017-05-17 22:08:43
In this mapping a winning guess in $G$ is a winning guess in $G'$ and vice versa.
In this mapping a winning guess in $G$ is a winning guess in $G'$ and vice versa.
KevinCarde
2017-05-17 22:08:52
Also, the optimal strategy for Waldo for $G'$ requires him to guess only odd cities, so he can translate this strategy from $G'$ back to $G$ and have a probability $\frac{N+1}{2N}$ of winning.
Also, the optimal strategy for Waldo for $G'$ requires him to guess only odd cities, so he can translate this strategy from $G'$ back to $G$ and have a probability $\frac{N+1}{2N}$ of winning.
KevinCarde
2017-05-17 22:09:02
Similarly, Carmen can translate her strategy (because Carmen's optimal strategy for $G'$ requires her to guess only even cities when Waldo's city is 0) from $G'$ to G and have a probability at least $\frac{N-1}{2N}$ of winning.
Similarly, Carmen can translate her strategy (because Carmen's optimal strategy for $G'$ requires her to guess only even cities when Waldo's city is 0) from $G'$ to G and have a probability at least $\frac{N-1}{2N}$ of winning.
KevinCarde
2017-05-17 22:09:31
Because these probabilities sum to 1, these have to be optimal strategies for $G$!
Because these probabilities sum to 1, these have to be optimal strategies for $G$!
KevinCarde
2017-05-17 22:09:44
In conclusion, the optimal strategy gives Waldo and Carmen probabilities $\frac{N+1}{2N}$ and $\frac{N-1}{2N}$ respectively of winning when $N$ is odd and $\frac{N+2}{2N}$ and $\frac{N-2}{2N}$ respectively of winning when $N$ is even.
In conclusion, the optimal strategy gives Waldo and Carmen probabilities $\frac{N+1}{2N}$ and $\frac{N-1}{2N}$ respectively of winning when $N$ is odd and $\frac{N+2}{2N}$ and $\frac{N-2}{2N}$ respectively of winning when $N$ is even.
KevinCarde
2017-05-17 22:09:57
And... that's Problem 7!
And... that's Problem 7!
MarisaD
2017-05-17 22:10:06
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us. We hope you enjoyed working on the Quiz!
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us. We hope you enjoyed working on the Quiz!
KevinCarde
2017-05-17 22:10:07
(Thanks to Pesto as well for providing me notes to help me through this problem!)
(Thanks to Pesto as well for providing me notes to help me through this problem!)
MathPathogen
2017-05-17 22:10:17
Wow... so elegant.
Wow... so elegant.
MarisaD
2017-05-17 22:10:22
I agree!
I agree!
MarisaD
2017-05-17 22:10:26
If you have non-Quiz questions about the program and the application process, feel free to post your questions to http://www.artofproblemsolving.com/community/c135_mathcamp and we'll respond there.
If you have non-Quiz questions about the program and the application process, feel free to post your questions to http://www.artofproblemsolving.com/community/c135_mathcamp and we'll respond there.
MarisaD
2017-05-17 22:10:40
Meanwhile, thanks again, everybody - good night!
Meanwhile, thanks again, everybody - good night!
mochi
2017-05-17 22:10:43
All problems...officially solved. Mission accomplished...resume elevator music.
All problems...officially solved. Mission accomplished...resume elevator music.
MarisaD
2017-05-17 22:10:45
IvantheKingIII
2017-05-17 22:10:48
Thank you!
Thank you!
340086
2017-05-17 22:10:48
Good night
Good night
KevinCarde
2017-05-17 22:10:56
Good night everyone!
Good night everyone!
mochi
2017-05-17 22:11:12
Thanks for taking the time to go over the problems!
Thanks for taking the time to go over the problems!
mochi
2017-05-17 22:11:12
Good night
Good night
MarisaD
2017-05-17 22:11:20
Thanks for coming to the Jam!
Thanks for coming to the Jam!
IvantheKingIII
2017-05-17 22:11:27
good night!
good night!
goodbear
2017-05-17 22:11:32
good night
good night
MathPathogen
2017-05-17 22:11:56
pasta-yogurt!
pasta-yogurt!
Ninja531
2017-05-17 22:11:56
LauraZed
2017-05-17 22:13:10
Thank you all for joining us, and a big thanks to Marisa, Kevin, and Adam!
Thank you all for joining us, and a big thanks to Marisa, Kevin, and Adam!
LauraZed
2017-05-17 22:13:54
I'm going to close the classroom soon, but if you got here late or want to review what was covered, a transcript of this Math Jam will be posted soon here: http://www.aops.com/school/mathjams-transcripts
I'm going to close the classroom soon, but if you got here late or want to review what was covered, a transcript of this Math Jam will be posted soon here: http://www.aops.com/school/mathjams-transcripts
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
