Summer schedule is now available! Enroll today to secure your spot!

Mathcamp 2019 Qualifying Quiz Math Jam

Go back to the Math Jam Archive

This Math Jam will discuss solutions to the 2019 Mathcamp Qualifying Quiz. Mathcamp is an intensive 5-week-long summer program for mathematically talented high school students. More than just a summer camp, Mathcamp is a vibrant community, made up of a wide variety of people who share a common love of learning and passion for mathematics.

Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.

Facilitator: Marisa Debowsky

vapodaca 2019-05-14 19:30:37
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
vapodaca 2019-05-14 19:30:49
Before I introduce our guests, let me briefly explain how our online classroom works.
vapodaca 2019-05-14 19:30:57
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
vapodaca 2019-05-14 19:31:03
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
vapodaca 2019-05-14 19:31:18
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
vapodaca 2019-05-14 19:31:30
Many AoPS instructors, assistants, and students are alumni of this outstanding problem!
vapodaca 2019-05-14 19:31:42
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 2018 Qualifying Quiz at http://www.mathcamp.org/prospectiveapplicants/quiz/index.php . In this Math Jam, the following Canada/USA Mathcamp admission committee members will discuss the problems from this year's Qualifying Quiz:
vapodaca 2019-05-14 19:31:59
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
vapodaca 2019-05-14 19:32:13
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
vapodaca 2019-05-14 19:32:23
Pesto (Adam Hesterberg, Kamior) is an MIT postdoc. He's been teaching Complexity Theory and playing cryptic word games at Mathcamp most summers since 2012.
vapodaca 2019-05-14 19:32:42
Let's turn the room over to Marisa now to get us started!
MarisaD 2019-05-14 19:32:55
Thanks! Hi, everybody, and welcome to the (now annual) Mathcamp Qualifying Quiz Jam!
MarisaD 2019-05-14 19:33:01
A big thanks as always to @vapodaca, @rrusczyk, and the AoPS team for hosting us.
MarisaD 2019-05-14 19:33:11
Kevin, Pesto, and I are here to talk about the Mathcamp 2019 QQ. To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/2019/qquiz.php
MarisaD 2019-05-14 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 2019-05-14 19:33:32
If you applied this year, I strongly recommend having your solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
MarisaD 2019-05-14 19:33:41
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:

We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.

This should give you:

We claim that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
MarisaD 2019-05-14 19:33:50
Also, as @vapodaca pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
MarisaD 2019-05-14 19:34:08
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/ ), or check out the AoPS Jam about the program and the application process from a few months ago: https://artofproblemsolving.com/school/mathjams-transcripts?id=485
MarisaD 2019-05-14 19:34:18
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
Quod.Erat.Demonstrandum 2019-05-14 19:34:22
Is this like a lecture or a Q and A
MarisaD 2019-05-14 19:34:33
Both! We'll guide, but it will be an interactive session.
MarisaD 2019-05-14 19:34:37
We've got a lot to cover in the next two hours, so let's get started!
MarisaD 2019-05-14 19:34:44
Problem 1 Statement:
If you take a scientific calculator, type in any number, and then alternate applying the operations ATAN and COS, then eventually you will reach a point where you run into a cycle: after every COS step, you will see a result of approximately 0.786 (and after every ATAN step, a result of approximately 0.666 radians, or 38.2 degrees).
MarisaD 2019-05-14 19:34:54
Problem 1a: Find a formula for the number you get by starting with 0 and then applying the procedure "apply ATAN and then COS" $n$ times.
MarisaD 2019-05-14 19:35:04
PROBLEM 1a SOLUTION
MarisaD 2019-05-14 19:35:28
Let's jump right in. For convenience, I'm going to let $f(x)$ denote $\cos(\arctan(x))$. What we want to know here is what happens when we compose $f$ with itself over and over.
MarisaD 2019-05-14 19:35:37
Let's see what we can do with right triangle trig.
MarisaD 2019-05-14 19:35:48
So, what's $\arctan(x)$? It's the angle $\theta$ whose tangent is $x$, right? In the SOHCAHTOA framework, let's set up a right triangle with sides 1 and $x$ and hypotenuse $\sqrt{1+x^2}$.
MarisaD 2019-05-14 19:36:02
Denote the angle opposite $x$ and adjacent to 1 to be $\theta$. Then, as we planned, $\arctan(x)=\theta$, and what is the cosine of this angle?
beiqiang 2019-05-14 19:37:20
1 / sqrt(1 + x^2)
mathpenguin7 2019-05-14 19:37:20
1/sqrt(1+x^2)
MarvelousMasterMark 2019-05-14 19:37:20
$\dfrac{1}{\sqrt{1+x^2}}$
turtles0120 2019-05-14 19:37:20
1/sqrt {1+x^2}
ilovemath04 2019-05-14 19:37:20
1/sqrt(1+x^2)
eisirrational 2019-05-14 19:37:20
$\cos A=\frac{1}{\sqrt{x^2+1}}$
MarisaD 2019-05-14 19:37:24
Right: it's

