Canada/USA Mathcamp Qualifying Quiz Math Jam

Go back to the Math Jam Archive

Copyright © 2017 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!
LauraZed 2017-05-17 19:30:58
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.
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.
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:
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.
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 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.
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.
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.
ItzVineeth 2017-05-17 19:32:44
Hello Ms. Debowsky!
ItzVineeth 2017-05-17 19:32:44
Hello Mr. Carde
ItzVineeth 2017-05-17 19:32:44
Future hello to Mr. Hesterberg
LauraZed 2017-05-17 19:32:46
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!
MarisaD 2017-05-17 19:32:56
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:
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!).
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!
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}$.
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).
LilliantheGeek 2017-05-17 19:34:07
astroroman 2017-05-17 19:34:07
MarisaD 2017-05-17 19:34:11
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 ), or check out the AoPS Jam about the program and the application process from a few months ago:
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:
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...
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.
MarisaD 2017-05-17 19:35:28
Ready? Here we got!
bobston314 2017-05-17 19:35:44
dawn1729 2017-05-17 19:35:44
Makorn 2017-05-17 19:35:44
Induction is my favorite
MarisaD 2017-05-17 19:35:53

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?






&1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 &2 & 1 & 3 & 1 & 2 & 1 & 5 \\

MarisaD 2017-05-17 19:36:13
And for kicks, let's keep going:






