Mathcamp 2019 Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveThis 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!
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.
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.
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.
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
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!
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:
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.
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.
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.
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!
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!
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.
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
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!).
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!
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}$.
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).
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
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
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
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.
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!
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).
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.
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
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.
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.
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}$.
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?
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)
1 / sqrt(1 + x^2)
mathpenguin7
2019-05-14 19:37:20
1/sqrt(1+x^2)
1/sqrt(1+x^2)
MarvelousMasterMark
2019-05-14 19:37:20
$\dfrac{1}{\sqrt{1+x^2}}$
$\dfrac{1}{\sqrt{1+x^2}}$
turtles0120
2019-05-14 19:37:20
1/sqrt {1+x^2}
1/sqrt {1+x^2}
ilovemath04
2019-05-14 19:37:20
1/sqrt(1+x^2)
1/sqrt(1+x^2)
eisirrational
2019-05-14 19:37:20
$\cos A=\frac{1}{\sqrt{x^2+1}}$
$\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}}.$$
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}}.$$
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.)
(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?
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:
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.
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:
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).
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?
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)
f(x-1)
beiqiang
2019-05-14 19:40:53
f(x_n-1)
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} $$
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}$$
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$.
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}$$
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?
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
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
0,1,1/2,2/3,3/5,5/8,... fibonacci
MP2016p42
2019-05-14 19:42:20
0,1,1/2
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$
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.
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$).
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!
Fibbonaci!
MP2016p42
2019-05-14 19:42:49
lets test it?
lets test it?
Z_Math404
2019-05-14 19:42:49
induction!
induction!
MarisaD
2019-05-14 19:42:52
Yeah!
Yeah!
MarisaD
2019-05-14 19:42:57
Induction it is.
Induction it is.
MarisaD
2019-05-14 19:43:03
For our base case, $a_0 = \frac{0}{1}$. Check.
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}}$.
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}}}$$
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}}$$
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:
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}}} $$
$$ f^n(x) = x_n = \sqrt{a_n} = \sqrt{\frac{F_n}{F_{n+1}}} $$
FIREDRAGONMATH16
2019-05-14 19:43:48
nice!
nice!
MarisaD
2019-05-14 19:43:52
Right? I think it's really pretty!
Right? I think it's really pretty!
MarisaD
2019-05-14 19:43:57
On to part b:
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.)
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.
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$.
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)$.
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}}$.
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.
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}}$$
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}$$
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?
We get to pick the positive root here. Why?
beiqiang
2019-05-14 19:45:54
L > 0
L > 0
Z_Math404
2019-05-14 19:45:54
L^2 is positive
L^2 is positive
AIME12345
2019-05-14 19:45:54
because $x_n$ is positive
because $x_n$ is positive
MarvelousMasterMark
2019-05-14 19:46:05
Because our sequence is restricted to positive numbers.
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.
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 $$
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)
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!
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.
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.
Onwards to problem 2.
KevinCarde
2019-05-14 19:47:37
Hi everyone! I'll take it from MarisaD for a bit here
.
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?
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
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.
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.
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!
But feel free to think about variants on your own time!
KevinCarde
2019-05-14 19:48:47
Susan's Score
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!
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!
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?
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)
(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
5/6 probability
alokkumar1974
2019-05-14 19:50:49
5/6 is the probability if she doesnt roll one.
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
Probability is 5/6, average score is 4
mathpenguin7
2019-05-14 19:50:49
Probability: 5/6 Average score: 4
Probability: 5/6 Average score: 4
VishnuM34
2019-05-14 19:50:49
5/6
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
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
5/6
FIREDRAGONMATH16
2019-05-14 19:50:49
average score: $(2+3+4+5+6)/5 = 4$
average score: $(2+3+4+5+6)/5 = 4$
Tinjeson347
2019-05-14 19:50:49
4
4
alokkumar1974
2019-05-14 19:50:49
4 is the average and 5/6 is the probability!
4 is the average and 5/6 is the probability!
alice5502
2019-05-14 19:50:49
5/6, 4
5/6, 4
KevinCarde
2019-05-14 19:51:03
Great! Some of you are already putting it together one step further.
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$.
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!)
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
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$
$S = \frac{5}{6}\cdot 4 + \frac{1}{6}\cdot T$
cornn
2019-05-14 19:53:08
5/6*4+T/6
5/6*4+T/6
Damalone
2019-05-14 19:53:08
S=T/6+10/3
S=T/6+10/3
aggu123
2019-05-14 19:53:08
(5/6)*4+(1/6)*T
(5/6)*4+(1/6)*T
Hueman
2019-05-14 19:53:08
S=10/3+T/6
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$.
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?
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$
$T = 2S$
mathpenguin7
2019-05-14 19:55:22
$T=2S$
$T=2S$
Hueman
2019-05-14 19:55:22
T=2S
T=2S
sbudaraj
2019-05-14 19:55:22
T=2S
T=2S
aggu123
2019-05-14 19:55:22
T=2S
T=2S
alice5502
2019-05-14 19:55:22
2T = S
2T = S
bookoverlord
2019-05-14 19:55:22
T =2S ?
T =2S ?
lightning50
2019-05-14 19:55:22
2S=T
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$.
$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!
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$
$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.
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.
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!
That's certainly a valid approach!
KevinCarde
2019-05-14 19:56:11
And we'll do something similar for Eric. (Foreshadowing!)
And we'll do something similar for Eric. (Foreshadowing!)
KevinCarde
2019-05-14 19:56:23
So, let's get to it!
So, let's get to it!
KevinCarde
2019-05-14 19:56:29
Eric's Score
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.
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.
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:
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?
* 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?
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
the same
mathpenguin7
2019-05-14 19:58:28
They are the same.
They are the same.
Tinjeson347
2019-05-14 19:58:28
Equal
Equal
alokkumar1974
2019-05-14 19:58:28
Neither, there equal!
Neither, there equal!
popcorn1
2019-05-14 19:58:28
They're equal, right?
They're equal, right?
Physick
2019-05-14 19:58:28
both have the same probability
both have the same probability
bookoverlord
2019-05-14 19:58:28
arn't they both 50 -50?
arn't they both 50 -50?
MarvelousMasterMark
2019-05-14 19:58:28
equal
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.
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!
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.
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.
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?
There are several ways to see this. Any ideas?
lightning50
2019-05-14 20:00:17
Doesn't that depend on n?
Doesn't that depend on n?
lcalvert99
2019-05-14 20:00:17
Do it by induction.
Do it by induction.
KevinCarde
2019-05-14 20:00:32
(Oops, meant to pass the "depends on n" comment earlier.)
(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.
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.
Imagine rolling the first n-1 dice.
AIME12345
2019-05-14 20:01:13
the last dice rolled determines parity of sum
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
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
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
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.
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.
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!
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.
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.
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.
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:
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)
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
= 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.
And that's exactly what the Flawed Claim wanted.
KevinCarde
2019-05-14 20:04:37
So, uh, what's wrong?
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!)
(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.
Case with one die.
lcalvert99
2019-05-14 20:05:52
It's not true for the base case.
It's not true for the base case.
MP2016p42
2019-05-14 20:05:52
1 die
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.
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!
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.
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.
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$.
Therefore, the claim holds, but only for $n \ge 2$.
KevinCarde
2019-05-14 20:07:03
Base cases are important!
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.
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$):
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.
$$
$$
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!
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}.
$$
$$
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?
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!
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
Its the derivative of the geometric series
mathpenguin7
2019-05-14 20:09:10
Yup.
Yup.
lcalvert99
2019-05-14 20:09:10
Yeah!
Yeah!
KevinCarde
2019-05-14 20:09:20
We've got some true statements and some enthusiasm!
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).
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.
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}
$$
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.)
(I sure hope I got my indexes right.)
KevinCarde
2019-05-14 20:11:03
Now we can continue to rewrite things:
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}
$$
$$
\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}
$$
$$
= 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
$$
$$
= 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!
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:
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
$$
$$
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.
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!
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.)
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.
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.
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
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?
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
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.
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
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...
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).
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?
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).
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)
But solving part (a) helped to solve part (b)
MarisaD
2019-05-14 20:15:03
Yeah!! That was the secret plan.
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)?
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."
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?
Thoughts?
MarvelousMasterMark
2019-05-14 20:16:30
The equivalent is lcm(K,M).
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
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.
It has to cycle.
duck_master
2019-05-14 20:16:30
every $\text{lcm}(K, M)$ turns the game cycles
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.
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.
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.")
(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?
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?
Pick some K and M?
jenniferwangg
2019-05-14 20:17:22
Try small values and look for a pattern.
Try small values and look for a pattern.
MarisaD
2019-05-14 20:17:27
Small cases!!
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.)
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:
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.
(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?
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:
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.
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
Prooving that cycling will happen
duck_master
2019-05-14 20:19:47
can we come up with this conjecture without coding?
can we come up with this conjecture without coding?
MarisaD
2019-05-14 20:19:50
Absolutely.
Absolutely.
MarisaD
2019-05-14 20:20:02
(It just sometimes helps.)
(It just sometimes helps.)
MarisaD
2019-05-14 20:20:20
So, essentially: in case (1), everyone gets to speak, like in part (a)
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.
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.)
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?
How many FLIPs occur every cycle?
MarvelousMasterMark
2019-05-14 20:21:19
lcm(K,M)/K
lcm(K,M)/K
MarisaD
2019-05-14 20:21:26
Yup. So, we know the game flips direction every cycle because...
Yup. So, we know the game flips direction every cycle because...
duck_master
2019-05-14 20:21:59
this number is odd
this number is odd
MarisaD
2019-05-14 20:22:09
Yup. An odd number of flips = the game changes direction. QED.
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.
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?
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
0
jenniferwangg
2019-05-14 20:23:15
0
0
MarisaD
2019-05-14 20:23:27
Right! Why?
Right! Why?
jenniferwangg
2019-05-14 20:24:18
Because every time you flip, you flip back.
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
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
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.
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.
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.
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?
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..)
(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.
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$.
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.
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?
What theorem will help us out?
duck_master
2019-05-14 20:28:10
chinese remainder theorem?
chinese remainder theorem?
jenniferwangg
2019-05-14 20:28:10
Chinese Remainder Theorem?
Chinese Remainder Theorem?
tervis
2019-05-14 20:28:10
chinese remainder theorem
chinese remainder theorem
MarisaD
2019-05-14 20:28:16
Yes! The Chinese Remainder Theorem.
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$.
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.)
(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.
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.
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$.
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!
OH!
MarisaD
2019-05-14 20:29:47
Right?
Right?
MarisaD
2019-05-14 20:29:52
Onwards to Problem 4!
Onwards to Problem 4!
KevinCarde
2019-05-14 20:29:56
Hello again everyone!
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$.
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$.
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$.
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.
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!
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.
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:
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)
(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.)
(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.)
(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.
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.
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!
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
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$?
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)$
$(1,1)$
duck_master
2019-05-14 20:33:19
you're already done
you're already done
Tony_1567366
2019-05-14 20:33:19
a circle?
a circle?
daniel500
2019-05-14 20:33:19
(1, 1)
(1, 1)
MarvelousMasterMark
2019-05-14 20:33:19
just a disc with the number 1
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!
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!
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$?
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)
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?
Can we make two complete disks out of them?
MarvelousMasterMark
2019-05-14 20:34:51
not possible
not possible
jenniferwangg
2019-05-14 20:34:51
It's not possible.
It's not possible.
achordia5
2019-05-14 20:34:51
No
No
daniel500
2019-05-14 20:34:51
no
no
iks92
2019-05-14 20:34:51
no
no
jenniferwangg
2019-05-14 20:34:51
No.
No.
ethiomath
2019-05-14 20:34:51
No solution
No solution
MP2016p42
2019-05-14 20:34:51
nope
nope
mathpenguin7
2019-05-14 20:34:51
No
No
popcorn1
2019-05-14 20:34:51
No!
No!
turtles0120
2019-05-14 20:34:51
I don't think so
I don't think so
KevinCarde
2019-05-14 20:34:57
Sad.
Sad
.
MP2016p42
2019-05-14 20:35:01
11 and 22 can't be paired
11 and 22 can't be paired
jenniferwangg
2019-05-14 20:35:01
You can't have two (1, 1) pieces.
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.
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!
And all our wedges must be used exactly once!
jenniferwangg
2019-05-14 20:35:30
But the question asks for k ≥ 2.
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!
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.)
(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$.
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.
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!
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:
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)
(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)}
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.
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:
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.
* 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
uh oh
KevinCarde
2019-05-14 20:38:14
I did not want that face there, oops.
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!
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.
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!
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!
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.
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)
Alternatively, one could add (1, 3), (3, 1)
KevinCarde
2019-05-14 20:39:57
The first of many branching paths!
The first of many branching paths!
KevinCarde
2019-05-14 20:40:03
There are many, many different possible solutions.
There are many, many different possible solutions.
KevinCarde
2019-05-14 20:40:12
Let's move onward to $N = 5$.
Let's move onward to $N = 5$.
KevinCarde
2019-05-14 20:40:17
It'll go very similarly!
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:
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$?
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$.
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$:
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.
* 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!)
(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.
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$.
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!
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!
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.
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$.
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:
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)
* (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!)
(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:
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]
\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!
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.
Yeah! Let's move on to the general case, also known as Part b.
KevinCarde
2019-05-14 20:46:17
PROBLEM 4b SOLUTION
PROBLEM 4b SOLUTION
KevinCarde
2019-05-14 20:46:29
We've already been building up new solutions from old, so that means... induction!
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$.
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?
A trick question of sorts: what's our base case?
duck_master
2019-05-14 20:47:17
$N=1$ or $N=4$
$N=1$ or $N=4$
AIME12345
2019-05-14 20:47:17
$N=4$
$N=4$
AIME12345
2019-05-14 20:47:17
$N=3$
$N=3$
MarvelousMasterMark
2019-05-14 20:47:17
for odd, N=1, for even N= 4?
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$.
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!
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.
We haven't touched even numbers, though.
KevinCarde
2019-05-14 20:48:11
Is $N = 4$ possible? $N = 2$ wasn't...
Is $N = 4$ possible? $N = 2$ wasn't...
EigenVictor
2019-05-14 20:48:52
Sure is!
Sure is!
MarvelousMasterMark
2019-05-14 20:48:56
Yes
Yes
ethiomath
2019-05-14 20:48:58
Yes
Yes
MP2016p42
2019-05-14 20:49:03
yes, the problem says to prove it
yes, the problem says to prove it
KevinCarde
2019-05-14 20:49:11
This is excellent logic
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}
\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
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$?
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
(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)
(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.
The size of the pieces grows, too.
Hueman
2019-05-14 20:51:25
Make 2 new disks + fill previous ones
Make 2 new disks + fill previous ones
turtles0120
2019-05-14 20:51:25
We had to use the n=3 cases?
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
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
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!
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:
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$.
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!
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$.
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:
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$.
* 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...)
(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)$.)
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!
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$.
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.
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.
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.
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!
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.
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!
Onwards to Problem 5!
Kamior
2019-05-14 20:56:34
Hi, all!
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.
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.
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
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?
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)
k/(k+1)
MarvelousMasterMark
2019-05-14 20:59:58
$\dfrac{k}{k+1}$
$\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.
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.
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
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.
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.
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.
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!
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.
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.
...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?
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.
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
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.
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.
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?
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
#3 because I tried to do it but couldn't make it work
sbudaraj
2019-05-14 21:08:51
3rd one
3rd one
Damalone
2019-05-14 21:08:51
#3
#3
MarvelousMasterMark
2019-05-14 21:08:51
3
3
turtles0120
2019-05-14 21:08:51
the third
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?
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
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$.
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.
Let's move on to the solution.
Kamior
2019-05-14 21:12:27
Problem 5b solution
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.)
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.
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.
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.
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.
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.
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}$).
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}.$$
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.)
(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]$?
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.)
(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.)
(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
1/2
MarvelousMasterMark
2019-05-14 21:19:50
1/2
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$.
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
1/2
laihpos062807
2019-05-14 21:20:02
1/2
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}$.
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$.
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?
Does that always decrease the expected wait time?
daniel500
2019-05-14 21:21:34
yes
yes
laihpos062807
2019-05-14 21:21:39
yesn
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.)
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.
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.
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!
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
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.
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?
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.
"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
strategy free
lcalvert99
2019-05-14 21:25:07
That it is efficient and strategy free
That it is efficient and strategy free
mathpenguin7
2019-05-14 21:25:07
Optimal total wait time and strategy free
Optimal total wait time and strategy free
daniel500
2019-05-14 21:25:07
the average total wait time
the average total wait time
daniel500
2019-05-14 21:25:07
and that it is strategy free
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
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
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.
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?
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
your wait time does not decrease
MP2016p42
2019-05-14 21:28:12
expected wait time is 13/4*2/3+2/3
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.
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?
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
6.25
achordia5
2019-05-14 21:29:41
6.25
6.25
turtles0120
2019-05-14 21:29:41
6.25 minutes?
6.25 minutes?
BooBooTM
2019-05-14 21:29:41
6.25 minutes
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.
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?
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.
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!
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.
Now, back to Kevin for problem 6.
KevinCarde
2019-05-14 21:31:36
Last problem! Whoo!
Last problem! Whoo!
KevinCarde
2019-05-14 21:31:52
Incoming giant copy and paste of the problem statement:
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).
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
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.
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.)
(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.
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.
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!
But let's do this!
KevinCarde
2019-05-14 21:33:25
PROBLEM 6a SOLUTION
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:
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}
$$
$$
\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.
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
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.
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!)
(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?
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!
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.
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$.
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.
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.
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.
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.
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.
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!
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
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)$.
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?
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
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!
I should have checked the queue before sending my message
!
MarvelousMasterMark
2019-05-14 21:38:18
(2,3,0)
(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.
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.
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?
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
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...
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
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...
...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.
(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!
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!
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
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.
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
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!
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.
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
PROBLEM 6c SOLUTION
KevinCarde
2019-05-14 21:42:29
There were some observations about powers of two, and checkerboard patterns, and
There were some observations about powers of two, and checkerboard patterns, and
MarvelousMasterMark
2019-05-14 21:42:32
It's a fractal!!
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!
...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
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.
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
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.
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:
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.
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$.
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.
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
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.
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.)
(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.
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$.
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.
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$.
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
Inductive step for Claim 1
KevinCarde
2019-05-14 21:49:32
Suppose we have a game with $M + K = n$.
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!
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)$.
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$.
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$.
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.
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.
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
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$.
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!)
(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.
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.
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.
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
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:
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.$$
$$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.
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!
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!
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$
$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$.
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.
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$)
(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$.
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$.
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$!
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!!
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.
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.
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!
Let's see it in action!
KevinCarde
2019-05-14 21:57:43
PROBLEM 6d SOLUTION
PROBLEM 6d SOLUTION
KevinCarde
2019-05-14 21:57:48
The game is $(2,4)$, $(1,8)$, and $(2019, 2030)$.
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.
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.
They are 2 and 3.
KevinCarde
2019-05-14 21:58:55
Now, the main event: what's the nimvalue of $(2019, 2030)$?
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
$$
Here are the relevant binary expansions:
$$
2019 = 11111100011_2
$$
$$
2030 = 11111101110_2
$$
MarvelousMasterMark
2019-05-14 21:59:37
4
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.
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.
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?
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.)
(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
There are lots of possibilities, and the simplest is perhaps
MarvelousMasterMark
2019-05-14 22:01:33
(1,2018)
(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.
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
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!
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)
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!
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!
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!
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!
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!
Thanks!
MarvelousMasterMark
2019-05-14 22:03:59
Thanks so much! This was fun!
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)
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!
Thanks again, everybody - good night!
Kamior
2019-05-14 22:05:00
Good night, all!
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!
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
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!
Thank you!
MarvelousMasterMark
2019-05-14 22:06:05
Goodbye!
Goodbye!
Damalone
2019-05-14 22:06:05
Thanks!
Thanks!
BooBooTM
2019-05-14 22:06:18
Bye!
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.