$$\cos(\theta) = \frac{\text{adj}}{\text{hyp}} = \frac{1}{\sqrt{1+x^2}}.$$
MarisaD 2019-05-14 19:37:30
In other words, $$f(x) = \frac{1}{\sqrt{1+x^2}}.$$
MarisaD 2019-05-14 19:37:49
(In the solutions we read, some of you derived this relationship algebraically, using the identity $sec^2(\theta) = 1+\tan^2(\theta).$ That's also a good way to get there.)
MarisaD 2019-05-14 19:37:57
Should we stop to worry about $x$ being negative and therefore not being a nice side length?
MarisaD 2019-05-14 19:39:11
Lots of folks are noting that $x$ is squared here. But there's a better reason to be happy:
MarisaD 2019-05-14 19:39:19
The range of arctan is $(-\pi/2, \pi/2)$, and $\cos(\theta)$ is positive when $\theta\in (-\pi/2,\pi/2)$, so $\cos(\arctan(x))>0$. So our triangle is fine.
MarisaD 2019-05-14 19:39:32
Back to our function, which we want to compose with itself over and over. Let's build a sequence using the results of applying this function:
MarisaD 2019-05-14 19:39:37
Set $x_0=0$ and define $x_n = f^n(x)$ (that is, the result of applying the arctan/cos functions $n$ times).
MarisaD 2019-05-14 19:39:44
Since we have a nice expression for $f$, we can produce a nice expression for $x_n$. What is it?
beiqiang 2019-05-14 19:40:53
f(x-1)
beiqiang 2019-05-14 19:40:53
f(x_n-1)
MarisaD 2019-05-14 19:40:59
Right: $$x_n = f(f^{n-1}(x)) = f(x_{n-1}) = \frac{1}{1+(x_{n-1})^2} $$
MarisaD 2019-05-14 19:41:12
This might look a little more straightforward if we phrased it as:

$$(x_n)^2 = \frac{1}{1 + (x_{n-1})^2}$$
MarisaD 2019-05-14 19:41:20
I'd really just like to rid myself of squares, so let me define a new sequence $a_n$ such that $a_n = (x_n)^2$.
MarisaD 2019-05-14 19:41:27
In other words, $a_n$ is the sequence such that $$a_0=0 \text{ and } a_{n+1} = \frac{1}{1+a_n}$$
MarisaD 2019-05-14 19:41:33
Now, that sure looks like a nice sequence. What are the first few terms?
mathpenguin7 2019-05-14 19:42:20
0,1,1/2,2/3,3/5
ilovemath04 2019-05-14 19:42:20
0,1,1/2,2/3,3/5,5/8,... fibonacci
MP2016p42 2019-05-14 19:42:20
0,1,1/2
MarisaD 2019-05-14 19:42:22
Right! We get $\frac{1}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{5}, \dots$
MarisaD 2019-05-14 19:42:36
And those sure are ratios of Fibonacci numbers.
MarisaD 2019-05-14 19:42:41
So I claim that $$a_n = \frac{F_{n}}{F_{n+1}}$$ where $F_n$ is the $n$th Fibonacci number ($F_0 = 0$, $F_1 = 1, \dotsc$).
alokkumar1974 2019-05-14 19:42:49
Fibbonaci!
MP2016p42 2019-05-14 19:42:49
lets test it?
Z_Math404 2019-05-14 19:42:49
induction!
MarisaD 2019-05-14 19:42:52
Yeah!
MarisaD 2019-05-14 19:42:57
Induction it is.
MarisaD 2019-05-14 19:43:03
For our base case, $a_0 = \frac{0}{1}$. Check.
MarisaD 2019-05-14 19:43:09
For the inductive hypothesis, suppose $a_n = \frac{F_n}{F_{n+1}}$.
MarisaD 2019-05-14 19:43:15
Then, looking at the next term:

$$a_{n+1} = \frac{1}{1+a_n} = \frac{1}{1+\frac{F_n}{F_{n+1}}}$$
MarisaD 2019-05-14 19:43:24
And simplifying:

$$a_{n+1} = \frac{F_n}{F_{n+1}+F_n} = \frac{F_{n+1}}{F_{n+2}}$$
MarisaD 2019-05-14 19:43:31
So, finally, returning to our original sequence $x_n$, we get what we came for:
MarisaD 2019-05-14 19:43:35
$$ f^n(x) = x_n = \sqrt{a_n} = \sqrt{\frac{F_n}{F_{n+1}}} $$
FIREDRAGONMATH16 2019-05-14 19:43:48
nice!
MarisaD 2019-05-14 19:43:52
Right? I think it's really pretty!
MarisaD 2019-05-14 19:43:57
On to part b:
MarisaD 2019-05-14 19:44:08
Problem 1b: Find an exact formula for the 0.786 number. (You do not need to prove that the formula that you found in part (a) converges to this number.)
MarisaD 2019-05-14 19:44:36
PROBLEM 1b SOLUTION
Some people used Binet's formula here; I'll do something a little simpler.
MarisaD 2019-05-14 19:44:47
Suppose our sequence $x_n$ converges to a limit $L$.
MarisaD 2019-05-14 19:44:53
Now, let's make a new sequence, where each element is $f(x_n)$. That should converge to $f(L)$.
MarisaD 2019-05-14 19:45:00
With our trusty definition of $f$, that means the sequence of terms $f(x_n)$ converges to $f(L) = \frac{1}{\sqrt{1+L^2}}$.
MarisaD 2019-05-14 19:45:10
But those sequences are really built from the same terms, just shifted over by one (since $f(x_n) = x_{n+1}$). They really should converge to the same limit, then.
MarisaD 2019-05-14 19:45:19
So:

$$L = \frac{1}{\sqrt{1+L^2}}$$
MarisaD 2019-05-14 19:45:28
Now we do some algebra: square both sides, rearrange terms, and we get $L^4 + L^2 - 1 = 0$. By the quadratic formula,

$$L^2 = \frac{-1 \pm \sqrt{5}}{2}$$
MarisaD 2019-05-14 19:45:41
We get to pick the positive root here. Why?
beiqiang 2019-05-14 19:45:54
L > 0
Z_Math404 2019-05-14 19:45:54
L^2 is positive
AIME12345 2019-05-14 19:45:54
because $x_n$ is positive
MarvelousMasterMark 2019-05-14 19:46:05
Because our sequence is restricted to positive numbers.
MarisaD 2019-05-14 19:46:13
Yep. As we checked back at the beginning, all the terms of our sequence are positive.
MarisaD 2019-05-14 19:46:18
So, finally, the limit itself is $$L = \sqrt{ \frac{-1 + \sqrt{5}}{2}} \approx 0.768 $$
MarisaD 2019-05-14 19:46:25
I used Wolfram Alpha to check: https://www.wolframalpha.com/input/?i=sqrt((-1%2Bsqrt(5))%2F2)
MarisaD 2019-05-14 19:46:33
There we have it!
MarisaD 2019-05-14 19:46:51
We picked this problem because it showcases just really careful use of Precalculus, and shows a cool connection between trig functions and a familiar sequence, and gives an opportunity to use induction. The most common issues in solutions were just not showing enough justification for arguments, but we were happy to see a lot of applicants getting the central ideas.
MarisaD 2019-05-14 19:47:09
Onwards to problem 2.
KevinCarde 2019-05-14 19:47:37
Hi everyone! I'll take it from MarisaD for a bit here .
KevinCarde 2019-05-14 19:47:40
Problem 2 Statement:
Susan and Eric are playing a dice game, with standard six-sided dice which have an equal probability of rolling each integer from 1 through 6. Each player takes turns scoring points as follows.

On Susan's turn, she rolls a die. If it's a 1, she rolls two dice in its place, continuing to replace any 1s by two new dice. When finally no 1s are showing, Susan scores points equal to the sum of the remaining dice, and then her turn ends. (For example, suppose she rolls a 1. Then it gets replaced by two dice; if these are a 3 and a 1, the 3 remains and the 1 gets replaced by two more; if these are a 2 and a 4, then Susan stops and scores 3+2+4=9 points.)

On Eric's turn, he rolls a die. If it's even, he replaces it with a roll of two dice; if the new total is even, he replaces it with a roll of three dice, etc. He continues to roll one more die than previously as long as his total is even. When he finally rolls an odd total, Eric scores that many points, and then his turn ends.

On average, how many points do Susan and Eric each score on a turn?
KevinCarde 2019-05-14 19:47:59
PROBLEM 2 SOLUTION
KevinCarde 2019-05-14 19:48:08
Since Susan and Eric don't interact with each other in any way, we will computed their average scores separately.
KevinCarde 2019-05-14 19:48:32
There are several different approaches you can take. One of my favorites involves generating functions, but I'll stick to precalculus-level topics.
KevinCarde 2019-05-14 19:48:41
But feel free to think about variants on your own time!
KevinCarde 2019-05-14 19:48:47
Susan's Score
KevinCarde 2019-05-14 19:49:00
Susan replaces any 1s she rolls with a pair of new dice. She could potentially roll ten, or a hundred, or millions of dice!
KevinCarde 2019-05-14 19:49:13
So we'll have to be a little clever to figure out how to compute this: we can't just add up all the possibilities, as there are an infinite number of them!
KevinCarde 2019-05-14 19:49:40
Let's start simple. Assume Susan doesn't roll a 1. What is the probability that she doesn't roll a 1? What's her average score, given that she doesn't roll a 1?
KevinCarde 2019-05-14 19:49:59
(Several of you are doing many steps at once! But for Susan at least, we'll take it one step at a time)
FIREDRAGONMATH16 2019-05-14 19:50:49
5/6 probability
alokkumar1974 2019-05-14 19:50:49
5/6 is the probability if she doesnt roll one.
aggu123 2019-05-14 19:50:49
Probability is 5/6, average score is 4
mathpenguin7 2019-05-14 19:50:49
Probability: 5/6 Average score: 4
VishnuM34 2019-05-14 19:50:49
5/6
Damalone 2019-05-14 19:50:49
She doesn't roll a 1 with probability 5/6. Her average score then would be 4
Tinjeson347 2019-05-14 19:50:49
5/6
FIREDRAGONMATH16 2019-05-14 19:50:49
average score: $(2+3+4+5+6)/5 = 4$
Tinjeson347 2019-05-14 19:50:49
4
alokkumar1974 2019-05-14 19:50:49
4 is the average and 5/6 is the probability!
alice5502 2019-05-14 19:50:49
5/6, 4
KevinCarde 2019-05-14 19:51:03
Great! Some of you are already putting it together one step further.
KevinCarde 2019-05-14 19:51:19
The remaining 1/6 of the time, she'll roll a 1, and when she does... she'll earn some number of points average in this case. Let's call that number $T$.
KevinCarde 2019-05-14 19:51:54
Let's call Susan's average number of points $S$ (that's what we want to compute). What's an equation for $S$, in terms of the work we've done so far and the unknown $T$? (Don't try to figure out what $T$ is yet -- we'll get there soon!)
mathpenguin7 2019-05-14 19:53:08
S=5/6*4+1/6*T
MarvelousMasterMark 2019-05-14 19:53:08
$S = \frac{5}{6}\cdot 4 + \frac{1}{6}\cdot T$
cornn 2019-05-14 19:53:08
5/6*4+T/6
Damalone 2019-05-14 19:53:08
S=T/6+10/3
aggu123 2019-05-14 19:53:08
(5/6)*4+(1/6)*T
Hueman 2019-05-14 19:53:08
S=10/3+T/6
KevinCarde 2019-05-14 19:53:21
Right, 1/6 of the time, she earns $T$ points, and 5/6 of the time, she earns 4 points, for a total of $S = 1/6\cdot T + 5/6\cdot 4$.
KevinCarde 2019-05-14 19:53:54
Now, let's think about $T$. If Susan rolls a 1, then she'll replace it with two dice, each of which follows the same rules. This allows us to relate $S$ and $T$: what's the relationship?
MarvelousMasterMark 2019-05-14 19:55:22
$T = 2S$
mathpenguin7 2019-05-14 19:55:22
$T=2S$
Hueman 2019-05-14 19:55:22
T=2S
sbudaraj 2019-05-14 19:55:22
T=2S
aggu123 2019-05-14 19:55:22
T=2S
alice5502 2019-05-14 19:55:22
2T = S
bookoverlord 2019-05-14 19:55:22
T =2S ?
lightning50 2019-05-14 19:55:22
2S=T
KevinCarde 2019-05-14 19:55:56
$S$ is her average score when she rolls one die, and $T$ is her average score when she rolls two dice independently, so $T = 2S$.
KevinCarde 2019-05-14 19:56:00
Now we can plug this in and solve!
KevinCarde 2019-05-14 19:56:01
$S = 1/6\cdot 2S + 5/6\cdot 4$

$3S = S + 10$

$2S = 10$

$S = 5$
KevinCarde 2019-05-14 19:56:02
Susan therefore earns 5 points on average.
KevinCarde 2019-05-14 19:56:03
At the start of this problem, several of you were excited about doing geometric series to deal with the infinite number of possibilities.
KevinCarde 2019-05-14 19:56:04
That's certainly a valid approach!
KevinCarde 2019-05-14 19:56:11
And we'll do something similar for Eric. (Foreshadowing!)
KevinCarde 2019-05-14 19:56:23
So, let's get to it!
KevinCarde 2019-05-14 19:56:29
Eric's Score
KevinCarde 2019-05-14 19:56:45
Eric refuses to end on an even total, and will reroll all his dice (plus one more) if he rolls an even number.
KevinCarde 2019-05-14 19:56:58
This is a little trickier than Susan's situation, as Eric's dice are tangled up with each other: whether or not he rerolls depends on the sum of all the dice, not on each one individually.
KevinCarde 2019-05-14 19:57:08
We'll be in good shape if we can answer two questions:
KevinCarde 2019-05-14 19:57:34
* Question 1: What is the probability of rolling an odd total, if you roll $n$ dice?

* Question 2: What is the average total of $n$ dice, given that the total is odd?
KevinCarde 2019-05-14 19:57:53
Let's start with Question 1. What's more likely, an even total or an odd total?
turtles0120 2019-05-14 19:58:28
the same
mathpenguin7 2019-05-14 19:58:28
They are the same.
Tinjeson347 2019-05-14 19:58:28
Equal
alokkumar1974 2019-05-14 19:58:28
Neither, there equal!
popcorn1 2019-05-14 19:58:28
They're equal, right?
Physick 2019-05-14 19:58:28
both have the same probability
bookoverlord 2019-05-14 19:58:28
arn't they both 50 -50?
MarvelousMasterMark 2019-05-14 19:58:28
equal
KevinCarde 2019-05-14 19:58:46
For almost all values of $n$, it turns out to be equal -- we'll see why in a moment.
KevinCarde 2019-05-14 19:58:56
But for those of you who said it depends on $n$, you're in fact right!
KevinCarde 2019-05-14 19:59:02
If we have $n = 0$ dice, an even total is much more likely .
KevinCarde 2019-05-14 19:59:31
But for $n > 0$, it's even odds of even and odd.
KevinCarde 2019-05-14 19:59:54
There are several ways to see this. Any ideas?
lightning50 2019-05-14 20:00:17
Doesn't that depend on n?
lcalvert99 2019-05-14 20:00:17
Do it by induction.
KevinCarde 2019-05-14 20:00:32
(Oops, meant to pass the "depends on n" comment earlier.)
KevinCarde 2019-05-14 20:00:41
We'll do some induction shortly, but for this step, we'll do it more directly.
mathpenguin7 2019-05-14 20:01:13
Imagine rolling the first n-1 dice.
AIME12345 2019-05-14 20:01:13
the last dice rolled determines parity of sum
sbudaraj 2019-05-14 20:01:13
because rolling n+1 dice is the same as adding the rolls for n dice and 1 die
MP2016p42 2019-05-14 20:01:13
if 1 less die is equally likely for both, adding 1 die has an equal probability of switching from even to odd, odd to even, saying even and staying odd
duck_master 2019-05-14 20:01:13
you don't even need induction: roll $n-1$ dice; then the next dice has even odds of even and odd, so the total has even odds of even and odd
KevinCarde 2019-05-14 20:01:38
We can imagine rolling all but one of our dice, and then see what happens when we roll the last one.
KevinCarde 2019-05-14 20:02:05
It's just as likely for the last die to roll $k$ as it is to roll $7 - k$, and these two possibilities have different parities.
KevinCarde 2019-05-14 20:02:20
Now, Question 2 is a bit more subtle. Here's an argument with a flaw; see if you can find the flaw!
KevinCarde 2019-05-14 20:02:54
Before that, though, it sounds like there are some questions about this idea.
KevinCarde 2019-05-14 20:03:29
I think some of my coinstructors will answer some questions individually if you have them in the queue, and we'll push forward in the main chat.
KevinCarde 2019-05-14 20:03:38
Flawed Claim: The average total of $n$ dice, given that the total is odd, is $7n/2$. The average total of $n$ dice, given that the total is even, is $7n/2$ as well.
KevinCarde 2019-05-14 20:03:56
Flawed Proof: By induction. Suppose it's true for $n$ dice. Then, using that the probability of an odd roll is 1/2 no matter how many dice, we can compute as follows:
KevinCarde 2019-05-14 20:04:10
Average of $n+1$ dice, given that it's odd = 1/2 * ((Average of $n$ dice given odd) + (2 + 4 + 6)/3) + 1/2 * ((Average of $n$ dice given even) + (1 + 3 + 5)/3)
KevinCarde 2019-05-14 20:04:20
= 1/2 * (7n/2 + 4) + 1/2 * (7n/2 + 3) = 7(n+1)/2
KevinCarde 2019-05-14 20:04:30
And that's exactly what the Flawed Claim wanted.
KevinCarde 2019-05-14 20:04:37
So, uh, what's wrong?
KevinCarde 2019-05-14 20:05:40
(Some of you say you wrote this proof! But take heart: it's almost right. We'll fix it soon!)
mathpenguin7 2019-05-14 20:05:52
Case with one die.
lcalvert99 2019-05-14 20:05:52
It's not true for the base case.
MP2016p42 2019-05-14 20:05:52
1 die
KevinCarde 2019-05-14 20:06:06
So, we said we'd prove it by induction, and we forgot to do a base case.
KevinCarde 2019-05-14 20:06:14
This Flawed Claim is false for 1 die!
KevinCarde 2019-05-14 20:06:30
The average given that a single die rolls an odd number is $(1 + 3 + 5)/3 = 3$, not 7/2.
KevinCarde 2019-05-14 20:06:45
For $n = 2$, though, the claim is true (as you can check with a little computation), so we can use $n = 2$ as a base case.
KevinCarde 2019-05-14 20:06:52
Therefore, the claim holds, but only for $n \ge 2$.
KevinCarde 2019-05-14 20:07:03
Base cases are important!
KevinCarde 2019-05-14 20:07:19
Now that that's cleaned up, we have the answers to our questions: there's a $1/2$ chance of an odd total if we roll $n$ dice, and given that it's odd, the total will on average be $3$ if $n = 1$ and $7n/2$ otherwise.
KevinCarde 2019-05-14 20:07:43
The 1/2 chance of an odd total means that we have a 1/2 chance to roll odd on our 1 die and immediately stop; 1/4 to roll even then odd and stop at 2 dice, 1/8 to roll even, even, then odd and stop at 3 dice, etc. We can set up an infinite series to compute Eric's average value (which we'll call $E$):
KevinCarde 2019-05-14 20:07:57
$$

E = 1/2\cdot 3 + 1/4\cdot 7/2 + 1/8\cdot 14/2 + 1/16\cdot 21/2 + \dots.

$$
KevinCarde 2019-05-14 20:08:11
The weirdness at $n = 1$ is breaking the pattern, so let's write $1/2\cdot 3 = -1/4 + 1/2\cdot 7/2$. Then all the terms have the same form!
KevinCarde 2019-05-14 20:08:18
$$

E = -1/4 + \frac{7}{2} \sum_{n=1}^\infty \frac{n}{2^n}.

$$
KevinCarde 2019-05-14 20:08:46
This looks kind of like a geometric series, but unfortunately, it isn't quite. Has anyone seen this kind of thing before?
duck_master 2019-05-14 20:09:10
the infinite sum at the right is an arithmetico-geometric series!
daniel500 2019-05-14 20:09:10
Its the derivative of the geometric series
mathpenguin7 2019-05-14 20:09:10
Yup.
lcalvert99 2019-05-14 20:09:10
Yeah!
KevinCarde 2019-05-14 20:09:20
We've got some true statements and some enthusiasm!
KevinCarde 2019-05-14 20:09:40
The fancy name is "arithmetico-geometric series", and you can look it up on wikipedia, or you can use calculus to work with it as a derivative of a geometric series (I love doing that).
KevinCarde 2019-05-14 20:10:04
We're going to avoid calculus (and avoid looking up the formula on wikipedia) with an indexing trick.
KevinCarde 2019-05-14 20:10:12
Notice that

$$

2\sum_{n=1}^\infty \frac{n}{2^n} = 1 + \sum_{n=1}^\infty \frac{n+1}{2^n}

$$
KevinCarde 2019-05-14 20:10:21
(I sure hope I got my indexes right.)
KevinCarde 2019-05-14 20:11:03
Now we can continue to rewrite things:
KevinCarde 2019-05-14 20:11:08
$$

\sum_{n=1}^\infty \frac{n}{2^n} = 2\sum_{n=1}^\infty \frac{n}{2^n} - \sum_{n=1}^\infty \frac{n}{2^n}

$$
KevinCarde 2019-05-14 20:11:19
$$

= 1 + \sum_{n=1}^\infty \frac{n+1}{2^n} - \sum_{n=1}^\infty \frac{n}{2^n}

$$
KevinCarde 2019-05-14 20:11:25
$$

= 1 + \sum_{n=1}^\infty \frac{1}{2^n} = 1 + 1 = 2

$$
KevinCarde 2019-05-14 20:11:40
Where, at long last, we got a normal old geometric series instead of a fancy arithmetico one!
KevinCarde 2019-05-14 20:11:54
With that series evaluated, we can finish up Eric's score:
KevinCarde 2019-05-14 20:11:59
$$

E = -1/4 + 7/2 \cdot 2 = 6.75

$$
KevinCarde 2019-05-14 20:12:25
Hopefully those of you who wanted to use series with Susan enjoyed getting to do that with Eric .
KevinCarde 2019-05-14 20:12:30
But now, onwards to problem 3!
MarisaD 2019-05-14 20:12:38
Hi again, folks, I'm back to chat Flip Flop with you. (In addition to being a QQ problem, this is an actual game we play at camp.)
MarisaD 2019-05-14 20:12:48
Problem 3 Statement:
In the game of Flip Flop, players stand in a circle and take turns saying the numbers 1, 2, 3, etc., going clockwise.

When they get to a multiple of 7, the player whose turn it is says FLIP instead, and the direction switches: if they were going clockwise before, they now go counterclockwise, or vice versa.

When they get to a multiple if 8, the player whose turn it is says FLOP instead. The direction stays the same, but the next person is skipped over.

For a number n that is a multiple of both 7 and 8, the player says FLIP FLOP. Direction reverses and you skip over the next person. This means $n$ + 1 is said by the person who said $n$ - 2.
MarisaD 2019-05-14 20:13:00
Problem 3a: Show that no matter how many people are in the circle, eventually each person will get a turn to speak.
MarisaD 2019-05-14 20:13:09
PROBLEM 3a SOLUTION
MarisaD 2019-05-14 20:13:14
Let's zip through part a. Can someone give me a solution in at most ten words?
cornn 2019-05-14 20:14:13
it cycles and moves one person per cycle
MarvelousMasterMark 2019-05-14 20:14:13
The person who says 57 is next to the person who says 1.
Hueman 2019-05-14 20:14:13
loops but shifts down one each time
MarisaD 2019-05-14 20:14:17
The key is that whatever the game does in turns 1-56, it'll do the same thing in the next 56 turns. And the next 56 turns after that. Et cetera, et cetera...
MarisaD 2019-05-14 20:14:26
As it turns out, in each cycle of 56 turns, the game moves one person clockwise, and continues facing the same direction (clockwise).
TheUltimate123 2019-05-14 20:14:34
Look at 3b?
MarisaD 2019-05-14 20:14:37
Another acceptable proof was "Follows from part (b)." If you managed to solve part (b).
AIME12345 2019-05-14 20:14:56
But solving part (a) helped to solve part (b)
MarisaD 2019-05-14 20:15:03
Yeah!! That was the secret plan.
MarisaD 2019-05-14 20:15:05
Problem 3b: If FLIPs come at multiples of K, and FLOPs come at multiples of M, then for what values of K and M is everyone guaranteed to get a turn to speak (regardless of the number of players)?
MarisaD 2019-05-14 20:15:22
First of all, let's take some inspiration from part (a). We want to say something similar to "Every 56 turns the game moves one person clockwise."
MarisaD 2019-05-14 20:15:26
Thoughts?
MarvelousMasterMark 2019-05-14 20:16:30
The equivalent is lcm(K,M).
sbudaraj 2019-05-14 20:16:30
If M/gcd(K, M) is even, then the FLIPS cancel each other out, but the FLOPS don't
jenniferwangg 2019-05-14 20:16:30
It has to cycle.
duck_master 2019-05-14 20:16:30
every $\text{lcm}(K, M)$ turns the game cycles
MarvelousMasterMark 2019-05-14 20:16:30
Then look at lcm(K,M) odd versus even.
MarisaD 2019-05-14 20:16:37
Right. We can split the game into "cycles" of $\text{lcm}(K, M)$ turns each. The game does the same thing every cycle.
MarisaD 2019-05-14 20:16:44
(From now on, I'll use the word "cycle" because it's faster than LaTeXing "every $\text{lcm}(K, M)$ turns.")
MarisaD 2019-05-14 20:16:51
So how do we figure out what happens each cycle??? What shall we try?
logz 2019-05-14 20:17:22
Pick some K and M?
jenniferwangg 2019-05-14 20:17:22
Try small values and look for a pattern.
MarisaD 2019-05-14 20:17:27
Small cases!!
MarisaD 2019-05-14 20:17:29
So let's say you check all cases $1 \leq K, M \leq 200$. (Programming isn't required for math, but sometimes it sure is useful.)
MarisaD 2019-05-14 20:17:36
The results inspire a conjecture:
MarisaD 2019-05-14 20:17:40
(1) When M has more factors of 2 than K, the game moves one person clockwise every cycle.

(2) Otherwise, every cycle, the game moves some number of people and flips direction.
MarisaD 2019-05-14 20:18:02
Soon we'll prove (1) and (2). But before that, let's think: how will proving them help solve the problem?
MarisaD 2019-05-14 20:19:04
Yep, I'm seeing lots of great responses in the queue. Passing on a few of them:
jenniferwangg 2019-05-14 20:19:39
We will find that if M divides a greater power of 2 than K, every player will be able to speak.
Tony_1567366 2019-05-14 20:19:39
Prooving that cycling will happen
duck_master 2019-05-14 20:19:47
can we come up with this conjecture without coding?
MarisaD 2019-05-14 20:19:50
Absolutely.
MarisaD 2019-05-14 20:20:02
(It just sometimes helps.)
MarisaD 2019-05-14 20:20:20
So, essentially: in case (1), everyone gets to speak, like in part (a)
MarisaD 2019-05-14 20:20:29
and in case (2), the game repeats every 2 cycles.
MarisaD 2019-05-14 20:20:44
Great. Now, let's prove (2) first. (Empirically, this was the easier half of the problem.)
MarisaD 2019-05-14 20:20:51
How many FLIPs occur every cycle?
MarvelousMasterMark 2019-05-14 20:21:19
lcm(K,M)/K
MarisaD 2019-05-14 20:21:26
Yup. So, we know the game flips direction every cycle because...
duck_master 2019-05-14 20:21:59
this number is odd
MarisaD 2019-05-14 20:22:09
Yup. An odd number of flips = the game changes direction. QED.
MarisaD 2019-05-14 20:22:17
Now let's move on to part (1). The logic we just used tells us that the game does NOT flip direction each cycle. Which is good. But we still have to prove that the game moves one person clockwise each cycle.
MarisaD 2019-05-14 20:22:29
Two things cause the game to move: FLOPs, and the normal one-person-per-turn movement. Let's first consider the one-person-per-turn movement. Ignoring FLOPs, how much, in net, does this cause the game to move each cycle?
sbudaraj 2019-05-14 20:23:15
0
jenniferwangg 2019-05-14 20:23:15
0
MarisaD 2019-05-14 20:23:27
Right! Why?
jenniferwangg 2019-05-14 20:24:18
Because every time you flip, you flip back.
MarvelousMasterMark 2019-05-14 20:24:18
even number of flips, each movement one direction will be canceled out other direction
daniel500 2019-05-14 20:24:18
Every two flips you go back to the original player
MarisaD 2019-05-14 20:24:24
Right. There's an even number of FLIPs each cycle and they happen at regular intervals. So the game spends an equal amount of time moving clockwise and counterclockwise.
MarisaD 2019-05-14 20:24:31
So, the one-person-per-turn movement of the game causes no net movement per cycle. This means that all the net movement is caused by the FLOPs.
MarisaD 2019-05-14 20:24:41
In other words, in order to prove our conjecture, it suffices to show that, out of the $\text{lcm}(K, M)/M$ flops each cycle, the number of clockwise FLOPs is one more than the number of counterclockwise FLOPs.
MarisaD 2019-05-14 20:24:56
Let's say that a FLOP occurs at turn number $t$. What condition on $t$ tells us whether this FLOP moves clockwise or counterclockwise?
MarisaD 2019-05-14 20:26:30
(I'm seeing some claims about even/odd; that's not quite it..)
MarisaD 2019-05-14 20:27:17
Ah, good, now I see some right answers.
MarisaD 2019-05-14 20:27:19
A FLOP moves clockwise iff its turn number is $0, 1, 2, \dots, \text{ or } K-1$ modulo $2K$.
MarisaD 2019-05-14 20:27:40
So, let's see: we know that FLOPs occur at numbers that are 0 mod $M$, and we want to know when they occur modulo $2K$. Luckily for us, there's a neat theorem that tells us how two different moduli interact with each other.
MarisaD 2019-05-14 20:27:58
What theorem will help us out?
duck_master 2019-05-14 20:28:10
chinese remainder theorem?
jenniferwangg 2019-05-14 20:28:10
Chinese Remainder Theorem?
tervis 2019-05-14 20:28:10
chinese remainder theorem
MarisaD 2019-05-14 20:28:16
Yes! The Chinese Remainder Theorem.
MarisaD 2019-05-14 20:28:20
It tells us that, setting $2g$ as the gcd of M and 2K, the FLOPs in a cycle occur once each at each of the residues $0, 2g, 4g, \dots, 2K-2g$ modulo $2K$.
MarisaD 2019-05-14 20:28:32
(Why can we set $2g$ as the gcd? Because, by assumption in this case, M is even.)
MarisaD 2019-05-14 20:28:54
And as we have already determined, the FLOPs at residues $0, 2g, 4g, \dots, K-g$ go clockwise, and the other FLOPs at residues $K+g, K+2g, \dots, 2K-2g$ go counterclockwise.
MarisaD 2019-05-14 20:29:14
All in all, one more FLOP goes clockwise than it goes counterclockwise. Which is exactly what we wanted to show. It means that every cycle, the game progresses clockwise one person.
MarisaD 2019-05-14 20:29:31
Phew! We are done. That last part was a bit of a tour de force. It's all motivated by wanting to know when the FLOPs occur modulo $2K$.
Tony_1567366 2019-05-14 20:29:42
OH!
MarisaD 2019-05-14 20:29:47
Right?
MarisaD 2019-05-14 20:29:52
Onwards to Problem 4!
KevinCarde 2019-05-14 20:29:56
Hello again everyone!
KevinCarde 2019-05-14 20:30:04
Problem 4 Statement:
There is a puzzle with $N^2$ pieces, each one shaped like a wedge that is $1/N$ of a disk. On the front of each piece, each of the two sides of the wedge is labeled with an integer between $1$ and $N$, so that each of the $N^2$ possible ordered pairs occurs exactly once. The goal of the puzzle is to form $N$ full disks in such a way that the edges come together to have the same label. Below is an example of some pieces fitting together to form a full disk when $N=5$.

http://mathcamp.org/2019/qquiz-2019-25-puzzle.png

Problem 4a: Show that the puzzle can be solved when $N=5$.

Problem 4b: Show that the puzzle can be solved for any integer $N \ge 3$. Partial credit will be awarded for a proof that the puzzle can be solved for infinitely many $N$.
KevinCarde 2019-05-14 20:30:48
Before we dive in, I want to point out that there are a lot of different ways to do this problem.
KevinCarde 2019-05-14 20:30:58
Many, many different ideas can be used for the constructions!
KevinCarde 2019-05-14 20:31:22
I'm going to walk through one way, but I invite you to think about other possibilities if you're interested in your own time.
KevinCarde 2019-05-14 20:31:36
Before we start working on the problem, let's set some notation. We'll use ordered pairs to indicate wedges, so we could describe the example disk in the image above as follows:
KevinCarde 2019-05-14 20:31:46
(3, 1)-(1, 2)-(2, 5)-(5, 1)-(1, 3)
KevinCarde 2019-05-14 20:31:55
(And then we imagine the 3 at the end circling back to the 3 at the beginning to connect up and make a full disk of size 5.)
KevinCarde 2019-05-14 20:32:13
(Also, apologies in advance for those of you who love $\LaTeX$ formatting of everything, if I'm a bit inconsistent about when I use it.)
KevinCarde 2019-05-14 20:32:23
OK, so our wedges are ordered pairs.
KevinCarde 2019-05-14 20:32:30
When we glue together several wedges, we'll call the result a piece of size equal to the number of wedges in it. So, the disk above is a piece of size 5, and an individual wedge is a piece of size 1.
KevinCarde 2019-05-14 20:32:39
We could jump straight to Part b, since it implies Part a, but we'll build up the $N=5$ case in a way that will show off our general strategy. In fact, we'll start even simpler!
KevinCarde 2019-05-14 20:32:46
PROBLEM 4a SOLUTION
KevinCarde 2019-05-14 20:32:57
We're asked to come up with a solution to this puzzle for $N = 5$, but let's step back. Here's an exciting question for you: what does the problem look like for $N = 1$?
popcorn1 2019-05-14 20:33:19
$(1,1)$
duck_master 2019-05-14 20:33:19
you're already done
Tony_1567366 2019-05-14 20:33:19
a circle?
daniel500 2019-05-14 20:33:19
(1, 1)
MarvelousMasterMark 2019-05-14 20:33:19
just a disc with the number 1
turtles0120 2019-05-14 20:33:19
its a circle with one piece, that is a circle, so it is automatically solved!
KevinCarde 2019-05-14 20:33:31
Yes, we have a single "wedge", and it's already an entire "disk" itself!
KevinCarde 2019-05-14 20:33:53
What does the problem look like for $N = 2$?
mathpenguin7 2019-05-14 20:34:20
Four pieces: (1,1) (1,2) (2,1) (2,2)
KevinCarde 2019-05-14 20:34:29
Can we make two complete disks out of them?
MarvelousMasterMark 2019-05-14 20:34:51
not possible
jenniferwangg 2019-05-14 20:34:51
It's not possible.
achordia5 2019-05-14 20:34:51
No
daniel500 2019-05-14 20:34:51
no
iks92 2019-05-14 20:34:51
no
jenniferwangg 2019-05-14 20:34:51
No.
ethiomath 2019-05-14 20:34:51
No solution
MP2016p42 2019-05-14 20:34:51
nope
mathpenguin7 2019-05-14 20:34:51
No
popcorn1 2019-05-14 20:34:51
No!
turtles0120 2019-05-14 20:34:51
I don't think so
KevinCarde 2019-05-14 20:34:57
Sad .
MP2016p42 2019-05-14 20:35:01
11 and 22 can't be paired
jenniferwangg 2019-05-14 20:35:01
You can't have two (1, 1) pieces.
KevinCarde 2019-05-14 20:35:21
Right, we need to use, say, (1, 1) somewhere, but it'd need another copy of itself to complete a disk of size 2.
KevinCarde 2019-05-14 20:35:25
And all our wedges must be used exactly once!
jenniferwangg 2019-05-14 20:35:30
But the question asks for k ≥ 2.
KevinCarde 2019-05-14 20:35:38
Yes, so luckily, we didn't prove the Qualifying Quiz to be wrong! Hooray!
KevinCarde 2019-05-14 20:35:49
(In fact, for strictly greater than 2, since 2 itself is a problem.)
KevinCarde 2019-05-14 20:36:07
So let's imagine increasing from $N = 1$ to $N = 3$.
KevinCarde 2019-05-14 20:36:24
We're going to overkill this special case and be unnecessarily organized.
KevinCarde 2019-05-14 20:36:46
Why? Because it will make the general case a breeze!
KevinCarde 2019-05-14 20:37:12
Ah, I see a great set of three disks in the queue already:
jenniferwangg 2019-05-14 20:37:18
(1, 1)- (1, 2) - (2, 1), (2, 2) - (2, 3) - (3, 2), (3, 3)-(3,1)-(1,3)
duck_master 2019-05-14 20:37:18
solution: {(1,1), (1,2), (2,1)}, {(2,2), (2,3), (3,2)}, {(3,3), (3,1), (1,3)}
KevinCarde 2019-05-14 20:37:31
Let's break down the situation and go overboard on this special case.
KevinCarde 2019-05-14 20:37:48
If we're going from $N = 1$ to $N = 3$, we have eight new wedges, and we're going to glue them together to make some larger pieces as follows:
KevinCarde 2019-05-14 20:38:02
* Type A: (1, 2)-(2, 1), a piece of size 2 which starts and ends with 1.

* Type B: (3, 2)-(2, 2)-(2, 3), a piece of size 3 which starts and ends with 3.

* Type C: (3, 1)-(1, 3), a piece of size 2 which starts and ends with 3.

* Type (3, 3) by itself, a piece of size 1 which starts and ends with 3.
KevinCarde 2019-05-14 20:38:05
uh oh
KevinCarde 2019-05-14 20:38:14
I did not want that face there, oops.
KevinCarde 2019-05-14 20:38:21
ok, one of our pieces is now Type , deal with it!
KevinCarde 2019-05-14 20:38:39
From $N = 1$, we have the "disk" (1, 1) of size 1.
KevinCarde 2019-05-14 20:38:52
We can augment that to a disk of size 3 by throwing in our piece of Type A, resulting in the disk (1, 1)-(1, 2)-(2, 1). One disk down, two to go!
KevinCarde 2019-05-14 20:39:11
The piece of Type B is already an entire disk of size 3, and the pieces of Type C and Type fit together to make our third and final disk. Hooray!
KevinCarde 2019-05-14 20:39:33
Explicitly, these are the three disks that you already came up with, if you want to see what they look like.
jenniferwangg 2019-05-14 20:39:52
Alternatively, one could add (1, 3), (3, 1)
KevinCarde 2019-05-14 20:39:57
The first of many branching paths!
KevinCarde 2019-05-14 20:40:03
There are many, many different possible solutions.
KevinCarde 2019-05-14 20:40:12
Let's move onward to $N = 5$.
KevinCarde 2019-05-14 20:40:17
It'll go very similarly!
KevinCarde 2019-05-14 20:40:22
Going from $N = 3$ to $N = 5$, our new wedges are any wedge that has a 4 or a 5. We divide them into four types as before:
duck_master 2019-05-14 20:40:32
wait why not $N=4$?
KevinCarde 2019-05-14 20:40:59
Good question! We'll think about $N = 4$ soon, but let's try to solve Part a, and repeat our success at going from $N$ to $N+2$.
KevinCarde 2019-05-14 20:41:25
So, four types of new pieces now that we're in $N = 5$:
KevinCarde 2019-05-14 20:41:32
* Type A: (i, 4)-(4, i) for $i = 1, 2, 3$, each a piece of size 2 which starts and ends with $i$.

* Type B: (5, 4)-(4, 4)-(4, 5), a piece of size 3 which starts and ends with 5.

* Type C: (5, i)-(i, 5) for $i = 1, 2, 3$, each a piece of size 2 which starts and ends with 5.

* Type (5, 5) by itself, a piece of size 1 which starts and ends with 5.
KevinCarde 2019-05-14 20:42:03
(Some of you have beautiful solutions in the queue already!)
KevinCarde 2019-05-14 20:42:14
From $N = 3$, we have three disks of size 3, and we can use the three pieces of Type A to augment them to disks of size 5.
KevinCarde 2019-05-14 20:42:26
Notice that in order to insert the piece (i, 4)-(4, i) into an existing disk, the existing disk must have an edge labeled $i$.
KevinCarde 2019-05-14 20:42:36
Luckily, when we did $N = 3$, the first disk we made has a 1, the second has a 2, and the third has a 3. Let's keep this in mind for when we do the general case!
KevinCarde 2019-05-14 20:42:57
With those three disks out of the way, we now need to make two disks out of Types B, C, and . But all these pieces start and end with a 5, so we can put them together however we'd like!
KevinCarde 2019-05-14 20:43:28
Our goal is two disks of size 5, and our remaining pieces have sizes 3, 2, 2, 2, and 1. It's easy to see that we can partition the pieces into two sets, each with size 5: 3+2 and 2+2+1. It doesn't matter which pieces of size 2 we use where; all Type C pieces behave identically.
KevinCarde 2019-05-14 20:43:46
Keeping in mind what we did with edges labels, let's make sure to call the disk with (5, 4)-(4, 4)-(4, 5) the 4th disk. This way, it'll continue to be the case that the $i$th disk has an edge labeled $i$.
KevinCarde 2019-05-14 20:43:56
Putting it together, here's what our $N = 5$ disks look like after making some arbitrary choices about our Type C pieces:
KevinCarde 2019-05-14 20:44:13
* (First $N = 3$ disk)-(1, 4)-(4, 1)

* (Second $N = 3$ disk)-(2, 4)-(4, 2)

* (Third $N = 3$ disk)-(3, 4)-(4, 3)

* (5, 4)-(4, 4)-(4, 5)-(5, 1)-(1, 5)

* (5, 5)-(5, 2)-(2, 5)-(5, 3)-(3, 5)
KevinCarde 2019-05-14 20:44:34
(Again, other solutions are possible: as we increase $N$, there will be more and more variants!)
KevinCarde 2019-05-14 20:45:42
Oh my, someone's even made a explicit $N = 7$ disks. I haven't checked the details, but check out how much better EigenVictor's formatting is than mine :
EigenVictor 2019-05-14 20:45:45
\left[ \begin{array}{ll}{1} & {2} & {1} & {4} & {1} & {6} & {1} \\ {2} & {3} & {2} & {4} & {2} & {6} & {2} \\ {3} & {1} & {3} & {5} & {3} & {6} & {3} \\ {4} & {3} & {4} & {5} & {4} & {7} & {7} \\ {5} & {1} & {5} & {2} & {5} & {7} & {5} \\ {6} & {4} & {6} & {5} & {6} & {7} & {6} \\ {7} & {1} & {7} & {2} & {7} & {3} & {7}\end{array}\right]
MarvelousMasterMark 2019-05-14 20:46:00
This will work in general, cool!
KevinCarde 2019-05-14 20:46:07
Yeah! Let's move on to the general case, also known as Part b.
KevinCarde 2019-05-14 20:46:17
PROBLEM 4b SOLUTION
KevinCarde 2019-05-14 20:46:29
We've already been building up new solutions from old, so that means... induction!
KevinCarde 2019-05-14 20:46:41
We'll make a solution for $N+2$ out of a solution for $N$.
KevinCarde 2019-05-14 20:46:45
A trick question of sorts: what's our base case?
duck_master 2019-05-14 20:47:17
$N=1$ or $N=4$
AIME12345 2019-05-14 20:47:17
$N=4$
AIME12345 2019-05-14 20:47:17
$N=3$
MarvelousMasterMark 2019-05-14 20:47:17
for odd, N=1, for even N= 4?
KevinCarde 2019-05-14 20:47:30
We need two base cases, if we're increasing by 2 each time: one for odd $N$, and one for even $N$.
KevinCarde 2019-05-14 20:47:52
Since the problem only asks $N \ge 3$, we could do $N = 3$ as our odd base case, or we can do $N = 1$ and get one more case in. Both are great, and both we've already done!
KevinCarde 2019-05-14 20:48:06
We haven't touched even numbers, though.
KevinCarde 2019-05-14 20:48:11
Is $N = 4$ possible? $N = 2$ wasn't...
EigenVictor 2019-05-14 20:48:52
Sure is!
MarvelousMasterMark 2019-05-14 20:48:56
Yes
ethiomath 2019-05-14 20:48:58
Yes
MP2016p42 2019-05-14 20:49:03
yes, the problem says to prove it
KevinCarde 2019-05-14 20:49:11
This is excellent logic
EigenVictor 2019-05-14 20:49:22
\begin{array}{l}{(1,1)(1,2)(1,2)(2,1)} \\ {(2,3)(3,1)(1,4)(4,2)} \\ {(3,3)(3,4)(4,4)(43)} \\ {(4,1)(1,3)(3,2)(2,4)}\end{array}
KevinCarde 2019-05-14 20:49:29
And here is slightly more explicit logic
KevinCarde 2019-05-14 20:49:43
Let's state what we want to prove very precisely because there's an important detail we need to make sure to include. What did we need to keep in mind when we grew the $N = 3$ case to $N = 5$?
achordia5 2019-05-14 20:50:53
(1,2) is there twice in the chart
KevinCarde 2019-05-14 20:51:11
(Oops, good catch, but that's just a typo -- we haven't used (2, 2) yet, and it fits perfectly there)
lcalvert99 2019-05-14 20:51:25
The size of the pieces grows, too.
Hueman 2019-05-14 20:51:25
Make 2 new disks + fill previous ones
turtles0120 2019-05-14 20:51:25
We had to use the n=3 cases?
KevinCarde 2019-05-14 20:51:37
And to do that, we needed to be able to insert our Type A pieces, and hence we needed it to be the case that
MarvelousMasterMark 2019-05-14 20:51:41
Disk 1 had a 1, Disk 2 had a 2, Disk 3 had a 3
KevinCarde 2019-05-14 20:51:59
Luckily, EigenVictor's example has this property, where the $i$th disk has an $i$ in it, so that's good for us!
KevinCarde 2019-05-14 20:52:13
Let's state precisely what we want to prove, then, keeping this edge condition in mind:
KevinCarde 2019-05-14 20:52:15
For all $N \ge 3$, the puzzle has a solution where the $i$th disk contains at least one edge labeled $i$.
KevinCarde 2019-05-14 20:52:37
We've talked about our base cases at length, so let's dive into the inductive step. It'll be basically no different from what we've done!
KevinCarde 2019-05-14 20:53:04
Suppose we've solved the puzzle for $N$, and now we want to solve it for $N+2$.
KevinCarde 2019-05-14 20:53:06
Our new wedges are the wedges that use $N+1$, $N+2$, or both. We classify them as before:
KevinCarde 2019-05-14 20:53:14
* Type A: (i, N+1)-(N+1, i) for $i = 1, 2, \dots, N$, each a piece of size 2 which starts and ends with $i$.

* Type B: (N+2, N+1)-(N+1, N+1)-(N+1, N+2), a piece of size 3 which starts and ends with $N+2$.

* Type C: (N+2, i)-(i, N+2) for $i = 1, 2, \dots, N$, each a piece of size 2 which starts and ends with $N+2$.

* Type D: (N+2, N+2) by itself, a piece of size 1 which starts and ends with $N+2$.
KevinCarde 2019-05-14 20:53:28
(Here is the hideous $\LaTeX$ and not hybrid, apologies...)
KevinCarde 2019-05-14 20:53:42
We have $N$ existing disks of size $N$, which can be augmented to $N$ disks of size $N+2$ using the pieces of Type A. (The edge condition guarantees there's always a spot in the $i$th disk to insert $(i, N+1)-(N+1, i)$.)
KevinCarde 2019-05-14 20:54:05
We now need to make two disks out of Types B, C, and , but every single one of these pieces starts and ends with $N+2$, so we can fit them together however we'd like!
KevinCarde 2019-05-14 20:54:27
Since we want two disks each of size $N+2$, we just need to check that we can partition these pieces into two sets, each of size $N+2$.
KevinCarde 2019-05-14 20:54:52
But since our sizes are small -- 1 piece of size 1, 1 of size 3, and the rest of size 2 -- it's not hard to shuffle them around to make this the case.
KevinCarde 2019-05-14 20:55:04
If $N+2$ is even, we'll make sure to put the odd pieces (B and ) together; if $N+2$ is odd, we'll split them.
KevinCarde 2019-05-14 20:55:37
We have to make sure that we continue to satisfy the edge condition, but we're set as long as we say that the disk with the Type B piece is our $N+1$ disk.
KevinCarde 2019-05-14 20:55:55
And with that, the general inductive step works just like Part a!
KevinCarde 2019-05-14 20:56:16
Since we've successfully created our $N+2$ disks of size $N+2$ given $N$ disks of size $N$, this completes the proof.
KevinCarde 2019-05-14 20:56:29
Onwards to Problem 5!
Kamior 2019-05-14 20:56:34
Hi, all!
Kamior 2019-05-14 20:56:46
Problem 5 Statement:

Every day at noon exactly, people submit orders of positive integer numbers of paninis at your panini store. It takes you 1 minute to make 1 panini.

When Alice orders 2 paninis and Bob orders 100 paninis, you decide to make Alice's paninis first, because it results in less total customer wait time (104 vs. 202 minutes).

* [Warm-up exercise: do not submit an answer] Show that for any set of orders, you achieve the smallest total wait time by processing the smaller orders first.

When the town gets wind of your scheme, they hatch devious plans. Instead of ordering 100 paninis, Bob decides to submit 100 orders of 1 panini each under different names, so he gets processed first. Oh no.

Call a panini-making scheme strategy-free if no customer, in any scenario, can strictly decrease their average wait time just by splitting their order up into several smaller (integer-size) orders.

Assume your customers are aware of your scheme and will not split up their orders if the scheme is strategy-free.
Kamior 2019-05-14 20:56:54
Problem 5a: Show that the scheme "choose the sequence of orders uniformly at random" is strategy-free.
Kamior 2019-05-14 20:57:33
Problem 5a solution
Kamior 2019-05-14 20:57:42
Consider a customer; call him Bob. If orders are processed in a uniformly random order, then all other customers have a $1/2$ chance of delaying Bob by going before him. If Bob splits his order up into $k$ parts, what’s each other customer’s chance of delaying Bob?
Skywalker64 2019-05-14 20:59:58
k/(k+1)
MarvelousMasterMark 2019-05-14 20:59:58
$\dfrac{k}{k+1}$
Kamior 2019-05-14 21:00:11
Right, each other customer has a $k/(k+1)$ chance of delaying Bob, since the $k$ orders of Bob's and that customer's one order could come in $k+1$ orders, and in only one of them (all of Bob's orders first) is Bob undelayed.
Kamior 2019-05-14 21:01:04
Some people suggested $1-\frac{1}{2^k}$, but if you know that Alice's order is ahead of one of Bob's, it's more likely to be ahead of another of Bob's; they aren't independent events that would give $2^k$ independent possibilities.
lcalvert99 2019-05-14 21:01:14
Ok, so: by splitting up your order, you increase your chance of getting stuck at the back of the line
Kamior 2019-05-14 21:01:18
Yep, this only makes things worse for Bob, and that's some intuition for why.
Kamior 2019-05-14 21:01:26
To formalize this: Bob’s expected wait time is the expected amount of time he has to wait for himself and everyone who delays him. By linearity of expectation, that’s the expected amount of time he has to wait for himself, plus the expected wait for each other person. And that’s the size of his own order, plus $\frac{k}{k+1}$ times the total size of all other orders.
Kamior 2019-05-14 21:01:38
Problem 5b: Give an example of a strategy-free scheme that has a lower average wait time than the above scheme whenever the orders are not all the same size.
Kamior 2019-05-14 21:02:08
First, let’s talk about some of the strategies that applicants proposed. There were a lot of them!
Kamior 2019-05-14 21:02:29
Four commonly attempted strategies on the Qualifying Quiz were variants of the following:
* Choose the sequence of orders uniformly at random. Then, with probability .001, if the smallest order would’ve been after the second-smallest order, switch them.
* With probability .001, process the orders in increasing orders of size. Otherwise, choose the sequence of orders uniformly at random.
* Process the smallest order (or an order tied for smallest) first. Then process the remaining orders uniformly at random.
* Pick a random panini, and mark its order 1. Then pick a random panini whose order isn’t already marked, and mark it 2, and so on. Then process the orders in descending order of their numbers.
Kamior 2019-05-14 21:02:40
...but two of those four strategies are wrong! One of them isn't strategy-free, and another doesn't have a lower average wait time in at least one case where the orders are not all the same size.
Kamior 2019-05-14 21:03:15
Which of those attempted strategies doesn't necessarily decrease the total expected wait time?
Kamior 2019-05-14 21:05:55
Lots of people have said the last one, but that one actually does decrease the wait time. We'll prove it later.
MarvelousMasterMark 2019-05-14 21:06:43
first
Kamior 2019-05-14 21:06:49
The first one doesn't for the silly reason that, if the smallest two orders are the same size, switching them doesn’t do anything, so the scheme doesn’t have a lower average wait time even if one of the bigger orders is not the same size.
Kamior 2019-05-14 21:07:20
This strategy can easily be fixed to correct that; missing that the average wait time needs to be lower in every case where the orders are not all the same size is an easy small mistake to make.
Kamior 2019-05-14 21:07:58
Let's try a more serious problem. One of those four proposed schemes isn't strategy-free. Which of those four attempted strategies isn't strategy-free?
Damalone 2019-05-14 21:08:51
#3 because I tried to do it but couldn't make it work
sbudaraj 2019-05-14 21:08:51
3rd one
Damalone 2019-05-14 21:08:51
#3
MarvelousMasterMark 2019-05-14 21:08:51
3
turtles0120 2019-05-14 21:08:51
the third
Kamior 2019-05-14 21:09:01
Yep, third third one is wrong! Can anyone give an example where you'd benefit by splitting your order?
daniel500 2019-05-14 21:11:00
splitting off your order into 1 panini and the others
Kamior 2019-05-14 21:11:03
Expanding an example like that a little: Alice has an order of size 3. Bob has an order of size 4. If Bob doesn’t split his order, he definitely has to wait for Alice, and his average wait time is $3+4 = 7$. If he splits his order into two orders of size 2, he still might have to wait for Alice, but not necessarily, and his average wait time is now only $2+(3/2)+2=5$.
Kamior 2019-05-14 21:12:26
Let's move on to the solution.
Kamior 2019-05-14 21:12:27
Problem 5b solution
Kamior 2019-05-14 21:12:41
Let’s prove that the fourth strategy works. (Lots of others work too, but we’ll only prove one here.)
Kamior 2019-05-14 21:12:51
Some people were confused about what the fourth strategy is; ``process the orders'' means that you actually make the paninis in them.
Kamior 2019-05-14 21:13:28
So if, say, there's one order of size 3 and one order of size 4, the order of size 4 has a 4/7 chance to be selected to be made last.
Kamior 2019-05-14 21:13:54
There are two things we need to prove:

* that the scheme is strategy-free, and

* that it has a lower average wait time.
Kamior 2019-05-14 21:14:32
First, we claim this is strategy-free. Indeed, for any customer Alice, no matter how she splits up her order, she has an equal chance of being chosen to go last at every step, when a random panini is picked. Therefore, splitting up her order cannot improve Alice's expected wait time at all.
Kamior 2019-05-14 21:14:54
Now we claim this scheme achieves a lower expected wait time than processing the customers uniformly at random, with equality holding only when all customers' orders are the same size.
Kamior 2019-05-14 21:15:07
Let the customers' order sizes be $s_{1},s_{2},\dots,s_{n}$. For any pair of customers $i,j$, either $i$ has to wait for $j$ (causing waiting time $s_{j}$), or $j$ has to wait for $i$ (causing waiting time $s_{i}$).
Kamior 2019-05-14 21:15:18
By linearity of expectation, the expected total waiting time of all customers is

$$\sum_{i} s_i + \sum_{i < j} \Pr\left[\mbox{i goes before j}\right]s_{j}+\Pr\left[\mbox{j goes before i}\right]s_{j}.$$
Kamior 2019-05-14 21:15:25
(The first term in the sum is customers waiting for their own orders, and the second term is customers waiting for each other.)
Kamior 2019-05-14 21:15:43
If we process customers uniformly at random, what’s $\Pr\left[\mbox{i goes before j}\right]$?
Kamior 2019-05-14 21:17:06
(Pr here stands for probability.)
Kamior 2019-05-14 21:17:32
(One of i and j will go before the other, and whoever goes later of the two of them has to wait for whoever goes earlier.)
achordia5 2019-05-14 21:19:46
1/2
MarvelousMasterMark 2019-05-14 21:19:50
1/2
Kamior 2019-05-14 21:19:55
Yes, 1/2, because there's an equal chance that $j$ comes before $i$ and that $i$ comes before $j$.
Collatz__conjecture 2019-05-14 21:20:02
1/2
laihpos062807 2019-05-14 21:20:02
1/2
Kamior 2019-05-14 21:20:11
So if we process orders uniformly at random, the term inside the sum is $\frac{1}{2}s_{i}+\frac{1}{2}s_{j}$.
Kamior 2019-05-14 21:20:31
But under the new scheme, someone with a bigger order always has a higher probability $p$ of getting picked to go later than someone with a smaller order, so if $s_i > s_j$, then $\Pr\left[\mbox{i goes before j}\right] < \frac12$.
Kamior 2019-05-14 21:20:56
Does that always decrease the expected wait time?
daniel500 2019-05-14 21:21:34
yes
laihpos062807 2019-05-14 21:21:39
yesn
Kamior 2019-05-14 21:21:42
If we call that probability $p$, then the term inside the sum went to $ps_i + (1-p)s_j$. which is a decrease of $(\frac12 - p)(s_i - s_j)$, so the expected total wait time decreased. (And if two peoples' orders are the same size, then we at least don't get any worse.)
Kamior 2019-05-14 21:21:48
QED.
Kamior 2019-05-14 21:22:03
Problem 5c: Suppose you know that, on any given day, you will either receive (1) three orders for one panini each, or (2) one order for one panini and one order for two paninis. Give a strategy-free panini-making scheme such that in either scenario (1) or (2), the average total wait time is at most 25/24 the optimal total wait time.
Kamior 2019-05-14 21:22:23
This was a tricky problem, because if you keep your panini press on constantly, there's no way to do it. But if you deliberately deliver some orders slowly, it's possible!
Kamior 2019-05-14 21:22:34
Problem 5c solution
Kamior 2019-05-14 21:22:46
Here’s a scheme:

* If you receive an order of size 2 and an order of size 1, then process the small one first $5/6$ of the time, and the big one first $1/6$ of the time.

* If you receive three orders of size 1, then process two orders at random, wait $1/4$ minute twiddling your thumbs, and finally process the last order.
Kamior 2019-05-14 21:22:52
If I want to claim that this is a valid scheme, what do I need to check?
Kamior 2019-05-14 21:24:53
"Optimal" means the wait time we'd get by processing orders in increasing order of size. You can prove as a warm-up problem that that gives the lowest total wait time.
turtles0120 2019-05-14 21:25:07
strategy free
lcalvert99 2019-05-14 21:25:07
That it is efficient and strategy free
mathpenguin7 2019-05-14 21:25:07
Optimal total wait time and strategy free
daniel500 2019-05-14 21:25:07
the average total wait time
daniel500 2019-05-14 21:25:07
and that it is strategy free
MP2016p42 2019-05-14 21:25:07
the average wait time between the two strategies is 25/24 times the wait time
MP2016p42 2019-05-14 21:25:07
sho it's strategy free
Kamior 2019-05-14 21:25:12
Again, we need to check that it’s strategy-free and has a low enough wait time.
Kamior 2019-05-14 21:26:45
First, let's check that it’s strategy-free. If you want two paninis, what's your expected wait time if you do submit it as one order of size 2? And what if you split your order into two orders of size 1?
daniel500 2019-05-14 21:28:12
your wait time does not decrease
MP2016p42 2019-05-14 21:28:12
expected wait time is 13/4*2/3+2/3
Kamior 2019-05-14 21:28:14
If you submit two orders of size 1, your expected wait time is $(2/3)(3+1/4) + (1/3)(2) = 17/6$. If you submit one order of size 2, your expected wait time is $(1/6)(2) + (5/6)(1) = 17/6.$ So it's strategy-free.
Kamior 2019-05-14 21:28:24
Now, let's check that it's fast enough. If there are three orders of one panini each, the optimal total wait time is 1+2+3=6. What's the total wait time with our scheme?
sbudaraj 2019-05-14 21:29:41
6.25
achordia5 2019-05-14 21:29:41
6.25
turtles0120 2019-05-14 21:29:41
6.25 minutes?
BooBooTM 2019-05-14 21:29:41
6.25 minutes
Kamior 2019-05-14 21:29:47
The total wait time is $1+2+(3+1/4) = 25/4$, which is 25/24 times the optimal wait time of 1+2+3=6.
Kamior 2019-05-14 21:29:56
If there’s one order of one panini and one order of two, the optimal total wait time is 4, by making the smaller order first. What's the total wait time with our scheme?
Kamior 2019-05-14 21:31:00
The expected total wait time is $(1/6)(5)+(5/6)(4) = 25/6$, which is 25/24 times the optimal wait time of 4.
Kamior 2019-05-14 21:31:08
So, you may have thought it was crazy to deliberately deliver an order later than it could be, but it works!
Kamior 2019-05-14 21:31:19
Now, back to Kevin for problem 6.
KevinCarde 2019-05-14 21:31:36
Last problem! Whoo!
KevinCarde 2019-05-14 21:31:52
Incoming giant copy and paste of the problem statement:
KevinCarde 2019-05-14 21:32:06
Problem 6 Statement:

Jennifer and Serena are playing a game called Candy Split. They start with two piles of candy, one of size $M$ and one of size $K$. On a player's turn, she eats one of the piles and splits the other pile into two (non-empty) piles any way she wants. Whoever can't make a legal move (i.e.~is presented with two piles of one candy each) loses. Note that eating as much candy as possible is not the object of the game, though it may be a pleasant side effect.

[Warm-up exercise: do not submit an answer] Serena gets to decide whether to go first or second. What should she do when $M = 2018$ and $K = 2019$? What about for general values of $M$ and $K$? (Hint: it's all about the parity of $M$ and $K$.)

The reason we're not asking you to submit an answer for the warm-up exercise is that it's a famous problem that can be found in many places on the internet. (Feel free to look it up if you can't figure out the answer.) What we are really interested is a harder problem:

Suppose Jennifer and Serena have three different types of candy. The game is now played with six piles of candy -- two piles of each type. On a player's turn, she chooses a type of candy, eats one of the piles of that type, and splits the other. Whoever can't move loses. If the numbers are $(M_1, K_1), (M_2, K_2)$ and $(M_3, K_3)$, is it better to go first or second, and what is the winning strategy?

In order to solve this problem, you will need to learn a little bit of combinatorial game theory at this link: http://www.mathcamp.org/2019/cgt.pdf

Problem 6a: Fill out the following table of nimvalues for Candy Split. The $(M,K)$ entry of your table should show the nimvalue of the game with piles of size $M$ and $K$.

Problem 6b: The game is $(2,4)$, $(1,8)$, and $(3,5)$. It is Serena's turn. What should she do? Explain how to derive the answer from your table.

Problem 6c: Can you see a pattern in the table? If not, try enlarging the table some more until you see it. (Feel free to use a computer if you'd like, but you can certainly solve the problem without it.)

Based on your conjectured pattern, write down a formula (or algorithm) for computing the nimvalue of $(M, K)$ for all $M$ and $K$. If you can, prove your formula!

Problem 6d: The game is $(2,4)$, $(1,8)$, and $(2019, 2030)$. It is Serena's turn. What should she do? Explain how to derive the answer from your formula or pattern (even if you haven't proved it).
KevinCarde 2019-05-14 21:32:19
PROBLEM 6 SOLUTION
KevinCarde 2019-05-14 21:32:43
OK, first of all, this problem was unusual, but the setup was pretty cool: solving it requires some combinatorial game theory, so we provided an almost 20 page crash course with everything you needed to know about the topic.
KevinCarde 2019-05-14 21:32:52
(You can see the link in the problem statement.)
KevinCarde 2019-05-14 21:33:02
A large portion of the problem is reading and understanding that material, which we won't be able to cover in this Math Jam.
KevinCarde 2019-05-14 21:33:10
We're also going to power through this pretty fast. You might have to work through the transcript of this Math Jam together with the crash course at your leisure, if you want to get everything.
KevinCarde 2019-05-14 21:33:24
But let's do this!
KevinCarde 2019-05-14 21:33:25
PROBLEM 6a SOLUTION
KevinCarde 2019-05-14 21:33:47
We're supposed to fill out a table, so time for more giant copy and paste:
KevinCarde 2019-05-14 21:33:57
$$

\begin{array}{c|c|c|c|c|c|c|c|c}

M\backslash K & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\

\hline

1 &0 &1 &0 &2 &0 &1 &0 &3 \\ \hline

2 &1 &1 &2 &2 &1 &1 &3 &3 \\ \hline

3 &0 &2 &0 &2 &0 &3 &0 &3 \\ \hline

4 &2 &2 &2 &2 &3 &3 &3 &3 \\ \hline

5 &0 &1 &0 &3 &0 &1 &0 &3 \\ \hline

6 &1 &1 &3 &3 &1 &1 &3 &3 \\ \hline

7 &0 &3 &0 &3 &0 &3 &0 &3 \\ \hline

8 &3 &3 &3 &3 &3 &3 &3 &3

\end{array}

$$
KevinCarde 2019-05-14 21:34:10
Where in the world did this table come from? Let's talk a bit about how to fill it out.
KevinCarde 2019-05-14 21:34:24
We begin at $(1, 1)$, in the top left corner
KevinCarde 2019-05-14 21:34:29
Since there are no moves from $(1, 1)$, whoever has to move from this position loses, so the nimvalue is 0.
KevinCarde 2019-05-14 21:34:37
(If you don't know what nimvalue is, that's what the crash course document is for!)
dragonstar 2019-05-14 21:34:47
modulo 4?
KevinCarde 2019-05-14 21:35:00
There's definitely something with 2s or 4s going on, but that's not quite it -- we'll see as the problem develops!
KevinCarde 2019-05-14 21:35:25
Once we get started with the 0 in the top left corner, we can start building out the table using the MEX rule.
KevinCarde 2019-05-14 21:35:32
For example, let's look at $M = 6$, $K = 5$.
KevinCarde 2019-05-14 21:35:42
According to the rules of the game, we can move to any other game of total size 5 or 6.
KevinCarde 2019-05-14 21:35:48
The games of total size 5 are on the diagonal starting at $(4, 1)$ and going northeast, all of which have nimvalue 2.
KevinCarde 2019-05-14 21:36:02
The games of total size 6 are on the diagonal starting at $(5, 1)$ and going northeast, which alternate nimvalues of 0 and 2.
KevinCarde 2019-05-14 21:36:12
We can therefore reach positions with nimvalues 0 and 2.
KevinCarde 2019-05-14 21:36:34
According to the MEX rule, which says the nimvalue is the smallest value we can't reach, the nimvalue of $(6, 5)$ is therefore 1.
KevinCarde 2019-05-14 21:36:59
Repeat arguments like that zillions of times (it gets easier as you get into the rhythm of it), and you've got a table!
KevinCarde 2019-05-14 21:37:02
PROBLEM 6b SOLUTION
KevinCarde 2019-05-14 21:37:10
Now we're supposed to figure out a winning move if the game is $(2,4)$, $(1,8)$, and $(3,5)$.
KevinCarde 2019-05-14 21:37:28
This is a sum of three games, and we can use the table to find the nimvalues of each individual game. What are those nimvalues?
MarvelousMasterMark 2019-05-14 21:37:36
just convert it to a game of Nim
KevinCarde 2019-05-14 21:37:46
I should have checked the queue before sending my message !
MarvelousMasterMark 2019-05-14 21:38:18
(2,3,0)
KevinCarde 2019-05-14 21:38:40
Looking up $M=2$ and $K=4$ in the table shows a value of 2, and we repeat for the other ordered pairs.
KevinCarde 2019-05-14 21:39:00
A winning move is one that results in a nimsum of 0.
KevinCarde 2019-05-14 21:39:08
If we start with nimvalues 2, 3, and 0, what can we do to change the nimsum to 0?
daniel500 2019-05-14 21:39:48
convert the values into binary and find the move that results in 0 after addition without carry
KevinCarde 2019-05-14 21:39:53
That's the general strategy and...
BooBooTM 2019-05-14 21:39:56
Either move the 3 to a 2, or the o to a 1
KevinCarde 2019-05-14 21:40:02
...is one way to do it, and...
mathpenguin7 2019-05-14 21:40:07
(1,8) should go to (4,4), so we get 2nimsum2nimsum0=0.
KevinCarde 2019-05-14 21:40:15
is a move that changes the nimvalue 3 to a nimvalue 2, which is what we want!
KevinCarde 2019-05-14 21:40:59
So: Move in the game $(1, 8)$, split the $8$ into $(4, 4)$, resulting in nimvalues 2, 2, and 0, which have nimsum 0. A winning move!
BooBooTM 2019-05-14 21:41:03
or (3,5) to (1,2) which results in 2nimsum3 = 1
KevinCarde 2019-05-14 21:41:14
Another way to win the game, changing the nimvalue 0 to nimvalue 1, which also works.
lcalvert99 2019-05-14 21:41:18
So you get a checkerboard pattern for progressively bigger n
KevinCarde 2019-05-14 21:41:48
Yes! The table does seem to have some sort of pattern of this sort. We won't be able to investigate fully all the cool ways things fit together, but observations like these lead to results!
KevinCarde 2019-05-14 21:42:06
So, we've found (more than) one way to win the game in Part b... time to get real and figure out what's going on in general.
KevinCarde 2019-05-14 21:42:11
PROBLEM 6c SOLUTION
KevinCarde 2019-05-14 21:42:29
There were some observations about powers of two, and checkerboard patterns, and
MarvelousMasterMark 2019-05-14 21:42:32
It's a fractal!!
KevinCarde 2019-05-14 21:43:00
...all of which suggests that 2s and powers of 2 are important. That means: check out binary!
KevinCarde 2019-05-14 21:43:28
There are a lot of ways to describe a pattern or algorithm to compute nimvalues in Candy Split
KevinCarde 2019-05-14 21:44:17
I'm going to charge forward and present some results for us to prove, so if you want to puzzle things out for yourself, it might be a good time to look away.
KevinCarde 2019-05-14 21:44:22
This is the last problem, so you wouldn't be missing anything else
KevinCarde 2019-05-14 21:45:25
But: when we look at binary expansions, we might discover some interesting patterns.
KevinCarde 2019-05-14 21:45:37
I'm going to short circuit the exploration, and we'll prove the following two claims:
KevinCarde 2019-05-14 21:45:45
Claim 1: The nimvalue of $(M, K)$ equals the smallest place in binary where both $M - 1$ and $K - 1$ are zero.
KevinCarde 2019-05-14 21:46:11
Claim 2: The set of nimvalues of all games $(M, K)$ with $M + K = S$ is precisely the set of places of 1s in the binary expansion of $S - 1$.
KevinCarde 2019-05-14 21:46:27
Let's take a look at an example, since the claims are kind of crazy.
KevinCarde 2019-05-14 21:47:16
Consider the game $(6, 5)$. The relevant binary expansions are $6 - 1 = 101_2$ and $5 - 1 = 100_2$. Since these both have a 0 in the 1st position ("2s digit"), Claim 1 says the nimvalue of $(6, 5)$ should be 1, which agrees with our table
KevinCarde 2019-05-14 21:47:59
Let $n = 7$. Then the games where $M + K = 7$ are the ones in the table starting at $(6, 1)$ and going northeast. We see as nimvalues the set $\{1, 2\}$, and in base 2, $7 - 1 = 110_2$ has a 1 in the 1st ("2s digit") and 2nd ("4s digit") places, which agrees with Claim 2.
KevinCarde 2019-05-14 21:48:18
(Note that the rightmost digit, the "1s digit", is the 0th place.)
KevinCarde 2019-05-14 21:48:38
Let's now prove this! The proof will be somewhat intricate in structure.
KevinCarde 2019-05-14 21:48:40
Proof of Claims: We prove the two claims simultaneously by strong induction on $S = M + K$.
KevinCarde 2019-05-14 21:48:50
For our base case $S = 2$, we have only one game $(1, 1)$ whose nimvalue is 1. This agrees with both claims.
KevinCarde 2019-05-14 21:49:19
Now we'll prove Claim 1 for $S = n$ by assuming the claims are true for $S < n$.
KevinCarde 2019-05-14 21:49:25
Inductive step for Claim 1
KevinCarde 2019-05-14 21:49:32
Suppose we have a game with $M + K = n$.
KevinCarde 2019-05-14 21:49:40
As an important first note, since $M$ and $K$ are each at least 1, $M$ and $K$ are both strictly less than $n$. This will be important for applying our inductive hypothesis!
KevinCarde 2019-05-14 21:49:49
Now let's see what nimvalues we can reach from $(M, K)$.
KevinCarde 2019-05-14 21:50:07
If we choose to split $M$, we can get all possible games with $(A, B)$ with $A + B = M$. Since $M < n$, Claim 2 applies, and the nimvalues we can reach are precisely the places of 1s in the binary expansion of $M-1$.
KevinCarde 2019-05-14 21:50:28
The exact same logic applies for $K$.
KevinCarde 2019-05-14 21:50:40
Therefore, according to the MEX rule, the nimvalue of $(M, K)$ will be the first place where neither $M-1$ nor $K-1$ has a 1; in other words, the first place they're both 0.
KevinCarde 2019-05-14 21:51:06
That's Claim 1! Claim 2 is going to be a little rougher.
KevinCarde 2019-05-14 21:51:14
Inductive step for Claim 2
KevinCarde 2019-05-14 21:51:28
Now that we have done Claim 1, we can in fact assume Claim 1 holds for $S = n$, and use it to prove Claim 2 for $S = n$.
KevinCarde 2019-05-14 21:51:56
(Our inductive ladder is a bit staggered here -- a little more complicated than a lot of inductive proofs!)
KevinCarde 2019-05-14 21:52:08
Let's rephrase Claim 2, both as a reminder to ourselves and to make our strategy clearer.
KevinCarde 2019-05-14 21:52:27
There is a game $(M, K)$ with $M + K = n$ and nimvalue $v$ if and only if the binary expansion of $n-1$ has a 1 in the $v$th place.
KevinCarde 2019-05-14 21:52:45
This is an if and only if statement, so we have two directions to prove.
KevinCarde 2019-05-14 21:52:49
Game with nimvalue $v$ implies $n-1$ has a 1 in the $v$th place
KevinCarde 2019-05-14 21:53:05
If $(M, K)$ has nimvalue $1$, then by Claim 1, the first place where neither $M - 1$ nor $K - 1$ has a 1 is $v$. This means that there's at least one 1 in all the lower places, and we can write:
KevinCarde 2019-05-14 21:53:19
$$n - 1 = 1 + (M-1) + (K-1) \ge 1 + 1 + 2 + 4 + \dots + 2^{v-1} = 2^v.$$
KevinCarde 2019-05-14 21:53:39
Therefore, when we add up to get $n - 1$, some carrying will occur to bring a 1 into the $v$th place.
KevinCarde 2019-05-14 21:54:05
Since neither $M-1$ nor $K-1$ has a 1 in the $v$th place to begin with, this 1 from carrying is the only contribution to the $v$th place of $n-1$, and we conclude that $n-1$ does have a 1 there!
KevinCarde 2019-05-14 21:54:42
That's this direction. Again, we're being pretty brisk here, so I invite you to go over the transcript more leisurely later if you're interested!
KevinCarde 2019-05-14 21:54:57
$n-1$ has a 1 in the $v$th place implies game with nimvalue $v$
KevinCarde 2019-05-14 21:55:11
For this direction, we simply need to construct a game with nimvalue $v$.
KevinCarde 2019-05-14 21:55:19
Set $M - 1$ to have the same binary expansion as $n - 1$, but with the 1 in place $v$ replaced by a zero.
KevinCarde 2019-05-14 21:55:48
(By assumption, there was a 1 in that place; now make it a 0, and call that $M-1$)
KevinCarde 2019-05-14 21:56:03
Since we want $M+K = n$, we set $K = n - M = (n-1) - (M-1) = 2^v$.
KevinCarde 2019-05-14 21:56:16
Note that $K - 1 = 2^v - 1$ has a 1 in every place up to, but not including, the $v$th place. Therefore, by Claim 1, the nimvalue of $(M, K)$ must be at least $v$.
KevinCarde 2019-05-14 21:56:35
However, $K-1$ has a 0 in the $v$th place, and $M-1$ does too by definition, so we conclude that the nimvalue of $(M, K)$ is precisely $v$!
KevinCarde 2019-05-14 21:56:58
That wraps up this direction, and with it, the entire proof!!
KevinCarde 2019-05-14 21:57:24
So: both Claim 1 (which tells us how to compute nimvalues) and Claim 2 (which tells us the nimvalues we can reach from a given game) are true.
KevinCarde 2019-05-14 21:57:33
In practice, Claim 1 is the useful claim for playing the game.
KevinCarde 2019-05-14 21:57:37
Let's see it in action!
KevinCarde 2019-05-14 21:57:43
PROBLEM 6d SOLUTION
KevinCarde 2019-05-14 21:57:48
The game is $(2,4)$, $(1,8)$, and $(2019, 2030)$.
KevinCarde 2019-05-14 21:58:24
The first two games are in our table, and we can look up the nimvalues.
KevinCarde 2019-05-14 21:58:42
They are 2 and 3.
KevinCarde 2019-05-14 21:58:55
Now, the main event: what's the nimvalue of $(2019, 2030)$?
KevinCarde 2019-05-14 21:59:04
Here are the relevant binary expansions:

$$

2019 = 11111100011_2

$$

$$

2030 = 11111101110_2

$$
MarvelousMasterMark 2019-05-14 21:59:37
4
KevinCarde 2019-05-14 22:00:07
Great: the smallest place where both binary numbers have a 0 is the 4th position (keeping in mind that the rightmost position is "0th"), so the nimvalue is 4.
KevinCarde 2019-05-14 22:00:23
We have nimvalues 2, 3, and 4, so to win this game, we should change the 4 into a 1, as the nimsum of 2, 3, and 1 is 0.
KevinCarde 2019-05-14 22:00:50
Any suggestions for moves that change $(2019, 2030)$ into something with nimvalue 1?
KevinCarde 2019-05-14 22:01:09
(I'll pause for a bit, but we should wrap up, so that might be a rhetorical question .)
KevinCarde 2019-05-14 22:01:31
There are lots of possibilities, and the simplest is perhaps
MarvelousMasterMark 2019-05-14 22:01:33
(1,2018)
KevinCarde 2019-05-14 22:02:00
2018 is 2 mod 4, which means it has a 0 in its 1st digit (the "2s digit"), where of course 1 also has a 0.
KevinCarde 2019-05-14 22:02:05
Therefore, the nimvalue is 1
KevinCarde 2019-05-14 22:02:15
If we split 2019 into $(1, 2018)$, we can win this big game!
BooBooTM 2019-05-14 22:02:35
Split into odd and even pile, with odd pile congruent to 1 (mod 4)
KevinCarde 2019-05-14 22:03:01
That's a way to generate this possibility and many others!
KevinCarde 2019-05-14 22:03:17
And winning this game is the final challenge of the 2019 Mathcamp Qualifying Quiz, so with that, we're through. Huzzah!
KevinCarde 2019-05-14 22:03:37
Time to wrap up -- thank you so much for spending your evening with us!
KevinCarde 2019-05-14 22:03:47
If we didn't get to your question, you can also post questions in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too!
BooBooTM 2019-05-14 22:03:59
Thanks!
MarvelousMasterMark 2019-05-14 22:03:59
Thanks so much! This was fun!
KevinCarde 2019-05-14 22:04:20
Thank you, and to the rest of the brave Math Jammers who stuck through to the end (and even to those who stayed for only part of the Jam )
KevinCarde 2019-05-14 22:04:29
Thanks again, everybody - good night!
Kamior 2019-05-14 22:05:00
Good night, all!
eminentabyss 2019-05-14 22:05:07
A huge thank you to all of you who attended tonight and the awesome Mathcamp staff for this rad Math Jam!
eminentabyss 2019-05-14 22:05:38
Just a note, a transcript of this Math Jam will be posted soon here: http://www.aops.com/school/mathjams-transcripts
iks92 2019-05-14 22:06:05
Thank you!
MarvelousMasterMark 2019-05-14 22:06:05
Goodbye!
Damalone 2019-05-14 22:06:05
Thanks!
BooBooTM 2019-05-14 22:06:18
Bye!

Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.