& 1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 6 \\

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?
Makorn 2017-05-17 19:37:07
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
bobston314 2017-05-17 19:37:07
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.
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?
ProGameXD 2017-05-17 19:38:11
odd days
Makorn 2017-05-17 19:38:11
She visits Client 1 on odd days
MathTechFire 2017-05-17 19:38:11
odd - 1
LilliantheGeek 2017-05-17 19:38:11
Lotta visits Client 1 every 2 days.
mathgirl16 2017-05-17 19:38:20
She visits 1 on every odd day
Thothdragonfly2 2017-05-17 19:38:29
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
Makorn 2017-05-17 19:38:29
Client 2 on days $2\mod4$, Client 3 on days $4\mod8$
LilliantheGeek 2017-05-17 19:38:29
Lotta visits Client 2 every 4 days.
reedmj 2017-05-17 19:38:40
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
bobston314 2017-05-17 19:38:40
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
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.
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}$.
LilliantheGeek 2017-05-17 19:39:19
I see powers of two!
Mario2357 2017-05-17 19:39:19
its like binary
MarisaD 2017-05-17 19:39:26
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.
astroroman 2017-05-17 19:39:53
this sequence reminds me of tower of hanoi
MarisaD 2017-05-17 19:40:00
MarisaD 2017-05-17 19:40:14
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
astroroman 2017-05-17 19:40:50
on 2^100?
Makorn 2017-05-17 19:40:50
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.)
goodbear 2017-05-17 19:41:13
3.47*(10^27) years after the sun explodes
MarisaD 2017-05-17 19:41:31
Okay, great: Let's justify that pattern!
MarisaD 2017-05-17 19:41:48
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}$."
futurewriter 2017-05-17 19:42:20
and we can prove by induction
bobston314 2017-05-17 19:42:20
Induction time!
astroroman 2017-05-17 19:42:20
lcalvert99 2017-05-17 19:42:20
Makorn 2017-05-17 19:42:20
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!)
MarisaD 2017-05-17 19:42:39
So, what's the base case?
Thothdragonfly2 2017-05-17 19:43:34
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.
MarisaD 2017-05-17 19:43:51
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?
astroroman 2017-05-17 19:44:26
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.
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
MarisaD 2017-05-17 19:44:38
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.
MarisaD 2017-05-17 19:44:53 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.
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?
astroroman 2017-05-17 19:45:26
every fourth day
ChaosImmortal 2017-05-17 19:45:26
Every fourth day
reedmj 2017-05-17 19:45:26
The days that are multiples of 4
EasyAs_Pi 2017-05-17 19:45:26
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.)
MarisaD 2017-05-17 19:45:47
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$."
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.
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$.
MarisaD 2017-05-17 19:46:27
When does Lotta visit Client $k+1$?
MathPathogen 2017-05-17 19:47:22
on the next open day.
reedmj 2017-05-17 19:47:22
After clients 1-k are happy
astroroman 2017-05-17 19:47:22
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.
awesomemaths 2017-05-17 19:47:22
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$.
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$.
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.
MarisaD 2017-05-17 19:48:02
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$.
MarisaD 2017-05-17 19:48:38
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.
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$.
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.
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.)
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}$.
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.
MarisaD 2017-05-17 19:50:12
That completes our induction!
MarisaD 2017-05-17 19:50:16
And we can conclude that Lotta will retire on Day $2^{100}$.
awesomemaths 2017-05-17 19:50:32
induction is really useful
MarisaD 2017-05-17 19:50:36
sbudaraj 2017-05-17 19:50:39
part b
MarisaD 2017-05-17 19:50:41
And yes!
MarisaD 2017-05-17 19:50:42
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.
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?
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?
GamerRonay 2017-05-17 19:51:29
2^99 days
Makorn 2017-05-17 19:51:29
The even days
ilovemath04 2017-05-17 19:51:29
goodbear 2017-05-17 19:51:29
richg 2017-05-17 19:51:29
Littlelachy 2017-05-17 19:51:29
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.
MarisaD 2017-05-17 19:51:51
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.
Mario2357 2017-05-17 19:53:53
also $2^99$
goodbear 2017-05-17 19:53:53
sorasoratkd7 2017-05-17 19:53:53
2^99 the same
ChaosImmortal 2017-05-17 19:53:53
MarisaD 2017-05-17 19:54:03
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).
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.
MarisaD 2017-05-17 19:54:18
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?)
MarisaD 2017-05-17 19:55:12
MarisaD 2017-05-17 19:55:15
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.
ilovemath04 2017-05-17 19:55:27
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.
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.
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.
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$.
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$.
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.
MarisaD 2017-05-17 19:57:04
We're almost done with #1!
MarisaD 2017-05-17 19:57:11
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.
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?
Littlelachy 2017-05-17 19:57:36
All of them.
sbudaraj 2017-05-17 19:57:36
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.
MarisaD 2017-05-17 19:57:49
Who will be happy on the morning of Day 3?
astroroman 2017-05-17 19:58:17
person 2
Makorn 2017-05-17 19:58:17
Client 2
MathPathogen 2017-05-17 19:58:17
only client 2.
richg 2017-05-17 19:58:17
Person 2
sbudaraj 2017-05-17 19:58:17
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.
MarisaD 2017-05-17 19:58:29
And on the morning of Day 4?
GamerRonay 2017-05-17 19:59:03
clients 1 and 2
Mario2357 2017-05-17 19:59:03
clients 1 and 2
richg 2017-05-17 19:59:03
persons 1 and 2
MarisaD 2017-05-17 19:59:08
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:
rafayaashary1 2017-05-17 19:59:17
use the binary representation of N
MathPathogen 2017-05-17 19:59:17
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.
astroroman 2017-05-17 19:59:33
binary use
GamerRonay 2017-05-17 19:59:33
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:
MarisaD 2017-05-17 19:59:45
\[ \begin{array}{c|ccccccc}

    Day \backslash Client& 1 & 2 & 3 & 4 & 5 & 6 & \cdots \\


     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?
astroroman 2017-05-17 20:00:33
the binary representation of n-1
goodbear 2017-05-17 20:00:33
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$.
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.
MarisaD 2017-05-17 20:00:59
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.
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.
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}$.
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.
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.
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.
MarisaD 2017-05-17 20:02:12
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:

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
MarisaD 2017-05-17 20:02:46
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.
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 \]
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 \]
MarisaD 2017-05-17 20:03:14
(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) \]
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}}. \]
MarisaD 2017-05-17 20:03:44
Nice that these behave so nicely!
MarisaD 2017-05-17 20:03:48
What happens when $k=0$?
LilliantheGeek 2017-05-17 20:04:31
ChaosImmortal 2017-05-17 20:04:31
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}} \]
MarisaD 2017-05-17 20:04:43
Okay, armed with this nice relation, let's dig into the problem.
MarisaD 2017-05-17 20:04:52
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

