Mathcamp 2022 Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveThis Math Jam will discuss solutions to the 2022 Mathcamp Qualifying Quiz. Mathcamp is an intensive 5-week-long summer program for mathematically talented high school student. 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: AoPS Staff
kevinyaiko
2022-05-17 19:02:59
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:30 pm ET (4:30 pm PT).
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:30 pm ET (4:30 pm PT).
kevinyaiko
2022-05-17 19:03:14
If you are enrolled in a course and trying to attend it, then you should leave the classroom now, click Classroom in the Online School dropdown, and then choose the appropriate link on the next page.
If you are enrolled in a course and trying to attend it, then you should leave the classroom now, click Classroom in the Online School dropdown, and then choose the appropriate link on the next page.
kevinyaiko
2022-05-17 19:03:20
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all.
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all.
kevinyaiko
2022-05-17 19:20:48
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:30 pm ET (4:30 pm PT).
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:30 pm ET (4:30 pm PT).
kevinyaiko
2022-05-17 19:20:56
If you are enrolled in a course and trying to attend it, then you should leave the classroom now, click Classroom in the Online School dropdown, and then choose the appropriate link on the next page.
If you are enrolled in a course and trying to attend it, then you should leave the classroom now, click Classroom in the Online School dropdown, and then choose the appropriate link on the next page.
kevinyaiko
2022-05-17 19:21:02
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all.
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all.
kevinyaiko
2022-05-17 19:31:11
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Taco-Cat
2022-05-17 19:31:29
Hello!
Hello!
Enderman_1010
2022-05-17 19:31:29
Hello!
Hello!
Cygnet
2022-05-17 19:31:29
Hello!
Hello!
TheMathLemmon314
2022-05-17 19:31:29
YAY!!
YAY!!
Pendronator
2022-05-17 19:31:29
hi!!!
hi!!!
kevinyaiko
2022-05-17 19:31:32
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.
kevinyaiko
2022-05-17 19:31:42
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.
kevinyaiko
2022-05-17 19:31:54
Also, you'll find that you can adjust the classroom windows in a variety of ways by clicking on the user dropdown menu in the top-right corner of the classroom.
Also, you'll find that you can adjust the classroom windows in a variety of ways by clicking on the user dropdown menu in the top-right corner of the classroom.
Cygnet
2022-05-17 19:32:15
What is Mathcamp?
What is Mathcamp?
kevinyaiko
2022-05-17 19:32: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: 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: www.mathcamp.org
kevinyaiko
2022-05-17 19:32:33
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
kevinyaiko
2022-05-17 19:32:46
Each year, Mathcamp creates a Qualifying Quiz, which is the main component of the application process. If you haven't already seen it, you can find the 2022 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, the following Mathcamp staff (all members of this year's Quiz committee) will discuss the problems and their solutions:
Each year, Mathcamp creates a Qualifying Quiz, which is the main component of the application process. If you haven't already seen it, you can find the 2022 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, the following Mathcamp staff (all members of this year's Quiz committee) will discuss the problems and their solutions:
kevinyaiko
2022-05-17 19:32:58
Kevin Carde (KevinCarde) iis the Assistant Director and Technical Lead of Mathcamp. He's been part of every Mathcamp summer since 2011.
Kevin Carde (KevinCarde) iis the Assistant Director and Technical Lead of Mathcamp. He's been part of every Mathcamp summer since 2011.
kevinyaiko
2022-05-17 19:33:11
Misha Lavrov (Misha) has been teaching topics ranging from graph theory to pillow-throwing at Mathcamp since 2014. During the rest of the year, he teaches and does math at Kennesaw State University in Georgia.
Misha Lavrov (Misha) has been teaching topics ranging from graph theory to pillow-throwing at Mathcamp since 2014. During the rest of the year, he teaches and does math at Kennesaw State University in Georgia.
kevinyaiko
2022-05-17 19:33:20
Tim Black (timblack) has taught Mathcamp classes ranging from complexity theory to children's board games, plus a lot of ways to avoid doing calculus. He's been at camp as either a camper or staff most summers since 2005. He is currently an Assistant Instructional Professor at the University of Chicago, where he teaches math and computer science.
Tim Black (timblack) has taught Mathcamp classes ranging from complexity theory to children's board games, plus a lot of ways to avoid doing calculus. He's been at camp as either a camper or staff most summers since 2005. He is currently an Assistant Instructional Professor at the University of Chicago, where he teaches math and computer science.
kevinyaiko
2022-05-17 19:33:35
Let's turn the room over to Kevin Carde now to get us started!
Let's turn the room over to Kevin Carde now to get us started!
KevinCarde
2022-05-17 19:33:48
Hi, everybody, and welcome to the annual Mathcamp Qualifying Quiz Jam!
Hi, everybody, and welcome to the annual Mathcamp Qualifying Quiz Jam!
Pendronator
2022-05-17 19:34:06
Hi Kevin!
Hi Kevin!
Pendronator
2022-05-17 19:34:06
and Misha!
and Misha!
LJCoder619
2022-05-17 19:34:06
hi
hi
NegativeZeroPlusOne
2022-05-17 19:34:06
Hello Kevin!
Hello Kevin!
alleycat
2022-05-17 19:34:06
hi
hi
anstar
2022-05-17 19:34:06
Hi
Hi
kfcruan
2022-05-17 19:34:06
Hi!
Hi!
Meh494
2022-05-17 19:34:06
hi!
hi!
KevinCarde
2022-05-17 19:34:10
A big thanks as always to the AoPS team for hosting us, and to all of you for being here!
A big thanks as always to the AoPS team for hosting us, and to all of you for being here!
KevinCarde
2022-05-17 19:34:22
Tonight, we'll be working through solutions to the Mathcamp 2022 Qualifying Quiz. This Math Jam is likely to be interesting mostly to students who applied to Mathcamp and worked through the Qualifying Quiz on their own, but if you didn't, you're of course still welcome to stick around and see some interesting problems!
Tonight, we'll be working through solutions to the Mathcamp 2022 Qualifying Quiz. This Math Jam is likely to be interesting mostly to students who applied to Mathcamp and worked through the Qualifying Quiz on their own, but if you didn't, you're of course still welcome to stick around and see some interesting problems!
KevinCarde
2022-05-17 19:34:34
To follow along, you may want to have the Qualifying Quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
To follow along, you may want to have the Qualifying Quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
KevinCarde
2022-05-17 19:34:48
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 https://www.mathcamp.org/about_mathcamp/).
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 https://www.mathcamp.org/about_mathcamp/).
KevinCarde
2022-05-17 19:35:05
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!).
KevinCarde
2022-05-17 19:35:21
If you applied this year, I strongly recommend having your own solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
If you applied this year, I strongly recommend having your own solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
KevinCarde
2022-05-17 19:35:39
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}$.
LJCoder619
2022-05-17 19:35:56
We claim that $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$.
We claim that $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$.
KevinCarde
2022-05-17 19:36:02
I'm glad we have agreement
I'm glad we have agreement
KevinCarde
2022-05-17 19:36:12
We'll be posting the transcript from tonight on https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, so no need to worry if you have to miss part of the event.
We'll be posting the transcript from tonight on https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, so no need to worry if you have to miss part of the event.
KevinCarde
2022-05-17 19:36:24
We've got a lot to cover in the next two hours, so let's get started! I'll dive right into Problem #1 to kick us off.
We've got a lot to cover in the next two hours, so let's get started! I'll dive right into Problem #1 to kick us off.
KevinCarde
2022-05-17 19:36:46
1. Define a "digital number" in base $b$ ($b>1$) to be a positive integer $n$ such that the base-$b$ digits of $n^2$ add up to $n$. For example, $9$ is a digital number in base $10$ because $9^2 = 81$, and $8+1=9$. Also, $9$ is a digital number in base $7$ because $9^2 = 81$ is written as $144$ in base $7$, and $1+4+4=9$.
1. Define a "digital number" in base $b$ ($b>1$) to be a positive integer $n$ such that the base-$b$ digits of $n^2$ add up to $n$. For example, $9$ is a digital number in base $10$ because $9^2 = 81$, and $8+1=9$. Also, $9$ is a digital number in base $7$ because $9^2 = 81$ is written as $144$ in base $7$, and $1+4+4=9$.
KevinCarde
2022-05-17 19:37:07
a. There are five other digital numbers in base $7$, aside from $9$. What are they?
a. There are five other digital numbers in base $7$, aside from $9$. What are they?
KevinCarde
2022-05-17 19:37:24
Okay, let's go! Let's just try a bunch of examples. What numbers turn out to be digital in base $7$?
Okay, let's go! Let's just try a bunch of examples. What numbers turn out to be digital in base $7$?
ARKie-09
2022-05-17 19:37:42
1
1
kwiq
2022-05-17 19:37:42
1
1
KevinCarde
2022-05-17 19:37:46
this one is always good to catch
this one is always good to catch
alleycat
2022-05-17 19:37:57
$1$, $3$, $4$, $6$, and $12$
$1$, $3$, $4$, $6$, and $12$
TheMathLemmon314
2022-05-17 19:37:57
1, 3, 4, 6, and 12
1, 3, 4, 6, and 12
Sigma_Monkey
2022-05-17 19:37:57
1, 3, 4, 6, 12
1, 3, 4, 6, 12
NoahLeaf
2022-05-17 19:37:57
1, 3, 4, 6, and 12
1, 3, 4, 6, and 12
Trigon
2022-05-17 19:37:57
1, 3, 4, 6, and 12
1, 3, 4, 6, and 12
mythicalcheese31
2022-05-17 19:37:57
1 comes first
1 comes first
Emathlover
2022-05-17 19:37:57
1
1
ProperPickle
2022-05-17 19:37:57
3
3
Thu2_2
2022-05-17 19:37:57
1,3,4,6,12
1,3,4,6,12
micahdorton
2022-05-17 19:37:57
3
3
KevinCarde
2022-05-17 19:38:14
So right, including $9$, we have $1, 3, 4, 6, 9, 12$ as digital numbers; if we believe the problem statement, that should be all of them. Let's prove it!
So right, including $9$, we have $1, 3, 4, 6, 9, 12$ as digital numbers; if we believe the problem statement, that should be all of them. Let's prove it!
KevinCarde
2022-05-17 19:38:37
For large $n$, we might expect that the sum of the base-$b$ digits of $n^2$ will eventually be much smaller than $n$ itself, so eventually they can't possibly be equal. How can we bound the sum of the base-$b$ digits of $n^2$?
For large $n$, we might expect that the sum of the base-$b$ digits of $n^2$ will eventually be much smaller than $n$ itself, so eventually they can't possibly be equal. How can we bound the sum of the base-$b$ digits of $n^2$?
Pendronator
2022-05-17 19:39:13
99999...99
99999...99
Pendronator
2022-05-17 19:39:13
in base b
in base b
KevinCarde
2022-05-17 19:39:25
Right, so this is a good start -- where by "9" we have "b-1" as our biggest digit.
Right, so this is a good start -- where by "9" we have "b-1" as our biggest digit.
KevinCarde
2022-05-17 19:39:38
How many base-$b$ digits will $n^2$ have?
How many base-$b$ digits will $n^2$ have?
Sigma_Monkey
2022-05-17 19:39:42
digit sum grows logarithmically
digit sum grows logarithmically
KevinCarde
2022-05-17 19:39:49
Definitely on to something here...
Definitely on to something here...
NoahLeaf
2022-05-17 19:40:14
twice the number of digits that n has (possibly minus one, depending on n)
twice the number of digits that n has (possibly minus one, depending on n)
KevinCarde
2022-05-17 19:40:22
Ooh, good, and $n$ has...
Ooh, good, and $n$ has...
Trigon
2022-05-17 19:40:23
$log_{b}n$
$log_{b}n$
KevinCarde
2022-05-17 19:40:35
digits, up to some rounding
digits, up to some rounding
KevinCarde
2022-05-17 19:40:54
So that gives us something like
So that gives us something like
Ericsz
2022-05-17 19:40:57
$\log_bn^2$+1
$\log_bn^2$+1
KevinCarde
2022-05-17 19:41:19
digits for $n^2$
digits for $n^2$
KevinCarde
2022-05-17 19:41:53
If we wanted to be precise, we could throw in a floor somewhere here, but we're interested in bounding the number of digits, so this'll do for us
If we wanted to be precise, we could throw in a floor somewhere here, but we're interested in bounding the number of digits, so this'll do for us
KevinCarde
2022-05-17 19:42:17
So putting it together, $n^2$ has $1 + \lfloor \log_b n^2 \rfloor \le 1 + 2\log_b n$ digits, and each digit in base $b$ is at most $b-1$, so we have that the sum of the digits of $n^2$ is at most $(b-1)(1 + 2\log_b n)$.
So putting it together, $n^2$ has $1 + \lfloor \log_b n^2 \rfloor \le 1 + 2\log_b n$ digits, and each digit in base $b$ is at most $b-1$, so we have that the sum of the digits of $n^2$ is at most $(b-1)(1 + 2\log_b n)$.
KevinCarde
2022-05-17 19:42:52
Great, so as Sigma_Monkey observed, this grows logarithmically, so eventually $n$ itself will be much bigger than this, and there's no hope of being a digital number anymore!
Great, so as Sigma_Monkey observed, this grows logarithmically, so eventually $n$ itself will be much bigger than this, and there's no hope of being a digital number anymore!
KevinCarde
2022-05-17 19:43:04
In fact, since the logarithm grows more and more slowly but $n$ has a constant slope, as soon as $n$ overtakes the logarithm, it will continue to be bigger from then on out.
In fact, since the logarithm grows more and more slowly but $n$ has a constant slope, as soon as $n$ overtakes the logarithm, it will continue to be bigger from then on out.
KevinCarde
2022-05-17 19:43:20
(If you're comfortable with calculus, you can prove this growth claim in a straightforward manner by using derivatives, but we don't require calculus to do the QQ, so a conceptual argument here is fine!)
(If you're comfortable with calculus, you can prove this growth claim in a straightforward manner by using derivatives, but we don't require calculus to do the QQ, so a conceptual argument here is fine!)
KevinCarde
2022-05-17 19:43:30
Let's now look at the particular problem at hand with base $b = 7$: when does $(b-1)(1 + 2\log_b n)$ start being less than $n$?
Let's now look at the particular problem at hand with base $b = 7$: when does $(b-1)(1 + 2\log_b n)$ start being less than $n$?
Trigon
2022-05-17 19:45:09
$n=27$
$n=27$
KevinCarde
2022-05-17 19:45:59
We have $(1 + 2 log_7 27)(7 − 1) \approx 26.3 < 27$, and as we argued above, there's no hope that the logarithm will equal $n$ ever again after this point.
We have $(1 + 2 log_7 27)(7 − 1) \approx 26.3 < 27$, and as we argued above, there's no hope that the logarithm will equal $n$ ever again after this point.
KevinCarde
2022-05-17 19:46:42
So, to prove that we have all the digital numbers, we can simply check all $n < 27$, and indeed, we find that our list $1, 3, 4, 6, 9, 12$ is complete.
So, to prove that we have all the digital numbers, we can simply check all $n < 27$, and indeed, we find that our list $1, 3, 4, 6, 9, 12$ is complete.
KevinCarde
2022-05-17 19:47:14
I'll pause a moment for this to get digested, then we'll charge forward to part b!
I'll pause a moment for this to get digested, then we'll charge forward to part b!
Pendronator
2022-05-17 19:48:26
Is a good takeaway from this problem utilizing bounds?
Is a good takeaway from this problem utilizing bounds?
KevinCarde
2022-05-17 19:49:03
Yes! We'll see this happen again: sometimes the long run behavior of something is clear (i.e., that the logarithm grows more slowly than $n$ itself), and if we can come up with some good bounds, that leaves only finitely many cases to check by hand
Yes! We'll see this happen again: sometimes the long run behavior of something is clear (i.e., that the logarithm grows more slowly than $n$ itself), and if we can come up with some good bounds, that leaves only finitely many cases to check by hand
KevinCarde
2022-05-17 19:49:16
Let's move on to the next part!
Let's move on to the next part!
KevinCarde
2022-05-17 19:49:21
b. It is not a coincidence that base $7 = 2^2 + 2 + 1$ has unusually many digital numbers. Prove that for all $k \ge 2$, there are at least five digital numbers in base $k^2+k+1$.
b. It is not a coincidence that base $7 = 2^2 + 2 + 1$ has unusually many digital numbers. Prove that for all $k \ge 2$, there are at least five digital numbers in base $k^2+k+1$.
KevinCarde
2022-05-17 19:49:36
This part is trickier in some ways, since we're not working with a specific base, but easier in others, since we don't have to prove we find *all* the digital numbers.
This part is trickier in some ways, since we're not working with a specific base, but easier in others, since we don't have to prove we find *all* the digital numbers.
KevinCarde
2022-05-17 19:49:48
I'll start us out with an example to demonstrate how these computations might look.
I'll start us out with an example to demonstrate how these computations might look.
KevinCarde
2022-05-17 19:49:56
I claim that $n = k+1$ is always digital in base $b = k^2+k+1$.
I claim that $n = k+1$ is always digital in base $b = k^2+k+1$.
KevinCarde
2022-05-17 19:50:13
We need to compute the sum of the digits of $n^2$ in base $b$, which we can do by writing $n^2 = (k+1)^2 = k^2 + 2k + 1 = (k^2 + k + 1) + k = 1\cdot b + k\cdot 1$.
We need to compute the sum of the digits of $n^2$ in base $b$, which we can do by writing $n^2 = (k+1)^2 = k^2 + 2k + 1 = (k^2 + k + 1) + k = 1\cdot b + k\cdot 1$.
KevinCarde
2022-05-17 19:50:32
So the base-$b$ digits are $1$ and $k$, which add to $k+1 = n$, so it is indeed digital!
So the base-$b$ digits are $1$ and $k$, which add to $k+1 = n$, so it is indeed digital!
KevinCarde
2022-05-17 19:50:41
What are some other examples?
What are some other examples?
aopsuser008
2022-05-17 19:51:28
1
1
Trigon
2022-05-17 19:51:28
1
1
KevinCarde
2022-05-17 19:51:37
I still love this one
I'll give a few seconds more for some other options
I still love this one
I'll give a few seconds more for some other options
chaidan_tamaroon
2022-05-17 19:52:25
(k+1)^2
(k+1)^2
TheBeast5520
2022-05-17 19:52:25
k(k+1)
k(k+1)
TheBeast5520
2022-05-17 19:52:25
$k^2, k(k+1), (k+1)^2$
$k^2, k(k+1), (k+1)^2$
Squ4r3-R00t
2022-05-17 19:52:25
n=k^2
n=k^2
TheBeast5520
2022-05-17 19:52:25
$1, k^2, k(k+1), (k+1)^2$
$1, k^2, k(k+1), (k+1)^2$
Thu2_2
2022-05-17 19:52:25
k(k+1)
k(k+1)
ARKie-09
2022-05-17 19:52:25
$k^2$?
$k^2$?
sargamsujit
2022-05-17 19:52:25
k+1?
k+1?
KevinCarde
2022-05-17 19:52:36
There were tons of responses! I didn't get to grab all of yours, so apologies if I missed you
There were tons of responses! I didn't get to grab all of yours, so apologies if I missed you
KevinCarde
2022-05-17 19:52:53
but between all these responses, we have the five of them that we need: $1$ (digital in any base!), $k+1$, $k^2$, $k^2+k$, and $k^2+2k+1$.
but between all these responses, we have the five of them that we need: $1$ (digital in any base!), $k+1$, $k^2$, $k^2+k$, and $k^2+2k+1$.
KevinCarde
2022-05-17 19:53:08
We'd have to do calculations like we did for $n=k+1$ for each of these to prove that they're digital, but in the interest of time, we'll leave it as an exercise to check that these all work (if you haven't already in your own QQ solutions!).
We'd have to do calculations like we did for $n=k+1$ for each of these to prove that they're digital, but in the interest of time, we'll leave it as an exercise to check that these all work (if you haven't already in your own QQ solutions!).
TheBeast5520
2022-05-17 19:53:25
is there any other form that is a digital number in many different bases?
is there any other form that is a digital number in many different bases?
KevinCarde
2022-05-17 19:53:43
What a good question! This problem only scratched the surface of the kinds of questions you could ask; I don't know the answer to this off-hand, but it could be fun to think about!
What a good question! This problem only scratched the surface of the kinds of questions you could ask; I don't know the answer to this off-hand, but it could be fun to think about!
Pendronator
2022-05-17 19:53:47
How would you think of those?
How would you think of those?
Ericsz
2022-05-17 19:54:05
where did we get the motivation to try those cases?
where did we get the motivation to try those cases?
KevinCarde
2022-05-17 19:54:17
Great questions! We can check that these worked, but where did they come from?
Great questions! We can check that these worked, but where did they come from?
KevinCarde
2022-05-17 19:54:31
One thing we can do is take the examples we found for $b=7$ as inspiration, since as noted in the problem, $7$ has this form
One thing we can do is take the examples we found for $b=7$ as inspiration, since as noted in the problem, $7$ has this form
KevinCarde
2022-05-17 19:54:51
so since $3$ was digital in base $7 = 2^2 + 2 + 1$, we might try $k+1$ to be digital in base $k^2 + k + 1$ in general
so since $3$ was digital in base $7 = 2^2 + 2 + 1$, we might try $k+1$ to be digital in base $k^2 + k + 1$ in general
KevinCarde
2022-05-17 19:55:00
some of these are definitely easier to find than others, though
some of these are definitely easier to find than others, though
alleycat
2022-05-17 19:55:14
I used python to find the original 5 answers, checked them, and tried to generalize them with b
I used python to find the original 5 answers, checked them, and tried to generalize them with b
KevinCarde
2022-05-17 19:55:26
Great use of code! (I found them by hand when I did this problem, but it probably took me longer!)
Great use of code! (I found them by hand when I did this problem, but it probably took me longer!)
KevinCarde
2022-05-17 19:55:42
We could talk endlessly about cool digital number stuff, but in the interest of time, I'm going to push forward to part c.
We could talk endlessly about cool digital number stuff, but in the interest of time, I'm going to push forward to part c.
KevinCarde
2022-05-17 19:55:48
c. Find all integers $b>1$ such that $b+3$ is a digital number in base $b$. (Prove your answer!)
c. Find all integers $b>1$ such that $b+3$ is a digital number in base $b$. (Prove your answer!)
KevinCarde
2022-05-17 19:56:06
As usual, we need the sum of the digits of $(b+3)^2$ to equal $b+3$, so let's see what happens -- there's a bit of catch in what I'm about to do that you'll have to keep me honest on.
As usual, we need the sum of the digits of $(b+3)^2$ to equal $b+3$, so let's see what happens -- there's a bit of catch in what I'm about to do that you'll have to keep me honest on.
vrondoS
2022-05-17 19:56:20
$(b*3)^2=b^2+6b+9$
$(b*3)^2=b^2+6b+9$
KevinCarde
2022-05-17 19:56:22
We have $(b+3)^2 = b^2 + 6b + 9$, which looks like it has digits $1,6,9$ in base $b$, which sum to $16$, so we must have $b+3 = 16$, or $b=13$ as our only option.
We have $(b+3)^2 = b^2 + 6b + 9$, which looks like it has digits $1,6,9$ in base $b$, which sum to $16$, so we must have $b+3 = 16$, or $b=13$ as our only option.
KevinCarde
2022-05-17 19:56:29
I did something really sketchy, though; what's the catch?
I did something really sketchy, though; what's the catch?
chaidan_tamaroon
2022-05-17 19:56:56
b<9
b<9
CoolCarsOnTheRun
2022-05-17 19:56:56
$b>9$
$b>9$
smarklebot
2022-05-17 19:56:56
what if b < 10
what if b < 10
samrocksnature
2022-05-17 19:56:56
carry overs
carry overs
aopsuser008
2022-05-17 19:56:56
didn't check bases less than 10
didn't check bases less than 10
mythicalcheese31
2022-05-17 19:56:56
this doesn't work if b<9
this doesn't work if b<9
alleycat
2022-05-17 19:56:56
it's not always $169$ in base $b$
it's not always $169$ in base $b$
vrondoS
2022-05-17 19:56:56
b>9
b>9
BlizzardWizard
2022-05-17 19:56:56
$b^2+6b+9$ is not $169$ in base $b$ when $b<10$.
$b^2+6b+9$ is not $169$ in base $b$ when $b<10$.
CT17
2022-05-17 19:56:56
What if $b\le 9$
What if $b\le 9$
KevinCarde
2022-05-17 19:57:05
Right, in $b^2 + 6b + 9$, if $b \le 9$, then "$9$" isn't a valid digit. So our nice argument doesn't work for $b \le 9$. How can we fix it?
Right, in $b^2 + 6b + 9$, if $b \le 9$, then "$9$" isn't a valid digit. So our nice argument doesn't work for $b \le 9$. How can we fix it?
mythicalcheese31
2022-05-17 19:57:09
but yeah this proves that once b is too big theres no more solutions
but yeah this proves that once b is too big theres no more solutions
KevinCarde
2022-05-17 19:57:13
A preemptive response! Nice
A preemptive response! Nice
KevinCarde
2022-05-17 19:57:27
Yes, as we saw before, finding a bound is useful, because now we can...
Yes, as we saw before, finding a bound is useful, because now we can...
BlizzardWizard
2022-05-17 19:57:31
Manually check $b<10$.
Manually check $b<10$.
TheBeast5520
2022-05-17 19:57:31
We can just manually check for b <= 9 since it is so small
We can just manually check for b <= 9 since it is so small
Sigma_Monkey
2022-05-17 19:57:31
we can hand write out the other 9
we can hand write out the other 9
aopsuser008
2022-05-17 19:57:31
just check all lower bases? not too many
just check all lower bases? not too many
KevinCarde
2022-05-17 19:57:37
Do we find any others?
Do we find any others?
CoolCarsOnTheRun
2022-05-17 19:57:53
$b=5$
$b=5$
Sigma_Monkey
2022-05-17 19:57:53
and find b = 5
and find b = 5
smarklebot
2022-05-17 19:57:53
5
5
aopsuser008
2022-05-17 19:57:53
b=5!
b=5!
BlizzardWizard
2022-05-17 19:57:53
$b=5$
$b=5$
joannax
2022-05-17 19:57:53
5
5
Squ4r3-R00t
2022-05-17 19:57:53
$b=5$
$b=5$
KevinCarde
2022-05-17 19:58:04
Yep, sneaky $b = 5$ works: $b+3 = 8$, which squares to $64 = 2\cdot 5^2 + 2\cdot 5 + 4\cdot 1$, which has digits $2,2,4$ in base $5$, which indeed adds up to $8$.
Yep, sneaky $b = 5$ works: $b+3 = 8$, which squares to $64 = 2\cdot 5^2 + 2\cdot 5 + 4\cdot 1$, which has digits $2,2,4$ in base $5$, which indeed adds up to $8$.
TheBeast5520
2022-05-17 19:58:15
oops on my app I wrote b + 3 instead of b
oops on my app I wrote b + 3 instead of b
KevinCarde
2022-05-17 19:58:38
We are always looking for ideas, regardless of whether there are typos like this! Mathematicians do this sort of thing all the time, so no worries
We are always looking for ideas, regardless of whether there are typos like this! Mathematicians do this sort of thing all the time, so no worries
KevinCarde
2022-05-17 19:58:50
So we conclude that there are two possibilities, $b = 5$ and $b = 13$.
So we conclude that there are two possibilities, $b = 5$ and $b = 13$.
KevinCarde
2022-05-17 19:59:01
One more part to this problem!
One more part to this problem!
KevinCarde
2022-05-17 19:59:05
Prove that in any base $b \ge 16$, every digital number is less than $b^{3/2}$. What's the best upper bound you can prove on the largest digital number in base $b$, when $b$ is large?'
Prove that in any base $b \ge 16$, every digital number is less than $b^{3/2}$. What's the best upper bound you can prove on the largest digital number in base $b$, when $b$ is large?'
KevinCarde
2022-05-17 19:59:14
I'm going to move fairly quickly through this problem, since we still have five more to go (and some of those are going to take more time than this problem!). So there may be pieces of this problem that you want to return to on your own time to think through more leisurely.
I'm going to move fairly quickly through this problem, since we still have five more to go (and some of those are going to take more time than this problem!). So there may be pieces of this problem that you want to return to on your own time to think through more leisurely.
KevinCarde
2022-05-17 19:59:31
Anyway, the initial bound asked in this problem is not that far out of reach given what we've done before; what can we bring back from the very start of this problem to help us out?
Anyway, the initial bound asked in this problem is not that far out of reach given what we've done before; what can we bring back from the very start of this problem to help us out?
BlizzardWizard
2022-05-17 20:00:08
The logarithmic bound on the sum of digits
The logarithmic bound on the sum of digits
Pendronator
2022-05-17 20:00:08
Bound it up
Bound it up
Pendronator
2022-05-17 20:00:08
the digits i mean
the digits i mean
KevinCarde
2022-05-17 20:00:11
Right!
Right!
TheBeast5520
2022-05-17 20:00:12
(b^(3/2))^2 = b^3, which is 1000 in base b
(b^(3/2))^2 = b^3, which is 1000 in base b
KevinCarde
2022-05-17 20:00:17
This'll be a useful observation in a minute
This'll be a useful observation in a minute
KevinCarde
2022-05-17 20:00:26
So, we had our logarithmic bound: the sum of the digits of $n^2$ is at most $(b-1)(1 + 2\log_b n)$. Let's plug in $b^{3/2}$ and see when there's any hope of being digital:
So, we had our logarithmic bound: the sum of the digits of $n^2$ is at most $(b-1)(1 + 2\log_b n)$. Let's plug in $b^{3/2}$ and see when there's any hope of being digital:
KevinCarde
2022-05-17 20:00:33
$(b-1)(1 + 2\log_b b^{3/2}) = (b-1)(1 + 3) = 4(b-1)$
$(b-1)(1 + 2\log_b b^{3/2}) = (b-1)(1 + 3) = 4(b-1)$
KevinCarde
2022-05-17 20:00:50
This in turn is strictly less than $4b$, which will be at most $b^{3/2}$ whenever $b \ge 16$.
This in turn is strictly less than $4b$, which will be at most $b^{3/2}$ whenever $b \ge 16$.
KevinCarde
2022-05-17 20:01:06
So whenever $b \ge 16$, our logarithm can't possibly be as big as $b^{3/2}$ itself, as desired!
So whenever $b \ge 16$, our logarithm can't possibly be as big as $b^{3/2}$ itself, as desired!
KevinCarde
2022-05-17 20:01:11
(That was a lot of chained inequalities thrown at you! You might have to think through it on your own time.)
(That was a lot of chained inequalities thrown at you! You might have to think through it on your own time.)
KevinCarde
2022-05-17 20:01:22
However, better bounds are possible; what did you find?
However, better bounds are possible; what did you find?
Pendronator
2022-05-17 20:01:45
Just leave it as an exercise to the grader. That's what I did on usamts
Just leave it as an exercise to the grader. That's what I did on usamts
KevinCarde
2022-05-17 20:01:52
Trust me, we get a *lot* of exercise
Trust me, we get a *lot* of exercise
mythicalcheese31
2022-05-17 20:02:07
I think i got m <2b but it might be wrong
I think i got m <2b but it might be wrong
Sigma_Monkey
2022-05-17 20:02:07
x smaller equal to 2b+1 when b> 25
x smaller equal to 2b+1 when b> 25
CoolCarsOnTheRun
2022-05-17 20:02:07
$b^{1+\epsilon}$ for arbitrarily small $\epsilon$ as long as $b$ is large enough
$b^{1+\epsilon}$ for arbitrarily small $\epsilon$ as long as $b$ is large enough
KevinCarde
2022-05-17 20:02:11
These are all much better bounds!
These are all much better bounds!
BlizzardWizard
2022-05-17 20:02:14
I found $\sqrt{3}b$.
I found $\sqrt{3}b$.
KevinCarde
2022-05-17 20:02:27
This is in fact the best bound, it turns out.
This is in fact the best bound, it turns out.
KevinCarde
2022-05-17 20:03:00
By carefully considering the three digits of $n^2$ (this is TheBeast5520's observation, that $n^2$ has at most three digits!), we can bound the leading digit on $n^2$.
By carefully considering the three digits of $n^2$ (this is TheBeast5520's observation, that $n^2$ has at most three digits!), we can bound the leading digit on $n^2$.
KevinCarde
2022-05-17 20:03:09
In fact, with careful work, we can show that the leading digit must be at most $2$, and hence $n^2 < 3b^2$, or $n \le \lfloor b \sqrt{3}\rfloor$.
In fact, with careful work, we can show that the leading digit must be at most $2$, and hence $n^2 < 3b^2$, or $n \le \lfloor b \sqrt{3}\rfloor$.
KevinCarde
2022-05-17 20:03:24
(And it turns out this is the best possible bound: there are infinitely many bases $b$ such that $n = \lfloor b \sqrt{3}\rfloor$ is digital. I didn't have a proof of this when I solved the problem, but some applicants were able to prove it!)
(And it turns out this is the best possible bound: there are infinitely many bases $b$ such that $n = \lfloor b \sqrt{3}\rfloor$ is digital. I didn't have a proof of this when I solved the problem, but some applicants were able to prove it!)
KevinCarde
2022-05-17 20:03:41
We won't go into further details of proving this optimal bound here, but we invite you to continue thinking about this on your own time if you're interested!
We won't go into further details of proving this optimal bound here, but we invite you to continue thinking about this on your own time if you're interested!
KevinCarde
2022-05-17 20:03:57
Instead, in order to keep things moving, we'll call this problem a wrap and move on to Misha, with Problem 2!
Instead, in order to keep things moving, we'll call this problem a wrap and move on to Misha, with Problem 2!
Misha
2022-05-17 20:04:04
Misha
2022-05-17 20:04:06
Problem 2. We construct a fractal by starting with a $1\times1$ black square at the $1^{\text{st}}$ stage. The $n^{\text{th}}$ stage is obtained by combining two congruent copies of the $(n-1)^{\text{th}}$ stage: one copy is rotated $90^\circ$ counterclockwise and placed to the right of the other. Their bounding rectangles are flush against each other and aligned along the bottom edge.
Problem 2. We construct a fractal by starting with a $1\times1$ black square at the $1^{\text{st}}$ stage. The $n^{\text{th}}$ stage is obtained by combining two congruent copies of the $(n-1)^{\text{th}}$ stage: one copy is rotated $90^\circ$ counterclockwise and placed to the right of the other. Their bounding rectangles are flush against each other and aligned along the bottom edge.
Misha
2022-05-17 20:04:15
Here's a picture of the fractal (you can also see it on the Qualifying Quiz page):
Here's a picture of the fractal (you can also see it on the Qualifying Quiz page):
Misha
2022-05-17 20:04:25
And here's a picture of how we go from one step to the next:
And here's a picture of how we go from one step to the next:
Misha
2022-05-17 20:04:40
Problem 2(a). As $n$ increases, the slope of the diagonal line from the bottom left corner to the top right corner gets closer and closer to some value $m$. What is $m$?
Problem 2(a). As $n$ increases, the slope of the diagonal line from the bottom left corner to the top right corner gets closer and closer to some value $m$. What is $m$?
Misha
2022-05-17 20:04:46
Before we go on to look at the solution, are there any questions about the setup: the construction of the fractal, or the statement of question (a)?
Before we go on to look at the solution, are there any questions about the setup: the construction of the fractal, or the statement of question (a)?
CoolCarsOnTheRun
2022-05-17 20:05:04
Is there a name for this fractal? It reminded me of something when I was solving the problem but I couldn't figure out what it's called
Is there a name for this fractal? It reminded me of something when I was solving the problem but I couldn't figure out what it's called
Misha
2022-05-17 20:05:09
Not as far as I know!
Not as far as I know!
Misha
2022-05-17 20:05:38
I'm getting lots of answers to questions I haven't even started asking yet, so I think everyone is unconfused so far.
I'm getting lots of answers to questions I haven't even started asking yet, so I think everyone is unconfused so far.
Misha
2022-05-17 20:05:46
Problem 2(a) solution.
Problem 2(a) solution.
Misha
2022-05-17 20:05:51
To solve for $m$, it helps to make up some more notation: let's say that some $n^{\text{th}}$ stage of the fractal has width $w$ and height $h$. (So the slope at that stage is $\frac{h}{w}$: rise over run.)
To solve for $m$, it helps to make up some more notation: let's say that some $n^{\text{th}}$ stage of the fractal has width $w$ and height $h$. (So the slope at that stage is $\frac{h}{w}$: rise over run.)
Misha
2022-05-17 20:05:57
Of course, $w$ and $h$ depend on $n$, and I should be writing $w_n$ and $h_n$, but I'll drop the subscripts to avoid making the notation too scary.
Of course, $w$ and $h$ depend on $n$, and I should be writing $w_n$ and $h_n$, but I'll drop the subscripts to avoid making the notation too scary.
Misha
2022-05-17 20:06:05
Now, in terms of $w$ and $h$, what are the width and height of the next stage: the $(n+1)^{\text{th}}$ stage?
Now, in terms of $w$ and $h$, what are the width and height of the next stage: the $(n+1)^{\text{th}}$ stage?
impromptuA
2022-05-17 20:06:43
w+h, w
w+h, w
chaidan_tamaroon
2022-05-17 20:06:43
h, w+h
h, w+h
BlizzardWizard
2022-05-17 20:06:43
$w+h$ and $w$, respectively
$w+h$ and $w$, respectively
TheBeast5520
2022-05-17 20:06:43
w_(n+1) = w_n + h_n, h_(n+1) = w_n
w_(n+1) = w_n + h_n, h_(n+1) = w_n
Sigma_Monkey
2022-05-17 20:06:43
h, w+h?
h, w+h?
Pendronator
2022-05-17 20:06:43
$h_{n+1}=w_n$
$h_{n+1}=w_n$
mythicalcheese31
2022-05-17 20:06:43
height is w, width is w+h, ratio is constant
height is w, width is w+h, ratio is constant
ARKie-09
2022-05-17 20:06:43
Width = w + h
Height = w
Width = w + h
Height = w
sargamsujit
2022-05-17 20:06:43
w+h, w?
w+h, w?
TheBeast5520
2022-05-17 20:06:43
$w_{n+1} = w_n + h_n, h_{n+1} = w_n$
$w_{n+1} = w_n + h_n, h_{n+1} = w_n$
joannax
2022-05-17 20:06:49
h, w+h
h, w+h
CoolCarsOnTheRun
2022-05-17 20:06:49
w+h and w, respectively
w+h and w, respectively
Misha
2022-05-17 20:06:56
Take a look at the diagram below:
Take a look at the diagram below:
Misha
2022-05-17 20:07:05
Along the bottom, we have segments of length $w$ and $h$, for a total width of $w+h$. Along the right, we have a segment of length $w$, for a total height of $w$.
Along the bottom, we have segments of length $w$ and $h$, for a total width of $w+h$. Along the right, we have a segment of length $w$, for a total height of $w$.
Misha
2022-05-17 20:07:15
So if the slope is getting close to some value $m$, then we have $m \approx \frac hw$, but also $m \approx \frac{w}{w+h}$. What next?
So if the slope is getting close to some value $m$, then we have $m \approx \frac hw$, but also $m \approx \frac{w}{w+h}$. What next?
Misha
2022-05-17 20:08:12
Lots of people are jumping ahead a bit, but I'll take things more slowly.
Lots of people are jumping ahead a bit, but I'll take things more slowly.
BlizzardWizard
2022-05-17 20:08:19
Equate them and find the common ratio.
Equate them and find the common ratio.
Trigon
2022-05-17 20:08:19
the inequalities become equalities as n goes to infinity
the inequalities become equalities as n goes to infinity
alleycat
2022-05-17 20:08:19
set them equal
set them equal
TheBeast5520
2022-05-17 20:08:19
set them equal to each other
set them equal to each other
Misha
2022-05-17 20:08:25
There's many ways to go, but I think the easiest is to solve the first equation for $h$: $h \approx wm$. Plug that into the second: $m \approx \frac{w}{w + wm} = \frac1{1+m}$.
There's many ways to go, but I think the easiest is to solve the first equation for $h$: $h \approx wm$. Plug that into the second: $m \approx \frac{w}{w + wm} = \frac1{1+m}$.
Misha
2022-05-17 20:08:36
Actually, the $\approx$ was there because no stage perfectly matches the limiting shape of the fractal. But we've gotten rid of both $w$ and $h$: the variables specific to the $n^{\text{th}}$ stage. So if there really is an ideal $m$, we must have $m = \frac1{1+m}$ exactly.
Actually, the $\approx$ was there because no stage perfectly matches the limiting shape of the fractal. But we've gotten rid of both $w$ and $h$: the variables specific to the $n^{\text{th}}$ stage. So if there really is an ideal $m$, we must have $m = \frac1{1+m}$ exactly.
Misha
2022-05-17 20:08:47
Solving the quadratic equation $m^2+m-1=0$, we get $m = \frac{\sqrt5 - 1}{2} \approx 0.618$. Some of you may recognize this number: it's the reciprocal of the golden ratio that the ancient Greeks were so fond of!
Solving the quadratic equation $m^2+m-1=0$, we get $m = \frac{\sqrt5 - 1}{2} \approx 0.618$. Some of you may recognize this number: it's the reciprocal of the golden ratio that the ancient Greeks were so fond of!
alleycat
2022-05-17 20:08:53
$m = \boxed{\dfrac{\sqrt{5} - 1}{2}}$
$m = \boxed{\dfrac{\sqrt{5} - 1}{2}}$
GeometryJake
2022-05-17 20:08:53
golden ratio!
golden ratio!
vrondoS
2022-05-17 20:08:53
$m = (sqrt(5)+1)/2$
$m = (sqrt(5)+1)/2$
Misha
2022-05-17 20:09:12
There's actually another connection to spot here. We didn't use it in this solution, but lots of you spotted it anyway!
There's actually another connection to spot here. We didn't use it in this solution, but lots of you spotted it anyway!
alleycat
2022-05-17 20:09:21
fibonacci sequence
fibonacci sequence
Thu2_2
2022-05-17 20:09:21
Arranging the width/height in a row, we see that it resemble the Fibonacci sequence
Arranging the width/height in a row, we see that it resemble the Fibonacci sequence
Sigma_Monkey
2022-05-17 20:09:21
fibonnaci
fibonnaci
TheBeast5520
2022-05-17 20:09:21
ratio between consecutive fibonacci numbers, which is the sequence which the widths and heights of consecutive stages of the fractals form
ratio between consecutive fibonacci numbers, which is the sequence which the widths and heights of consecutive stages of the fractals form
Misha
2022-05-17 20:09:30
The side lengths of the fractal's stages are Fibonacci numbers! We go from $1 \times 1$ to $1 \times 2$ to $2 \times 3$ to $3 \times 5$ to $5 \times 8$ and so on.
The side lengths of the fractal's stages are Fibonacci numbers! We go from $1 \times 1$ to $1 \times 2$ to $2 \times 3$ to $3 \times 5$ to $5 \times 8$ and so on.
Misha
2022-05-17 20:09:37
This means that the slope is the ratio $\frac{F_n}{F_{n+1}}$ of two adjacent Fibonacci numbers. The astronomer Kepler was the first to show that this ratio also tends to $\frac{\sqrt5 - 1}{2}$ as $n$ gets large.
This means that the slope is the ratio $\frac{F_n}{F_{n+1}}$ of two adjacent Fibonacci numbers. The astronomer Kepler was the first to show that this ratio also tends to $\frac{\sqrt5 - 1}{2}$ as $n$ gets large.
Misha
2022-05-17 20:09:55
On to the next part!
On to the next part!
Misha
2022-05-17 20:09:56
Problem 2(b). In the $n^{\text{th}}$ stage, let $a_n$ be the area of the black region above the diagonal line, and let $b_n$ be the area of the black region below the diagonal line.
Problem 2(b). In the $n^{\text{th}}$ stage, let $a_n$ be the area of the black region above the diagonal line, and let $b_n$ be the area of the black region below the diagonal line.
Misha
2022-05-17 20:10:06
As $n$ increases, $\frac{a_n}{b_n}$ gets closer and closer to some value $\frac ab$. What is $\frac ab$?
As $n$ increases, $\frac{a_n}{b_n}$ gets closer and closer to some value $\frac ab$. What is $\frac ab$?
Misha
2022-05-17 20:10:11
Any questions about the statement here before we begin?
Any questions about the statement here before we begin?
Misha
2022-05-17 20:10:36
Only answers, it seems Let's wait a bit for those.
Only answers, it seems
Let's wait a bit for those.
Misha
2022-05-17 20:10:45
Problem 2(b) solution.
Problem 2(b) solution.
Misha
2022-05-17 20:10:56
Take a look at another diagram of this fractal that I've lovingly annotated in MS Paint:
Take a look at another diagram of this fractal that I've lovingly annotated in MS Paint:
Misha
2022-05-17 20:11:02
I've divided up the area $a_n$ above the diagonal into two pieces. What's the area of the red piece, in terms of the previous stages?
I've divided up the area $a_n$ above the diagonal into two pieces. What's the area of the red piece, in terms of the previous stages?
Misha
2022-05-17 20:11:25
(I mean, the area of the black pixels in the red piece.)
(I mean, the area of the black pixels in the red piece.)
BlizzardWizard
2022-05-17 20:12:19
$a_{n-1}$
$a_{n-1}$
Ericsz
2022-05-17 20:12:19
$a_{n-1}$
$a_{n-1}$
Misha
2022-05-17 20:12:26
The red pieces is $a_{n-1}$: it's the area above the diagonal in the previous stage.
The red pieces is $a_{n-1}$: it's the area above the diagonal in the previous stage.
Misha
2022-05-17 20:12:34
What about the area of the blue piece? This one's trickier.
What about the area of the blue piece? This one's trickier.
Trigon
2022-05-17 20:13:02
$b_{n-2}$
$b_{n-2}$
BlizzardWizard
2022-05-17 20:13:02
$b_{n-2}$
$b_{n-2}$
ARKie-09
2022-05-17 20:13:02
$b_{n-2}$?
$b_{n-2}$?
Misha
2022-05-17 20:13:05
The blue piece is $b_{n-2}$. If we follow that part of the diagram two stages back, it is exactly what was below the diagram at that stage.
The blue piece is $b_{n-2}$. If we follow that part of the diagram two stages back, it is exactly what was below the diagram at that stage.
Misha
2022-05-17 20:13:18
So we've got one equation (approximate because the slope of the diagonal line isn't perfectly consistent between stages): $a_n \approx a_{n-1} + b_{n-2}$.
So we've got one equation (approximate because the slope of the diagonal line isn't perfectly consistent between stages): $a_n \approx a_{n-1} + b_{n-2}$.
Misha
2022-05-17 20:13:36
(Some of you gave this answer earlier, but I got a bit overwhelmed by the number of responses, sorry.)
(Some of you gave this answer earlier, but I got a bit overwhelmed by the number of responses, sorry.)
Misha
2022-05-17 20:13:43
We'll need a second fact about the areas. What can you say just from the fact that we put two copies of the $(n-1)^{\text{th}}$ stage to make the $n^{\text{th}}$ stage?
We'll need a second fact about the areas. What can you say just from the fact that we put two copies of the $(n-1)^{\text{th}}$ stage to make the $n^{\text{th}}$ stage?
sargamsujit
2022-05-17 20:14:33
it doubles every time
it doubles every time
alleycat
2022-05-17 20:14:33
it has twice the area
it has twice the area
joannax
2022-05-17 20:14:33
twice the area of the previous stage
twice the area of the previous stage
Misha
2022-05-17 20:14:39
The area doubles. So if $\frac{a_n}{b_n}$ approaches some consistent value, then $a_n$ and $b_n$ should double as well: $a_n \approx 2a_{n-1}$ and $b_n \approx 2b_{n-1}$.
The area doubles. So if $\frac{a_n}{b_n}$ approaches some consistent value, then $a_n$ and $b_n$ should double as well: $a_n \approx 2a_{n-1}$ and $b_n \approx 2b_{n-1}$.
Thu2_2
2022-05-17 20:14:44
we have 4 copies of the (n-2)th stage
we have 4 copies of the (n-2)th stage
Misha
2022-05-17 20:14:57
And $a_n \approx 4a_{n-2}$ and so on, of course.
And $a_n \approx 4a_{n-2}$ and so on, of course.
Misha
2022-05-17 20:15:06
So if we take $a_n \approx a_{n-1} + b_{n-2}$ and try to rewrite it in terms of $a_n$ and $b_n$, what do we get?
So if we take $a_n \approx a_{n-1} + b_{n-2}$ and try to rewrite it in terms of $a_n$ and $b_n$, what do we get?
BlizzardWizard
2022-05-17 20:16:16
$a_n\approx \frac{1}{2}a_{n}+\frac{1}{4}b_{n}$
$a_n\approx \frac{1}{2}a_{n}+\frac{1}{4}b_{n}$
aopsuser008
2022-05-17 20:16:16
$a_n/2+b_n/4$
$a_n/2+b_n/4$
alleycat
2022-05-17 20:16:16
$a_{n} = \dfrac{a_{n}}{2} + \dfrac{b_{n}}{4}$
$a_{n} = \dfrac{a_{n}}{2} + \dfrac{b_{n}}{4}$
Misha
2022-05-17 20:16:20
The equation becomes $a_n \approx \frac12 a_n + \frac14 b_n$. We can solve this...
The equation becomes $a_n \approx \frac12 a_n + \frac14 b_n$. We can solve this...
vrondoS
2022-05-17 20:17:00
a_n = 1/2 * b_n
a_n = 1/2 * b_n
sargamsujit
2022-05-17 20:17:00
a_n/b_n=2
a_n/b_n=2
Pendronator
2022-05-17 20:17:00
$a/b = 1/2$
$a/b = 1/2$
Misha
2022-05-17 20:17:02
...and get $\frac12a_n \approx \frac14b_n$, or $\frac{a_n}{b_n} \approx \frac12$. That's our answer!
...and get $\frac12a_n \approx \frac14b_n$, or $\frac{a_n}{b_n} \approx \frac12$. That's our answer!
Misha
2022-05-17 20:17:27
Note: hroughout this problem, we're not worrying about the technical definition of a limit. These ratios do get closer and closer to the right value, but we're not proving that.
Note: hroughout this problem, we're not worrying about the technical definition of a limit. These ratios do get closer and closer to the right value, but we're not proving that.
Misha
2022-05-17 20:17:33
Our solution does imply that if the ratio has any kind of limit, then the limit has the value we promised!
Our solution does imply that if the ratio has any kind of limit, then the limit has the value we promised!
Misha
2022-05-17 20:17:38
Now, it's back over to Kevin for Problem 3.
Now, it's back over to Kevin for Problem 3.
KevinCarde
2022-05-17 20:17:49
Problem 3. Marvin is playing a solitaire game with marbles. There are $n$ bowls (for some positive integer $n$), and initially each bowl contains one marble. Each turn, Marvin may either
\begin{itemize}
\item remove a marble from a bowl, or
\item choose a bowl $A$ with at least one marble and a different bowl $B$ with at least as many marbles as bowl $A$, and move one marble from bowl $A$ to bowl $B$.
\end{itemize}
The game ends when there are no marbles left, but Marvin wants to make it last as long as possible.
Problem 3. Marvin is playing a solitaire game with marbles. There are $n$ bowls (for some positive integer $n$), and initially each bowl contains one marble. Each turn, Marvin may either
\begin{itemize}
\item remove a marble from a bowl, or
\item choose a bowl $A$ with at least one marble and a different bowl $B$ with at least as many marbles as bowl $A$, and move one marble from bowl $A$ to bowl $B$.
\end{itemize}
The game ends when there are no marbles left, but Marvin wants to make it last as long as possible.
KevinCarde
2022-05-17 20:17:55
that sure didn't work, my copy and paste has failed me!
that sure didn't work, my copy and paste has failed me!
KevinCarde
2022-05-17 20:17:57
let's try again:
let's try again:
KevinCarde
2022-05-17 20:18:18
Problem 3. Marvin is playing a solitaire game with marbles. There are $n$ bowls (for some positive integer $n$), and initially each bowl contains one marble. Each turn, Marvin may either
* remove a marble from a bowl, or
* choose a bowl $A$ with at least one marble and a different bowl $B$ with at least as many marbles as bowl $A$, and move one marble from bowl $A$ to bowl $B$.
The game ends when there are no marbles left, but Marvin wants to make it last as long as possible.
Problem 3. Marvin is playing a solitaire game with marbles. There are $n$ bowls (for some positive integer $n$), and initially each bowl contains one marble. Each turn, Marvin may either
* remove a marble from a bowl, or
* choose a bowl $A$ with at least one marble and a different bowl $B$ with at least as many marbles as bowl $A$, and move one marble from bowl $A$ to bowl $B$.
The game ends when there are no marbles left, but Marvin wants to make it last as long as possible.
TheBeast5520
2022-05-17 20:18:26
Im not sure whether \begin{itemize} works in aops...
Im not sure whether \begin{itemize} works in aops...
KevinCarde
2022-05-17 20:18:35
I have learned this lesson the hard way, so we've done a janky itemize with asterisks
I have learned this lesson the hard way, so we've done a janky itemize with asterisks
KevinCarde
2022-05-17 20:18:48
I love this problem because while the mechanics of the marbles stay the same, the parts all feel pretty different from each other. So let's dive in!
I love this problem because while the mechanics of the marbles stay the same, the parts all feel pretty different from each other. So let's dive in!
KevinCarde
2022-05-17 20:18:57
a. Prove that the game must end after at most $\frac{n(n+1)}{2}$ turns.
a. Prove that the game must end after at most $\frac{n(n+1)}{2}$ turns.
KevinCarde
2022-05-17 20:19:07
There are so, so many ways to go about this problem!! What were some of the ideas you had?
There are so, so many ways to go about this problem!! What were some of the ideas you had?
Pendronator
2022-05-17 20:19:57
Triangle numbers?
Triangle numbers?
CoolCarsOnTheRun
2022-05-17 20:19:57
monovariant!
monovariant!
W202jpw19
2022-05-17 20:19:57
brute force method
brute force method
Trigon
2022-05-17 20:19:57
Use a decreasing monovariant
Use a decreasing monovariant
Sigma_Monkey
2022-05-17 20:19:57
start with base case of 1 and 2 marbles
start with base case of 1 and 2 marbles
tricyclekick10
2022-05-17 20:19:57
viewing the marbles in bowls as in layers
viewing the marbles in bowls as in layers
chaidan_tamaroon
2022-05-17 20:19:57
Imagined the bowls in sorted order. marbles can only go to the left
Imagined the bowls in sorted order. marbles can only go to the left
CT17
2022-05-17 20:19:57
Consider the sum of the squares of the number of marbles in each bowl
Consider the sum of the squares of the number of marbles in each bowl
Ericsz
2022-05-17 20:19:57
the number of turns each marble can be used in?
the number of turns each marble can be used in?
KevinCarde
2022-05-17 20:20:07
All of these ideas could be turned into a proof!
All of these ideas could be turned into a proof!
KevinCarde
2022-05-17 20:20:14
We're only going to work through one way to solve the problem, but as usual, we invite you to think about some of the other ideas that we don't talk about.
We're only going to work through one way to solve the problem, but as usual, we invite you to think about some of the other ideas that we don't talk about.
ARKie-09
2022-05-17 20:20:17
what is a monovariant
what is a monovariant
KevinCarde
2022-05-17 20:20:26
Great question, and that's the idea I'm going to present here
Great question, and that's the idea I'm going to present here
KevinCarde
2022-05-17 20:20:34
Monovariants are a very powerful proof technique in general: if you can define a quantity that only strictly increases or strictly decreases as you carry out a process, you can learn a lot about that process!
Monovariants are a very powerful proof technique in general: if you can define a quantity that only strictly increases or strictly decreases as you carry out a process, you can learn a lot about that process!
KevinCarde
2022-05-17 20:20:49
There are many ways to do this problem without monovariants, but there are also many different monovariants you could define! I'm going to introduce one that's combinatorially defined, to limit the amount of algebra we have to do.
There are many ways to do this problem without monovariants, but there are also many different monovariants you could define! I'm going to introduce one that's combinatorially defined, to limit the amount of algebra we have to do.
KevinCarde
2022-05-17 20:21:10
Let's define the weight of a collection of marbles in bowls to be the total number of marbles plus the number of ways we can pick a pair of marbles from different bowls.
Let's define the weight of a collection of marbles in bowls to be the total number of marbles plus the number of ways we can pick a pair of marbles from different bowls.
KevinCarde
2022-05-17 20:21:29
We claim this is a monovariant: whatever Marvin does, the weight always decreases by at least $1$. So let's see that: what happens to the weight when Marvin removes a marble?
We claim this is a monovariant: whatever Marvin does, the weight always decreases by at least $1$. So let's see that: what happens to the weight when Marvin removes a marble?
Pendronator
2022-05-17 20:22:02
Decreases
Decreases
Sigma_Monkey
2022-05-17 20:22:02
it just goes down
it just goes down
BlizzardWizard
2022-05-17 20:22:02
It decreases.
It decreases.
KevinCarde
2022-05-17 20:22:08
As we should hope!
As we should hope!
KevinCarde
2022-05-17 20:22:14
Our weight includes a term for the total number of marbles, which goes down by $1$ if we remove a marble.
Our weight includes a term for the total number of marbles, which goes down by $1$ if we remove a marble.
KevinCarde
2022-05-17 20:22:20
(We probably also reduce the number of ways we can pick a pair of marbles, so maybe it goes down by more, but certainly it decreases by at least that $1$.)
(We probably also reduce the number of ways we can pick a pair of marbles, so maybe it goes down by more, but certainly it decreases by at least that $1$.)
KevinCarde
2022-05-17 20:22:33
What happens to the weight if we transfer a marble from a bowl $A$ to a bowl $B$ with at least as many marbles?
What happens to the weight if we transfer a marble from a bowl $A$ to a bowl $B$ with at least as many marbles?
KevinCarde
2022-05-17 20:23:30
Ooh, there are a few back and forth responses -- both increasing and decreasing, but how does it shake out in the end?
Ooh, there are a few back and forth responses -- both increasing and decreasing, but how does it shake out in the end?
Pendronator
2022-05-17 20:23:35
Decreases more
Decreases more
CoolCarsOnTheRun
2022-05-17 20:23:35
decreases, as $ab > (a-1)(b+1)$ when $b>a$
decreases, as $ab > (a-1)(b+1)$ when $b>a$
Thu2_2
2022-05-17 20:23:38
the number of pair decrease --> the weight still decrease
the number of pair decrease --> the weight still decrease
mythicalcheese31
2022-05-17 20:23:50
total stays the same, but a big number gets bigger and a smaller number gets smaller so im guessing the number of pairs go down, thus the monovariant decreases
total stays the same, but a big number gets bigger and a smaller number gets smaller so im guessing the number of pairs go down, thus the monovariant decreases
KevinCarde
2022-05-17 20:24:06
Exactly: CoolCarsOnTheRun has the algebraic explanation for why the term involving pairs will go down, and others have the conceptual explanation
Exactly: CoolCarsOnTheRun has the algebraic explanation for why the term involving pairs will go down, and others have the conceptual explanation
KevinCarde
2022-05-17 20:24:28
So we've shown that this weight that we defined is indeed a monovariant, decreasing by at least $1$ whenever Marvin does anything.
So we've shown that this weight that we defined is indeed a monovariant, decreasing by at least $1$ whenever Marvin does anything.
ARKie-09
2022-05-17 20:24:32
So a monovariant is basically something that will be proven to always either increase or decrease?
So a monovariant is basically something that will be proven to always either increase or decrease?
KevinCarde
2022-05-17 20:24:35
Yes indeed!
Yes indeed!
KevinCarde
2022-05-17 20:24:45
So, now let's see how our monovariant is useful!
So, now let's see how our monovariant is useful!
Pendronator
2022-05-17 20:24:54
Monovariants can also be stagnant, right? Even if that's not useful?
Monovariants can also be stagnant, right? Even if that's not useful?
KevinCarde
2022-05-17 20:25:11
It depends on how you define it -- sometimes it's useful to have a quantity that's strictly monotonic (so it strictly increases or decreases), sometimes weakly
It depends on how you define it -- sometimes it's useful to have a quantity that's strictly monotonic (so it strictly increases or decreases), sometimes weakly
KevinCarde
2022-05-17 20:25:14
both can be useful!
both can be useful!
KevinCarde
2022-05-17 20:25:22
in this case, our monovariant is strictly decreasing, which is what will be useful for us
in this case, our monovariant is strictly decreasing, which is what will be useful for us
KevinCarde
2022-05-17 20:25:26
What's the weight of our starting configuration, with $n$ bowls of $1$ marble each?
What's the weight of our starting configuration, with $n$ bowls of $1$ marble each?
CoolCarsOnTheRun
2022-05-17 20:25:55
$\binom{n}{2}+n$
$\binom{n}{2}+n$
Sigma_Monkey
2022-05-17 20:25:55
N + NC2
N + NC2
tricyclekick10
2022-05-17 20:25:55
n+nCr(n,2) = n(n+1)/2
n+nCr(n,2) = n(n+1)/2
mythicalcheese31
2022-05-17 20:26:04
n+n choose 2
n+n choose 2
Pendronator
2022-05-17 20:26:04
$n + \binom{n}{2}$
$n + \binom{n}{2}$
BlizzardWizard
2022-05-17 20:26:04
$\binom{n}{2}+n$, which is conveniently equal to $\frac{n(n+1)}{2}$
$\binom{n}{2}+n$, which is conveniently equal to $\frac{n(n+1)}{2}$
KevinCarde
2022-05-17 20:26:44
Great, so now: What's the weight of our ending configuration?
Great, so now: What's the weight of our ending configuration?
Stanlee
2022-05-17 20:26:57
wait what exactly are we saying is decreasing?
wait what exactly are we saying is decreasing?
Pendronator
2022-05-17 20:26:57
0
0
vrondoS
2022-05-17 20:26:57
0
0
Trigon
2022-05-17 20:26:57
0
0
alleycat
2022-05-17 20:26:57
$0$
$0$
Sigma_Monkey
2022-05-17 20:26:57
0
0
ARKie-09
2022-05-17 20:26:57
0
0
aopsuser008
2022-05-17 20:26:57
0
0
Stanlee
2022-05-17 20:27:05
we'd like it to be 0, right?
we'd like it to be 0, right?
W202jpw19
2022-05-17 20:27:05
0?
0?
impromptuA
2022-05-17 20:27:05
0
0
KevinCarde
2022-05-17 20:27:18
And it is indeed -- the game ends when Marvin removes all the marbles, so there are 0 marbles left and 0 pairs of marbles left!
And it is indeed -- the game ends when Marvin removes all the marbles, so there are 0 marbles left and 0 pairs of marbles left!
vrondoS
2022-05-17 20:27:21
if it is strictly decreasing, it can decrease a maximum of n(n+1)/2 times, so we're done
if it is strictly decreasing, it can decrease a maximum of n(n+1)/2 times, so we're done
Sigma_Monkey
2022-05-17 20:27:24
so at max, with every move decreasing weight by 1, the game would still only last n(n+1)/2 turns
so at max, with every move decreasing weight by 1, the game would still only last n(n+1)/2 turns
KevinCarde
2022-05-17 20:27:30
And that's the power of the monovariant!
And that's the power of the monovariant!
KevinCarde
2022-05-17 20:27:45
Since the weight goes from $n(n+1)/2$ to $0$, decreasing by at least $1$ each time, it can take at most $n(n+1)/2$ moves to get there. That's exactly what we needed to show!
Since the weight goes from $n(n+1)/2$ to $0$, decreasing by at least $1$ each time, it can take at most $n(n+1)/2$ moves to get there. That's exactly what we needed to show!
KevinCarde
2022-05-17 20:28:08
Again, lots of ways you could do this part -- it's possibly my favorite of all the problems on the QQ!
Again, lots of ways you could do this part -- it's possibly my favorite of all the problems on the QQ!
KevinCarde
2022-05-17 20:28:15
So don't stop thinking about it just because we've proved it one way
So don't stop thinking about it just because we've proved it one way
KevinCarde
2022-05-17 20:28:19
But for now, we'll move on to part b!
But for now, we'll move on to part b!
KevinCarde
2022-05-17 20:28:32
Oh, actually, I do want to address one question briefly --
Oh, actually, I do want to address one question briefly --
Sigma_Monkey
2022-05-17 20:28:33
how could we have thought of defining this weight in this specific way
how could we have thought of defining this weight in this specific way
KevinCarde
2022-05-17 20:29:05
This is part of the creativity of math! Solving equations is rote and straightforward; coming up with creative ideas (like useful monovariants or cool constructions) is the real magic
This is part of the creativity of math! Solving equations is rote and straightforward; coming up with creative ideas (like useful monovariants or cool constructions) is the real magic
KevinCarde
2022-05-17 20:29:41
In this case, we do have some guidance -- we need removing a marble to lower the monovariant, so we have a term for total number of marbles; and we need transfering a marble to lower it, so we have a term involving pairs
In this case, we do have some guidance -- we need removing a marble to lower the monovariant, so we have a term for total number of marbles; and we need transfering a marble to lower it, so we have a term involving pairs
mythicalcheese31
2022-05-17 20:29:44
i guess you could guess monovariants until you get something that looks like n(n+1)/2
i guess you could guess monovariants until you get something that looks like n(n+1)/2
KevinCarde
2022-05-17 20:29:49
and what we're trying to prove guides us too!
and what we're trying to prove guides us too!
KevinCarde
2022-05-17 20:29:54
Okay, now, for real, on to part b!
Okay, now, for real, on to part b!
KevinCarde
2022-05-17 20:29:55
b. Prove that for every positive integer $k$, there is an $n$ such that Marvin can make the $n$-bowl game last for at least $kn$ turns.
b. Prove that for every positive integer $k$, there is an $n$ such that Marvin can make the $n$-bowl game last for at least $kn$ turns.
KevinCarde
2022-05-17 20:30:15
Before, we needed to show that *every* game ended within a certain number of moves, which means that finding one sequence of moves that satisfies the inequality doesn't suffice.
Before, we needed to show that *every* game ended within a certain number of moves, which means that finding one sequence of moves that satisfies the inequality doesn't suffice.
KevinCarde
2022-05-17 20:30:26
Now, we need to show that there's *some* game that lasts long enough, so now it does suffice just to find one sequence of moves that satisfies the inequality!
Now, we need to show that there's *some* game that lasts long enough, so now it does suffice just to find one sequence of moves that satisfies the inequality!
KevinCarde
2022-05-17 20:30:40
So we get to be creative in a different way -- we need to construct a sequence of moves Marvin can make, any such sequence, that lasts enough turns. Any ideas?
So we get to be creative in a different way -- we need to construct a sequence of moves Marvin can make, any such sequence, that lasts enough turns. Any ideas?
Sigma_Monkey
2022-05-17 20:31:05
define his max turns with t(n). What we need to show is that t(n) grows faster than any linear function.
define his max turns with t(n). What we need to show is that t(n) grows faster than any linear function.
KevinCarde
2022-05-17 20:31:16
That's one approach, though potentially more powerful than we need -- since we don't actually have to be maximal here
That's one approach, though potentially more powerful than we need -- since we don't actually have to be maximal here
CoolCarsOnTheRun
2022-05-17 20:32:08
Take the $2^{2k-2}$-bowl game
Take the $2^{2k-2}$-bowl game
Pendronator
2022-05-17 20:32:08
Keep moving them all the way to the right, one by one, and then get rid of all of them at the end. It will last exactly $n(n+1)/2$ turns
Keep moving them all the way to the right, one by one, and then get rid of all of them at the end. It will last exactly $n(n+1)/2$ turns
BlizzardWizard
2022-05-17 20:32:08
First, move about half of the marbles so that there are two marbles each in about half of the bowls.
First, move about half of the marbles so that there are two marbles each in about half of the bowls.
KevinCarde
2022-05-17 20:32:35
The most common theme I saw among applicants was a power of two strategy, and the second most common involved building a sort of "staircase" of bowls with increasing numbers of marbles. (This second one is sort of what I think Pendronator's idea could turn into, though we can't actually reach the full $n(n+1)/2$ moves while following the rules)
The most common theme I saw among applicants was a power of two strategy, and the second most common involved building a sort of "staircase" of bowls with increasing numbers of marbles. (This second one is sort of what I think Pendronator's idea could turn into, though we can't actually reach the full $n(n+1)/2$ moves while following the rules)
chaidan_tamaroon
2022-05-17 20:32:55
k^k
k^k
KevinCarde
2022-05-17 20:32:58
This came up sometimes too!
This came up sometimes too!
Trigon
2022-05-17 20:33:01
If n is a power of 2 we can keep halving the number of bowls with marbles
If n is a power of 2 we can keep halving the number of bowls with marbles
KevinCarde
2022-05-17 20:33:12
This idea I think makes the algebra simplest, so let's push forward with this idea.
This idea I think makes the algebra simplest, so let's push forward with this idea.
KevinCarde
2022-05-17 20:33:24
We can move half of the marbles until we have $2^{m-1}$ bowls of $2$ marbles each, then half of the marbles until we have $2^{m-2}$ bowls of $4$ marbles each, etc.
We can move half of the marbles until we have $2^{m-1}$ bowls of $2$ marbles each, then half of the marbles until we have $2^{m-2}$ bowls of $4$ marbles each, etc.
KevinCarde
2022-05-17 20:33:43
After moving half of the marbles $m$ times, we'll have $2^0 = 1$ bowl with all $2^m$ marbles, at which point we can simply spend $2^m$ moves removing the marbles one by one.
After moving half of the marbles $m$ times, we'll have $2^0 = 1$ bowl with all $2^m$ marbles, at which point we can simply spend $2^m$ moves removing the marbles one by one.
KevinCarde
2022-05-17 20:33:48
How many moves did we take?
How many moves did we take?
Pendronator
2022-05-17 20:34:04
What if n is odd?
What if n is odd?
KevinCarde
2022-05-17 20:34:04
While thinking about that...
While thinking about that...
KevinCarde
2022-05-17 20:34:30
Great question! This is one of the ways that part b is easier -- we don't have to show that *every* game can last $kn$ turns, just that we can find *at last one* game that does last that long
Great question! This is one of the ways that part b is easier -- we don't have to show that *every* game can last $kn$ turns, just that we can find *at last one* game that does last that long
KevinCarde
2022-05-17 20:34:36
So we are free to pick whatever value of $n$ we find most convenient
So we are free to pick whatever value of $n$ we find most convenient
KevinCarde
2022-05-17 20:35:46
Back to our power of two world -- we took $m$ rounds of moving half the marbles before they got into a single bowl, which means...
Back to our power of two world -- we took $m$ rounds of moving half the marbles before they got into a single bowl, which means...
Trigon
2022-05-17 20:35:48
$n\frac{m}{2}$
$n\frac{m}{2}$
KevinCarde
2022-05-17 20:35:51
moves to do that.
moves to do that.
KevinCarde
2022-05-17 20:36:01
Then we removed marbles one by one, which gives us a total of...
Then we removed marbles one by one, which gives us a total of...
mythicalcheese31
2022-05-17 20:36:02
(m/2+1)*2^m from what I remember
(m/2+1)*2^m from what I remember
KevinCarde
2022-05-17 20:36:05
moves in this game
moves in this game
KevinCarde
2022-05-17 20:36:16
Yeah, we're basically done! Our goal was to take at least $kn$ moves, and starting with $n = 2^m$ marbles, we have constructed a game that takes $(m/2+1)2^m = (m/2+1)n$ moves.
Yeah, we're basically done! Our goal was to take at least $kn$ moves, and starting with $n = 2^m$ marbles, we have constructed a game that takes $(m/2+1)2^m = (m/2+1)n$ moves.
KevinCarde
2022-05-17 20:36:34
So if we simply take $m/2+1 = k$, or $m = 2k-2$, our construction will take $kn$ moves, as desired.
So if we simply take $m/2+1 = k$, or $m = 2k-2$, our construction will take $kn$ moves, as desired.
KevinCarde
2022-05-17 20:37:04
I think CoolCarsOnTheRun even specifically had $2^{2k-2}$ in their suggestion at the start, so that exponent was not an accident, I bet
I think CoolCarsOnTheRun even specifically had $2^{2k-2}$ in their suggestion at the start, so that exponent was not an accident, I bet
KevinCarde
2022-05-17 20:37:19
And now for something completely different in part c!
And now for something completely different in part c!
KevinCarde
2022-05-17 20:37:30
c. Marisa comes along and asks to join the game. Marvin and Marisa revise the rules: they will alternate taking turns, starting with Marisa. When the game ends, whoever took the last turn is the winner.
Prove that among any three consecutive values of $n$, there is at least one value for which Marvin has a winning strategy.
c. Marisa comes along and asks to join the game. Marvin and Marisa revise the rules: they will alternate taking turns, starting with Marisa. When the game ends, whoever took the last turn is the winner.
Prove that among any three consecutive values of $n$, there is at least one value for which Marvin has a winning strategy.
KevinCarde
2022-05-17 20:37:57
One immediate caveat: it's tempting to try to make a simplifying conjecture, like, "Marvin can win whenever the number of marbles is divisible by 3." While this feels like it'd be easier to work with than the problem as stated, it has one crucial disadvantage: it's false!
One immediate caveat: it's tempting to try to make a simplifying conjecture, like, "Marvin can win whenever the number of marbles is divisible by 3." While this feels like it'd be easier to work with than the problem as stated, it has one crucial disadvantage: it's false!
KevinCarde
2022-05-17 20:38:19
It's hard to find a pattern in the sequence of who wins (I haven't!): Marisa wins at least every other game, but sometimes she wins twice in a row before Marvin can win a game.
It's hard to find a pattern in the sequence of who wins (I haven't!): Marisa wins at least every other game, but sometimes she wins twice in a row before Marvin can win a game.
KevinCarde
2022-05-17 20:38:30
So rather than be disheartened, we'll use the problem statement as inspiration for how we'll set things up:
So rather than be disheartened, we'll use the problem statement as inspiration for how we'll set things up:
KevinCarde
2022-05-17 20:38:43
we'll show that, if Marisa can win games with $n-1$ and $n$ marbles, then Marvin has a winning strategy for the $n+1$ game.
we'll show that, if Marisa can win games with $n-1$ and $n$ marbles, then Marvin has a winning strategy for the $n+1$ game.
KevinCarde
2022-05-17 20:39:05
Note that this isn't induction or contradiction or any fancy proof technique (though you can phrase it in those ways if you find it more comfortable!): it's a simple if-then statement. To prove it, we simply assume that if the first player can win two games in a row, then argue that it logically follows that the second player can win the next game.
Note that this isn't induction or contradiction or any fancy proof technique (though you can phrase it in those ways if you find it more comfortable!): it's a simple if-then statement. To prove it, we simply assume that if the first player can win two games in a row, then argue that it logically follows that the second player can win the next game.
KevinCarde
2022-05-17 20:39:31
First, let's study what it means if Marisa, the first player, can win both the $n-1$ and the $n$ marble game. What must her first move be in the $n$ marble game?
First, let's study what it means if Marisa, the first player, can win both the $n-1$ and the $n$ marble game. What must her first move be in the $n$ marble game?
mathleticguyyy
2022-05-17 20:39:57
not remove for sure
not remove for sure
Sigma_Monkey
2022-05-17 20:39:57
if n-1 cups is winning, she cannot take away a marble
if n-1 cups is winning, she cannot take away a marble
KevinCarde
2022-05-17 20:40:08
Correct; if she had removed a marble, she'd leave Marvin with the $n-1$ marble game, which we're assuming is won by whoever moves first.
Correct; if she had removed a marble, she'd leave Marvin with the $n-1$ marble game, which we're assuming is won by whoever moves first.
captainsnake
2022-05-17 20:40:17
make it so there is one pile of size $2$ and $n-2$ piles of size $1$
make it so there is one pile of size $2$ and $n-2$ piles of size $1$
KevinCarde
2022-05-17 20:40:35
Great! Since the other move doesn't work, that means Marisa has to be able to win from here, if she gives this arrangement to Marvin.
Great! Since the other move doesn't work, that means Marisa has to be able to win from here, if she gives this arrangement to Marvin.
KevinCarde
2022-05-17 20:40:59
Now we've studied the $n-1$ and $n$ games a bit, so let's figure out how Marvin wins the $n+1$ game.
Now we've studied the $n-1$ and $n$ games a bit, so let's figure out how Marvin wins the $n+1$ game.
KevinCarde
2022-05-17 20:41:07
We need to win no matter what Marisa does, so we have two cases:
We need to win no matter what Marisa does, so we have two cases:
KevinCarde
2022-05-17 20:41:14
(1) Marisa removes a marble, leaving $n$ piles of $1$ marble each. Does Marvin win?
(1) Marisa removes a marble, leaving $n$ piles of $1$ marble each. Does Marvin win?
Sigma_Monkey
2022-05-17 20:41:30
either she gives n marbles which is winning
either she gives n marbles which is winning
Sigma_Monkey
2022-05-17 20:41:30
because she won in the same position
because she won in the same position
CoolCarsOnTheRun
2022-05-17 20:41:38
yes, because the first player wins the $n$-marble game
yes, because the first player wins the $n$-marble game
BlizzardWizard
2022-05-17 20:41:38
Yes, because the $n-$marble game is winning for whoever's turn it is.
Yes, because the $n-$marble game is winning for whoever's turn it is.
Trigon
2022-05-17 20:41:38
Yes, because Marisa won when she goes first
Yes, because Marisa won when she goes first
KevinCarde
2022-05-17 20:41:46
Right -- Marisa doesn't want to give Marvin the same arrangement where she had the advantage!
Right -- Marisa doesn't want to give Marvin the same arrangement where she had the advantage!
KevinCarde
2022-05-17 20:41:57
So she can't win if she does that, what if instead:
So she can't win if she does that, what if instead:
KevinCarde
2022-05-17 20:41:57
(2) Marisa moves a marble, leaving a single pile of $2$ marbles and $n-1$ piles of $1$. What should Marvin do?
(2) Marisa moves a marble, leaving a single pile of $2$ marbles and $n-1$ piles of $1$. What should Marvin do?
joannax
2022-05-17 20:42:47
remove a marble
remove a marble
tricyclekick10
2022-05-17 20:42:47
remove one marble from those $n-1$ piles of 1
remove one marble from those $n-1$ piles of 1
BlizzardWizard
2022-05-17 20:42:47
Remove a marble. By our earlier logic, the resulting position is losing for the next player, Marisa.
Remove a marble. By our earlier logic, the resulting position is losing for the next player, Marisa.
Amoszhang
2022-05-17 20:42:47
remove a marble
remove a marble
Trigon
2022-05-17 20:42:47
remove a marble - now it is as if he went first in the $n$ marble game
remove a marble - now it is as if he went first in the $n$ marble game
KevinCarde
2022-05-17 20:43:02
This one's trickier, but now we use what we learned before: if Marvin removes one of the singleton piles, he'll hand Marisa a single pile of $2$ and $n-2$ piles of $1$, which is the same position that she gave him in the $n$ marble game.
This one's trickier, but now we use what we learned before: if Marvin removes one of the singleton piles, he'll hand Marisa a single pile of $2$ and $n-2$ piles of $1$, which is the same position that she gave him in the $n$ marble game.
alleycat
2022-05-17 20:43:04
remove a marble in a pile of $1$ to get the same position Marisa had in the $n-2$ game
remove a marble in a pile of $1$ to get the same position Marisa had in the $n-2$ game
KevinCarde
2022-05-17 20:43:06
Exactly!
Exactly!
KevinCarde
2022-05-17 20:43:13
Marisa went on to win that game before, but now she's on the receiving end of this position, so Marvin can prevail here!
Marisa went on to win that game before, but now she's on the receiving end of this position, so Marvin can prevail here!
KevinCarde
2022-05-17 20:43:24
So we see that whatever opening move Marisa makes, Marvin has a path to victory, and we've successfully shown that if Marisa wins two games in a row, Marvin will win the next, which is exactly what we wanted.
So we see that whatever opening move Marisa makes, Marvin has a path to victory, and we've successfully shown that if Marisa wins two games in a row, Marvin will win the next, which is exactly what we wanted.
KevinCarde
2022-05-17 20:43:29
This last part had a very different flavor from the first two! But now for something even more completely different, I'll pass it back to Misha for Problem 4.
This last part had a very different flavor from the first two! But now for something even more completely different, I'll pass it back to Misha for Problem 4.
Misha
2022-05-17 20:43:39
Problem 4. An architect is designing a city. The city will be built on the segment of the $x$-axis from $(0,0)$ to $(1,0)$. Each building is a rectangle whose bottom edge rests on this segment of the $x$-axis. In the architect's vision, the city has infinitely many buildings: the $n^{\text{th}}$ building to be built will have width $(1/2)^n$ and height $n$. Two buildings cannot overlap, but they can share a vertical edge.
Problem 4. An architect is designing a city. The city will be built on the segment of the $x$-axis from $(0,0)$ to $(1,0)$. Each building is a rectangle whose bottom edge rests on this segment of the $x$-axis. In the architect's vision, the city has infinitely many buildings: the $n^{\text{th}}$ building to be built will have width $(1/2)^n$ and height $n$. Two buildings cannot overlap, but they can share a vertical edge.
Misha
2022-05-17 20:43:44
The sun rises in the east (in the positive $x$ direction, to the right of the city). A building has a nice view if you can see the sunrise from the top floor: there are no taller buildings to its right blocking the view.
The sun rises in the east (in the positive $x$ direction, to the right of the city). A building has a nice view if you can see the sunrise from the top floor: there are no taller buildings to its right blocking the view.
Misha
2022-05-17 20:43:52
There are also some parks in the city. You may have noticed that the widths of the buildings add up to $1$, so there's no room to add parks. Therefore all the parks are very small: just single points on the $x$-axis. However, parks must still be outdoors: If a building's bottom edge runs from $(a,0)$ to $(b,0)$, we cannot add a park at any point $(x,0)$ for $a < x < b$.
There are also some parks in the city. You may have noticed that the widths of the buildings add up to $1$, so there's no room to add parks. Therefore all the parks are very small: just single points on the $x$-axis. However, parks must still be outdoors: If a building's bottom edge runs from $(a,0)$ to $(b,0)$, we cannot add a park at any point $(x,0)$ for $a < x < b$.
Misha
2022-05-17 20:43:59
Problem 4(a). Suppose that there is a park at the point $(1/3, 0)$. Is it possible to design the city so that every building east of the park has a nice view? Can any buildings west of the park have a nice view?
Problem 4(a). Suppose that there is a park at the point $(1/3, 0)$. Is it possible to design the city so that every building east of the park has a nice view? Can any buildings west of the park have a nice view?
Misha
2022-05-17 20:44:17
(lots of text here, but hopefully you've all seen this problem already)
(lots of text here, but hopefully you've all seen this problem already)
Misha
2022-05-17 20:44:25
Let's put a park down at $(1/3,0)$ and try to build the city:
Let's put a park down at $(1/3,0)$ and try to build the city:
Misha
2022-05-17 20:44:33
When you try to build the first building, which is a width-$\frac12$, height-$1$ rectangle, what has to happen?
When you try to build the first building, which is a width-$\frac12$, height-$1$ rectangle, what has to happen?
ARKie-09
2022-05-17 20:44:53
go to right
go to right
Pendronator
2022-05-17 20:44:53
It has to be to the right of the garden
It has to be to the right of the garden
mythicalcheese31
2022-05-17 20:44:53
got to go on the right
got to go on the right
Trigon
2022-05-17 20:44:53
It has to go on the east of the park
It has to go on the east of the park
Sigma_Monkey
2022-05-17 20:44:53
it has to be to the right of the park
it has to be to the right of the park
impromptuA
2022-05-17 20:44:53
it has to be to the right of (1/3, 0)
it has to be to the right of (1/3, 0)
Thu2_2
2022-05-17 20:44:53
it must be on the right
it must be on the right
tricyclekick10
2022-05-17 20:44:53
it has to be right of the park
it has to be right of the park
joannax
2022-05-17 20:44:53
to the right of the park
to the right of the park
Misha
2022-05-17 20:44:56
It can only fit east of the park:
It can only fit east of the park:
Misha
2022-05-17 20:45:04
What about the second building, which has width $\frac14$ and height $2$?
What about the second building, which has width $\frac14$ and height $2$?
Pendronator
2022-05-17 20:45:23
To the left of the garden
To the left of the garden
mythicalcheese31
2022-05-17 20:45:23
go on left
go on left
tricyclekick10
2022-05-17 20:45:23
left of the park
left of the park
impromptuA
2022-05-17 20:45:23
*left
*left
CoolCarsOnTheRun
2022-05-17 20:45:23
now has to go left of the park
now has to go left of the park
Thu2_2
2022-05-17 20:45:23
it will go to the left
it will go to the left
Trigon
2022-05-17 20:45:23
Has to go on the west
Has to go on the west
impromptuA
2022-05-17 20:45:23
it has to be to the left
it has to be to the left
Misha
2022-05-17 20:45:25
The only remaining space where it fits is west of the park:
The only remaining space where it fits is west of the park:
Misha
2022-05-17 20:45:34
(I've had to rescale this diagram a bit to fit. The $x$-axis and $y$-axis no longer follow the same scale.)
(I've had to rescale this diagram a bit to fit. The $x$-axis and $y$-axis no longer follow the same scale.)
Misha
2022-05-17 20:45:46
If we continue placing buildings, we'll be forced to alternate east-west-east-west. This works out, because $\frac12 + \frac18 + \frac1{32} + \cdots = \frac23$ and $\frac14 + \frac1{16} + \frac1{64} + \dots = \frac13$.
If we continue placing buildings, we'll be forced to alternate east-west-east-west. This works out, because $\frac12 + \frac18 + \frac1{32} + \cdots = \frac23$ and $\frac14 + \frac1{16} + \frac1{64} + \dots = \frac13$.
Sigma_Monkey
2022-05-17 20:46:14
all odd number buildings built in the east, and all even number
buildings built in the west
all odd number buildings built in the east, and all even number
buildings built in the west
Misha
2022-05-17 20:46:27
Exactly: odd numbers east of the park, even numbers west of the park.
Exactly: odd numbers east of the park, even numbers west of the park.
Misha
2022-05-17 20:46:31
So far, we haven't said where exactly these buildings are placed: just whether they go east of the park or west of the park. But if we want to maximize the buildings with nice views of the sunrise to the east, what should we do?
So far, we haven't said where exactly these buildings are placed: just whether they go east of the park or west of the park. But if we want to maximize the buildings with nice views of the sunrise to the east, what should we do?
chaidan_tamaroon
2022-05-17 20:47:08
sort them
sort them
CoolCarsOnTheRun
2022-05-17 20:47:08
put the taller buildings as west as possible
put the taller buildings as west as possible
aopsuser008
2022-05-17 20:47:08
increasing height from right to left
increasing height from right to left
Misha
2022-05-17 20:47:11
If we're going in order, we should place each building as far east as possible, so that no other building blocks the sunlight. The buildings east of the park will look something like this:
If we're going in order, we should place each building as far east as possible, so that no other building blocks the sunlight. The buildings east of the park will look something like this:
Misha
2022-05-17 20:47:45
(Geometric series look kind of ridiculous: all the other odd buildings fit into the tiny gap between #5 and the park.)
(Geometric series look kind of ridiculous: all the other odd buildings fit into the tiny gap between #5 and the park.)
Misha
2022-05-17 20:47:54
With this design, all the buildings east of the park have nice views, because each one is taller than all the buildings east of it!
With this design, all the buildings east of the park have nice views, because each one is taller than all the buildings east of it!
Misha
2022-05-17 20:48:02
However, all the buildings west of the park are doomed. There are infinitely many buildings which must be built east of the park, so there are arbitrarily tall buildings east of the park! No matter how tall a building west of the park is, it can never see the sunrise.
However, all the buildings west of the park are doomed. There are infinitely many buildings which must be built east of the park, so there are arbitrarily tall buildings east of the park! No matter how tall a building west of the park is, it can never see the sunrise.
Misha
2022-05-17 20:48:39
That's an important idea to keep in mind: if there's infinitely many buildings to your right, you can never see the sunrise.
That's an important idea to keep in mind: if there's infinitely many buildings to your right, you can never see the sunrise.
Pendronator
2022-05-17 20:48:41
So how will the residents feel when they have a penthouse suite that crushes them and they can't see the sunrise?
So how will the residents feel when they have a penthouse suite that crushes them and they can't see the sunrise?
Misha
2022-05-17 20:48:52
Yes, this is a very soulcrushing problem, and it will only get worse later.
Yes, this is a very soulcrushing problem, and it will only get worse later.
Sigma_Monkey
2022-05-17 20:49:07
but for every building in the east, isn't there a building in the west 1 taller?
but for every building in the east, isn't there a building in the west 1 taller?
Misha
2022-05-17 20:49:18
Every building in the east also has taller buildings to the west.
Every building in the east also has taller buildings to the west.
Misha
2022-05-17 20:49:22
But they don't block the sunrise
But they don't block the sunrise
Misha
2022-05-17 20:49:31
Problem 4(b). Suppose that there are two parks: one at $(x_1, 0)$ and one at $(x_2,0)$, with $0 < x_1 < x_2 < 1$. For which $x_1$ and $x_2$ is it possible to design such a city? (No nice views are required.)
Problem 4(b). Suppose that there are two parks: one at $(x_1, 0)$ and one at $(x_2,0)$, with $0 < x_1 < x_2 < 1$. For which $x_1$ and $x_2$ is it possible to design such a city? (No nice views are required.)
Misha
2022-05-17 20:49:37
Problem 2(b) solution.
Problem 2(b) solution.
Misha
2022-05-17 20:49:43
In the first part, we saw that there was only one way to decide which buildings go where. There's a deeper underlying reason for that, and that's binary representations.
In the first part, we saw that there was only one way to decide which buildings go where. There's a deeper underlying reason for that, and that's binary representations.
Misha
2022-05-17 20:49:49
The sum $\frac12 + \frac18 + \frac1{32} + \cdots = \frac23$ is telling us that in base $2$, the fraction $\frac23$ is written as $0.10101010101\dots_2$. Similarly, the fraction $\frac13$ is written as $0.01010101010\dots_2$.
The sum $\frac12 + \frac18 + \frac1{32} + \cdots = \frac23$ is telling us that in base $2$, the fraction $\frac23$ is written as $0.10101010101\dots_2$. Similarly, the fraction $\frac13$ is written as $0.01010101010\dots_2$.
Misha
2022-05-17 20:50:00
With one exception we'll get to later, there is only one binary representation of any number between $0$ and $1$. So in our problem, the binary representations of the gaps $x_1$, $x_2 - x_1$, and $1 - x_2$ tell us which buildings must fill those gaps.
With one exception we'll get to later, there is only one binary representation of any number between $0$ and $1$. So in our problem, the binary representations of the gaps $x_1$, $x_2 - x_1$, and $1 - x_2$ tell us which buildings must fill those gaps.
Misha
2022-05-17 20:50:13
They also tell us when it's not possible at all. Suppose we have $x_1 = \frac13 = 0.0101010101\dots_2$, $x_2 - x_1 = \frac47 = 0.100100100\dots_2$, and $1 - x_2 = \frac{2}{21} = 0.00011000011\dots_2$, then what's the problem?
They also tell us when it's not possible at all. Suppose we have $x_1 = \frac13 = 0.0101010101\dots_2$, $x_2 - x_1 = \frac47 = 0.100100100\dots_2$, and $1 - x_2 = \frac{2}{21} = 0.00011000011\dots_2$, then what's the problem?
CoolCarsOnTheRun
2022-05-17 20:50:51
the fourth decimal place is $1$ in both 4/7 and 2/21, but we don't have two of those buildings
the fourth decimal place is $1$ in both 4/7 and 2/21, but we don't have two of those buildings
Trigon
2022-05-17 20:50:51
Building #4 is used multiple times
Building #4 is used multiple times
joannax
2022-05-17 20:50:51
3rd building disappears
3rd building disappears
Misha
2022-05-17 20:50:57
These numbers disagree about where the buildings go! None of these have a $1$ in the third place after the decimal, so none of the gaps "want" the third building. And all three gaps have a $1$ in the fourth place after the decimal, so all three gaps "want" the fourth building.
These numbers disagree about where the buildings go! None of these have a $1$ in the third place after the decimal, so none of the gaps "want" the third building. And all three gaps have a $1$ in the fourth place after the decimal, so all three gaps "want" the fourth building.
Misha
2022-05-17 20:51:07
We can only build the city if the binary representations agree. There's a few good ways to phrase this condition. One is: "in binary, everywhere that $x_1$ has a $1$, $x_2$ also has a $1$". Another is: "in binary, we can add $x_1 + (x_2 - x_1) = x_2$ without carrying".
We can only build the city if the binary representations agree. There's a few good ways to phrase this condition. One is: "in binary, everywhere that $x_1$ has a $1$, $x_2$ also has a $1$". Another is: "in binary, we can add $x_1 + (x_2 - x_1) = x_2$ without carrying".
Misha
2022-05-17 20:51:16
I mentioned that there's one exception to the uniqueness of binary representations. What is it?
I mentioned that there's one exception to the uniqueness of binary representations. What is it?
Thu2_2
2022-05-17 20:51:47
1/2
1/2
CoolCarsOnTheRun
2022-05-17 20:51:47
finite "decimals"
finite "decimals"
Trigon
2022-05-17 20:51:47
1 = 0.11...
1 = 0.11...
Misha
2022-05-17 20:51:50
It's the terminating expansions. In ordinary base $10$, we could write $\frac25$ as $0.4000\dots$ or $0.39999\dots$, where the $0$'s or $9$'s at the end repeat forever. Similarly, in base $2$, we could write $\frac38$ as $0.0110000\dots_2$ or $0.0101111\dots_2$, where the $0$'s or $1$'s at the end repeat forever.
It's the terminating expansions. In ordinary base $10$, we could write $\frac25$ as $0.4000\dots$ or $0.39999\dots$, where the $0$'s or $9$'s at the end repeat forever. Similarly, in base $2$, we could write $\frac38$ as $0.0110000\dots_2$ or $0.0101111\dots_2$, where the $0$'s or $1$'s at the end repeat forever.
Misha
2022-05-17 20:52:00
For our answer, this ultimately means that we should check both representations to see if they have the property we want.
For our answer, this ultimately means that we should check both representations to see if they have the property we want.
Misha
2022-05-17 20:52:16
Problem 4(c). For which $x_1$ and $x_2$ is it possible to design the city so that every building between the two parks has a nice view?
Problem 4(c). For which $x_1$ and $x_2$ is it possible to design the city so that every building between the two parks has a nice view?
Misha
2022-05-17 20:52:21
Problem 4(c) solution.
Problem 4(c) solution.
Misha
2022-05-17 20:52:26
Let's first think back to part (a), in which no building west of the park could have a nice view because there were arbitrarily tall buildings blocking the sunrise. The same thing could very well happen here, if there are arbitrarily tall buildings west of the park at $(x_2,0)$. When can we avoid that?
Let's first think back to part (a), in which no building west of the park could have a nice view because there were arbitrarily tall buildings blocking the sunrise. The same thing could very well happen here, if there are arbitrarily tall buildings west of the park at $(x_2,0)$. When can we avoid that?
Misha
2022-05-17 20:52:39
Okay, before that:
Okay, before that:
Pendronator
2022-05-17 20:52:42
I'm a little confused about how binary representations map to building locations geometrically?
I'm a little confused about how binary representations map to building locations geometrically?
Misha
2022-05-17 20:53:09
The $n^{\text{th}}$ digit of the binary representation is $1$ when the $n^{\text{th}}$ building goes into that gap.
The $n^{\text{th}}$ digit of the binary representation is $1$ when the $n^{\text{th}}$ building goes into that gap.
Misha
2022-05-17 20:53:42
Anyway, back to part (c).
Anyway, back to part (c).
Trigon
2022-05-17 20:53:49
$x_{2}$ is rational with a power of 2 denominator
$x_{2}$ is rational with a power of 2 denominator
Sigma_Monkey
2022-05-17 20:54:06
If the binary expansion of ?2
does not go on infinitely, that means it ends in a 0 (or an infinite stream of 0s), which means that
there are no buildings west of ?2 taller than buildings east of ?2.
If the binary expansion of ?2
does not go on infinitely, that means it ends in a 0 (or an infinite stream of 0s), which means that
there are no buildings west of ?2 taller than buildings east of ?2.
Misha
2022-05-17 20:54:07
The first thing that has to happen is that $1 - x_2$ must have a terminating binary expansion (like $\frac38 = 0.011_2$). Formally, $1-x_2$ has to be a rational number whose denominator is a power of $2$. Then, the buildings west of the park at $(x_2,0)$ have a fighting chance.
The first thing that has to happen is that $1 - x_2$ must have a terminating binary expansion (like $\frac38 = 0.011_2$). Formally, $1-x_2$ has to be a rational number whose denominator is a power of $2$. Then, the buildings west of the park at $(x_2,0)$ have a fighting chance.
Misha
2022-05-17 20:54:19
That's not quite all.
That's not quite all.
BlizzardWizard
2022-05-17 20:54:47
Every building designated to go to the right of $x_2$ must be shorter than every building to the left.
Every building designated to go to the right of $x_2$ must be shorter than every building to the left.
Misha
2022-05-17 20:54:50
In addition to that, we want to make sure that the buildings between the two parks are shorter than the tallest building east of the second park. In other words, all the $1$s in the binary representation of $x_2 - x_1$ must appear *after* all the $1$s in the binary expansion of $1-x_2$.
In addition to that, we want to make sure that the buildings between the two parks are shorter than the tallest building east of the second park. In other words, all the $1$s in the binary representation of $x_2 - x_1$ must appear *after* all the $1$s in the binary expansion of $1-x_2$.
Sigma_Monkey
2022-05-17 20:55:01
they also have to be ordered
they also have to be ordered
Misha
2022-05-17 20:55:03
Once this condition is satisfied, we can always place the buildings. Just make sure that — as in our solution to (a) — the buildings between the two parks are sorted by height, so that they don't block each other.
Once this condition is satisfied, we can always place the buildings. Just make sure that — as in our solution to (a) — the buildings between the two parks are sorted by height, so that they don't block each other.
Misha
2022-05-17 20:55:25
Problem 4(d). Show that it's possible to design the city so that no building shares a vertical edge with any other building. Can any buildings in such a city have a nice view — and if so, how many?
Problem 4(d). Show that it's possible to design the city so that no building shares a vertical edge with any other building. Can any buildings in such a city have a nice view — and if so, how many?
Misha
2022-05-17 20:55:56
Problem 4(d) solution.
Problem 4(d) solution.
Sigma_Monkey
2022-05-17 20:56:05
i don't understand how this could be possible, don't the widths of the buildings add up to 1?
i don't understand how this could be possible, don't the widths of the buildings add up to 1?
Misha
2022-05-17 20:56:12
Lots of people felt this way!
Lots of people felt this way!
Pendronator
2022-05-17 20:56:15
Welp, we just broke reality
Welp, we just broke reality
Misha
2022-05-17 20:56:23
This is a fun problem, because we're asking you to do something that's obviously impossible! After all, there's no room to put any space between the buildings, because their widths add up to 1.
This is a fun problem, because we're asking you to do something that's obviously impossible! After all, there's no room to put any space between the buildings, because their widths add up to 1.
Misha
2022-05-17 20:56:32
To get some intuition for why this is possible after all, let's look at diagram from part (a) again, but this time, add in the other buildings:
To get some intuition for why this is possible after all, let's look at diagram from part (a) again, but this time, add in the other buildings:
Misha
2022-05-17 20:56:40
Which buildings here do not have buildings on both sides?
Which buildings here do not have buildings on both sides?
Pendronator
2022-05-17 20:57:01
Edges?
Edges?
zhuzhu
2022-05-17 20:57:01
1 and 6?
1 and 6?
impromptuA
2022-05-17 20:57:01
6 and 1
6 and 1
Sigma_Monkey
2022-05-17 20:57:01
#6 and #1
#6 and #1
lpieleanu
2022-05-17 20:57:01
1 and 6
1 and 6
Misha
2022-05-17 20:57:14
1 is right, 6 is not, because there's more stuff to the left of 6
1 is right, 6 is not, because there's more stuff to the left of 6
Misha
2022-05-17 20:57:28
but there's another one hidden in plain sight...
but there's another one hidden in plain sight...
chaidan_tamaroon
2022-05-17 20:57:37
2, 1
2, 1
ThriftyPiano
2022-05-17 20:57:37
2
2
Trigon
2022-05-17 20:57:37
2
2
BlizzardWizard
2022-05-17 20:57:37
2
2
Misha
2022-05-17 20:57:52
One of the buildings we want is building #1, which is boring: it has the city edge to its west. But building #2 also does not have a building immediately after it: it has an infinite sequence of buildings getting closer and closer! That's what we'll have to do, but for every single building.
One of the buildings we want is building #1, which is boring: it has the city edge to its west. But building #2 also does not have a building immediately after it: it has an infinite sequence of buildings getting closer and closer! That's what we'll have to do, but for every single building.
Misha
2022-05-17 20:58:09
Totally not a problem right?
Totally not a problem right?
Misha
2022-05-17 20:58:16
Now that we know this problem might be possible to solve after all, here is the laziest possible way to solve it. We'll just go through the buildings in order (#1, #2, #3, and so on) and place each building so that it doesn't touch any other already-placed buildings.
Now that we know this problem might be possible to solve after all, here is the laziest possible way to solve it. We'll just go through the buildings in order (#1, #2, #3, and so on) and place each building so that it doesn't touch any other already-placed buildings.
Misha
2022-05-17 20:58:21
How can this go wrong? (Interpret "go wrong" broadly.)
How can this go wrong? (Interpret "go wrong" broadly.)
ThriftyPiano
2022-05-17 20:58:55
You get tired after placing building #34856935468
You get tired after placing building #34856935468
Misha
2022-05-17 20:59:00
We assume infinite patience
We assume infinite patience
chaidan_tamaroon
2022-05-17 20:59:07
no space for some building
no space for some building
tricyclekick10
2022-05-17 20:59:07
eventually we cant fit a building in
eventually we cant fit a building in
mythicalcheese31
2022-05-17 20:59:07
you use bad positioning and as a result you cant fit a building within any of the spaces
you use bad positioning and as a result you cant fit a building within any of the spaces
CT17
2022-05-17 20:59:07
all gaps are smaller than the width of the next available building
all gaps are smaller than the width of the next available building
Trigon
2022-05-17 20:59:07
There isn't enough space to place one of the buildings
There isn't enough space to place one of the buildings
Misha
2022-05-17 20:59:10
One way to fail is to get a partial city design where we can't actually place the next building. For example, after buildings #1 and #2 are placed, the total width of the gaps is $\frac14$: if we leave three equal gaps of width $\frac1{12}$, then none of them are big enough to fit building #3.
One way to fail is to get a partial city design where we can't actually place the next building. For example, after buildings #1 and #2 are placed, the total width of the gaps is $\frac14$: if we leave three equal gaps of width $\frac1{12}$, then none of them are big enough to fit building #3.
Misha
2022-05-17 20:59:32
(So leaving three equal gaps of width $\frac1{12}$ would be a bad idea.)
(So leaving three equal gaps of width $\frac1{12}$ would be a bad idea.)
Thu2_2
2022-05-17 20:59:42
you need to consider the space between the buildings?
you need to consider the space between the buildings?
Misha
2022-05-17 20:59:51
And there's another problem, too!
And there's another problem, too!
Misha
2022-05-17 20:59:56
Does anyone see the other problem?
Does anyone see the other problem?
mythicalcheese31
2022-05-17 21:00:31
you can place the next building but only if you touch another building
you can place the next building but only if you touch another building
Misha
2022-05-17 21:00:33
Another possible problem: there is a place to put the next building, but it's forced to touch a previous building. For example, say we place building #1 to leave a gap of width $\frac14$ on either side: then building #2 must fill one of those gaps entirely, so it will touch #1.
Another possible problem: there is a place to put the next building, but it's forced to touch a previous building. For example, say we place building #1 to leave a gap of width $\frac14$ on either side: then building #2 must fill one of those gaps entirely, so it will touch #1.
Misha
2022-05-17 21:00:42
In general, the second problem happens if we leave a gap that will be filled by finitely many buildings. Only an infinite set of buildings can behave weirdly enough to solve question 4(d)!
In general, the second problem happens if we leave a gap that will be filled by finitely many buildings. Only an infinite set of buildings can behave weirdly enough to solve question 4(d)!
Misha
2022-05-17 21:01:04
In theory, it's possible to avoid these problems by thinking very very very hard.
In theory, it's possible to avoid these problems by thinking very very very hard.
Misha
2022-05-17 21:01:19
If you have a solution that tells us exactly where every building goes, then you can check that it works, and everything is good.
If you have a solution that tells us exactly where every building goes, then you can check that it works, and everything is good.
Misha
2022-05-17 21:01:21
But that's too much work!
But that's too much work!
Misha
2022-05-17 21:01:25
We solve both problems by doing the bare minimum of thinking ahead. What we'll do is: whenever we leave a gap, we decide which buildings will go in that gap, and make sure there's infinitely many of them. That will tell us how wide the gap must be.
We solve both problems by doing the bare minimum of thinking ahead. What we'll do is: whenever we leave a gap, we decide which buildings will go in that gap, and make sure there's infinitely many of them. That will tell us how wide the gap must be.
Misha
2022-05-17 21:01:34
For example, suppose that when we're placing building #1, we decide that buildings #2, #4, #6, and so on will go to its left, and buildings #3, #5, #7, and so on will go to its right. Where should building #1 go, in that case?
For example, suppose that when we're placing building #1, we decide that buildings #2, #4, #6, and so on will go to its left, and buildings #3, #5, #7, and so on will go to its right. Where should building #1 go, in that case?
chaidan_tamaroon
2022-05-17 21:02:05
1/3
1/3
Sigma_Monkey
2022-05-17 21:02:05
1/3
1/3
BlizzardWizard
2022-05-17 21:02:05
(1/3, 5/6)
(1/3, 5/6)
Misha
2022-05-17 21:02:07
The buildings to its left have widths $\frac14 + \frac16 + \frac1{64} + \dots = \frac13$, and the buildings to its right have widths $\frac18 + \frac1{32} + \frac1{128} + \dots = \frac16$. So we should place #1 to cover up the interval $[\frac13, \frac56]$ on the $x$-axis.
The buildings to its left have widths $\frac14 + \frac16 + \frac1{64} + \dots = \frac13$, and the buildings to its right have widths $\frac18 + \frac1{32} + \frac1{128} + \dots = \frac16$. So we should place #1 to cover up the interval $[\frac13, \frac56]$ on the $x$-axis.
Misha
2022-05-17 21:02:19
We can continue on like this. For example, when we place building #2 somewhere in the middle of the interval $[0,\frac13]$, we'll leave two gaps. Let's say buildings #4, #8, #12, #16, and so on will fill the first gap, and buildings #6, #10, #14, #18, and so on will fill the second. We can sum a geometric series to find out that building #2 is placed on the interval $[\frac1{15}, \frac{19}{60}]$.
We can continue on like this. For example, when we place building #2 somewhere in the middle of the interval $[0,\frac13]$, we'll leave two gaps. Let's say buildings #4, #8, #12, #16, and so on will fill the first gap, and buildings #6, #10, #14, #18, and so on will fill the second. We can sum a geometric series to find out that building #2 is placed on the interval $[\frac1{15}, \frac{19}{60}]$.
Misha
2022-05-17 21:02:51
(That geometric series is obnoxious as you can see from the value $\frac{19}{60}$, but the details aren't super important.)
(That geometric series is obnoxious as you can see from the value $\frac{19}{60}$, but the details aren't super important.)
Misha
2022-05-17 21:02:53
In general, to place the $n^{\text{th}}$ building, we divide all the other buildings in the same gap into two infinite sets (however we like). We sum up their lengths to figure out how much space each infinite set needs, and then we place the $n^{\text{th}}$ building to leave exactly that much space on each side.
In general, to place the $n^{\text{th}}$ building, we divide all the other buildings in the same gap into two infinite sets (however we like). We sum up their lengths to figure out how much space each infinite set needs, and then we place the $n^{\text{th}}$ building to leave exactly that much space on each side.
Misha
2022-05-17 21:03:03
This plan will work, because we can always do the $n^{\text{th}}$ step, for any $n$. No buildings will touch, because the $n^{\text{th}}$ building does not touch any of the first $n-1$ buildings, for any $n$.
This plan will work, because we can always do the $n^{\text{th}}$ step, for any $n$. No buildings will touch, because the $n^{\text{th}}$ building does not touch any of the first $n-1$ buildings, for any $n$.
Misha
2022-05-17 21:03:13
I feel like I've just said something really dubious-sounding (but true). Does anyone have any skepticism to express?
I feel like I've just said something really dubious-sounding (but true). Does anyone have any skepticism to express?
chaidan_tamaroon
2022-05-17 21:03:20
Does this method require the axiom of choice?
Does this method require the axiom of choice?
Misha
2022-05-17 21:03:45
A maximally lazy solution would need the axiom of choice, but we can avoid it by having a reasonable rule for how we split the buildings.
A maximally lazy solution would need the axiom of choice, but we can avoid it by having a reasonable rule for how we split the buildings.
Misha
2022-05-17 21:03:53
For instance, always alternate left-right.
For instance, always alternate left-right.
Pendronator
2022-05-17 21:03:55
What's the axiom of choice
What's the axiom of choice
Misha
2022-05-17 21:04:00
Don't worry about it
Don't worry about it
Trigon
2022-05-17 21:04:11
There's no touching at any finite step, how do we know it's still true when we've done infinitely many?
There's no touching at any finite step, how do we know it's still true when we've done infinitely many?
Misha
2022-05-17 21:04:44
If two buildings touch, then those two buildings have some finite numbers $n_1 < n_2$. So they'll already need to touch by the time we do step $n_2$.
If two buildings touch, then those two buildings have some finite numbers $n_1 < n_2$. So they'll already need to touch by the time we do step $n_2$.
Misha
2022-05-17 21:04:49
(And we prove they don't.)
(And we prove they don't.)
Sigma_Monkey
2022-05-17 21:04:51
wait so the sizes of the gaps add up to 0??
wait so the sizes of the gaps add up to 0??
Misha
2022-05-17 21:04:54
Yepppp.
Yepppp.
alleycat
2022-05-17 21:05:16
its like induction but informal
its like induction but informal
Misha
2022-05-17 21:05:34
We can make it more formal by specifying all the details, but hopefully it's clear that we *can* specify them.
We can make it more formal by specifying all the details, but hopefully it's clear that we *can* specify them.
Misha
2022-05-17 21:05:42
Finally: will this plan let any buildings have a nice view?
Finally: will this plan let any buildings have a nice view?
chaidan_tamaroon
2022-05-17 21:06:19
yes, 1
yes, 1
CT17
2022-05-17 21:06:19
only the one touching the right edge
only the one touching the right edge
alleycat
2022-05-17 21:06:19
not this particular one, but we can make it so that the 1/2 building has a nice view by placing it all the way to the right and then doing the same thing
not this particular one, but we can make it so that the 1/2 building has a nice view by placing it all the way to the right and then doing the same thing
BlizzardWizard
2022-05-17 21:06:19
If we set the buildings up such that there is a rightmost building, then that rightmost building has a nice view.
If we set the buildings up such that there is a rightmost building, then that rightmost building has a nice view.
Trigon
2022-05-17 21:06:21
This specific plan won't but it's possible to make only the first building have a nice view
This specific plan won't but it's possible to make only the first building have a nice view
Misha
2022-05-17 21:06:42
Let's first talk about the plan we did where we never put anything along the right edge.
Let's first talk about the plan we did where we never put anything along the right edge.
Misha
2022-05-17 21:06:50
It won't have any buildings with nice views! At every stage of the building process, there will be a gap on the east edge of the city, where we plan to build infinitely many buildings. Those buildings will block the sunrise from any building built so far (and again, since that's true for every $n$, it's true for all buildings).
It won't have any buildings with nice views! At every stage of the building process, there will be a gap on the east edge of the city, where we plan to build infinitely many buildings. Those buildings will block the sunrise from any building built so far (and again, since that's true for every $n$, it's true for all buildings).
Misha
2022-05-17 21:06:56
In fact, when you think about it, every building has taller buildings arbitrarily close to it: it will only see the sun when the sun is directly overhead. I'm not sure I like this city design so much anymore...
In fact, when you think about it, every building has taller buildings arbitrarily close to it: it will only see the sun when the sun is directly overhead. I'm not sure I like this city design so much anymore...
Pendronator
2022-05-17 21:06:58
I can't tell if this architect deserves a raise or deserves to get fired
I can't tell if this architect deserves a raise or deserves to get fired
Misha
2022-05-17 21:07:10
And this is not just true for the solution we found to 4(d). The only mildly different thing we can do is put a single building against the east edge of the city: then that building gets to have a nice view.
And this is not just true for the solution we found to 4(d). The only mildly different thing we can do is put a single building against the east edge of the city: then that building gets to have a nice view.
Misha
2022-05-17 21:07:28
Otherwise, no building in any solution to 4(d) can have a nice view, because a nice view requires that there's only finitely many buildings to the east. (We proved this back in part (a).)
Otherwise, no building in any solution to 4(d) can have a nice view, because a nice view requires that there's only finitely many buildings to the east. (We proved this back in part (a).)
Misha
2022-05-17 21:07:33
And when there's only finitely many buildings on an interval, they will have to touch!
And when there's only finitely many buildings on an interval, they will have to touch!
mathleticguyyy
2022-05-17 21:07:48
We can't do any sort of "finite" construction
We can't do any sort of "finite" construction
Misha
2022-05-17 21:07:50
Exactly.
Exactly.
Misha
2022-05-17 21:07:53
Having solved this bizarre, impossible problem, let's turn it over to Tim! who will tell us about the hit game show Singleton!
Having solved this bizarre, impossible problem, let's turn it over to Tim! who will tell us about the hit game show Singleton!
timblack
2022-05-17 21:08:04
Thanks, Misha!
Thanks, Misha!
timblack
2022-05-17 21:08:19
I'm excited to talk with you all about this problem, because it's about one of my favorite TV shows
I'm excited to talk with you all about this problem, because it's about one of my favorite TV shows
timblack
2022-05-17 21:08:30
Problem 5 Assaf, Ben, Charlotte, Dan, and Emily are set to appear on the hit reality TV game show Singleton. At the end of each episode, one of the contestants is "voted out of the set" and eliminated from the game. The last contestant remaining wins.
Problem 5 Assaf, Ben, Charlotte, Dan, and Emily are set to appear on the hit reality TV game show Singleton. At the end of each episode, one of the contestants is "voted out of the set" and eliminated from the game. The last contestant remaining wins.
timblack
2022-05-17 21:08:41
In the voting phase of the episode, each contestant left in the game casts a vote against another contestant still in the game. They vote one at a time, in alphabetical order. The votes are public: when a contestant goes to vote, they are aware of all votes cast so far, and can use that information to inform who they vote against. Once everyone has voted, the contestant that received the most votes is eliminated. If there is a tie, the player who is last alphabetically among those who received the maximum number of votes is eliminated.
In the voting phase of the episode, each contestant left in the game casts a vote against another contestant still in the game. They vote one at a time, in alphabetical order. The votes are public: when a contestant goes to vote, they are aware of all votes cast so far, and can use that information to inform who they vote against. Once everyone has voted, the contestant that received the most votes is eliminated. If there is a tie, the player who is last alphabetically among those who received the maximum number of votes is eliminated.
timblack
2022-05-17 21:08:57
It is common knowledge that the contestants all act rationally according to the following priorities:
It is common knowledge that the contestants all act rationally according to the following priorities:
timblack
2022-05-17 21:09:03
I. A contestant's top priority is to avoid elimination for as many episodes as possible (in particular, they would like to win the game if possible).
I. A contestant's top priority is to avoid elimination for as many episodes as possible (in particular, they would like to win the game if possible).
timblack
2022-05-17 21:09:10
II. A contestant wants to eliminate someone in this episode that is as early in the alphabet as possible (without compromising the top priority of lasting as long as they can).
II. A contestant wants to eliminate someone in this episode that is as early in the alphabet as possible (without compromising the top priority of lasting as long as they can).
alleycat
2022-05-17 21:09:41
its kinda like the pirate problem
its kinda like the pirate problem
timblack
2022-05-17 21:09:53
Yes, that's another problem about voting and backstabbing
Yes, that's another problem about voting and backstabbing
timblack
2022-05-17 21:09:55
What a great show
What a great show
timblack
2022-05-17 21:10:04
The problem has three parts, all about the decisions that the players make in the game. The most fundamental question is:
The problem has three parts, all about the decisions that the players make in the game. The most fundamental question is:
timblack
2022-05-17 21:10:11
Part a. Who gets eliminated in the first episode? Who wins the game?
Part a. Who gets eliminated in the first episode? Who wins the game?
timblack
2022-05-17 21:10:22
Problem 5 solution
Problem 5 solution
timblack
2022-05-17 21:10:29
I should admit that I’ve been watching Singleton from the very first season, when it was hosted by Georg Cantor.
I should admit that I’ve been watching Singleton from the very first season, when it was hosted by Georg Cantor.
timblack
2022-05-17 21:10:37
So even though it’s possible to write up a solution a little bit shorter than what we’ll do here, I like to get into the minds of the contestants and try to understand their thought process and intuitions.
So even though it’s possible to write up a solution a little bit shorter than what we’ll do here, I like to get into the minds of the contestants and try to understand their thought process and intuitions.
Pendronator
2022-05-17 21:11:12
If everyone votes as early in the alphabet as they can, wouldn't Assaf lose first?
If everyone votes as early in the alphabet as they can, wouldn't Assaf lose first?
timblack
2022-05-17 21:11:58
Well, if Ben votes out Assaf first, then suddenly Ben is at the front of the alphabet, and he's not liking this "vote the first person out alphabetically plan anymore"
Well, if Ben votes out Assaf first, then suddenly Ben is at the front of the alphabet, and he's not liking this "vote the first person out alphabetically plan anymore"
timblack
2022-05-17 21:12:21
The contestants are Assaf, Ben, Charlotte, Dan, and Emily. They are listed in alphabetical order, but I also want to think of this as the pecking order: Assaf is at the top; he gets to vote first, and if he’s tied for the most votes, he doesn’t get eliminated.
The contestants are Assaf, Ben, Charlotte, Dan, and Emily. They are listed in alphabetical order, but I also want to think of this as the pecking order: Assaf is at the top; he gets to vote first, and if he’s tied for the most votes, he doesn’t get eliminated.
timblack
2022-05-17 21:12:34
(And maybe Assaf has a target on his back)
(And maybe Assaf has a target on his back)
timblack
2022-05-17 21:12:41
Emily is at the bottom; she votes last, and if she is tied for the most votes, she’s the one that’s out.
Emily is at the bottom; she votes last, and if she is tied for the most votes, she’s the one that’s out.
timblack
2022-05-17 21:12:53
The problem asks who gets voted out in the first episode, but to understand that, we need to learn their motivations, their thought process. So, we need to look into the future, and think about how the later episodes will play out.
The problem asks who gets voted out in the first episode, but to understand that, we need to learn their motivations, their thought process. So, we need to look into the future, and think about how the later episodes will play out.
timblack
2022-05-17 21:13:07
For simplicity, I’m going to assume that at every stage of the game, the players initials are A, B, C, etc. So, if Assaf were to get voted out the first episode, all the other players would get promoted: Ben would become Aen, Charlotte would move up Bharlotte, Dan would turn into Can, and Emily would henceforth be Dmily.
For simplicity, I’m going to assume that at every stage of the game, the players initials are A, B, C, etc. So, if Assaf were to get voted out the first episode, all the other players would get promoted: Ben would become Aen, Charlotte would move up Bharlotte, Dan would turn into Can, and Emily would henceforth be Dmily.
TheBeast5520
2022-05-17 21:13:24
recursively build it up from the case of just two people.
recursively build it up from the case of just two people.
Thu2_2
2022-05-17 21:13:24
we can start upside down by examining cases where there're only 2, 3, 4, then 5 contestants
we can start upside down by examining cases where there're only 2, 3, 4, then 5 contestants
captainsnake
2022-05-17 21:13:24
We can start by analyzing a $2$ person game, and use the results of that to figure out how people would vote in a $3$ person game, and so on until $5$ person game
We can start by analyzing a $2$ person game, and use the results of that to figure out how people would vote in a $3$ person game, and so on until $5$ person game
timblack
2022-05-17 21:13:34
Let’s begin at the end. In the finale episode, we have The Final Two. There are just two players left, A and B. Who wins the game?
Let’s begin at the end. In the finale episode, we have The Final Two. There are just two players left, A and B. Who wins the game?
Trigon
2022-05-17 21:13:51
A
A
Thu2_2
2022-05-17 21:13:51
A
A
Sigma_Monkey
2022-05-17 21:13:51
A
A
boing123
2022-05-17 21:13:51
A
A
tricyclekick10
2022-05-17 21:13:51
A
A
Pendronator
2022-05-17 21:13:51
A
A
alleycat
2022-05-17 21:13:51
A
A
timblack
2022-05-17 21:13:53
That’s right, A and B both vote for each other, but since B is later alphabetically, B is eliminated, and A wins the game.
That’s right, A and B both vote for each other, but since B is later alphabetically, B is eliminated, and A wins the game.
impromptuA
2022-05-17 21:13:58
how do you pronounce dmily
how do you pronounce dmily
timblack
2022-05-17 21:14:04
This is why the Math Jam is online
This is why the Math Jam is online
timblack
2022-05-17 21:14:14
By the way, this is why I want to think of being early in the alphabet as being “at the top” and being late alphabetically as “at the bottom,” because at the end of the game, it’s the player at the top that comes out on top.
By the way, this is why I want to think of being early in the alphabet as being “at the top” and being late alphabetically as “at the bottom,” because at the end of the game, it’s the player at the top that comes out on top.
Thu2_2
2022-05-17 21:14:25
is it a real TV show???
is it a real TV show???
timblack
2022-05-17 21:14:32
I’m seeing a lot of messages in the chat from people saying how much they love the TV show Singleton. People are saying what their favorite part of the show is. People are saying how it’s totally a real show and I’m not just making it all up. I’ll pass some of those messages in a minute.
I’m seeing a lot of messages in the chat from people saying how much they love the TV show Singleton. People are saying what their favorite part of the show is. People are saying how it’s totally a real show and I’m not just making it all up. I’ll pass some of those messages in a minute.
timblack
2022-05-17 21:14:52
My favorite episode was the one in season 52 when one of the contestants smuggled the power set operator into the game. The production company couldn’t handle the size of the game and had to shut down the whole operation.
My favorite episode was the one in season 52 when one of the contestants smuggled the power set operator into the game. The production company couldn’t handle the size of the game and had to shut down the whole operation.
Sigma_Monkey
2022-05-17 21:15:03
can confirm. Singleton is one of my favorite shows to binge.
can confirm. Singleton is one of my favorite shows to binge.
TheoZhang666
2022-05-17 21:15:23
for sure
for sure
Thu2_2
2022-05-17 21:15:23
i should check it out then
i should check it out then
Pendronator
2022-05-17 21:15:23
Do y'all remember when that thing happened in that one episode
Do y'all remember when that thing happened in that one episode
timblack
2022-05-17 21:15:28
Anyways.
Anyways.
timblack
2022-05-17 21:15:35
If you’ve watched a lot of Singleton on TV, you know that sometimes the people at the top are in control, picking off the people at the bottom. But other times, the person at the top is seen as too much of a threat to win the game, and the other players conspire to vote them out. But does the math back up this strategy? We shall see.
If you’ve watched a lot of Singleton on TV, you know that sometimes the people at the top are in control, picking off the people at the bottom. But other times, the person at the top is seen as too much of a threat to win the game, and the other players conspire to vote them out. But does the math back up this strategy? We shall see.
captainsnake
2022-05-17 21:15:46
My favorite part of Singleton was when assaf revealed that he was teaming up with Dan the entire time. Huge plot twist. (sorry for spoilers!)
My favorite part of Singleton was when assaf revealed that he was teaming up with Dan the entire time. Huge plot twist. (sorry for spoilers!)
timblack
2022-05-17 21:16:08
Let’s go back to the penultimate episode, The Final Three, when there are three players left, A, B, and C. Who is A’s first choice to eliminate?
Let’s go back to the penultimate episode, The Final Three, when there are three players left, A, B, and C. Who is A’s first choice to eliminate?
mathleticguyyy
2022-05-17 21:16:24
B would definitely want to eliminate A to win
B would definitely want to eliminate A to win
TheoZhang666
2022-05-17 21:16:24
B
B
captainsnake
2022-05-17 21:16:24
$A$ wants to eliminate $B$
$A$ wants to eliminate $B$
timblack
2022-05-17 21:16:29
Yes, A wants B out. Let’s look back at the player’s priorities:
Yes, A wants B out. Let’s look back at the player’s priorities:
timblack
2022-05-17 21:16:35
“I. A contestant's top priority is to avoid elimination for as many episodes as possible (in particular, they would like to win the game if possible).”
“I. A contestant's top priority is to avoid elimination for as many episodes as possible (in particular, they would like to win the game if possible).”
timblack
2022-05-17 21:16:41
As long as A can avoid elimination this round, A will be at the top going into the finale, and will end up winning it all. So, whether B or C is eliminated, priority I is satisfied. So we move onto priority II:
As long as A can avoid elimination this round, A will be at the top going into the finale, and will end up winning it all. So, whether B or C is eliminated, priority I is satisfied. So we move onto priority II:
timblack
2022-05-17 21:16:54
“II. A contestant wants to eliminate someone in this episode that is as early in the alphabet as possible (without compromising the top priority of lasting as long as they can).”
“II. A contestant wants to eliminate someone in this episode that is as early in the alphabet as possible (without compromising the top priority of lasting as long as they can).”
timblack
2022-05-17 21:17:03
Since B is earlier alphabetically (higher in the pecking order) than C, we know that A wants B out the most.
Since B is earlier alphabetically (higher in the pecking order) than C, we know that A wants B out the most.
timblack
2022-05-17 21:17:12
Let’s see what B is thinking. We’re still talking about the penultimate episode, when there are three players left, A, B, and C. Who does B want out?
Let’s see what B is thinking. We’re still talking about the penultimate episode, when there are three players left, A, B, and C. Who does B want out?
Sigma_Monkey
2022-05-17 21:17:29
A
A
TheoZhang666
2022-05-17 21:17:29
A
A
Pendronator
2022-05-17 21:17:29
A
A
alleycat
2022-05-17 21:17:29
A
A
Mathboy345
2022-05-17 21:17:29
A
A
BlizzardWizard
2022-05-17 21:17:29
A, because this lets B win.
A, because this lets B win.
Trigon
2022-05-17 21:17:29
B wants A out
B wants A out
timblack
2022-05-17 21:17:31
Yup. B wants to get A out.
Yup. B wants to get A out.
timblack
2022-05-17 21:17:37
It all comes down to priority I: If A is eliminated, then B moves up to the top position, and wins the game. On the other hand, if C were eliminated, then B would be at the bottom and get second place. So B prefers for A to get voted out.
It all comes down to priority I: If A is eliminated, then B moves up to the top position, and wins the game. On the other hand, if C were eliminated, then B would be at the bottom and get second place. So B prefers for A to get voted out.
timblack
2022-05-17 21:17:42
Alright, who does C want to see eliminated?
Alright, who does C want to see eliminated?
Sigma_Monkey
2022-05-17 21:17:48
so C decides what happens
so C decides what happens
Trigon
2022-05-17 21:17:57
C wants A out
C wants A out
captainsnake
2022-05-17 21:17:57
$A$
$A$
mythicalcheese31
2022-05-17 21:17:57
A
A
BlizzardWizard
2022-05-17 21:17:57
Also A, but this time by rule II.
Also A, but this time by rule II.
Thu2_2
2022-05-17 21:17:57
A
A
vrondoS
2022-05-17 21:17:57
A
A
timblack
2022-05-17 21:18:05
Yes, C wants A out.
Yes, C wants A out.
timblack
2022-05-17 21:18:10
If C survives this vote, no matter whether A or B is booted, C is at the bottom going into the finale, and ends up in second place. So, priority II says that C would prefer to get out the person earlier alphabetically, and that’s A.
If C survives this vote, no matter whether A or B is booted, C is at the bottom going into the finale, and ends up in second place. So, priority II says that C would prefer to get out the person earlier alphabetically, and that’s A.
timblack
2022-05-17 21:18:18
To summarize: When there are three players, A, B, and C, player A wants B out, while B and C want A out.
To summarize: When there are three players, A, B, and C, player A wants B out, while B and C want A out.
timblack
2022-05-17 21:18:23
So who gets voted out?
So who gets voted out?
Sigma_Monkey
2022-05-17 21:18:33
A
A
hellokikki
2022-05-17 21:18:33
A
A
HumanCalculator9
2022-05-17 21:18:33
A
A
mathleticguyyy
2022-05-17 21:18:33
A
A
CT17
2022-05-17 21:18:33
A
A
Trigon
2022-05-17 21:18:33
A
A
joannax
2022-05-17 21:18:33
A
A
timblack
2022-05-17 21:18:38
Yep, A gets the boot. Both B and C want A out, and that’s a majority. No matter who A votes for, player B can vote for A knowing that player C will definitely back that up with a second vote for A.
Yep, A gets the boot. Both B and C want A out, and that’s a majority. No matter who A votes for, player B can vote for A knowing that player C will definitely back that up with a second vote for A.
timblack
2022-05-17 21:18:47
So going into The Final Three, players want to be right in the middle: The player at the top (A) gets eliminated in third place, the player at the bottom (C) ends up in second, while the middle player (B) wins the whole game.
So going into The Final Three, players want to be right in the middle: The player at the top (A) gets eliminated in third place, the player at the bottom (C) ends up in second, while the middle player (B) wins the whole game.
timblack
2022-05-17 21:18:53
Let’s work a bit further back in time, to The Final Four. There are four players remaining: A, B, C, and D.
Let’s work a bit further back in time, to The Final Four. There are four players remaining: A, B, C, and D.
timblack
2022-05-17 21:18:59
Player A is going to stay at the top no matter what, so A just wants to eliminate someone as early in the alphabet (as close to the top) as possible, other than themself.
Player A is going to stay at the top no matter what, so A just wants to eliminate someone as early in the alphabet (as close to the top) as possible, other than themself.
timblack
2022-05-17 21:19:10
Player D is going to stay at the bottom no matter what, so D also wants to eliminate someone as close to the top as possible (and D would be happiest if A were voted out).
Player D is going to stay at the bottom no matter what, so D also wants to eliminate someone as close to the top as possible (and D would be happiest if A were voted out).
Mathboy345
2022-05-17 21:19:14
isn't this a really complicated game theory question
isn't this a really complicated game theory question
timblack
2022-05-17 21:19:18
:/ ?
:/
?
timblack
2022-05-17 21:19:26
What about player B? Who is B’s top choice for elimination?
What about player B? Who is B’s top choice for elimination?
Trigon
2022-05-17 21:19:51
C
C
CoolCarsOnTheRun
2022-05-17 21:19:51
C
C
mythicalcheese31
2022-05-17 21:19:51
ideally C, but he can settle for D
ideally C, but he can settle for D
Pendronator
2022-05-17 21:19:51
C
C
HumanCalculator9
2022-05-17 21:19:51
B wants to eliminate C or D, meaning C
B wants to eliminate C or D, meaning C
BlizzardWizard
2022-05-17 21:19:51
C or D by rule I. C by rule II.
C or D by rule I. C by rule II.
timblack
2022-05-17 21:20:00
The answer is C. Player B wants to go into the final three right in the middle position in order to be able to win the game. So B wants A to stay in the game to act as a “meat shield” to be taken out later.
The answer is C. Player B wants to go into the final three right in the middle position in order to be able to win the game. So B wants A to stay in the game to act as a “meat shield” to be taken out later.
timblack
2022-05-17 21:20:14
Eliminating either C or D would lead to a B victory, so those are B’s top two choices to vote out, with C taking priority for being earlier in the alphabet.
Eliminating either C or D would lead to a B victory, so those are B’s top two choices to vote out, with C taking priority for being earlier in the alphabet.
timblack
2022-05-17 21:20:23
If neither C nor D gets eliminated, B would prefer to see A go rather than themself. So, B’s priority order for who to see voted out at the final four is C, D, A, B.
If neither C nor D gets eliminated, B would prefer to see A go rather than themself. So, B’s priority order for who to see voted out at the final four is C, D, A, B.
timblack
2022-05-17 21:20:31
Okay, and who does C want to eliminate?
Okay, and who does C want to eliminate?
Trigon
2022-05-17 21:21:00
A
A
OlympusHero
2022-05-17 21:21:00
A
A
CT17
2022-05-17 21:21:00
A$ $
A$ $
BlizzardWizard
2022-05-17 21:21:00
A or B by rule I; A by rule II.
A or B by rule I; A by rule II.
HumanCalculator9
2022-05-17 21:21:00
A
A
vrondoS
2022-05-17 21:21:00
$A$
$A$
joannax
2022-05-17 21:21:00
A or B, preferably A
A or B, preferably A
timblack
2022-05-17 21:21:08
Well, C also wants to be in the middle position going into The Final Three, instead of B. So, C’s preferences are the exact opposite of B’s preferences: C would like to see either A or B out, with a preference for A for being earlier in the alphabet. So, C’s priority order for who to see voted out at the final four is A, B, D, C.
Well, C also wants to be in the middle position going into The Final Three, instead of B. So, C’s preferences are the exact opposite of B’s preferences: C would like to see either A or B out, with a preference for A for being earlier in the alphabet. So, C’s priority order for who to see voted out at the final four is A, B, D, C.
Mathboy345
2022-05-17 21:21:18
ngl timblack is a really entertaining tv show host
ngl timblack is a really entertaining tv show host
timblack
2022-05-17 21:21:23
ngl happy to pass compliments
ngl happy to pass compliments
timblack
2022-05-17 21:21:31
In summary, with four players, A, B, C, D, here are each player’s priorities for who they want out:
A: B, C, D, A
B: C, D, A, B
C: A, B, D, C
D: A, B, C, D
In summary, with four players, A, B, C, D, here are each player’s priorities for who they want out:
A: B, C, D, A
B: C, D, A, B
C: A, B, D, C
D: A, B, C, D
timblack
2022-05-17 21:21:47
So, at The Final Four, just like at The Final Three, the two players at the bottom would like to see the player at the top eliminated. But this time, they don’t quite have a majority on their own.
So, at The Final Four, just like at The Final Three, the two players at the bottom would like to see the player at the top eliminated. But this time, they don’t quite have a majority on their own.
HumanCalculator9
2022-05-17 21:22:23
so A is out and C wins
so A is out and C wins
OlympusHero
2022-05-17 21:22:23
A gets out
A gets out
hellokikki
2022-05-17 21:22:23
A is out!
A is out!
timblack
2022-05-17 21:22:30
It looks like A is in trouble
It looks like A is in trouble
timblack
2022-05-17 21:22:48
Two people want A out, and A and B want different people out.
Two people want A out, and A and B want different people out.
CoolCarsOnTheRun
2022-05-17 21:23:01
A will vote C though to avoid being voted out
A will vote C though to avoid being voted out
vrondoS
2022-05-17 21:23:01
So he votes C
So he votes C
Thu2_2
2022-05-17 21:23:01
actually though, A eventually survives - huge plot twist I belive!
actually though, A eventually survives - huge plot twist I belive!
CT17
2022-05-17 21:23:01
A wins in tiebreakers, so they're not automatically out
A wins in tiebreakers, so they're not automatically out
timblack
2022-05-17 21:23:11
If A and B were to vote for different people, then C and D could indeed pile both of their votes on A and carry the day, knocking A out.
If A and B were to vote for different people, then C and D could indeed pile both of their votes on A and carry the day, knocking A out.
timblack
2022-05-17 21:23:19
But, if A and B were to vote together, then C or D would be unable to get A out. They could still put two votes on A if they wanted to, but the rules say that in the case of a tie, the player later in the alphabet is eliminated, and since A is sitting pretty at the top of the game and at the front of the alphabet, A would be safe.
But, if A and B were to vote together, then C or D would be unable to get A out. They could still put two votes on A if they wanted to, but the rules say that in the case of a tie, the player later in the alphabet is eliminated, and since A is sitting pretty at the top of the game and at the front of the alphabet, A would be safe.
Mathboy345
2022-05-17 21:23:34
what if A and B worked together?
what if A and B worked together?
Amoszhang
2022-05-17 21:23:34
wont A know this and vote C?
wont A know this and vote C?
mathleticguyyy
2022-05-17 21:23:34
B wants A to survive so they work together
B wants A to survive so they work together
timblack
2022-05-17 21:23:39
Neither A nor B really wants to see A eliminated, so they have a big incentive to vote together.
Neither A nor B really wants to see A eliminated, so they have a big incentive to vote together.
timblack
2022-05-17 21:23:48
Let’s think about what A should do. Does A have any way to eliminate B?
Let’s think about what A should do. Does A have any way to eliminate B?
joannax
2022-05-17 21:24:16
no
no
BlizzardWizard
2022-05-17 21:24:16
Nope, because then B won't cooperate.
Nope, because then B won't cooperate.
vrondoS
2022-05-17 21:24:16
no
no
Amoszhang
2022-05-17 21:24:16
no?
no?
TheoZhang666
2022-05-17 21:24:25
no
no
Thu2_2
2022-05-17 21:24:25
Nope, if A vote for B, B would then vote for A and it leads to A being eliminated with 3 votes
Nope, if A vote for B, B would then vote for A and it leads to A being eliminated with 3 votes
timblack
2022-05-17 21:24:28
No, A can’t eliminate B. The only way to save A from elimination is for A and B to vote together, and there is no way that B is voting for themself. So let’s scrap that plan.
No, A can’t eliminate B. The only way to save A from elimination is for A and B to vote together, and there is no way that B is voting for themself. So let’s scrap that plan.
timblack
2022-05-17 21:24:40
A’s top choice for elimination other than B is C. That happens to be B’s top choice, too. So, A can vote for C knowing that B will vote for C as well.
A’s top choice for elimination other than B is C. That happens to be B’s top choice, too. So, A can vote for C knowing that B will vote for C as well.
timblack
2022-05-17 21:24:55
Those two votes for C are enough to take out C (the only way to overcome that would be three votes for A or B, which isn’t possible, or two votes for D, which isn’t going to happen because D isn’t going to vote for themself).
Those two votes for C are enough to take out C (the only way to overcome that would be three votes for A or B, which isn’t possible, or two votes for D, which isn’t going to happen because D isn’t going to vote for themself).
Sigma_Monkey
2022-05-17 21:25:36
so C is out and B wins?
so C is out and B wins?
Mathboy345
2022-05-17 21:25:36
rip C
rip C
timblack
2022-05-17 21:25:45
Let’s take stock of the best and worst position to be in at The Final Four. The players are A, B, C, and D.
A: 3rd place — Survives the Final Four vote, but gets knocked out as the big threat at the Final Three.
B: 1st place — Knocks out a lower player at The Final Four, putting them in the perfect middle position at The Final Three.
C: 4th place — Gets voted out at the Final Four.
2nd place — The person at the bottom slips through both The Final Four and Final Three votes, but stays at the bottom so can’t win the game.
Let’s take stock of the best and worst position to be in at The Final Four. The players are A, B, C, and D.
A: 3rd place — Survives the Final Four vote, but gets knocked out as the big threat at the Final Three.
B: 1st place — Knocks out a lower player at The Final Four, putting them in the perfect middle position at The Final Three.
C: 4th place — Gets voted out at the Final Four.
2nd place — The person at the bottom slips through both The Final Four and Final Three votes, but stays at the bottom so can’t win the game.
timblack
2022-05-17 21:26:00
Hmmm an issue I did not anticipate
Hmmm an issue I did not anticipate
Pendronator
2022-05-17 21:26:10
D :
D :
mathleticguyyy
2022-05-17 21:26:20
indeed
indeed
Mathboy345
2022-05-17 21:26:20
oh no
oh no
timblack
2022-05-17 21:26:24
Now that we know the best and worst positions to be in at Four, we know the players’ motivations, and can turn back to the main problem of what happens in the first episode with five players in the game. Everything we did above was important — actually, it’s incredibly important; we can’t even start thinking about how the players vote with five players without understanding where players want to be after that vote.
Now that we know the best and worst positions to be in at Four, we know the players’ motivations, and can turn back to the main problem of what happens in the first episode with five players in the game. Everything we did above was important — actually, it’s incredibly important; we can’t even start thinking about how the players vote with five players without understanding where players want to be after that vote.
Sigma_Monkey
2022-05-17 21:26:37
i meant thats how i would feel getting 2nd
i meant thats how i would feel getting 2nd
timblack
2022-05-17 21:26:49
The game starts with Assaf, Ben, Charlotte, Dan, and Emily. Let’s think about each of them and where they want to end up.
The game starts with Assaf, Ben, Charlotte, Dan, and Emily. Let’s think about each of them and where they want to end up.
Mathboy345
2022-05-17 21:26:52
so we were working backwards the entire time
so we were working backwards the entire time
timblack
2022-05-17 21:26:57
Assaf is at the top of the game (at the front of the alphabet), and will remain at the top as long as he’s not voted out. He wants to vote out someone as early in the alphabet as possible other than himself. Priority order for who to eliminate: Ben, Charlotte, Dan, Emily, Assaf.
Assaf is at the top of the game (at the front of the alphabet), and will remain at the top as long as he’s not voted out. He wants to vote out someone as early in the alphabet as possible other than himself. Priority order for who to eliminate: Ben, Charlotte, Dan, Emily, Assaf.
timblack
2022-05-17 21:27:11
Ben can try to vote out the person above him (Assaf) or someone below him (Charlotte, Dan, or Emily). If he votes out Assaf, he gets promoted to Aen. If he votes out someone below him, he stays Ben. Would he rather become Aen or stay Ben at The Final Four?
Ben can try to vote out the person above him (Assaf) or someone below him (Charlotte, Dan, or Emily). If he votes out Assaf, he gets promoted to Aen. If he votes out someone below him, he stays Ben. Would he rather become Aen or stay Ben at The Final Four?
Trigon
2022-05-17 21:27:20
The suspense is palpable
The suspense is palpable
Pendronator
2022-05-17 21:27:20
It's evolving, just backwards
It's evolving, just backwards
Thu2_2
2022-05-17 21:27:20
the first episode with 5 players is my fav one!
the first episode with 5 players is my fav one!
HumanCalculator9
2022-05-17 21:27:44
Ben
Ben
Sigma_Monkey
2022-05-17 21:27:44
BEn
BEn
vrondoS
2022-05-17 21:27:44
Ben
Ben
Trigon
2022-05-17 21:27:44
Stay Ben
Stay Ben
timblack
2022-05-17 21:27:50
Right, Ben wants to stay Ben. We know that whoever is B at the Final Four will win the whole game. So, his priority order for who to eliminate: Charlotte, Dan, Emily, Assaf, Ben.
Right, Ben wants to stay Ben. We know that whoever is B at the Final Four will win the whole game. So, his priority order for who to eliminate: Charlotte, Dan, Emily, Assaf, Ben.
timblack
2022-05-17 21:28:00
Charlotte can try to eliminate one of the people above her (Assaf or Ben) in order to become Bharlotte, or can try to eliminate one of the people below her (Dan or Emily) to stay Charlotte. Would she prefer to be Bharlotte or Charlotte?
Charlotte can try to eliminate one of the people above her (Assaf or Ben) in order to become Bharlotte, or can try to eliminate one of the people below her (Dan or Emily) to stay Charlotte. Would she prefer to be Bharlotte or Charlotte?
TheoZhang666
2022-05-17 21:28:37
Bharlotte
Bharlotte
boing123
2022-05-17 21:28:37
Bharlotte
Bharlotte
mythicalcheese31
2022-05-17 21:28:37
Bharlotte
Bharlotte
Mathboy345
2022-05-17 21:28:37
Bharlotte because it sounds cooler and then she will win
Bharlotte because it sounds cooler and then she will win
Sigma_Monkey
2022-05-17 21:28:37
Bharlotte
Bharlotte
Trigon
2022-05-17 21:28:37
Become Bharlotte
Become Bharlotte
HumanCalculator9
2022-05-17 21:28:37
Bharlotte
Bharlotte
vrondoS
2022-05-17 21:28:37
Bharlotte
Bharlotte
timblack
2022-05-17 21:28:41
Bharlotte! Again, whoever is B at the Final Four will win the game! Her priority order for who to eliminate: Assaf, Ben, Dan, Emily, Charlotte.
Bharlotte! Again, whoever is B at the Final Four will win the game! Her priority order for who to eliminate: Assaf, Ben, Dan, Emily, Charlotte.
timblack
2022-05-17 21:28:55
Dan can try to take out Assaf, Ben or Charlotte to turn into Can, or can try to take out Emily to stay Dan. Which would he choose, given the choice?
Dan can try to take out Assaf, Ben or Charlotte to turn into Can, or can try to take out Emily to stay Dan. Which would he choose, given the choice?
vrondoS
2022-05-17 21:29:38
Dan
Dan
mathleticguyyy
2022-05-17 21:29:38
Dan
Dan
BlizzardWizard
2022-05-17 21:29:38
Stay Dan
Stay Dan
mathleticguyyy
2022-05-17 21:29:38
Dan can't win
Dan can't win
Amoszhang
2022-05-17 21:29:38
Dan
Dan
TheoZhang666
2022-05-17 21:29:38
dan
dan
Pendronator
2022-05-17 21:29:38
Stay Dan
Stay Dan
Sigma_Monkey
2022-05-17 21:29:38
Dan, but its still not a win
Dan, but its still not a win
timblack
2022-05-17 21:29:41
He’ll stay Dan if possible. Having a C name at the Final Four is the worst place to be, because it means getting vote out in fourth place. So Dan’s priority order for who to eliminate: Emily, Assaf, Ben, Charlotte, Dan.
He’ll stay Dan if possible. Having a C name at the Final Four is the worst place to be, because it means getting vote out in fourth place. So Dan’s priority order for who to eliminate: Emily, Assaf, Ben, Charlotte, Dan.
timblack
2022-05-17 21:29:57
Emily is at the bottom and will stay at the bottom unless voted out, so she will just focus on voting out someone early in the alphabet. Priority order: Assaf, Ben, Charlotte, Dan, Emily.
Emily is at the bottom and will stay at the bottom unless voted out, so she will just focus on voting out someone early in the alphabet. Priority order: Assaf, Ben, Charlotte, Dan, Emily.
timblack
2022-05-17 21:30:09
In summary, with five players, A, B, C, D, E, here are each player’s priorities for who they want out:
A: B, C, D, E, A
B: C, D, E, A, B
C: A, B, D, E, C
D: E, A, B, C, D
E: A, B, C, D, E
In summary, with five players, A, B, C, D, E, here are each player’s priorities for who they want out:
A: B, C, D, E, A
B: C, D, E, A, B
C: A, B, D, E, C
D: E, A, B, C, D
E: A, B, C, D, E
timblack
2022-05-17 21:30:28
Now that we know who wants who out, we can move onto the next phase of the problem: voting strategy.
Now that we know who wants who out, we can move onto the next phase of the problem: voting strategy.
timblack
2022-05-17 21:30:42
Before we get too deep into the analysis, let’s try to get a general sense of what’s going on.
Before we get too deep into the analysis, let’s try to get a general sense of what’s going on.
timblack
2022-05-17 21:30:47
Do you see anybody who seems to be in a lot of danger? Maybe someone who appears early in a majority of those priority lists?
Do you see anybody who seems to be in a lot of danger? Maybe someone who appears early in a majority of those priority lists?
timblack
2022-05-17 21:31:09
Lots of people weighed in before I even asked!
Lots of people weighed in before I even asked!
OlympusHero
2022-05-17 21:31:15
A is out
A is out
Mathboy345
2022-05-17 21:31:15
A gets kicked out if no one works together
A gets kicked out if no one works together
HumanCalculator9
2022-05-17 21:31:15
A still gets out first lol
A still gets out first lol
Sigma_Monkey
2022-05-17 21:31:15
A is out!
A is out!
timblack
2022-05-17 21:31:29
Some more responses:
Some more responses:
CoolCarsOnTheRun
2022-05-17 21:31:31
A
A
joannax
2022-05-17 21:31:31
A
A
mathleticguyyy
2022-05-17 21:31:31
so A has to act fast
so A has to act fast
Amoszhang
2022-05-17 21:31:31
Assaf needs to make some strategical decisions
Assaf needs to make some strategical decisions
timblack
2022-05-17 21:31:37
Yeah, I agree that Assaf looks to be in trouble. Both Charlotte and Emily want Assaf out as a top priority, and Dan wants Assaf out as a second choice. We can almost think of Charlotte, Dan, and Emily as an alliance, all working together. They all really want Assaf out; the only hiccup is that Dan wants Emily out even more.
Yeah, I agree that Assaf looks to be in trouble. Both Charlotte and Emily want Assaf out as a top priority, and Dan wants Assaf out as a second choice. We can almost think of Charlotte, Dan, and Emily as an alliance, all working together. They all really want Assaf out; the only hiccup is that Dan wants Emily out even more.
timblack
2022-05-17 21:32:20
I’m going to get at the parts of the problem a little bit out of order.
I’m going to get at the parts of the problem a little bit out of order.
timblack
2022-05-17 21:32:26
Part (b) of the problem says, “Suppose the game show begins with an immunity challenge. The winner of the challenge cannot be eliminated in the first episode; nobody is allowed to vote against them.”
Part (b) of the problem says, “Suppose the game show begins with an immunity challenge. The winner of the challenge cannot be eliminated in the first episode; nobody is allowed to vote against them.”
timblack
2022-05-17 21:32:34
I want to start with the question, Who gets voted out if Emily wins immunity?
I want to start with the question, Who gets voted out if Emily wins immunity?
timblack
2022-05-17 21:32:51
If voting out Emily is off the table, we can delete E from players’ priority lists:
A: B, C, D, A
B: C, D, A, B
C: A, B, D, C
D: A, B, C, D
E: A, B, C, D
If voting out Emily is off the table, we can delete E from players’ priority lists:
A: B, C, D, A
B: C, D, A, B
C: A, B, D, C
D: A, B, C, D
E: A, B, C, D
timblack
2022-05-17 21:33:02
With that, there is a clear majority of players that want Assaf out. Can we conclude that Assaf gets eliminated?
With that, there is a clear majority of players that want Assaf out. Can we conclude that Assaf gets eliminated?
BlizzardWizard
2022-05-17 21:33:31
It looks like A may be in danger again. Who can A cooperate with this time to survive?
It looks like A may be in danger again. Who can A cooperate with this time to survive?
mythicalcheese31
2022-05-17 21:33:31
A
A
OlympusHero
2022-05-17 21:33:31
A then
A then
Trigon
2022-05-17 21:33:31
Assaf gets voted out because he's top priority for 3 people
Assaf gets voted out because he's top priority for 3 people
TheoZhang666
2022-05-17 21:33:31
yes
yes
mythicalcheese31
2022-05-17 21:33:31
ye, A has no counter
ye, A has no counter
vrondoS
2022-05-17 21:33:31
yes
yes
timblack
2022-05-17 21:33:46
Yes, it turns out that Charlotte, Dan, and Emily will all vote for Assaf, so Assaf gets knocked out. But we should be careful about our logic to conclude that this is what actually happens. We’ll work backwards.
Yes, it turns out that Charlotte, Dan, and Emily will all vote for Assaf, so Assaf gets knocked out. But we should be careful about our logic to conclude that this is what actually happens. We’ll work backwards.
timblack
2022-05-17 21:33:56
Emily votes last. If Emily sees that there are already two votes for Assaf, then she will vote for Emily as well, securing Assaf’s elimination.
Emily votes last. If Emily sees that there are already two votes for Assaf, then she will vote for Emily as well, securing Assaf’s elimination.
timblack
2022-05-17 21:34:06
Before that, Dan votes. If Dan sees that there is at least one vote already for Assaf, then Dan will be the second vote, knowing that Emily will be the third, conclusive vote.
Before that, Dan votes. If Dan sees that there is at least one vote already for Assaf, then Dan will be the second vote, knowing that Emily will be the third, conclusive vote.
timblack
2022-05-17 21:34:19
Before that, Charlotte votes. We can be confident that Charlotte will provide the first vote for Assaf, because she knows that if she votes for Assaf, then Dan will see that vote for Assaf and do his part to make sure Assaf is eliminated, then Emily will see those two votes for Assaf and do her part as well.
Before that, Charlotte votes. We can be confident that Charlotte will provide the first vote for Assaf, because she knows that if she votes for Assaf, then Dan will see that vote for Assaf and do his part to make sure Assaf is eliminated, then Emily will see those two votes for Assaf and do her part as well.
timblack
2022-05-17 21:34:38
So, if Emily has immunity, Charlotte, Dan, and Emily really do all vote for Assaf, and Assaf is eliminated.
So, if Emily has immunity, Charlotte, Dan, and Emily really do all vote for Assaf, and Assaf is eliminated.
Sigma_Monkey
2022-05-17 21:34:56
but emily does not have immunity
but emily does not have immunity
timblack
2022-05-17 21:34:59
Let’s go back to part (a) of the problem.
Let’s go back to part (a) of the problem.
timblack
2022-05-17 21:35:05
If there is no immunity, who gets eliminated in the first episode?
If there is no immunity, who gets eliminated in the first episode?
TheoZhang666
2022-05-17 21:35:20
but won't the players know that if they wont assaf then charlotte wins?
but won't the players know that if they wont assaf then charlotte wins?
timblack
2022-05-17 21:35:41
They will! They will have to balance their priorities and see if they can form an alliance to make it happen
They will! They will have to balance their priorities and see if they can form an alliance to make it happen
timblack
2022-05-17 21:35:55
That's why the show has stayed on the air all these centuries!
That's why the show has stayed on the air all these centuries!
timblack
2022-05-17 21:36:05
As a reminder, with five players, A, B, C, D, E, here are each player’s priorities for who they want out:
A: B, C, D, E, A
B: C, D, E, A, B
C: A, B, D, E, C
D: E, A, B, C, D
E: A, B, C, D, E
As a reminder, with five players, A, B, C, D, E, here are each player’s priorities for who they want out:
A: B, C, D, E, A
B: C, D, E, A, B
C: A, B, D, E, C
D: E, A, B, C, D
E: A, B, C, D, E
timblack
2022-05-17 21:36:12
The alliance consisting of Charlotte, Dan, and Emily appears to have a lot of power. But it looks to me like Dan has the most power of all: He can always go along with the alliance and vote out A, but he also has the option to defect if there’s an opportunity to vote out Emily instead.
The alliance consisting of Charlotte, Dan, and Emily appears to have a lot of power. But it looks to me like Dan has the most power of all: He can always go along with the alliance and vote out A, but he also has the option to defect if there’s an opportunity to vote out Emily instead.
timblack
2022-05-17 21:36:31
Here’s some tempting logic, but it’s actually wrong:
Here’s some tempting logic, but it’s actually wrong:
timblack
2022-05-17 21:36:37
The player that is eliminated must be either Assaf or Emily: If Dan has the opportunity to get out Emily, he will do so. If eliminating Emily is not a possibility, his top choice becomes Assaf, so at that point there are three people who want Assaf out the most, and the three of them vote together to do so. Dan never has to reach down his priority list any further than that, so either Assaf or Emily is eliminated.
The player that is eliminated must be either Assaf or Emily: If Dan has the opportunity to get out Emily, he will do so. If eliminating Emily is not a possibility, his top choice becomes Assaf, so at that point there are three people who want Assaf out the most, and the three of them vote together to do so. Dan never has to reach down his priority list any further than that, so either Assaf or Emily is eliminated.
timblack
2022-05-17 21:36:47
What’s the problem with this logic?
What’s the problem with this logic?
TheoZhang666
2022-05-17 21:37:11
backstabbing?
backstabbing?
timblack
2022-05-17 21:37:35
It’s pretty subtle.
It’s pretty subtle.
Trigon
2022-05-17 21:37:40
Charlotte has already voted so there is no longer a team of 3 that want Assaf out
Charlotte has already voted so there is no longer a team of 3 that want Assaf out
mathleticguyyy
2022-05-17 21:38:21
Yeah Dan can get out
Yeah Dan can get out
Sigma_Monkey
2022-05-17 21:38:21
wow i never realized how complicated this was when i wrote my response
wow i never realized how complicated this was when i wrote my response
Pendronator
2022-05-17 21:38:21
Sneaky
Sneaky
timblack
2022-05-17 21:38:23
If Dan had to vote before Charlotte, then this logic would be okay: He could either vote for Emily if it would be the deciding vote to get her out, and otherwise, he could put his vote on Assaf with the knowledge that Charlotte and Emily will be all too happy to provide the two additional votes to get Assaf out.
If Dan had to vote before Charlotte, then this logic would be okay: He could either vote for Emily if it would be the deciding vote to get her out, and otherwise, he could put his vote on Assaf with the knowledge that Charlotte and Emily will be all too happy to provide the two additional votes to get Assaf out.
OlympusHero
2022-05-17 21:38:45
This is insane
This is insane
timblack
2022-05-17 21:38:52
Great TV
Great TV
TheoZhang666
2022-05-17 21:39:07
amazing
amazing
timblack
2022-05-17 21:39:10
The problem is that Dan votes after Charlotte does — so Dan will have a chance to defect from the alliance after Charlotte’s vote is locked in.
The problem is that Dan votes after Charlotte does — so Dan will have a chance to defect from the alliance after Charlotte’s vote is locked in.
timblack
2022-05-17 21:39:28
While Charlotte would be happy to vote for Assaf if Dan were guaranteed to do so too, Charlotte’s not just automatically going to vote for Assaf if that’s not who is going to end up getting eliminated.
While Charlotte would be happy to vote for Assaf if Dan were guaranteed to do so too, Charlotte’s not just automatically going to vote for Assaf if that’s not who is going to end up getting eliminated.
timblack
2022-05-17 21:39:43
Charlotte isn’t particularly interested in seeing Emily eliminated — she’d really like to get out Assaf, but she’d still prefer eliminating Ben or even Dan rather than Emily.
Charlotte isn’t particularly interested in seeing Emily eliminated — she’d really like to get out Assaf, but she’d still prefer eliminating Ben or even Dan rather than Emily.
timblack
2022-05-17 21:39:57
So, if Charlotte can’t get out Assaf, she’s open to voting some other way to block Dan from taking out Emily.
So, if Charlotte can’t get out Assaf, she’s open to voting some other way to block Dan from taking out Emily.
Thu2_2
2022-05-17 21:40:07
this deserves to be the "show of the year"
this deserves to be the "show of the year"
timblack
2022-05-17 21:40:16
Yes! Why did it stop winning Emmys?!?
Yes! Why did it stop winning Emmys?!?
timblack
2022-05-17 21:40:26
But if Charlotte doesn’t vote for Assaf because she can’t trust Dan, then Dan may no longer have the option to eliminate Assaf. At the same time, Charlotte’s vote can also interfere with getting Emily out, too. So Dan may just be out of luck.
But if Charlotte doesn’t vote for Assaf because she can’t trust Dan, then Dan may no longer have the option to eliminate Assaf. At the same time, Charlotte’s vote can also interfere with getting Emily out, too. So Dan may just be out of luck.
timblack
2022-05-17 21:40:51
This is great news for Assaf and Ben. The two of them seemed to be in the minority against the supposed alliance of Charlotte, Dan, and Emily. But it appears that there is a crack in the alliance that they may be able to exploit.
This is great news for Assaf and Ben. The two of them seemed to be in the minority against the supposed alliance of Charlotte, Dan, and Emily. But it appears that there is a crack in the alliance that they may be able to exploit.
timblack
2022-05-17 21:41:28
Any ideas who they should team up on?
Any ideas who they should team up on?
Amoszhang
2022-05-17 21:41:48
So A B and D vote for E right?
So A B and D vote for E right?
vrondoS
2022-05-17 21:41:48
C
C
CoolCarsOnTheRun
2022-05-17 21:41:48
E
E
BlizzardWizard
2022-05-17 21:41:48
Emily or Dan, but ideally Dan by rule II.
Emily or Dan, but ideally Dan by rule II.
vrondoS
2022-05-17 21:41:48
E
E
Thu2_2
2022-05-17 21:41:48
C
C
Trigon
2022-05-17 21:41:48
Dan!! The drama!!
Dan!! The drama!!
timblack
2022-05-17 21:42:00
Let's consider the options
Let's consider the options
timblack
2022-05-17 21:42:01
One option for Assaf and Ben is to vote for Emily. That would make Dan very happy; with Dan’s vote, that guarantees Emily’s elimination.
One option for Assaf and Ben is to vote for Emily. That would make Dan very happy; with Dan’s vote, that guarantees Emily’s elimination.
timblack
2022-05-17 21:42:19
But maybe they can do better. They’d both rather have Charlotte or Dan out rather than Emily (and Assaf would like Ben out most of all). What happens if they decide to go for someone else and neither of them votes for Emily? Who ends up voted out?
But maybe they can do better. They’d both rather have Charlotte or Dan out rather than Emily (and Assaf would like Ben out most of all). What happens if they decide to go for someone else and neither of them votes for Emily? Who ends up voted out?
timblack
2022-05-17 21:43:20
Remember they are counting on Dan to cause chaos by possibly voting for Emily
Remember they are counting on Dan to cause chaos by possibly voting for Emily
vrondoS
2022-05-17 21:43:56
C
C
Amoszhang
2022-05-17 21:43:56
ohhh dan gets out because of C
ohhh dan gets out because of C
TheoZhang666
2022-05-17 21:43:56
Charlotte
Charlotte
Amoszhang
2022-05-17 21:43:56
I messed up
I messed up
vrondoS
2022-05-17 21:43:56
C because of alphabeticity
C because of alphabeticity
timblack
2022-05-17 21:44:05
Lots of people said Charlotte, but...
Lots of people said Charlotte, but...
Trigon
2022-05-17 21:44:11
If they vote for Charlotte, Dan can't betray the alliance anymore so they all vote for Assaf
If they vote for Charlotte, Dan can't betray the alliance anymore so they all vote for Assaf
Mathboy345
2022-05-17 21:44:27
Emily
Emily
timblack
2022-05-17 21:44:38
Assaf would get voted out in that case: Without there alreadybeing one vote on Emily, Dan has to give up on voting out Emily. Charlotte knows this and knows the alliance will stick together, so Charlotte, Dan, and Emily vote out Assaf.
Assaf would get voted out in that case: Without there alreadybeing one vote on Emily, Dan has to give up on voting out Emily. Charlotte knows this and knows the alliance will stick together, so Charlotte, Dan, and Emily vote out Assaf.
timblack
2022-05-17 21:45:08
It seems like Assaf and Ben had better just vote for Emily and get Emily out. Are there any other options?
It seems like Assaf and Ben had better just vote for Emily and get Emily out. Are there any other options?
timblack
2022-05-17 21:45:46
timblack
2022-05-17 21:45:59
Bad news bears for Assaf and Ben?
Bad news bears for Assaf and Ben?
timblack
2022-05-17 21:46:18
Singleton: Bad News Bears was my favorite season, incidentally
Singleton: Bad News Bears was my favorite season, incidentally
timblack
2022-05-17 21:46:37
Yeah, there’s one more possibility: We’ve considered Assaf and Ben putting zero votes on Emily or putting two votes on Emily, but by process of elimination they could also put just one of their two votes on Emily. They could put one vote on Emily and one vote on someone else.
Yeah, there’s one more possibility: We’ve considered Assaf and Ben putting zero votes on Emily or putting two votes on Emily, but by process of elimination they could also put just one of their two votes on Emily. They could put one vote on Emily and one vote on someone else.
timblack
2022-05-17 21:47:00
This... doesn’t feel like a good option. Note that Assaf can’t really get Ben out now, and Ben isn’t going to let Assaf get voted out. Other than that, Assaf and Ben have the exact same preferences for who should go (Charlotte then Dan then Emily). So, one would think that Assaf and Ben should just figure out who the best person they can eliminate is, and both vote for that person.
This... doesn’t feel like a good option. Note that Assaf can’t really get Ben out now, and Ben isn’t going to let Assaf get voted out. Other than that, Assaf and Ben have the exact same preferences for who should go (Charlotte then Dan then Emily). So, one would think that Assaf and Ben should just figure out who the best person they can eliminate is, and both vote for that person.
timblack
2022-05-17 21:47:24
But actually there is a reason for them to split their votes. What is the intuition for why one of them might vote for Emily, and the other not?
But actually there is a reason for them to split their votes. What is the intuition for why one of them might vote for Emily, and the other not?
timblack
2022-05-17 21:47:49
Some suspense from a minute ago:
Some suspense from a minute ago:
alleycat
2022-05-17 21:47:52
*the suspense*
*the suspense*
alleycat
2022-05-17 21:47:52
im like sooo nervous about this even tho its all already over lmao
im like sooo nervous about this even tho its all already over lmao
russellk
2022-05-17 21:47:52
thats crazy
thats crazy
timblack
2022-05-17 21:48:11
Why they should split their votes:
Why they should split their votes:
Thu2_2
2022-05-17 21:48:35
A can vote for D while B vote for E
A can vote for D while B vote for E
Thu2_2
2022-05-17 21:48:35
And we shall see drama among C, D and E
And we shall see drama among C, D and E
Sigma_Monkey
2022-05-17 21:48:35
to split up the alliance??
to split up the alliance??
Thu2_2
2022-05-17 21:48:35
E is at risk of being eliminated, and so E betray the alliance
E is at risk of being eliminated, and so E betray the alliance
Pendronator
2022-05-17 21:48:41
I heard they're bringing in Fred and Xander for the next season
I heard they're bringing in Fred and Xander for the next season
joannax
2022-05-17 21:48:51
so Charlotte wouldn't trust Dan but can't get Assaf out and votes Dan
so Charlotte wouldn't trust Dan but can't get Assaf out and votes Dan
Trigon
2022-05-17 21:48:51
Dan still has the possibility to defect while they also get one vote on the person they *actually* want to get voted out
Dan still has the possibility to defect while they also get one vote on the person they *actually* want to get voted out
timblack
2022-05-17 21:49:12
If there’s one vote on Emily, that raises the possibility that Dan could vote Emily out, which could cause Charlotte to give up on getting out Assaf and get her to work with Assaf and Ben instead.
If there’s one vote on Emily, that raises the possibility that Dan could vote Emily out, which could cause Charlotte to give up on getting out Assaf and get her to work with Assaf and Ben instead.
Thu2_2
2022-05-17 21:49:25
omg i want the next season asap
omg i want the next season asap
Thu2_2
2022-05-17 21:49:31
but then my mind will potentially explode as a viewer who love plot twist and theory
but then my mind will potentially explode as a viewer who love plot twist and theory
timblack
2022-05-17 21:49:50
Let’s consider the cases where exactly one out of Assaf or Ben votes for Emily, and the other votes from some player X who is not Emily.
Let’s consider the cases where exactly one out of Assaf or Ben votes for Emily, and the other votes from some player X who is not Emily.
timblack
2022-05-17 21:50:09
If Charlotte and Emily both vote for X as well, then that’s three votes for X, and X gets eliminated.
If Charlotte and Emily both vote for X as well, then that’s three votes for X, and X gets eliminated.
timblack
2022-05-17 21:50:28
If Charlotte doesn’t vote for X, who gets voted out?
If Charlotte doesn’t vote for X, who gets voted out?
alleycat
2022-05-17 21:50:39
XANDER
XANDER
timblack
2022-05-17 21:50:47
Oops sorry passed that at the wrong time
Oops sorry passed that at the wrong time
Sigma_Monkey
2022-05-17 21:51:10
emily
emily
joannax
2022-05-17 21:51:10
Emily
Emily
timblack
2022-05-17 21:51:17
Right, Emily gets voted out. In particular, Dan can put his second vote on Emily. Since Emily is last alphabetically, the only way to overcome two votes for Emily would be three votes for someone else. But since Charlotte didn’t vote for X, that’s not going to happen.
Right, Emily gets voted out. In particular, Dan can put his second vote on Emily. Since Emily is last alphabetically, the only way to overcome two votes for Emily would be three votes for someone else. But since Charlotte didn’t vote for X, that’s not going to happen.
timblack
2022-05-17 21:52:08
There are four possibilities:
There are four possibilities:
timblack
2022-05-17 21:52:14
X = Assaf: Charlotte and Emily can simply both vote for Assaf to get their top choice eliminated.
X = Assaf: Charlotte and Emily can simply both vote for Assaf to get their top choice eliminated.
timblack
2022-05-17 21:52:29
X = Ben: This would result in Ben getting voted out, but there’s no way Ben is letting this happen. Ben’s not voting for himself, and if Assaf were to vote for Ben, then Ben would just vote for not Emily which would result in Assaf getting voted out.
X = Ben: This would result in Ben getting voted out, but there’s no way Ben is letting this happen. Ben’s not voting for himself, and if Assaf were to vote for Ben, then Ben would just vote for not Emily which would result in Assaf getting voted out.
timblack
2022-05-17 21:52:50
X = Charlotte: Who gets voted out in this case?
X = Charlotte: Who gets voted out in this case?
timblack
2022-05-17 21:53:52
Lots of different answers in the chat!
Lots of different answers in the chat!
Sigma_Monkey
2022-05-17 21:54:02
Emily
Emily
HJHJHJHJH
2022-05-17 21:54:02
emily
emily
BlizzardWizard
2022-05-17 21:54:02
Emily gets voted out
Emily gets voted out
Thu2_2
2022-05-17 21:54:02
actually, it's E
actually, it's E
timblack
2022-05-17 21:54:05
Emily gets voted out in this case. Charlotte’s not going to vote for herself. And as we discussed above, no matter who Charlotte votes for other than herself, Dan can put a second vote on Emily, and that is enough to ensure Emily’s elimination.
Emily gets voted out in this case. Charlotte’s not going to vote for herself. And as we discussed above, no matter who Charlotte votes for other than herself, Dan can put a second vote on Emily, and that is enough to ensure Emily’s elimination.
timblack
2022-05-17 21:54:30
X = Dan: Charlotte is in a bit of a bind. If Charlotte doesn’t vote for Dan, we saw above that Emily gets eliminated. If Charlotte does vote for Dan, who gets voted out?
X = Dan: Charlotte is in a bit of a bind. If Charlotte doesn’t vote for Dan, we saw above that Emily gets eliminated. If Charlotte does vote for Dan, who gets voted out?
Alex-131
2022-05-17 21:55:08
Dan
Dan
BlizzardWizard
2022-05-17 21:55:08
Dan gets voted out.
Dan gets voted out.
joannax
2022-05-17 21:55:08
Dan
Dan
Mathlete12345654
2022-05-17 21:55:08
Dan?
Dan?
Fisicist
2022-05-17 21:55:08
dan
dan
timblack
2022-05-17 21:55:13
Yes, Dan gets voted out! Here’s why:
Yes, Dan gets voted out! Here’s why:
timblack
2022-05-17 21:55:18
When it’s Dan’s turn to vote, he’s sweating a bit because there are already two votes on him. He can’t save himself by piling votes on Assaf, Ben, or Charlotte, because it would take three votes against one of them to get that person out, and there are only two people still to vote.
When it’s Dan’s turn to vote, he’s sweating a bit because there are already two votes on him. He can’t save himself by piling votes on Assaf, Ben, or Charlotte, because it would take three votes against one of them to get that person out, and there are only two people still to vote.
Thu2_2
2022-05-17 21:55:25
"dun dun dun"
"dun dun dun"
timblack
2022-05-17 21:55:32
The other option is to try to get Emily out. But regardless of whether Dan puts a second vote on Emily, Emily can just put a third vote on Dan to avoid her own elimination and send Dan packing instead.
The other option is to try to get Emily out. But regardless of whether Dan puts a second vote on Emily, Emily can just put a third vote on Dan to avoid her own elimination and send Dan packing instead.
timblack
2022-05-17 21:55:55
So, if X = Dan, then Dan gets voted out.
So, if X = Dan, then Dan gets voted out.
Trigon
2022-05-17 21:56:13
He should vote for himself and go out in style
He should vote for himself and go out in style
z5r6x7v8
2022-05-17 21:56:13
dan actually bribes the producer to create a plot twist and let him survive
dan actually bribes the producer to create a plot twist and let him survive
mathleticguyyy
2022-05-17 21:56:13
What if Dan renames to Frank at that moment and then votes?
What if Dan renames to Frank at that moment and then votes?
timblack
2022-05-17 21:56:26
Of all the options above, both Assaf and Ben prefer the plan that gets Dan out. So, Assaf can vote for either Dan or Emily (it doesn’t matter which), and Ben will vote for the other one. Then, Charlotte for vote for Dan, then Dan will panic and vote for whoever, then if it’s not already all wrapped up, Emily will vote for Dan to send him packing.
Of all the options above, both Assaf and Ben prefer the plan that gets Dan out. So, Assaf can vote for either Dan or Emily (it doesn’t matter which), and Ben will vote for the other one. Then, Charlotte for vote for Dan, then Dan will panic and vote for whoever, then if it’s not already all wrapped up, Emily will vote for Dan to send him packing.
timblack
2022-05-17 21:56:39
Answer: Dan is the first to be voted out.
Answer: Dan is the first to be voted out.
duckguni
2022-05-17 21:56:57
oof
oof
timblack
2022-05-17 21:57:00
This is an example of strategic voting! It’s to Assaf and Ben’s advantage for one of them to vote for Emily, even though in the end Emily isn’t the one that either of them is trying to get out.
This is an example of strategic voting! It’s to Assaf and Ben’s advantage for one of them to vote for Emily, even though in the end Emily isn’t the one that either of them is trying to get out.
timblack
2022-05-17 21:57:07
I think this is pretty strange!
I think this is pretty strange!
WYoX1234
2022-05-17 21:57:17
sad
sad
WYoX1234
2022-05-17 21:57:17
0-0
0-0
alleycat
2022-05-17 21:57:22
YES
YES
russellk
2022-05-17 21:57:25
sad
sad
timblack
2022-05-17 21:57:33
Okay, onto the next question: Who wins the game?
Okay, onto the next question: Who wins the game?
mythicalcheese31
2022-05-17 21:57:52
and ben wins
and ben wins
Trigon
2022-05-17 21:57:52
Ben wins
Ben wins
Sigma_Monkey
2022-05-17 21:57:52
Ben
Ben
CoolCarsOnTheRun
2022-05-17 21:57:52
bEN
bEN
boing123
2022-05-17 21:57:52
Ben
Ben
CoolCarsOnTheRun
2022-05-17 21:57:52
Ben**
Ben**
mathleticguyyy
2022-05-17 21:57:55
Recursion!
Recursion!
timblack
2022-05-17 21:58:02
We saw that at The Final Four, whoever was second alphabetically wins the game. Ben starts the game in the second position alphabetically, and after Dan’s elimination, is still second alphabetically at The Final Four. So, Ben wins the whole game!
We saw that at The Final Four, whoever was second alphabetically wins the game. Ben starts the game in the second position alphabetically, and after Dan’s elimination, is still second alphabetically at The Final Four. So, Ben wins the whole game!
timblack
2022-05-17 21:58:32
Let’s move on to part b. of the problem:
Let’s move on to part b. of the problem:
timblack
2022-05-17 21:58:39
Part b. Suppose the game show begins with an immunity challenge. The winner of the challenge cannot be eliminated in the first episode; nobody is allowed to vote against them.
Part b. Suppose the game show begins with an immunity challenge. The winner of the challenge cannot be eliminated in the first episode; nobody is allowed to vote against them.
timblack
2022-05-17 21:58:50
If Dan wins the immunity challenge, who gets voted out? What if Emily wins instead? What if Assaf wins?
If Dan wins the immunity challenge, who gets voted out? What if Emily wins instead? What if Assaf wins?
timblack
2022-05-17 21:58:56
We already saw that if Emily wins immunity, then Assaf is voted out.
We already saw that if Emily wins immunity, then Assaf is voted out.
timblack
2022-05-17 21:59:33
Wait, can we just talk about that for a second?
Wait, can we just talk about that for a second?
timblack
2022-05-17 21:59:40
If there’s no immunity, then as we saw, Dan gets voted out.
If there’s no immunity, then as we saw, Dan gets voted out.
timblack
2022-05-17 21:59:48
So if there is an immunity challenge but Dan doesn’t win it, that shouldn’t change anything, right? Dan should still be voted out, right?
So if there is an immunity challenge but Dan doesn’t win it, that shouldn’t change anything, right? Dan should still be voted out, right?
timblack
2022-05-17 21:59:54
timblack
2022-05-17 22:00:09
Nope, it turns out it doesn’t work that way. It seems counterintuitive, but the outcome of the vote can change even if Dan loses the immunity challenge.
Nope, it turns out it doesn’t work that way. It seems counterintuitive, but the outcome of the vote can change even if Dan loses the immunity challenge.
timblack
2022-05-17 22:00:21
The more accurate intuition is that Charlotte, Dan, and Emily formed a pretty good alliance, and the one crack in the alliance was Dan wanting to get Emily out.
The more accurate intuition is that Charlotte, Dan, and Emily formed a pretty good alliance, and the one crack in the alliance was Dan wanting to get Emily out.
timblack
2022-05-17 22:00:33
But if that option is off the table, Charlotte doesn’t have to worry about Dan defecting, and they can all just work together to vote out Assaf.
But if that option is off the table, Charlotte doesn’t have to worry about Dan defecting, and they can all just work together to vote out Assaf.
WilliamSantoso
2022-05-17 22:00:48
Wait. Does the winner of the immunity challenge still get to vote?
Wait. Does the winner of the immunity challenge still get to vote?
timblack
2022-05-17 22:00:57
Yes, they still vote; they just can't be voted for
Yes, they still vote; they just can't be voted for
timblack
2022-05-17 22:01:06
You might notice that even though Emily didn’t need to win the immunity challenge to be safe from elimination, Emily still gets something out of having immunity because when she has immunity, her first choice gets voted out. Perhaps the person with immunity ends up with just a bit more power.
You might notice that even though Emily didn’t need to win the immunity challenge to be safe from elimination, Emily still gets something out of having immunity because when she has immunity, her first choice gets voted out. Perhaps the person with immunity ends up with just a bit more power.
timblack
2022-05-17 22:01:23
Next: If Dan wins the immunity challenge, who gets voted out?
Next: If Dan wins the immunity challenge, who gets voted out?
timblack
2022-05-17 22:01:38
Definitely not Dan!
Definitely not Dan!
Alex-131
2022-05-17 22:01:57
Emily
Emily
alleycat
2022-05-17 22:01:57
Emily
Emily
Thu2_2
2022-05-17 22:01:57
Emily
Emily
timblack
2022-05-17 22:01:59
(I’m going to go through this one a bit more quickly in the interest of time.)
(I’m going to go through this one a bit more quickly in the interest of time.)
timblack
2022-05-17 22:02:04
Assaf and Ben still need to put at least one vote on Dan to prevent Assaf from being voted out. With Dan off the table, their best option is to vote out Emily. Assaf and Ben can both vote for Emily, then Dan will join them to vote for Emily as well, and Emily gets eliminated.
Assaf and Ben still need to put at least one vote on Dan to prevent Assaf from being voted out. With Dan off the table, their best option is to vote out Emily. Assaf and Ben can both vote for Emily, then Dan will join them to vote for Emily as well, and Emily gets eliminated.
timblack
2022-05-17 22:02:16
This is another case where the person with immunity is able to vote out their top preference.
This is another case where the person with immunity is able to vote out their top preference.
timblack
2022-05-17 22:02:27
Next: If Assaf wins the immunity challenge, who gets voted out?
Next: If Assaf wins the immunity challenge, who gets voted out?
timblack
2022-05-17 22:02:39
This totally upsets the game! Assaf wants to get out Ben most of all, but that wasn’t really a feasible option before.
This totally upsets the game! Assaf wants to get out Ben most of all, but that wasn’t really a feasible option before.
timblack
2022-05-17 22:02:51
In particular, everyone else (besides Assaf) who might have been interested in voting out Ben would rather oust Assaf, and if Ben’s neck were ever on the line, he’d jump on that bandwagon to save himself.
In particular, everyone else (besides Assaf) who might have been interested in voting out Ben would rather oust Assaf, and if Ben’s neck were ever on the line, he’d jump on that bandwagon to save himself.
timblack
2022-05-17 22:03:05
Here’s everyone’s preferences for elimination if Assaf is off the table. We’ve deleted A from all the preference lists:
A: B, C, D, E
B: C, D, E, B
C: B, D, E, C
D: E, B, C, D
E: B, C, D, E
Here’s everyone’s preferences for elimination if Assaf is off the table. We’ve deleted A from all the preference lists:
A: B, C, D, E
B: C, D, E, B
C: B, D, E, C
D: E, B, C, D
E: B, C, D, E
timblack
2022-05-17 22:03:10
Who gets voted out in this case?
Who gets voted out in this case?
Trigon
2022-05-17 22:03:32
Ben gets voted out because he is the highest priority target of A, C, and E
Ben gets voted out because he is the highest priority target of A, C, and E
Lamboreghini
2022-05-17 22:03:32
Ben
Ben
JZTX19
2022-05-17 22:03:32
Ben?
Ben?
BlizzardWizard
2022-05-17 22:03:32
Ben
Ben
impromptuA
2022-05-17 22:03:32
Ben
Ben
vrondoS
2022-05-17 22:03:32
B
B
vrondoS
2022-05-17 22:03:32
BEN
BEN
joannax
2022-05-17 22:03:32
B
B
timblack
2022-05-17 22:03:38
Now a majority of players — Assaf, Charlotte, and Emily — all want Ben out most. They all vote for Ben, and Ben is eliminated.
Now a majority of players — Assaf, Charlotte, and Emily — all want Ben out most. They all vote for Ben, and Ben is eliminated.
timblack
2022-05-17 22:03:48
And just when it seemed like Assaf and Ben were working so well together! (But really the only thing holding that duo together was the fact that without immunity Assaf couldn’t really turn against Ben even if he wanted to.)
And just when it seemed like Assaf and Ben were working so well together! (But really the only thing holding that duo together was the fact that without immunity Assaf couldn’t really turn against Ben even if he wanted to.)
timblack
2022-05-17 22:04:05
This is yet another example of the person winning the immunity challenge getting their way.
This is yet another example of the person winning the immunity challenge getting their way.
timblack
2022-05-17 22:04:20
I should mention here that not every immunity winner would be able to change the outcome of the vote like this. Remember that if there’s no immunity challenge, then Dan gets voted out. If either Ben or Charlotte were to win immunity, Dan would still be voted out.
I should mention here that not every immunity winner would be able to change the outcome of the vote like this. Remember that if there’s no immunity challenge, then Dan gets voted out. If either Ben or Charlotte were to win immunity, Dan would still be voted out.
timblack
2022-05-17 22:04:41
Here’s a summary what the outcome is based on the immunity winner:
No immunity: Dan is voted out first.
Assaf has immunity:: Ben is voted out first.
Ben has immunity:: Dan is voted out first.
Charlotte has immunity:: Dan is voted out first.
Dan has immunity:: Emily is voted out first.
Emily has immunity:: Assaf is voted out first.
Here’s a summary what the outcome is based on the immunity winner:
No immunity: Dan is voted out first.
Assaf has immunity:: Ben is voted out first.
Ben has immunity:: Dan is voted out first.
Charlotte has immunity:: Dan is voted out first.
Dan has immunity:: Emily is voted out first.
Emily has immunity:: Assaf is voted out first.
timblack
2022-05-17 22:04:59
This brings us to the last part of the question:
This brings us to the last part of the question:
timblack
2022-05-17 22:05:09
Part c. Suppose the winner of the immunity challenge is allowed to give their immunity away to another contestant. Does it ever make sense for a contestant to choose to do so?
Part c. Suppose the winner of the immunity challenge is allowed to give their immunity away to another contestant. Does it ever make sense for a contestant to choose to do so?
timblack
2022-05-17 22:05:36
We already saw that if Assaf, Dan, or Emily have immunity, the player with immunity is able to eliminate their first choice. So none of those three has an incentive to give immunity away.
We already saw that if Assaf, Dan, or Emily have immunity, the player with immunity is able to eliminate their first choice. So none of those three has an incentive to give immunity away.
timblack
2022-05-17 22:05:47
If Ben wins immunity, does he give it away?
If Ben wins immunity, does he give it away?
paixiao
2022-05-17 22:06:34
No.
No.
SmallStone9
2022-05-17 22:06:34
no
no
boing123
2022-05-17 22:06:34
no, he can't force charlotte out
no, he can't force charlotte out
kattyames
2022-05-17 22:06:34
no
no
mythicalcheese31
2022-05-17 22:06:34
no
no
kewlking
2022-05-17 22:06:34
No
No
z5r6x7v8
2022-05-17 22:06:34
not really
not really
timblack
2022-05-17 22:06:38
No, Ben’s first choice is to eliminate Charlotte, but no matter who has immunity, that doesn’t happen. His next best option is to eliminate Dan, which he can accomplish by holding onto immunity. (He could also accomplish that by giving immunity to Charlotte, but why bother.)
No, Ben’s first choice is to eliminate Charlotte, but no matter who has immunity, that doesn’t happen. His next best option is to eliminate Dan, which he can accomplish by holding onto immunity. (He could also accomplish that by giving immunity to Charlotte, but why bother.)
timblack
2022-05-17 22:07:00
If Charlotte wins immunity, does she give it away? To whom?
If Charlotte wins immunity, does she give it away? To whom?
mathleticguyyy
2022-05-17 22:07:43
Wait, so if Charlotte wins the challenge, she can win by giving immunity to Assaf and Emily
Wait, so if Charlotte wins the challenge, she can win by giving immunity to Assaf and Emily
mathleticguyyy
2022-05-17 22:07:43
Emily over Assaf since alphabet
Emily over Assaf since alphabet
boing123
2022-05-17 22:07:43
Charlotte gives it to Emily
Charlotte gives it to Emily
joannax
2022-05-17 22:07:43
to Emily
to Emily
timblack
2022-05-17 22:07:52
Yes! Charlotte’s first choice to be eliminated is Assaf, and that will happen if she gives away immunity to Emily.
Yes! Charlotte’s first choice to be eliminated is Assaf, and that will happen if she gives away immunity to Emily.
timblack
2022-05-17 22:08:05
So yes, sometimes it does make sense for a player to give away immunity!
So yes, sometimes it does make sense for a player to give away immunity!
timblack
2022-05-17 22:08:17
But, you have to remember that Singleton is a game of perfect information, with players who (these days) are all known to behave perfectly rationally.
But, you have to remember that Singleton is a game of perfect information, with players who (these days) are all known to behave perfectly rationally.
timblack
2022-05-17 22:08:39
If you ever watched an early season of Singleton where the players didn’t have perfect information and didn’t play perfectly rationally and had a heart <3, you might remember that players who gave away immunity tended to be voted out immediately and were roundly mocked.
If you ever watched an early season of Singleton where the players didn’t have perfect information and didn’t play perfectly rationally and had a heart <3, you might remember that players who gave away immunity tended to be voted out immediately and were roundly mocked.
timblack
2022-05-17 22:09:05
These days, you can calculate out every last move and know when it’s okay to give away immunity, but it’s a very precarious position. If the game is tweaked just a little bit, giving away immunity may suddenly become a very, very bad idea.
These days, you can calculate out every last move and know when it’s okay to give away immunity, but it’s a very precarious position. If the game is tweaked just a little bit, giving away immunity may suddenly become a very, very bad idea.
Thu2_2
2022-05-17 22:09:34
it would be a nice idea for a special season
it would be a nice idea for a special season
timblack
2022-05-17 22:09:43
Maybe that explains Singleton’s new slogan, “The monster group is coming.”
Maybe that explains Singleton’s new slogan, “The monster group is coming.”
mathleticguyyy
2022-05-17 22:09:48
If we introduce our dear friends Frank, George, Helena, Isabella, Jeremy, the calculation might intensify just a bit for the contestants
If we introduce our dear friends Frank, George, Helena, Isabella, Jeremy, the calculation might intensify just a bit for the contestants
WYoX1234
2022-05-17 22:10:05
lol
lol
JasonLIUYM
2022-05-17 22:10:05
tru
tru
timblack
2022-05-17 22:10:07
And that, finally, is problem 5!
And that, finally, is problem 5!
Mathboy345
2022-05-17 22:10:10
oof
oof
Trigon
2022-05-17 22:10:17
What if one contestant's vote counted double?
What if one contestant's vote counted double?
Bhavsar
2022-05-17 22:10:24
yay
yay
Thu2_2
2022-05-17 22:10:24
what a journey
what a journey
paixiao
2022-05-17 22:10:24
phew!
phew!
chuh22
2022-05-17 22:10:24
*thunderous applause*
*thunderous applause*
Amoszhang
2022-05-17 22:10:24
much oof indeed
much oof indeed
impromptuA
2022-05-17 22:10:43
._.
._.
kewlking
2022-05-17 22:10:43
timblack
2022-05-17 22:10:45
Okay, let's take another sort of journey together
Okay, let's take another sort of journey together
timblack
2022-05-17 22:10:49
This journey is called
This journey is called
timblack
2022-05-17 22:10:55
Problem 6
Problem 6
timblack
2022-05-17 22:11:29
Problem 6 You are investigating a dangerous cult, with the goal of uncovering its reclusive Mastermind. From previously gathered intelligence, you know that the cult has 100 members: the Mastermind, the Go-between, the Figurehead, and 97 Pawns. Each member of the cult associates with some, but not all, of the other members. In particular:
Problem 6 You are investigating a dangerous cult, with the goal of uncovering its reclusive Mastermind. From previously gathered intelligence, you know that the cult has 100 members: the Mastermind, the Go-between, the Figurehead, and 97 Pawns. Each member of the cult associates with some, but not all, of the other members. In particular:
timblack
2022-05-17 22:11:35
- The Mastermind is very reclusive; they associate with the Go-between, but no other member.
- The Mastermind is very reclusive; they associate with the Go-between, but no other member.
timblack
2022-05-17 22:11:43
- The Go-between associates with the Mastermind and the Figurehead, but none of the Pawns.
- The Go-between associates with the Mastermind and the Figurehead, but none of the Pawns.
timblack
2022-05-17 22:11:48
- The Figurehead associates with everyone except the Mastermind.
- The Figurehead associates with everyone except the Mastermind.
timblack
2022-05-17 22:11:54
- The Pawns associate with the Figurehead, but not the Mastermind nor the Go-between. Some pairs of Pawns may also associate with each other (so, each Pawn could potentially have up to 97 total associations).
- The Pawns associate with the Figurehead, but not the Mastermind nor the Go-between. Some pairs of Pawns may also associate with each other (so, each Pawn could potentially have up to 97 total associations).
timblack
2022-05-17 22:12:00
You cannot figure out which members have special roles just by looking. However, each day, you can select a pair of members to investigate, and determine whether they associate with each other.
You cannot figure out which members have special roles just by looking. However, each day, you can select a pair of members to investigate, and determine whether they associate with each other.
timblack
2022-05-17 22:12:11
Part a. Prove that if you investigate all pairs of members, then you can identify the Mastermind.
Part a. Prove that if you investigate all pairs of members, then you can identify the Mastermind.
hellokikki
2022-05-17 22:12:28
It's like 9:12 over here and I'm like yawn
It's like 9:12 over here and I'm like yawn
hellokikki
2022-05-17 22:12:28
and then I'm like nope stay awake self
and then I'm like nope stay awake self
timblack
2022-05-17 22:12:30
We
We
timblack
2022-05-17 22:12:32
We
We
timblack
2022-05-17 22:12:41
We'll make this one a bit quicker
We'll make this one a bit quicker
timblack
2022-05-17 22:13:05
Solution
Solution
timblack
2022-05-17 22:13:20
We’ll be able to tell apart some of the roles based on the number of associates.
We’ll be able to tell apart some of the roles based on the number of associates.
timblack
2022-05-17 22:13:26
How many associates does a Pawn have?
How many associates does a Pawn have?
joannax
2022-05-17 22:14:15
at least 1
at least 1
Trigon
2022-05-17 22:14:15
1 to 97
1 to 97
paixiao
2022-05-17 22:14:15
$1$ to $97.$
$1$ to $97.$
vrondoS
2022-05-17 22:14:15
more than or equal to 1
more than or equal to 1
joannax
2022-05-17 22:14:15
at most 97
at most 97
WYoX1234
2022-05-17 22:14:15
up to97?
up to97?
vrondoS
2022-05-17 22:14:15
$>=1$
$>=1$
timblack
2022-05-17 22:14:18
Every Pawn has at least one and at most 97 associates: a Pawn definitely associates with the Figurehead, and doesn't associate with themself, the Mastermind, or the Go-Between.
Every Pawn has at least one and at most 97 associates: a Pawn definitely associates with the Figurehead, and doesn't associate with themself, the Mastermind, or the Go-Between.
timblack
2022-05-17 22:14:32
How many associates does the Figurehead have?
How many associates does the Figurehead have?
chaidan_tamaroon
2022-05-17 22:14:52
Only the Figurehead associates with all but one of the cult members. Only the Mastermind doesn’t associate with the Figurehead.
Only the Figurehead associates with all but one of the cult members. Only the Mastermind doesn’t associate with the Figurehead.
TheBeast5520
2022-05-17 22:15:03
exactly 98
exactly 98
boing123
2022-05-17 22:15:03
98
98
TheBeast5520
2022-05-17 22:15:03
$98$
$98$
fishchips
2022-05-17 22:15:03
98
98
Lamboreghini
2022-05-17 22:15:03
98
98
GeniusGiraffe
2022-05-17 22:15:03
98
98
erickson_max
2022-05-17 22:15:03
98
98
mythicalcheese31
2022-05-17 22:15:03
98
98
timblack
2022-05-17 22:15:12
Right, 98 associates: they associate with everyone except themself and the Mastermind.
Right, 98 associates: they associate with everyone except themself and the Mastermind.
timblack
2022-05-17 22:15:30
The Mastermind has 1 associate (just the Go-Between).
The Mastermind has 1 associate (just the Go-Between).
timblack
2022-05-17 22:15:40
The Go-Between has 2 (the Mastermind and the Figurehead).
The Go-Between has 2 (the Mastermind and the Figurehead).
timblack
2022-05-17 22:16:01
If all $\binom{100}{2}$ investigations are done, we can identify the Figurehead as the only cult member with 98 associates.
If all $\binom{100}{2}$ investigations are done, we can identify the Figurehead as the only cult member with 98 associates.
TheBeast5520
2022-05-17 22:16:05
just check whoever the figurehead doesn't communicate with to find the mastermind
just check whoever the figurehead doesn't communicate with to find the mastermind
timblack
2022-05-17 22:16:11
Then, we can identify the Mastermind as the only cult member who does not associate with the Figurehead.
Then, we can identify the Mastermind as the only cult member who does not associate with the Figurehead.
timblack
2022-05-17 22:16:28
Part b. Is there a strategy to find the Mastermind in under 1000 days?
Part b. Is there a strategy to find the Mastermind in under 1000 days?
timblack
2022-05-17 22:16:51
Yes, there are a bunch! Here's one of them.
Yes, there are a bunch! Here's one of them.
timblack
2022-05-17 22:16:57
We’ll carry out our strategy in two phases:
We’ll carry out our strategy in two phases:
timblack
2022-05-17 22:17:07
Phase 1: The first thing we’ll need is a big bulletin board, some thumbtacks, and some twine. Let’s tack up pictures of the members in a big circle. Use the twine to connect each picture to the two pictures before it and the two after it.
Phase 1: The first thing we’ll need is a big bulletin board, some thumbtacks, and some twine. Let’s tack up pictures of the members in a big circle. Use the twine to connect each picture to the two pictures before it and the two after it.
timblack
2022-05-17 22:17:15
Each piece of twine represents a pair of people we will investigate.
Each piece of twine represents a pair of people we will investigate.
timblack
2022-05-17 22:17:22
WYoX1234
2022-05-17 22:17:37
uwu emojis
uwu emojis
hellokikki
2022-05-17 22:17:37
nice emojis
nice emojis
timblack
2022-05-17 22:17:47
Thanks! Carefully selected!
Thanks! Carefully selected!
timblack
2022-05-17 22:18:00
How many pieces of twine have we used?
How many pieces of twine have we used?
hellokikki
2022-05-17 22:18:11
I have a feeling the glasses guy is the mastermind
I have a feeling the glasses guy is the mastermind
Thu2_2
2022-05-17 22:18:11
hmm, "there's a mastermind among us"
hmm, "there's a mastermind among us"
Inaaya
2022-05-17 22:18:36
sus
sus
mathleticguyyy
2022-05-17 22:18:47
So 200 pairs so far?
So 200 pairs so far?
Trigon
2022-05-17 22:18:47
200
200
boing123
2022-05-17 22:18:47
200
200
Amoszhang
2022-05-17 22:18:47
what i mean 200
what i mean 200
vrondoS
2022-05-17 22:18:47
200
200
timblack
2022-05-17 22:18:56
We’ve used 200 pieces of twine: There are four ends of a piece of twine on each of 100 faces, so that’s $4 \cdot 100 = 400$, but divide by two because each piece of twine has two ends.
We’ve used 200 pieces of twine: There are four ends of a piece of twine on each of 100 faces, so that’s $4 \cdot 100 = 400$, but divide by two because each piece of twine has two ends.
timblack
2022-05-17 22:19:06
So, we'll spend the first 200 days conducting these investigations. When we are done, we'll have investigated each member in connection to four others.
So, we'll spend the first 200 days conducting these investigations. When we are done, we'll have investigated each member in connection to four others.
timblack
2022-05-17 22:19:40
We’ll keep track of how many associates each member has among the possibilities we've investigated so far.
We’ll keep track of how many associates each member has among the possibilities we've investigated so far.
timblack
2022-05-17 22:19:53
timblack
2022-05-17 22:20:09
Phase 2: It's time to rearrange our bulletin board. We’ll sort the members into two rows:
Phase 2: It's time to rearrange our bulletin board. We’ll sort the members into two rows:
timblack
2022-05-17 22:20:21
Row 1: “antisocial” members, who have 0, 1, or 2 associates out of the possible four you investigated, and
Row 1: “antisocial” members, who have 0, 1, or 2 associates out of the possible four you investigated, and
timblack
2022-05-17 22:20:29
Row 2: “social” members, who have 3 or 4 associates.
Row 2: “social” members, who have 3 or 4 associates.
timblack
2022-05-17 22:20:37
timblack
2022-05-17 22:20:55
The idea behind this is that certain members (Mastermind, Go-between, Figurehead, or Pawns) will end up in certain rows. Can you name a member that will end up in a particular row?
The idea behind this is that certain members (Mastermind, Go-between, Figurehead, or Pawns) will end up in certain rows. Can you name a member that will end up in a particular row?
Amoszhang
2022-05-17 22:21:41
possible masterminds and possible figureheads
possible masterminds and possible figureheads
Alex-131
2022-05-17 22:21:41
Mastermind in row 1
Mastermind in row 1
Sigma_Monkey
2022-05-17 22:21:41
mastermind is antisocial
mastermind is antisocial
chaidan_tamaroon
2022-05-17 22:21:41
Mastermind and Go-Between are anti-social. Figurehead is social
Mastermind and Go-Between are anti-social. Figurehead is social
joannax
2022-05-17 22:21:41
Mastermind: antisocial
Mastermind: antisocial
boing123
2022-05-17 22:21:41
mastermind, go-between in top row, figurehead in the bottom
mastermind, go-between in top row, figurehead in the bottom
vrondoS
2022-05-17 22:21:41
mastermind is in the first
mastermind is in the first
joannax
2022-05-17 22:21:41
Go-between: antisocial
Go-between: antisocial
timblack
2022-05-17 22:21:50
No matter what, the Mastermind and Go-between will wind up in the antisocial row, because they have only one or two associates in total.
No matter what, the Mastermind and Go-between will wind up in the antisocial row, because they have only one or two associates in total.
timblack
2022-05-17 22:22:10
On the other hand, the Figurehead will be in the social row, because there is only one member they don't associate with.
On the other hand, the Figurehead will be in the social row, because there is only one member they don't associate with.
timblack
2022-05-17 22:22:16
Pawns may be split between the rows.
Pawns may be split between the rows.
hellokikki
2022-05-17 22:22:36
yes glasses guy is a possible mastermind
yes glasses guy is a possible mastermind
timblack
2022-05-17 22:22:40
On the remaining days, we will hold a competition (of sorts) between the two rows. You investigate the first member in each row.
On the remaining days, we will hold a competition (of sorts) between the two rows. You investigate the first member in each row.
timblack
2022-05-17 22:23:04
If they associate, the social member wins the face-off, and if not, the antisocial member wins. The loser's picture gets torn down off the board.
If they associate, the social member wins the face-off, and if not, the antisocial member wins. The loser's picture gets torn down off the board.
timblack
2022-05-17 22:23:22
There are two players who are particularly good at this game. Who are they?
There are two players who are particularly good at this game. Who are they?
chuh22
2022-05-17 22:23:29
i guess it makes sense that the guy with a zipped mouth and the guy quieting everyone aren't exactly social
i guess it makes sense that the guy with a zipped mouth and the guy quieting everyone aren't exactly social
vrondoS
2022-05-17 22:23:41
0.0
0.0
Sigma_Monkey
2022-05-17 22:24:21
Mastermind is cracked and so is figurehead
Mastermind is cracked and so is figurehead
Trigon
2022-05-17 22:24:21
The Figurehead and Mastermind
The Figurehead and Mastermind
Thu2_2
2022-05-17 22:24:21
the figurehead?
the figurehead?
timblack
2022-05-17 22:24:25
The Mastermind and the Figurehead.
The Mastermind and the Figurehead.
timblack
2022-05-17 22:24:36
The Mastermind never loses: they are in the antisocial row, and the only person they associate with is the Go-between, but since the Go-between is in the same row, they will never face off.
The Mastermind never loses: they are in the antisocial row, and the only person they associate with is the Go-between, but since the Go-between is in the same row, they will never face off.
timblack
2022-05-17 22:24:55
The Figurehead is in the social row, and associates with everybody except the Mastermind, so only the Mastermind can defeat them.
The Figurehead is in the social row, and associates with everybody except the Mastermind, so only the Mastermind can defeat them.
timblack
2022-05-17 22:25:12
As the days go on, either the Mastermind or the Figurehead will make it to the front of their respective row.
As the days go on, either the Mastermind or the Figurehead will make it to the front of their respective row.
timblack
2022-05-17 22:25:27
At that point, whoever it is, that player will keep winning day after day, until one day, the Mastermind and Figurehead go head-to-head.
At that point, whoever it is, that player will keep winning day after day, until one day, the Mastermind and Figurehead go head-to-head.
mwu2010
2022-05-17 22:25:44
final roar
final roar
JustinJ
2022-05-17 22:25:49
Then mastermind wins and we know the mastermind
Then mastermind wins and we know the mastermind
paixiao
2022-05-17 22:26:10
The mastermind wins!
The mastermind wins!
timblack
2022-05-17 22:26:16
The Mastermind wins this match-up!
The Mastermind wins this match-up!
timblack
2022-05-17 22:26:28
The Mastermind also wins every subsequent match-up, until the social row is empty.
The Mastermind also wins every subsequent match-up, until the social row is empty.
timblack
2022-05-17 22:26:42
We can then report back that the first remaining face in the antisocial row is in fact the Mastermind.
We can then report back that the first remaining face in the antisocial row is in fact the Mastermind.
timblack
2022-05-17 22:26:52
timblack
2022-05-17 22:26:57
chaidan_tamaroon
2022-05-17 22:27:03
Yay!
Yay!
hellokikki
2022-05-17 22:27:03
NOO
NOO
hellokikki
2022-05-17 22:27:03
sad
sad
chuh22
2022-05-17 22:27:03
I KNEW IT
I KNEW IT
Alex-131
2022-05-17 22:27:13
how many days does this add to tho?
how many days does this add to tho?
amopuri
2022-05-17 22:27:20
rip not glasses guy
rip not glasses guy
timblack
2022-05-17 22:27:22
Phase 1 took 200 days. What is the maximum number of days that Phase 2 could take?
Phase 1 took 200 days. What is the maximum number of days that Phase 2 could take?
hellokikki
2022-05-17 22:27:28
????
????
JustinJ
2022-05-17 22:27:28
the glasses emoji is cooler ;(
the glasses emoji is cooler ;(
Thu2_2
2022-05-17 22:28:16
99 days
99 days
binyubin
2022-05-17 22:28:16
99
99
CoolCarsOnTheRun
2022-05-17 22:28:16
99
99
boing123
2022-05-17 22:28:16
99, each day one gets eliminated?
99, each day one gets eliminated?
Amoszhang
2022-05-17 22:28:16
99 probably
99 probably
timblack
2022-05-17 22:28:28
In Phase 2, one photo is torn down each day
In Phase 2, one photo is torn down each day
timblack
2022-05-17 22:28:34
We started with 100 photos
We started with 100 photos
timblack
2022-05-17 22:28:37
So it's at most 100
So it's at most 100
timblack
2022-05-17 22:28:55
But actually, there's at least one photo left at the end, so it's actually at most 99 days
But actually, there's at least one photo left at the end, so it's actually at most 99 days
timblack
2022-05-17 22:29:04
In total, we've spent at most 299 days.
In total, we've spent at most 299 days.
timblack
2022-05-17 22:29:35
That's well within the 1000 day limit, but I may have even seem some solutions that are even a bit faster.
That's well within the 1000 day limit, but I may have even seem some solutions that are even a bit faster.
timblack
2022-05-17 22:29:50
Part c. Suppose there are n members in the cult: one Mastermind, one Go-between, one Figurehead, and n - 3 Pawns. How quickly can you find the Mastermind?
Part c. Suppose there are n members in the cult: one Mastermind, one Go-between, one Figurehead, and n - 3 Pawns. How quickly can you find the Mastermind?
timblack
2022-05-17 22:29:58
(We don't know the exact answer to (c), but we know some good bounds. Do your best!)
(We don't know the exact answer to (c), but we know some good bounds. Do your best!)
mathleticguyyy
2022-05-17 22:30:22
Is there a probabilistic strategy that finds the mastermind in X days with probability Y where X is really small and Y is reasonable?
Is there a probabilistic strategy that finds the mastermind in X days with probability Y where X is really small and Y is reasonable?
timblack
2022-05-17 22:30:36
Great question! I hadn't thought about it!
Great question! I hadn't thought about it!
vrondoS
2022-05-17 22:30:44
it is the same thing, so 2n+n-1 right?
it is the same thing, so 2n+n-1 right?
paixiao
2022-05-17 22:30:44
$3n-1$
$3n-1$
timblack
2022-05-17 22:30:50
If there are $n$ members in the cult, you can use the same strategy.
If there are $n$ members in the cult, you can use the same strategy.
timblack
2022-05-17 22:30:59
In Phase 1, we still compare each member with 4 others, and the total number of investigations is $2n$.
In Phase 1, we still compare each member with 4 others, and the total number of investigations is $2n$.
timblack
2022-05-17 22:31:13
In Phase 2, we still tear down one of the $n$ faces remaining, ending with at least one face left, so Phase 2 takes at most $n - 1$ days.
In Phase 2, we still tear down one of the $n$ faces remaining, ending with at least one face left, so Phase 2 takes at most $n - 1$ days.
timblack
2022-05-17 22:31:23
Adding these together, we take at most $3n - 1$ days.
Adding these together, we take at most $3n - 1$ days.
chuh22
2022-05-17 22:31:34
c) is the definition of "good, now do it again, but better" and it's some combination of pure evil and joy but i love it
c) is the definition of "good, now do it again, but better" and it's some combination of pure evil and joy but i love it
Thu2_2
2022-05-17 22:31:48
I got 3n - 8
I got 3n - 8
Amoszhang
2022-05-17 22:31:48
how about only n checks first and then check the ones with one connection
how about only n checks first and then check the ones with one connection
mathleticguyyy
2022-05-17 22:32:00
My first subquadratic bound was 2n-3 actually
My first subquadratic bound was 2n-3 actually
timblack
2022-05-17 22:32:22
I only saw a couple of the submissions, so I may have not seen the fastest ideas people came up with!
I only saw a couple of the submissions, so I may have not seen the fastest ideas people came up with!
aa1024
2022-05-17 22:32:36
Is there a strategy with better complexity than o(n)
Is there a strategy with better complexity than o(n)
timblack
2022-05-17 22:33:02
I think we can show it takes at least n (ish) days. I'd be interested in seeing some lower bounds!
I think we can show it takes at least n (ish) days. I'd be interested in seeing some lower bounds!
timblack
2022-05-17 22:33:37
This problem leaves open the question of what's the best you can do, but that's where we will leave it!
This problem leaves open the question of what's the best you can do, but that's where we will leave it!
timblack
2022-05-17 22:33:53
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
mathleticguyyy
2022-05-17 22:34:00
ty!!
ty!!
timblack
2022-05-17 22:34:08
We'll be posting tonight's transcript on https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, in case you want to revisit some of what we covered tonight.
We'll be posting tonight's transcript on https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, in case you want to revisit some of what we covered tonight.
timblack
2022-05-17 22:34:17
We hope you enjoyed this year's QQ, and stay tuned for the 2023 Quiz (and the summer 2023 application) to be posted in January. I'll stick around for another five minutes and answer non-Quiz questions about the program and the application process in case anybody has questions about Mathcamp itself.
We hope you enjoyed this year's QQ, and stay tuned for the 2023 Quiz (and the summer 2023 application) to be posted in January. I'll stick around for another five minutes and answer non-Quiz questions about the program and the application process in case anybody has questions about Mathcamp itself.
CoolCarsOnTheRun
2022-05-17 22:34:31
thank you so much!
thank you so much!
vrondoS
2022-05-17 22:34:31
thank you bye
thank you bye
mathleticguyyy
2022-05-17 22:34:31
looking forward to great problems next year again
looking forward to great problems next year again
chaidan_tamaroon
2022-05-17 22:34:31
Bye
Bye
aa1024
2022-05-17 22:34:31
Thank you
Thank you
Sigma_Monkey
2022-05-17 22:34:31
thank you all so much!!
thank you all so much!!
TheBeast5520
2022-05-17 22:34:31
thank you!
thank you!
binyubin
2022-05-17 22:34:31
thank you
thank you
joannax
2022-05-17 22:34:31
Thank you so much!
Thank you so much!
Thu2_2
2022-05-17 22:34:31
thank youuuuu!
thank youuuuu!
Amoszhang
2022-05-17 22:34:43
Thank you!!
Thank you!!
timblack
2022-05-17 22:34:45
Thanks again, everybody - good night!
Thanks again, everybody - good night!
Amoszhang
2022-05-17 22:34:47
are there proofs?
are there proofs?
Amoszhang
2022-05-17 22:34:47
for n ish days?
for n ish days?
timblack
2022-05-17 22:35:03
I need to think a bit more
I need to think a bit more
Trigon
2022-05-17 22:35:07
Thank you!
Thank you!
hellokikki
2022-05-17 22:35:07
thanks, bye!!
thanks, bye!!
z5r6x7v8
2022-05-17 22:35:07
thanks!!!
thanks!!!
aopsuser008
2022-05-17 22:35:07
thank you so much!
thank you so much!
WYoX1234
2022-05-17 22:35:21
thank youu byee
thank youu byee
mythicalcheese31
2022-05-17 22:35:21
gn tysm
gn tysm
Amoszhang
2022-05-17 22:35:50
i see, can you post this on related media?
i see, can you post this on related media?
timblack
2022-05-17 22:36:06
I think it's fine to discuss the problems now. (Kevin/Misha can you confirm?)
I think it's fine to discuss the problems now. (Kevin/Misha can you confirm?)
timblack
2022-05-17 22:36:20
Well I mean it better be okay because we just discussed them.
Well I mean it better be okay because we just discussed them.
KevinCarde
2022-05-17 22:36:30
Yes, open season on discussing the problems anywhere!
Yes, open season on discussing the problems anywhere!
kevinyaiko
2022-05-17 22:44:01
If you have further questions for Mathcamp, you can contact them at https://www.mathcamp.org/contact_us/
If you have further questions for Mathcamp, you can contact them at https://www.mathcamp.org/contact_us/
kevinyaiko
2022-05-17 22:44:06
Finally, a transcript of this Math Jam will be posted soon here: www.aops.com/school/mathjams-transcripts
Finally, a transcript of this Math Jam will be posted soon here: www.aops.com/school/mathjams-transcripts
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