To get us started: what's the answer?
goodbear 2017-05-17 20:05:33
Makorn 2017-05-17 20:05:33
$2^{n-1}$ each
GamerRonay 2017-05-17 20:05:33
2^n-1 for both
awesomemaths 2017-05-17 20:05:33
MarisaD 2017-05-17 20:05:38
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$.
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} $?
goodbear 2017-05-17 20:06:15
MarisaD 2017-05-17 20:06:22
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}}$$


$$\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}$.
MarisaD 2017-05-17 20:06:46
And why do our two quantities sum to $2^n$?
astroroman 2017-05-17 20:07:11
because rows of pscal's triangle
awesomemaths 2017-05-17 20:07:11
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.$$
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}$.
goodbear 2017-05-17 20:07:32
binomial expansion
ChaosImmortal 2017-05-17 20:07:32
Because the binomial theorem
MarisaD 2017-05-17 20:07:37
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).
MarisaD 2017-05-17 20:07:45
And a nice concise version!
MarisaD 2017-05-17 20:07:47
Great. Onto the next part.
MarisaD 2017-05-17 20:07:58

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

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?
goodbear 2017-05-17 20:09:28
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.
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.)
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$:
MarisaD 2017-05-17 20:10:00
(Make your window wide for this!)
MarisaD 2017-05-17 20:10:07

& 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

MarisaD 2017-05-17 20:10:16
What pattern do you see for each $n$?
LilliantheGeek 2017-05-17 20:11:16
This diagonal pattern.
ChaosImmortal 2017-05-17 20:11:16
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
astroroman 2017-05-17 20:11:35
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$.
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.
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.
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).
MarisaD 2017-05-17 20:12:14
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),
MarisaD 2017-05-17 20:12:24
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!)
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.
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.
MarisaD 2017-05-17 20:12:50
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
MarisaD 2017-05-17 20:13:04
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.
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.
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},$$
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}$$
MarisaD 2017-05-17 20:14:06 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:
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}$,
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}$.
MarisaD 2017-05-17 20:14:44
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$).
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,
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.
MarisaD 2017-05-17 20:15:50
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!
MarisaD 2017-05-17 20:16:17
(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?
leum22 2017-05-17 20:16:49
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" -
MarisaD 2017-05-17 20:17:32
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.)
MarisaD 2017-05-17 20:18:06
Okay, on to part c:
MarisaD 2017-05-17 20:18:07

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?
MarisaD 2017-05-17 20:18:43
sorasoratkd7 2017-05-17 20:18:47
Fibonacci numbers
MathPathogen 2017-05-17 20:18:47
MarisaD 2017-05-17 20:18:51
MarisaD 2017-05-17 20:19:01
Precisely: $D_n = F_{n+1}$, where $F_n$ is the $n$th Fibonacci number. (Cool, right?)
LilliantheGeek 2017-05-17 20:19:06
The n+1th Fibonacci number.
MarisaD 2017-05-17 20:19:09
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.
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).

MarisaD 2017-05-17 20:19:44
(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}$:
MarisaD 2017-05-17 20:20:02

& 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 \\


MarisaD 2017-05-17 20:20:15
What pattern do you see this time?
bobston314 2017-05-17 20:20:45
stranger diagonals
LilliantheGeek 2017-05-17 20:20:45
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:
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.)
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.
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$).
MarisaD 2017-05-17 20:22:12
One last time: we can prove that this pattern holds by induction on $n$. (Are you surprised?)
MarisaD 2017-05-17 20:22:22
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}).\]
MarisaD 2017-05-17 20:22:41
Let's write down what happens when we move from $n$ to $n+1$.
goodbear 2017-05-17 20:22:47
astroroman 2017-05-17 20:22:47
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})\]
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}$.
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.
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.
MarisaD 2017-05-17 20:24:21
(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!
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.
MarisaD 2017-05-17 20:25:11
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$.
MarisaD 2017-05-17 20:25:51
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!).
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?
MathPathogen 2017-05-17 20:27:24
yeah, b does it trivially.
mathgirl16 2017-05-17 20:27:24
MarisaD 2017-05-17 20:27:40
Yep, starting with part (b) is the slicker stragy.
MarisaD 2017-05-17 20:27:44
MarisaD 2017-05-17 20:27:51
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?
bobston314 2017-05-17 20:28:33
LilliantheGeek 2017-05-17 20:28:33
goodbear 2017-05-17 20:28:33
astroroman 2017-05-17 20:28:33
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.
MarisaD 2017-05-17 20:28:50
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.
goodbear 2017-05-17 20:29:29
1 or 2
MarisaD 2017-05-17 20:29:31
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.
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.
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.
bobston314 2017-05-17 20:30:07
Once, except for Jane and Sam (twice)
MathPathogen 2017-05-17 20:30:07
If two overlaps, the contribute 4.
MarisaD 2017-05-17 20:30:15
MarisaD 2017-05-17 20:30:23
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,
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.
MarisaD 2017-05-17 20:30:51
Now we can put it all together!
MarisaD 2017-05-17 20:30:56
We have $2(A-C) + 4C = 2NB$,
MarisaD 2017-05-17 20:31:01
so $A+C = NB$,
MarisaD 2017-05-17 20:31:05
and $N = \frac{A+C}{B}$.
MarisaD 2017-05-17 20:31:10
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):
MarisaD 2017-05-17 20:31:35
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
MarisaD 2017-05-17 20:31:40
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."
MarisaD 2017-05-17 20:32:06
Any questions before we move on?
awesomemaths 2017-05-17 20:32:30
part a is 12 right???
MarisaD 2017-05-17 20:32:33
Sure is!
MarisaD 2017-05-17 20:32:36
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!
awesomemaths 2017-05-17 20:33:03
hi kevin
Mario2357 2017-05-17 20:33:11
goodbear 2017-05-17 20:33:11
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
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!
KevinCarde 2017-05-17 20:33:48
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$.
KevinCarde 2017-05-17 20:34:39
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.
KevinCarde 2017-05-17 20:35:00
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.
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$.
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}.\]
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!
KevinCarde 2017-05-17 20:36:09
So, quick question: What goes wrong if $k=2$ or $k=3$?
astroroman 2017-05-17 20:36:53
divides by 0z?
ChaosImmortal 2017-05-17 20:36:53
Denominator is 0
rafayaashary1 2017-05-17 20:36:53
very few possibilities for a
BobaFett101 2017-05-17 20:36:53
denominator is negative or 0
Mario2357 2017-05-17 20:36:53
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.
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.
KevinCarde 2017-05-17 20:37:29
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$.
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)$.
Mario2357 2017-05-17 20:38:03
KevinCarde 2017-05-17 20:38:10
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.
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.)
KevinCarde 2017-05-17 20:38:50
That's the even case.
KevinCarde 2017-05-17 20:38:51
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$.
KevinCarde 2017-05-17 20:39:13
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
KevinCarde 2017-05-17 20:40:43
If we have $k=2a+3$, the denominator becomes $2$
Mario2357 2017-05-17 20:40:47
KevinCarde 2017-05-17 20:40:52
Good fix
KevinCarde 2017-05-17 20:41:06
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!
KevinCarde 2017-05-17 20:41:25
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.
KevinCarde 2017-05-17 20:41:51
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$.
KevinCarde 2017-05-17 20:42:12
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.
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)}.\]
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.
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.
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$?
Ninja531 2017-05-17 20:43:49
rafayaashary1 2017-05-17 20:43:49
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$.
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$.
KevinCarde 2017-05-17 20:44:32
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.
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!)
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$.
KevinCarde 2017-05-17 20:45:19
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?
LilliantheGeek 2017-05-17 20:46:14
$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.
LilliantheGeek 2017-05-17 20:46:39
$1$ or $1009$
astroroman 2017-05-17 20:46:39
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.
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$.
KevinCarde 2017-05-17 20:47:52
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
mathgirl16 2017-05-17 20:48:06
2, 3, 7
KevinCarde 2017-05-17 20:48:18
but this severely limits what the possibilities are for $1008-a$
astroroman 2017-05-17 20:48:22
chemdude 2017-05-17 20:48:22
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.
KevinCarde 2017-05-17 20:48:48
So we want $1008-a$ to be the biggest factor of $1008$ possible.
goodbear 2017-05-17 20:48:57
MathPathogen 2017-05-17 20:48:57
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.
MathPathogen 2017-05-17 20:49:17
But that fails.
KevinCarde 2017-05-17 20:49:26
(The pesky $2$ in the denominator gets us in trouble!)
KevinCarde 2017-05-17 20:49:32
What's the next biggest factor?
LilliantheGeek 2017-05-17 20:50:02
awesomemaths 2017-05-17 20:50:02
mathgirl16 2017-05-17 20:50:02
MathPathogen 2017-05-17 20:50:02
Next largest is 336.
Ninja531 2017-05-17 20:50:02
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$.
goodbear 2017-05-17 20:50:23
mathgirl16 2017-05-17 20:50:23
it works!
KevinCarde 2017-05-17 20:50:27
Hooray !
awesomemaths 2017-05-17 20:50:32
LilliantheGeek 2017-05-17 20:50:33
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$.
KevinCarde 2017-05-17 20:51:02
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?
KevinCarde 2017-05-17 20:51:39
KevinCarde 2017-05-17 20:51:43
Let's call $k$ groovy if $\mathcal E_k$ has a unique solution.
awesomemaths 2017-05-17 20:51:49
funny name
KevinCarde 2017-05-17 20:51:51
(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?
goodbear 2017-05-17 20:52:56
mathgirl16 2017-05-17 20:52:56
astroroman 2017-05-17 20:52:56
not 2 or 3
MathPathogen 2017-05-17 20:52:56
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!
KevinCarde 2017-05-17 20:53:11
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$.
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!
KevinCarde 2017-05-17 20:54:06
What about $k=5$, $6$, or $7$? (Feel free to think about just one at a time!)
LilliantheGeek 2017-05-17 20:54:46
k=5 is groovy!
mathgirl16 2017-05-17 20:54:53
mathgirl16 2017-05-17 20:55:03
MathPathogen 2017-05-17 20:55:13
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.
MathPathogen 2017-05-17 20:55:31
8 is not.
KevinCarde 2017-05-17 20:55:37
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.
KevinCarde 2017-05-17 20:56:04
(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.
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}\]
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!
KevinCarde 2017-05-17 20:57:01
Thus every proper factor of $2r-1$ or $2r+1$ yields a solution to $\mathcal E_{2r}$.
aops_philip 2017-05-17 20:57:14
that copy and paste tho
KevinCarde 2017-05-17 20:57:20
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!
KevinCarde 2017-05-17 20:58:00
That does it for Lemma 1 (with a slight digression!).
LilliantheGeek 2017-05-17 20:58:07
Word of the day (night): groovy!
astroroman 2017-05-17 20:58:07
twin primes = groovy!
KevinCarde 2017-05-17 20:58:11
True on both counts!
KevinCarde 2017-05-17 20:58:23
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$.
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}\]
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.
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$!)
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.
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$.
KevinCarde 2017-05-17 20:59:54
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!
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.
KevinCarde 2017-05-17 21:00:29
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\}$.
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.
KevinCarde 2017-05-17 21:01:06
Is $k=8$ groovy, and which lemma tells us that?
MathPathogen 2017-05-17 21:01:33
7 and 9 are not twin primes.
astroroman 2017-05-17 21:01:33
lemma 1 says not groovy because 9
Buddy03 2017-05-17 21:01:38
No it is not
LilliantheGeek 2017-05-17 21:01:38
$k=8$ is not groovy, and Lemma 1 tells us that.
KevinCarde 2017-05-17 21:01:43
KevinCarde 2017-05-17 21:01:49
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.
KevinCarde 2017-05-17 21:02:09
What does Lemma 1 say about the odd one?
LilliantheGeek 2017-05-17 21:02:39
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!
KevinCarde 2017-05-17 21:03:05
Lemma 2 tells us the odd one must be divisible by $3$.
Buddy03 2017-05-17 21:03:14
K=2r+1=0 mod3
KevinCarde 2017-05-17 21:03:22
And then Lemma 1
MathPathogen 2017-05-17 21:03:24
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!
KevinCarde 2017-05-17 21:03:44
Therefore, there can be no other pairs of consecutive groovy numbers!
Buddy03 2017-05-17 21:03:57
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 .
KevinCarde 2017-05-17 21:04:25
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.
KevinCarde 2017-05-17 21:04:55
PROBLEM 5a: $N+10$ and $3N+1$

How many wizards could live together in such a tower?
KevinCarde 2017-05-17 21:05:17
LilliantheGeek 2017-05-17 21:05:22
KevinCarde 2017-05-17 21:05:25
(excitement, not factorial)
goodbear 2017-05-17 21:05:29
astroroman 2017-05-17 21:05:29
LilliantheGeek 2017-05-17 21:05:39
3 wizards only! These are some very picky wizards!
astroroman 2017-05-17 21:05:39
but only 3
Buddy03 2017-05-17 21:05:39
acegikmoqsuwy2000 2017-05-17 21:05:39
$\lfloor \pi\rfloor$
KevinCarde 2017-05-17 21:05:43
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$.
KevinCarde 2017-05-17 21:06:12
How does the $3N+1$ operation affect residues mod $10$?
bobston314 2017-05-17 21:06:36
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}$.
bobston314 2017-05-17 21:07:00
e.g. 2 mod 10 goes to 7 mod 10
KevinCarde 2017-05-17 21:07:07
Where does $7$ go next?
Buddy03 2017-05-17 21:07:14
hilarious 2017-05-17 21:07:18
back to 2
Mario2357 2017-05-17 21:07:20
but 7 goes back to 2 and ur done with the loop
astroroman 2017-05-17 21:07:20
KevinCarde 2017-05-17 21:07:26
Right. We're getting cycles!
Mario2357 2017-05-17 21:07:28


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.
KevinCarde 2017-05-17 21:07:41
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!
KevinCarde 2017-05-17 21:08:10
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?
MathPathogen 2017-05-17 21:08:32
infinitely less icky.
MathPathogen 2017-05-17 21:08:32
KevinCarde 2017-05-17 21:08:40
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!
KevinCarde 2017-05-17 21:09:01
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.
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.
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$.
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.
KevinCarde 2017-05-17 21:10:00
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.
KevinCarde 2017-05-17 21:10:15
Buddy03 2017-05-17 21:10:23
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.
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$.
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).
KevinCarde 2017-05-17 21:10:59
What can we do from floor $4n$?
KevinCarde 2017-05-17 21:11:05
Where can we go next?
MathPathogen 2017-05-17 21:11:24
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!
bobston314 2017-05-17 21:11:48
bobston314 2017-05-17 21:11:48
can't go up b/c contradiction of c
KevinCarde 2017-05-17 21:11:56
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.
KevinCarde 2017-05-17 21:12:13
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.
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!
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$.
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$.
KevinCarde 2017-05-17 21:12:59
We conclude that distinct floors that are $2 \pmod4$ cannot be connected!
astroroman 2017-05-17 21:13:25
so infinite wizards?
Mario2357 2017-05-17 21:13:35
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.
KevinCarde 2017-05-17 21:14:04
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?
KevinCarde 2017-05-17 21:14:21
KevinCarde 2017-05-17 21:14:43
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.
MathPathogen 2017-05-17 21:15:02
Now on to the super picky wizard.
BobaFett101 2017-05-17 21:15:02
goodbear 2017-05-17 21:15:02
1 fat wizard
Mario2357 2017-05-17 21:15:02
dawn1729 2017-05-17 21:15:02
astroroman 2017-05-17 21:15:02
only one?
KevinCarde 2017-05-17 21:15:11
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.
KevinCarde 2017-05-17 21:15:34
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.
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!
KevinCarde 2017-05-17 21:15:57
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$.
KevinCarde 2017-05-17 21:16:08
$a = 3r$: How do we descend to a lower floor?
Mario2357 2017-05-17 21:16:42
6r+1 then 2r
acegikmoqsuwy2000 2017-05-17 21:16:42
up to $6n+1$ and down to $2n$
bobston314 2017-05-17 21:16:42
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.
KevinCarde 2017-05-17 21:16:57
Next case, $a = 3r+1$: How do we descend to a lower floor?
acegikmoqsuwy2000 2017-05-17 21:17:22
directly down to $r$
Mario2357 2017-05-17 21:17:22
hilarious 2017-05-17 21:17:22
MathPathogen 2017-05-17 21:17:22
take a blue portal downstairs.
jg123 2017-05-17 21:17:22
down the 3n+1 portal
BobaFett101 2017-05-17 21:17:22
go to r
PhoneChargers 2017-05-17 21:17:22
3r+1 to r
KevinCarde 2017-05-17 21:17:27
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$.
MathPathogen 2017-05-17 21:17:41
Now, on to the case that cost me days to do...
KevinCarde 2017-05-17 21:17:43
Uh oh
KevinCarde 2017-05-17 21:17:44
$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.
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!)
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\]
KevinCarde 2017-05-17 21:19:02
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!
KevinCarde 2017-05-17 21:19:11
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?
KevinCarde 2017-05-17 21:19:25
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.
KevinCarde 2017-05-17 21:19:55
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.
KevinCarde 2017-05-17 21:20:27
And that justifies only $1$ wizard in the tower!
Buddy03 2017-05-17 21:20:36
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!
KevinCarde 2017-05-17 21:21:00
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!
MathPathogen 2017-05-17 21:21:17
yay for brute force!
KevinCarde 2017-05-17 21:21:22
It has its place sometimes .
KevinCarde 2017-05-17 21:21:28
OK, onwards to Problem 6, something very different!
KevinCarde 2017-05-17 21:21:41
(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?
KevinCarde 2017-05-17 21:22:12
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.
KevinCarde 2017-05-17 21:22:42
But it turns out it's not going to be very nice -- hang in there!
MathPathogen 2017-05-17 21:22:51
PhoneChargers 2017-05-17 21:22:51
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.
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.
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.
KevinCarde 2017-05-17 21:23:28
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.
KevinCarde 2017-05-17 21:23:46
(And yes, I just verbed "triforce".)
acegikmoqsuwy2000 2017-05-17 21:24:04
and you also verbed "verb"
KevinCarde 2017-05-17 21:24:07
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).
KevinCarde 2017-05-17 21:24:31
You can check this by applying the triforce property twice.
LilliantheGeek 2017-05-17 21:24:34
There should be a dictionary on improper words used in this Math Jam.
KevinCarde 2017-05-17 21:24:37
Groovy idea!
KevinCarde 2017-05-17 21:24:51
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.
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).
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!)
KevinCarde 2017-05-17 21:25:41
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.
KevinCarde 2017-05-17 21:25:53
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.
KevinCarde 2017-05-17 21:26:12
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?
KevinCarde 2017-05-17 21:26:27
Good question!
KevinCarde 2017-05-17 21:26:39
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.
KevinCarde 2017-05-17 21:27:29
(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:
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:
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)\]
LilliantheGeek 2017-05-17 21:28:34
Pretty triangles!
LilliantheGeek 2017-05-17 21:28:34
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 .
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.
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!
bobston314 2017-05-17 21:29:21
PhoneChargers 2017-05-17 21:29:24
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.
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.
KevinCarde 2017-05-17 21:30:32
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!
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!
astroroman 2017-05-17 21:31:01
Next problem!
KevinCarde 2017-05-17 21:31:10
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.)
Kamior 2017-05-17 21:32:18

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.
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.
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:
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.
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.
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?
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.)
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$.
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.)
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.
Kamior 2017-05-17 21:38:16
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?
MathPathogen 2017-05-17 21:40:24
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.
Kamior 2017-05-17 21:40:49
Let's see an example:
Kamior 2017-05-17 21:40:56
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).
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.
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.)
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:
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.
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.
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?
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.)
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):
MarisaD 2017-05-17 21:47:59
[Elevator music plays during a brief pause while Pesto's computer restarts.]
jg123 2017-05-17 21:48:29
this is a strange game
MarisaD 2017-05-17 21:48:38
It sure is! But a mathematically interesting one.
Ninja531 2017-05-17 21:48:42
[Gentle watered down jazz slowly starts]
bobston314 2017-05-17 21:48:42
some elevator music
jg123 2017-05-17 21:49:32
actual elevator music:
MathPathogen 2017-05-17 21:49:32
[Jeopardy music begins]
LilliantheGeek 2017-05-17 21:49:37
[Music that plays in Gym to make it less awkward while you're running)
bobston314 2017-05-17 21:50:08
in the meantime
bobston314 2017-05-17 21:50:08
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.
IvantheKingIII 2017-05-17 21:52:26
[Kahoot music begins]
Ninja531 2017-05-17 21:54:12
[song remixes from 2012] ]
bobston314 2017-05-17 21:54:12
*lightly tapping foot*
KevinCarde 2017-05-17 21:54:20
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.
KevinCarde 2017-05-17 21:54:42
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.
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:
KevinCarde 2017-05-17 21:55:39
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.
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.
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$.
KevinCarde 2017-05-17 21:57:04
Now let's see what Carmen can do.
KevinCarde 2017-05-17 21:57:05
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.
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.
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.
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$.
KevinCarde 2017-05-17 21:58:44
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... ...
KevinCarde 2017-05-17 21:59:08
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!)
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:
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$.
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.
KevinCarde 2017-05-17 22:01:23
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).
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$.
KevinCarde 2017-05-17 22:02:33
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.
KevinCarde 2017-05-17 22:03:01
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.
KevinCarde 2017-05-17 22:03:55
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.
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}$.
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}$.
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).
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}.$$
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}).$$
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).$$


$$\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.
KevinCarde 2017-05-17 22:06:21
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$!
bobston314 2017-05-17 22:07:02
LilliantheGeek 2017-05-17 22:07:02
KevinCarde 2017-05-17 22:07:05
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.
KevinCarde 2017-05-17 22:07:40
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'$.
KevinCarde 2017-05-17 22:08:00
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).
KevinCarde 2017-05-17 22:08:34
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.
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.
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.
KevinCarde 2017-05-17 22:09:31
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.
KevinCarde 2017-05-17 22:09:57
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!
KevinCarde 2017-05-17 22:10:07
(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.
MarisaD 2017-05-17 22:10:22
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 and we'll respond there.
MarisaD 2017-05-17 22:10:40
Meanwhile, thanks again, everybody - good night!
LilliantheGeek 2017-05-17 22:10:43
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!
bobston314 2017-05-17 22:10:48
Good night
KevinCarde 2017-05-17 22:10:56
Good night everyone!
LilliantheGeek 2017-05-17 22:11:12
Thanks for taking the time to go over the problems!
LilliantheGeek 2017-05-17 22:11:12
Good night
MarisaD 2017-05-17 22:11:20
Thanks for coming to the Jam!
IvantheKingIII 2017-05-17 22:11:27
good night!
goodbear 2017-05-17 22:11:32
good night
MathPathogen 2017-05-17 22:11:56
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!
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:

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


Stay Connected

Subscribe to get news and
updates from AoPS, or Contact Us.
© 2017
AoPS Incorporated
Invalid username
Login to AoPS