Mathcamp 2021 Qualifying Quiz
Go back to the Math Jam ArchiveJoin the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to the 2021 Mathcamp Qualifying Quiz! Mathcamp is an intensive 5-week-long summer program for mathematically talented high school students. The Qualifying Quiz is the centerpiece of the Mathcamp application each year, and the problems are designed to be fun, challenging, and thought-provoking. We invite anybody who's interested to come to this event, whether you applied to Mathcamp this year or just want to talk about some cool problems with Mathcamp instructors. It'll be even more fun for you if you bring your own solutions so you can participate in the discussion during the Jam!
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: MiraBernstein
AngelBell
2021-05-19 18:55:32
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:00 pm ET (4:00 pm PT).
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:00 pm ET (4:00 pm PT).
AngelBell
2021-05-19 18:55:38
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.
AngelBell
2021-05-19 18:55:45
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.
vapodaca
2021-05-19 19:00:09
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
vapodaca
2021-05-19 19:00:24
Before I introduce our guests, let me briefly explain how our online classroom works.
Before I introduce our guests, let me briefly explain how our online classroom works.
vapodaca
2021-05-19 19:00:35
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
vapodaca
2021-05-19 19:00:46
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
vapodaca
2021-05-19 19:00:52
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
vapodaca
2021-05-19 19:01:43
Tonight we'll have Marisa Debowsky leading our discussion!
Tonight we'll have Marisa Debowsky leading our discussion!
vapodaca
2021-05-19 19:01:47
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
Marisa Debowsky (MarisaD) is the Executive Director of Mathcamp. She's been teaching Topological Graph Theory and singing pop songs at Mathcamp every summer since 2006.
vapodaca
2021-05-19 19:02:02
And now, I'll hand it off to Marisa!
And now, I'll hand it off to Marisa!
MarisaD
2021-05-19 19:02:15
Hi, everybody, and welcome to the annual Mathcamp Qualifying Quiz Jam!
Hi, everybody, and welcome to the annual Mathcamp Qualifying Quiz Jam!
MarisaD
2021-05-19 19:02:21
A big thanks as always to @AngelBell, @vapodaca, @rrusczyk, and the AoPS team for hosting us.
A big thanks as always to @AngelBell, @vapodaca, @rrusczyk, and the AoPS team for hosting us.
MarisaD
2021-05-19 19:02:33
My Mathcamp colleagues and I are here to talk about the Mathcamp 2021 QQ. To follow along, you should all have the quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
My Mathcamp colleagues and I are here to talk about the Mathcamp 2021 QQ. To follow along, you should all have the quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
MarisaD
2021-05-19 19:02:44
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
MarisaD
2021-05-19 19:02:49
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!
MarisaD
2021-05-19 19:02:56
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We claim that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We claim that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
MarisaD
2021-05-19 19:03:17
Also, as @AngelBell and @vapodaca pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
Also, as @AngelBell and @vapodaca pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
MarisaD
2021-05-19 19:03:28
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/), or check out the AoPS Jam about the program and the application process from a few months ago: https://artofproblemsolving.com/school/mathjams-transcripts?id=572
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/), or check out the AoPS Jam about the program and the application process from a few months ago: https://artofproblemsolving.com/school/mathjams-transcripts?id=572
MarisaD
2021-05-19 19:03:35
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS: http://www.artofproblemsolving.com/community/c135
MarisaD
2021-05-19 19:03:40
We've got a lot to cover in the next two hours, so let's get started! I'll turn it over to Assaf to kick us off with Problem #1.
We've got a lot to cover in the next two hours, so let's get started! I'll turn it over to Assaf to kick us off with Problem #1.
safibn
2021-05-19 19:03:46
Hello there! I’m Assaf, and I’ll be presenting problem 1. This problem has to do with the circle of lies as described below:
Hello there! I’m Assaf, and I’ll be presenting problem 1. This problem has to do with the circle of lies as described below:
safibn
2021-05-19 19:03:52
safibn
2021-05-19 19:03:58
In other words, mentors always lie to campers, campers always lie to JCs, and JCs always lie to mentors. All other interactions are truthful.
In other words, mentors always lie to campers, campers always lie to JCs, and JCs always lie to mentors. All other interactions are truthful.
safibn
2021-05-19 19:04:06
Fun fact: all of the people mentioned in this problem have actually been mentors, campers, and JCs. Some have even lied to me.
Fun fact: all of the people mentioned in this problem have actually been mentors, campers, and JCs. Some have even lied to me.
safibn
2021-05-19 19:04:22
Part (a): Sachi and Yuval have a conversation. Sachi says to Yuval, "At least one of us is a mentor." Yuval replies to Sachi, "At least one of us is a camper." What can you deduce about Yuval?
Part (a): Sachi and Yuval have a conversation. Sachi says to Yuval, "At least one of us is a mentor." Yuval replies to Sachi, "At least one of us is a camper." What can you deduce about Yuval?
safibn
2021-05-19 19:04:38
There’s various approaches to solving this problem. We can use a truth table, or analyze all possible role pairs for Yuval and Sachi, or analyze whether Yuval or Sachi are lying. I’ll show the latter.
There’s various approaches to solving this problem. We can use a truth table, or analyze all possible role pairs for Yuval and Sachi, or analyze whether Yuval or Sachi are lying. I’ll show the latter.
safibn
2021-05-19 19:04:52
First, notice that it’s impossible for both Yuval and Sachi to be lying.
First, notice that it’s impossible for both Yuval and Sachi to be lying.
safibn
2021-05-19 19:05:02
Sachi is lying: If Sachi is lying, then neither Yuval nor Sachi are mentors. What does this mean? *consults circle of lies*
Sachi is lying: If Sachi is lying, then neither Yuval nor Sachi are mentors. What does this mean? *consults circle of lies*
squirrellover
2021-05-19 19:05:40
Yuval is a JC
Yuval is a JC
Lilavigne
2021-05-19 19:05:40
sachi is a camper and yuvi is a jc
sachi is a camper and yuvi is a jc
SHZhang
2021-05-19 19:05:44
Sachi is camper, Yuval is JC
Sachi is camper, Yuval is JC
safibn
2021-05-19 19:05:54
If Sachi is lying, then Sachi must be a camper and Yuval must be a JC
If Sachi is lying, then Sachi must be a camper and Yuval must be a JC
CircleInvert
2021-05-19 19:05:58
Sachi is a camper and Yuval is a JC
Sachi is a camper and Yuval is a JC
RoboBuilder
2021-05-19 19:05:58
Sachi is a camper and Yuval is a JC
Sachi is a camper and Yuval is a JC
safibn
2021-05-19 19:06:14
yuval is lying: if yuval is lying, then neither yuval nor sachi are campers. what does the circle of lies tell us?
yuval is lying: if yuval is lying, then neither yuval nor sachi are campers. what does the circle of lies tell us?
rickiebosun
2021-05-19 19:06:53
Yuval is a JC and Sachi is a Mentor
Yuval is a JC and Sachi is a Mentor
w_aops
2021-05-19 19:06:53
Yuval is a JC and Sachi is a mentor
Yuval is a JC and Sachi is a mentor
Peatato
2021-05-19 19:06:53
Yuval is JC and Sachi is a mentor
Yuval is JC and Sachi is a mentor
Lilavigne
2021-05-19 19:06:53
Yuval is a JC and Sachi is a mentor
Yuval is a JC and Sachi is a mentor
m0bius
2021-05-19 19:06:53
Yuval is a JC and Sachi is a mentor
Yuval is a JC and Sachi is a mentor
eshu_mittal
2021-05-19 19:06:53
Yuval is a JC, Sachi is a mentor
Yuval is a JC, Sachi is a mentor
safibn
2021-05-19 19:07:06
If Yuval is lying then Sachi must be a mentor and Yuval must be a JC
If Yuval is lying then Sachi must be a mentor and Yuval must be a JC
safibn
2021-05-19 19:07:15
Neither Yuval nor Sachi are lying: In this case, one of them is a mentor, and one is a camper, but then one would lie to the other! This can’t happen
Neither Yuval nor Sachi are lying: In this case, one of them is a mentor, and one is a camper, but then one would lie to the other! This can’t happen
safibn
2021-05-19 19:07:22
In all possible cases, Yuval is a JC
In all possible cases, Yuval is a JC
safibn
2021-05-19 19:07:34
Part (b): You are a camper and you meet someone named Miranda at camp. What question can you ask Miranda about herself to determine whether she is a JC?
Part (b): You are a camper and you meet someone named Miranda at camp. What question can you ask Miranda about herself to determine whether she is a JC?
safibn
2021-05-19 19:07:45
Some answers were of the form: I, a camper, will say: “Your name is Miranda”, and if the universe will implode in a paradox if Miranda is a JC.
Some answers were of the form: I, a camper, will say: “Your name is Miranda”, and if the universe will implode in a paradox if Miranda is a JC.
safibn
2021-05-19 19:07:55
We did not accept answers that imploded the universe in a paradox.
We did not accept answers that imploded the universe in a paradox.
safibn
2021-05-19 19:08:07
What happens if you asked Miranda “Are you a JC?”
What happens if you asked Miranda “Are you a JC?”
gordonhero
2021-05-19 19:08:39
JC would say yes if they are a JC, but yes if they are a mentor as well
JC would say yes if they are a JC, but yes if they are a mentor as well
safibn
2021-05-19 19:08:44
So that’s no good - it detects campers instead of JCs. What question would detect JCs?
So that’s no good - it detects campers instead of JCs. What question would detect JCs?
safibn
2021-05-19 19:08:56
If we ask: “Are you a camper?” only a JC would say “no”. We can also ask “are you staff,” and only a JC would say “yes.”
If we ask: “Are you a camper?” only a JC would say “no”. We can also ask “are you staff,” and only a JC would say “yes.”
safibn
2021-05-19 19:09:08
Part (c) Don and Viv are having a conversation as you pass by. Is there a single statement you can overhear from that conversation from which you can deduce that Don and Viv are both in the same group of people (both campers, or both JCs, or both mentors) without giving you any additional information about which group it is?
Part (c) Don and Viv are having a conversation as you pass by. Is there a single statement you can overhear from that conversation from which you can deduce that Don and Viv are both in the same group of people (both campers, or both JCs, or both mentors) without giving you any additional information about which group it is?
safibn
2021-05-19 19:09:37
We’d like to find a single statement that essentially says: “we are in the same group”. What distinguishes people in the same group?
We’d like to find a single statement that essentially says: “we are in the same group”. What distinguishes people in the same group?
Arnuv1000
2021-05-19 19:10:04
they trust each other
they trust each other
olive0827
2021-05-19 19:10:04
do not lie to each other
do not lie to each other
pi271828
2021-05-19 19:10:04
They wont lie to each other
They wont lie to each other
juliankuang
2021-05-19 19:10:04
they both tell truth to each other
they both tell truth to each other
gordonhero
2021-05-19 19:10:04
They tell the truth both ways
They tell the truth both ways
GreenFrog1
2021-05-19 19:10:04
They bot tell the truth.
They bot tell the truth.
SHZhang
2021-05-19 19:10:04
The two people tell the truth to each other
The two people tell the truth to each other
m0bius
2021-05-19 19:10:04
they tell the truth to each other
they tell the truth to each other
bronzetruck2016
2021-05-19 19:10:04
They don't lie to each other.
They don't lie to each other.
student20201011
2021-05-19 19:10:04
they tell each other the truth
they tell each other the truth
w_aops
2021-05-19 19:10:04
They tell the truth to each other
They tell the truth to each other
CoolCarsOnTheRun
2021-05-19 19:10:13
there's no lying between the two of them
there's no lying between the two of them
llddmmtt1
2021-05-19 19:10:13
they don't lie to eachother
they don't lie to eachother
Edelweiss_USA
2021-05-19 19:10:13
They don't lie to each other.
They don't lie to each other.
Batee5a
2021-05-19 19:10:13
they'll both say the truth
they'll both say the truth
ypang9804
2021-05-19 19:10:13
They both will lie to a certain group of people
They both will lie to a certain group of people
pritiks
2021-05-19 19:10:13
they say the truth to eachother
they say the truth to eachother
GreenFrog1
2021-05-19 19:10:13
They both tell the truth.
They both tell the truth.
safibn
2021-05-19 19:10:16
Two people are in the same group if and only if they both tell the truth to each other. Can anyone in a lying pair say that both of them tell the truth to each other?
Two people are in the same group if and only if they both tell the truth to each other. Can anyone in a lying pair say that both of them tell the truth to each other?
safibn
2021-05-19 19:10:49
A lot of people have the right idea here!
A lot of people have the right idea here!
safibn
2021-05-19 19:11:01
Without loss of generality, assume that Viv says: “you are not lying to me.” If Viv was lying, then Don must be lying. However, by the circle of lies, Don must be telling the truth, a contradiction.
Without loss of generality, assume that Viv says: “you are not lying to me.” If Viv was lying, then Don must be lying. However, by the circle of lies, Don must be telling the truth, a contradiction.
safibn
2021-05-19 19:11:12
If Viv was telling the truth, then Don must also be telling the truth.
If Viv was telling the truth, then Don must also be telling the truth.
safibn
2021-05-19 19:11:22
So if we overhear “you are not lying to me,” we know that Viv and Don are in the same group.
So if we overhear “you are not lying to me,” we know that Viv and Don are in the same group.
safibn
2021-05-19 19:11:33
A super-short solution can be: “I agree” because if we overhear that, it’s equivalent to overhearing “you are not lying to me.”
A super-short solution can be: “I agree” because if we overhear that, it’s equivalent to overhearing “you are not lying to me.”
safibn
2021-05-19 19:11:50
Thanks for coming by! Enjoy problem 2!
Thanks for coming by! Enjoy problem 2!
KevinCarde
2021-05-19 19:12:07
Hi all, I'm Kevin, and I'll be presenting Problem 2, which involves a lot of probability!
Hi all, I'm Kevin, and I'll be presenting Problem 2, which involves a lot of probability!
KevinCarde
2021-05-19 19:12:18
Since the full problem with all of its parts is quite long, we'll keep only parts of the problem stickied at any given time. So let's dive in:
Since the full problem with all of its parts is quite long, we'll keep only parts of the problem stickied at any given time. So let's dive in:
KevinCarde
2021-05-19 19:12:25
Problem 2 Statement:
Problem 2 Statement:
KevinCarde
2021-05-19 19:12:33
Kai has a collection of magic, shape-changing dice. When he rolls a blue die, it changes shape to have a number of sides equal to the number rolled minus one. For example, if a blue die starts out with 12 sides, then Kai has an equal probability of rolling any of the twelve integers from 1 through 12. If he rolls an 8, then the blue die changes shape to have 7 sides, and the next roll will have an equal probability of rolling any of the seven integers from 1 through 7. After rolling the same blue die over and over, eventually Kai will roll a 1, at which point the die will disappear.
Kai has a collection of magic, shape-changing dice. When he rolls a blue die, it changes shape to have a number of sides equal to the number rolled minus one. For example, if a blue die starts out with 12 sides, then Kai has an equal probability of rolling any of the twelve integers from 1 through 12. If he rolls an 8, then the blue die changes shape to have 7 sides, and the next roll will have an equal probability of rolling any of the seven integers from 1 through 7. After rolling the same blue die over and over, eventually Kai will roll a 1, at which point the die will disappear.
KevinCarde
2021-05-19 19:12:45
Part a: Suppose the blue die starts with 4 sides (and so it has an equal probability of rolling any of the four integers from 1 through 4). How many rolls, on average, will it take for the die to disappear?
Part a: Suppose the blue die starts with 4 sides (and so it has an equal probability of rolling any of the four integers from 1 through 4). How many rolls, on average, will it take for the die to disappear?
KevinCarde
2021-05-19 19:13:06
Part a (and b, coming up soon), are warm-ups with explicit numbers rather than variables, though they can still be tricky if probability is somewhat new to you, and then c, d, and e will involve proofs.
Part a (and b, coming up soon), are warm-ups with explicit numbers rather than variables, though they can still be tricky if probability is somewhat new to you, and then c, d, and e will involve proofs.
CircleInvert
2021-05-19 19:13:12
Time for some classic expected value
Time for some classic expected value
KevinCarde
2021-05-19 19:13:33
Indeed! "Expected value" is a fancier way of saying "average" for our purposes, since we don't necessarily expect people working on the quiz to have a background in probability
Indeed! "Expected value" is a fancier way of saying "average" for our purposes, since we don't necessarily expect people working on the quiz to have a background in probability
KevinCarde
2021-05-19 19:13:49
The pace that we move through this problem will accelerate as we go through all the parts, but the transcript will be available online shortly after this Math Jam if you'd like more time to puzzle over some of the trickier details.
The pace that we move through this problem will accelerate as we go through all the parts, but the transcript will be available online shortly after this Math Jam if you'd like more time to puzzle over some of the trickier details.
KevinCarde
2021-05-19 19:14:11
Here in Part a, Kai's rolling a 4-sided die, which means there are four outcomes: he rolls 1, 2, 3, or 4. If he rolls a 1, then we're done after 1 roll; for any other roll, we'll need to know how many rolls it takes for the die to disappear starting from 1, 2, or 3 sides. So let's build this up step by step!
Here in Part a, Kai's rolling a 4-sided die, which means there are four outcomes: he rolls 1, 2, 3, or 4. If he rolls a 1, then we're done after 1 roll; for any other roll, we'll need to know how many rolls it takes for the die to disappear starting from 1, 2, or 3 sides. So let's build this up step by step!
KevinCarde
2021-05-19 19:14:31
If Kai rolls a 1-sided die: The die always disappears after 1 roll, so the average number of rolls with a 1-sided die is 1.
If Kai rolls a 1-sided die: The die always disappears after 1 roll, so the average number of rolls with a 1-sided die is 1.
KevinCarde
2021-05-19 19:14:41
What about a 2-sided die? How many rolls on average before it disappears?
What about a 2-sided die? How many rolls on average before it disappears?
KevinCarde
2021-05-19 19:15:11
I'm seeing a bunch of answers between 1 and 2 -- 1 and 2 are both possibilities, so the average number should be between them.
I'm seeing a bunch of answers between 1 and 2 -- 1 and 2 are both possibilities, so the average number should be between them.
sj2015
2021-05-19 19:15:18
1.5
1.5
bronzetruck2016
2021-05-19 19:15:18
$\frac{3}{2}$
$\frac{3}{2}$
physicsbaby
2021-05-19 19:15:18
1.5
1.5
SHZhang
2021-05-19 19:15:18
$\frac{3}{2}$
$\frac{3}{2}$
MirmanStudent08
2021-05-19 19:15:18
1.5
1.5
pritiks
2021-05-19 19:15:18
3/2
3/2
kfcruan
2021-05-19 19:15:18
1.5
1.5
student20201011
2021-05-19 19:15:18
1.5
1.5
KevinCarde
2021-05-19 19:15:29
We'll write this out carefully:
We'll write this out carefully:
KevinCarde
2021-05-19 19:15:53
2-sided die: There's a 50% chance to roll a 1, meaning the die disappears after 1 roll. This contributes 1/2*1 to the average number of rolls. There's a 50% chance to roll a 2, meaning the die becomes 1-sided, and it disappears after one more roll. This contributes 1/2*(1+1) to the average. In total, then, the average number of rolls is 3/2.
2-sided die: There's a 50% chance to roll a 1, meaning the die disappears after 1 roll. This contributes 1/2*1 to the average number of rolls. There's a 50% chance to roll a 2, meaning the die becomes 1-sided, and it disappears after one more roll. This contributes 1/2*(1+1) to the average. In total, then, the average number of rolls is 3/2.
KevinCarde
2021-05-19 19:16:11
What about a 3-sided die?
What about a 3-sided die?
KevinCarde
2021-05-19 19:16:32
(I might not give you quite enough time to compute this from scratch, but hopefully you have a chance to think about it a bit!)
(I might not give you quite enough time to compute this from scratch, but hopefully you have a chance to think about it a bit!)
KevinCarde
2021-05-19 19:16:50
I'm seeing a lot of 2s -- and it's very close to 2, but not quite.
I'm seeing a lot of 2s -- and it's very close to 2, but not quite.
MirmanStudent08
2021-05-19 19:17:05
11/6
11/6
w_aops
2021-05-19 19:17:05
1 + (0 + 1 + 3/2)/3
1 + (0 + 1 + 3/2)/3
SHZhang
2021-05-19 19:17:05
\frac{11}{6}
\frac{11}{6}
SHZhang
2021-05-19 19:17:05
$\frac{11}{6}$
$\frac{11}{6}$
KevinCarde
2021-05-19 19:17:11
3-sided die: Let's list this out quickly:
3-sided die: Let's list this out quickly:
KevinCarde
2021-05-19 19:17:17
* 1/3 chance to roll a 1, and the die disappears. This contributes 1/3*1 to the average.
* 1/3 chance to roll a 1, and the die disappears. This contributes 1/3*1 to the average.
KevinCarde
2021-05-19 19:17:27
* 1/3 chance to roll a 2, and the die becomes 1-sided, which we've computed. This contributes 1/3*(1+1).
* 1/3 chance to roll a 2, and the die becomes 1-sided, which we've computed. This contributes 1/3*(1+1).
KevinCarde
2021-05-19 19:17:40
* 1/3 chance to roll a 3, and the die becomes 2-sided, which we've computed. This contributes 1/3*(1+3/2), where the 3/2 is the average number of rolls for a 2-sided die to disappear.
* 1/3 chance to roll a 3, and the die becomes 2-sided, which we've computed. This contributes 1/3*(1+3/2), where the 3/2 is the average number of rolls for a 2-sided die to disappear.
KevinCarde
2021-05-19 19:17:57
Adding up all these contributions, we get that the average number of rolls is 11/6.
Adding up all these contributions, we get that the average number of rolls is 11/6.
KevinCarde
2021-05-19 19:18:15
(The way w_aops wrote it out is very nice: it was the first roll, then a 1/3 chance each of 0, 1, or 3/2 further rolls!)
(The way w_aops wrote it out is very nice: it was the first roll, then a 1/3 chance each of 0, 1, or 3/2 further rolls!)
KevinCarde
2021-05-19 19:18:38
Okay, now let's actually do part 4. In the interest of time, I'll write it out quickly:
Okay, now let's actually do part 4. In the interest of time, I'll write it out quickly:
KevinCarde
2021-05-19 19:18:48
(Though some of you are beating me to it!)
(Though some of you are beating me to it!)
bronzetruck2016
2021-05-19 19:18:52
$\frac{25}{12}$
$\frac{25}{12}$
MirmanStudent08
2021-05-19 19:18:52
25/12
25/12
KevinCarde
2021-05-19 19:19:00
4-sided die: Computing as before, rolling a 1 contributes 1/4*1, rolling a 2 contributes 1/4*(1+1), rolling a 3 contributes 1/4*(1+3/2), and rolling a 4 contributes 1/4*(1+11/6). Adding them up, we get a final answer of 25/12 rolls.
4-sided die: Computing as before, rolling a 1 contributes 1/4*1, rolling a 2 contributes 1/4*(1+1), rolling a 3 contributes 1/4*(1+3/2), and rolling a 4 contributes 1/4*(1+11/6). Adding them up, we get a final answer of 25/12 rolls.
gordonhero
2021-05-19 19:19:09
1+(0+1+3/2+11/6)/4
1+(0+1+3/2+11/6)/4
KevinCarde
2021-05-19 19:19:23
This is very similar to how we wrote it out, and the analog of what w_aops wrote for 3-sided dice!
This is very similar to how we wrote it out, and the analog of what w_aops wrote for 3-sided dice!
KevinCarde
2021-05-19 19:19:47
If you play with these numbers a bit, you might discover that $25/12 = 1 + 1/2 + 1/3 + 1/4$. Sums of reciprocals like this are called harmonic numbers, and there are several ways to prove that the $N$th harmonic number gives the average number of rolls before an $N$-sided die disappears. Play around with this more later if it seems interesting, but let's keep moving for now!
If you play with these numbers a bit, you might discover that $25/12 = 1 + 1/2 + 1/3 + 1/4$. Sums of reciprocals like this are called harmonic numbers, and there are several ways to prove that the $N$th harmonic number gives the average number of rolls before an $N$-sided die disappears. Play around with this more later if it seems interesting, but let's keep moving for now!
KevinCarde
2021-05-19 19:20:25
So, that's one of our warmups in Part a; now we're going to have Kai start playing games with Helena.
So, that's one of our warmups in Part a; now we're going to have Kai start playing games with Helena.
KevinCarde
2021-05-19 19:20:33
Now Kai is playing a game with Helena. Kai rolls a blue die first (causing it to change shape), then Helena rolls the same blue die (which changes shape again), and then they continue to take turns rolling the same die until one of them rolls a 1. Whoever rolls the 1 loses.
Part b: Suppose the blue die starts with 4 sides. What is the probability that Kai wins?
Part c: Suppose the blue die starts with $N$ sides. What is the probability that Kai wins?
Now Kai is playing a game with Helena. Kai rolls a blue die first (causing it to change shape), then Helena rolls the same blue die (which changes shape again), and then they continue to take turns rolling the same die until one of them rolls a 1. Whoever rolls the 1 loses.
Part b: Suppose the blue die starts with 4 sides. What is the probability that Kai wins?
Part c: Suppose the blue die starts with $N$ sides. What is the probability that Kai wins?
KevinCarde
2021-05-19 19:20:50
Let's define $p(N)$ to be the probability that the first player wins the game with an $N$-sided die.
Let's define $p(N)$ to be the probability that the first player wins the game with an $N$-sided die.
KevinCarde
2021-05-19 19:21:05
Note that I said "first player," not "Kai," because if Kai rolls, say, a 4 on his first roll, then Helena now is acting as if she's the first player in a game with a 3-sided die, so Helena wins with probability $p(3)$ from here, and hence Kai wins this specific case with probability $1 - p(3)$.
Note that I said "first player," not "Kai," because if Kai rolls, say, a 4 on his first roll, then Helena now is acting as if she's the first player in a game with a 3-sided die, so Helena wins with probability $p(3)$ from here, and hence Kai wins this specific case with probability $1 - p(3)$.
KevinCarde
2021-05-19 19:21:38
Okay, let's now try to compute $p(4)$, which is Part b. Like with Part a, let's build this up from smaller values:
Okay, let's now try to compute $p(4)$, which is Part b. Like with Part a, let's build this up from smaller values:
KevinCarde
2021-05-19 19:21:44
What's $p(1)$? In other words, what's the chance Kai wins a game with a 1-sided die?
What's $p(1)$? In other words, what's the chance Kai wins a game with a 1-sided die?
mathy88
2021-05-19 19:22:07
0
0
peace09
2021-05-19 19:22:07
0!
0!
bronzetruck2016
2021-05-19 19:22:07
0
0
gordonhero
2021-05-19 19:22:07
0% I mean
0% I mean
kxiang
2021-05-19 19:22:07
0
0
sj2015
2021-05-19 19:22:07
0
0
SHZhang
2021-05-19 19:22:07
0
0
KevinCarde
2021-05-19 19:22:17
(I'm assuming the "0!" is enthusiasm, not factorial )
(I'm assuming the "0!" is enthusiasm, not factorial
)
KevinCarde
2021-05-19 19:22:30
And yes:
* $p(1) = 0$, as Kai is guaranteed to lose immediately with a 1-sided die.
And yes:
* $p(1) = 0$, as Kai is guaranteed to lose immediately with a 1-sided die.
KevinCarde
2021-05-19 19:22:43
What about $p(2)$?
What about $p(2)$?
w_aops
2021-05-19 19:23:05
1/2
1/2
gordonhero
2021-05-19 19:23:05
50%
50%
bronzetruck2016
2021-05-19 19:23:05
$\frac{1}{2}$
$\frac{1}{2}$
SHZhang
2021-05-19 19:23:05
$\frac{1}{2}$
$\frac{1}{2}$
peace09
2021-05-19 19:23:05
$\tfrac{1}{2}$
$\tfrac{1}{2}$
student20201011
2021-05-19 19:23:05
50
50
sj2015
2021-05-19 19:23:05
1/2
1/2
mathy88
2021-05-19 19:23:17
1/2 either Kai rolls a 1 or gives Helena P(1)
1/2 either Kai rolls a 1 or gives Helena P(1)
KevinCarde
2021-05-19 19:23:23
Great explanation!
Great explanation!
KevinCarde
2021-05-19 19:23:27
* $p(2) = 1/2$, as there's a 50% chance Kai rolls a 1 and loses immediately, and a 50% chance Kai rolls a 2 and hands Helena a 1-sided die, causing her to lose immediately.
* $p(2) = 1/2$, as there's a 50% chance Kai rolls a 1 and loses immediately, and a 50% chance Kai rolls a 2 and hands Helena a 1-sided die, causing her to lose immediately.
KevinCarde
2021-05-19 19:23:41
$p(3)$? (getting trickier...)
$p(3)$? (getting trickier...)
KevinCarde
2021-05-19 19:24:27
I'm seeing some interesting guesses: remember that even if Kai doesn't immediately lose (by rolling a 1), that doesn't necessarily mean he wins
I'm seeing some interesting guesses: remember that even if Kai doesn't immediately lose (by rolling a 1), that doesn't necessarily mean he wins
gordonhero
2021-05-19 19:24:34
1/2
1/2
kxiang
2021-05-19 19:24:34
1/2?
1/2?
bronzetruck2016
2021-05-19 19:24:34
Also $\frac{1}{2}$
Also $\frac{1}{2}$
Lilavigne
2021-05-19 19:24:34
1/2 again
1/2 again
KevinCarde
2021-05-19 19:24:47
I'll write out the full logic:
I'll write out the full logic:
KevinCarde
2021-05-19 19:24:58
* For $p(3)$, there's a 1/3 chance of rolling a 3, handing Helena a 2-sided die, where we already know each player has a 1/2 chance of winning. Then there's a 1/3 chance of rolling a 2, causing Helena to lose instantly, and a 1/3 chance of rolling a 1, causing Kai to lose instantly. Thus $p(3) = 1/3*(1/2 + 1 + 0) = 1/2$.
* For $p(3)$, there's a 1/3 chance of rolling a 3, handing Helena a 2-sided die, where we already know each player has a 1/2 chance of winning. Then there's a 1/3 chance of rolling a 2, causing Helena to lose instantly, and a 1/3 chance of rolling a 1, causing Kai to lose instantly. Thus $p(3) = 1/3*(1/2 + 1 + 0) = 1/2$.
Batee5a
2021-05-19 19:25:06
$1/3*(0+1/2+1)$
$1/3*(0+1/2+1)$
mc21s
2021-05-19 19:25:06
1/3*0+1/3*1+1/3*1/2
1/3*0+1/3*1+1/3*1/2
bronzetruck2016
2021-05-19 19:25:15
You may not send the same message twice in a row
You may not send the same message twice in a row
KevinCarde
2021-05-19 19:25:27
Uh oh, that might be an issue with this problem
Uh oh, that might be an issue with this problem
apricot_sherry
2021-05-19 19:25:35
is it the case that it is 1/2 with any die?
is it the case that it is 1/2 with any die?
KevinCarde
2021-05-19 19:25:42
Hmm, things are getting suspicious, aren't they?
Hmm, things are getting suspicious, aren't they?
KevinCarde
2021-05-19 19:25:53
Indeed, we can do a similar calculation for $p(4)$, and we'll get 1/2
Indeed, we can do a similar calculation for $p(4)$, and we'll get 1/2
mc21s
2021-05-19 19:25:58
1/4(0+1+1/2+1/2)
1/4(0+1+1/2+1/2)
Edelweiss_USA
2021-05-19 19:26:07
It's always(except for 1) $\frac{1}{2}$.
It's always(except for 1) $\frac{1}{2}$.
gordonhero
2021-05-19 19:26:07
$\frac{1}{2}$ wao fun game
$\frac{1}{2}$ wao fun game
KevinCarde
2021-05-19 19:26:13
Fair games are fun! Maybe.
Fair games are fun! Maybe.
KevinCarde
2021-05-19 19:26:32
So we're starting to suspect that, other than $N=1$, it's always a completely fair game: 1/2 chance for Kai to win, 1/2 for Helena.
So we're starting to suspect that, other than $N=1$, it's always a completely fair game: 1/2 chance for Kai to win, 1/2 for Helena.
w_aops
2021-05-19 19:26:34
Induction to prove for all die?
Induction to prove for all die?
KevinCarde
2021-05-19 19:26:51
This was the most popular strategy in the applications, but we'll do some induction later, so we're going to present a different argument.
This was the most popular strategy in the applications, but we'll do some induction later, so we're going to present a different argument.
KevinCarde
2021-05-19 19:27:21
Often in math, if you want to prove that two sets have the same size, you can do this by constructing a bijection between them.
Often in math, if you want to prove that two sets have the same size, you can do this by constructing a bijection between them.
Arcticturn
2021-05-19 19:27:48
what is a bijection
what is a bijection
rickiebosun
2021-05-19 19:27:48
. What's a bijection
. What's a bijection
KevinCarde
2021-05-19 19:28:03
Excellent question!
Excellent question!
mc21s
2021-05-19 19:28:05
1-1 correspondence
1-1 correspondence
KevinCarde
2021-05-19 19:28:34
Yes: a bijection is a way to have a 1 to 1 correspondence between the two sets, so that everything in each set corresponds to exactly one object in the other.
Yes: a bijection is a way to have a 1 to 1 correspondence between the two sets, so that everything in each set corresponds to exactly one object in the other.
KevinCarde
2021-05-19 19:28:52
When working with probability, we can similarly use a bijection to prove that something happens 1/2 the time, but we have to be careful: we have to make sure that our bijection always takes one successful outcome to an equally likely unsuccessful outcome.
When working with probability, we can similarly use a bijection to prove that something happens 1/2 the time, but we have to be careful: we have to make sure that our bijection always takes one successful outcome to an equally likely unsuccessful outcome.
KevinCarde
2021-05-19 19:29:11
So, let's construct a bijection between possible sequences of die rolls where Kai wins and ones where Helena wins, making sure that our bijection preserves probabilities. Any ideas?
So, let's construct a bijection between possible sequences of die rolls where Kai wins and ones where Helena wins, making sure that our bijection preserves probabilities. Any ideas?
KevinCarde
2021-05-19 19:30:07
So I'm seeing some ideas about rolling a 1 vs rolling a 2, and that's a key idea here.
So I'm seeing some ideas about rolling a 1 vs rolling a 2, and that's a key idea here.
gordonhero
2021-05-19 19:30:11
rolling 1 vs rolling a 2
rolling 1 vs rolling a 2
KevinCarde
2021-05-19 19:30:20
That's exactly what I just said
That's exactly what I just said
KevinCarde
2021-05-19 19:30:27
(But gordonhero did say it just before me, I promise)
(But gordonhero did say it just before me, I promise)
KevinCarde
2021-05-19 19:30:48
If, say, Kai rolls a 2 at any point, then Helena automatically loses. However, Kai is just as likely to roll a 1 at that point instead of a 2, causing him to lose.
If, say, Kai rolls a 2 at any point, then Helena automatically loses. However, Kai is just as likely to roll a 1 at that point instead of a 2, causing him to lose.
KevinCarde
2021-05-19 19:30:59
This gives us a pair of equally likely games, one of which Kai wins, and one of which Helena wins.
This gives us a pair of equally likely games, one of which Kai wins, and one of which Helena wins.
KevinCarde
2021-05-19 19:31:13
Similarly, if Helena rolls a 2, this is just as likely as her rolling a 1 at that point, and we get a similar pair of equally likely games.
Similarly, if Helena rolls a 2, this is just as likely as her rolling a 1 at that point, and we get a similar pair of equally likely games.
KevinCarde
2021-05-19 19:31:32
So, that's our bijection: every game that Kai wins is in bijection to an equally likely game where Helena wins, simply by inserting or removing a roll of 2.
So, that's our bijection: every game that Kai wins is in bijection to an equally likely game where Helena wins, simply by inserting or removing a roll of 2.
KevinCarde
2021-05-19 19:31:50
The existence of this bijection immediately proves that $p(N) = 1/2$ for $N \ge 2$!
The existence of this bijection immediately proves that $p(N) = 1/2$ for $N \ge 2$!
KevinCarde
2021-05-19 19:32:13
This kind of argument can be a little tricky if you haven't seen something like it before, so I encourage you to think about it more if you need to.
This kind of argument can be a little tricky if you haven't seen something like it before, so I encourage you to think about it more if you need to.
Batee5a
2021-05-19 19:32:47
and if they roll another number n it can simply be considered as a new game with n-1 sides?
and if they roll another number n it can simply be considered as a new game with n-1 sides?
KevinCarde
2021-05-19 19:33:21
So we're thinking about entire games here: for example, if Kai rolls 5, then Helena 3, then Kai 1, that sequence of rolls has exactly the same probability of occurring as if Kai rolled 5, then Helena 3, then Kai 2, then Helena 1, but now the winner has swapped.
So we're thinking about entire games here: for example, if Kai rolls 5, then Helena 3, then Kai 1, that sequence of rolls has exactly the same probability of occurring as if Kai rolled 5, then Helena 3, then Kai 2, then Helena 1, but now the winner has swapped.
KevinCarde
2021-05-19 19:33:56
You may have some pondering to do, but since we have a lot to cover, we're going to move onwards to some fancier green dice!
You may have some pondering to do, but since we have a lot to cover, we're going to move onwards to some fancier green dice!
KevinCarde
2021-05-19 19:34:05
Kai also has green dice, which work slightly differently from blue dice. When he rolls a green die, it changes shape to have a number of sides equal to the number rolled (so if Kai rolls the maximum possible value, the green die doesn't change shape at all).
Kai also has green dice, which work slightly differently from blue dice. When he rolls a green die, it changes shape to have a number of sides equal to the number rolled (so if Kai rolls the maximum possible value, the green die doesn't change shape at all).
KevinCarde
2021-05-19 19:34:14
Part d: He plays the same game with Helena, but now with an $N$-sided green die; the first player to roll a 1 still loses. What is the probability that Kai wins?
Part d: He plays the same game with Helena, but now with an $N$-sided green die; the first player to roll a 1 still loses. What is the probability that Kai wins?
KevinCarde
2021-05-19 19:34:34
So: green dice are very similar to blue dice, but now the number of sides doesn't automatically decrease.
So: green dice are very similar to blue dice, but now the number of sides doesn't automatically decrease.
KevinCarde
2021-05-19 19:34:55
It's similar to the last game, so we might expect the probability to be close to 1/2, but it's unclear if it'll be exactly 1/2, like it was before.
It's similar to the last game, so we might expect the probability to be close to 1/2, but it's unclear if it'll be exactly 1/2, like it was before.
KevinCarde
2021-05-19 19:35:07
So let's look for a pattern!
So let's look for a pattern!
KevinCarde
2021-05-19 19:35:20
Keeping $p(N)$ as the probability that the first player wins, what's $p(2)$?
Keeping $p(N)$ as the probability that the first player wins, what's $p(2)$?
KevinCarde
2021-05-19 19:35:25
(Already this is a little trickier to compute!)
(Already this is a little trickier to compute!)
bronzetruck2016
2021-05-19 19:35:59
$\frac{1}{3}$
$\frac{1}{3}$
apricot_sherry
2021-05-19 19:36:06
1/3
1/3
Arcticturn
2021-05-19 19:36:06
1/3
1/3
KevinCarde
2021-05-19 19:36:17
We can think of it this way: Kai has a 50% chance of losing immediately, and a 50% chance of handing Helena a 2-sided die, where Helena has by definition a $p(2)$ chance of winning, and thus Kai has a $1-p(2)$ chance of winning.
We can think of it this way: Kai has a 50% chance of losing immediately, and a 50% chance of handing Helena a 2-sided die, where Helena has by definition a $p(2)$ chance of winning, and thus Kai has a $1-p(2)$ chance of winning.
KevinCarde
2021-05-19 19:36:26
Putting it together, $p(2) = 1/2*(0 + 1-p(2))$, or $3/2 p(2) = 1/2$, or $p(2) = 1/3$.
Putting it together, $p(2) = 1/2*(0 + 1-p(2))$, or $3/2 p(2) = 1/2$, or $p(2) = 1/3$.
KevinCarde
2021-05-19 19:36:40
(Sorry for the ugly latex *, my bad!)
(Sorry for the ugly latex *, my bad!)
KevinCarde
2021-05-19 19:36:55
In the interest of time, we won't explicitly compute more values, but we'd get $p(3) = 5/12$ and $p(4) = 9/20$. Notice any pattern?
In the interest of time, we won't explicitly compute more values, but we'd get $p(3) = 5/12$ and $p(4) = 9/20$. Notice any pattern?
MirmanStudent08
2021-05-19 19:37:22
All slightly less than 1/2
All slightly less than 1/2
awesomeguy856
2021-05-19 19:37:22
denominator is n(n-1)
denominator is n(n-1)
kxiang
2021-05-19 19:37:22
Close to $\frac{1}{2}$
Close to $\frac{1}{2}$
fuwa
2021-05-19 19:37:29
always a unit smaller than a half?
always a unit smaller than a half?
bronzetruck2016
2021-05-19 19:37:34
Closer and closer to 2. Maybe $\frac{1}{2}-\frac{1}{(n)(n+1)}$?
Closer and closer to 2. Maybe $\frac{1}{2}-\frac{1}{(n)(n+1)}$?
KevinCarde
2021-05-19 19:37:39
Aha! An explicit conjecture!
Aha! An explicit conjecture!
KevinCarde
2021-05-19 19:37:52
And indeed, bronzetruck2016's formula works with all our examples so far.
And indeed, bronzetruck2016's formula works with all our examples so far.
KevinCarde
2021-05-19 19:38:24
Let's think about Kai's first roll based on whether he rolls $N$ or not:
Let's think about Kai's first roll based on whether he rolls $N$ or not:
apricot_sherry
2021-05-19 19:38:54
isn't it similar to the previous problem with an extra case?
isn't it similar to the previous problem with an extra case?
KevinCarde
2021-05-19 19:39:05
It is, but that extra case -- where we can repeat the number that was just rolled -- makes it pretty tricky!
It is, but that extra case -- where we can repeat the number that was just rolled -- makes it pretty tricky!
KevinCarde
2021-05-19 19:39:09
Okay, back to Kai's first roll:
Okay, back to Kai's first roll:
KevinCarde
2021-05-19 19:39:17
* Kai rolls $N$, which occurs $1/N$ of the time: We're now playing exactly the same game (since the die still has $N$ sides), but now Helena goes first, so Kai wins with probability $(1 - p(N))$.
* Kai rolls $N$, which occurs $1/N$ of the time: We're now playing exactly the same game (since the die still has $N$ sides), but now Helena goes first, so Kai wins with probability $(1 - p(N))$.
KevinCarde
2021-05-19 19:39:41
* Kai rolls something else, which occurs $(N-1)/N$ of the time: In this case, Kai is equally likely to roll each of the numbers 1 through $N-1$. But we have notation for Kai's win chance when he's equally likely to roll $1$ through $N-1$: it's simply $p(N-1)$. So $p(N-1)$ is the chance that Kai wins in this case.
* Kai rolls something else, which occurs $(N-1)/N$ of the time: In this case, Kai is equally likely to roll each of the numbers 1 through $N-1$. But we have notation for Kai's win chance when he's equally likely to roll $1$ through $N-1$: it's simply $p(N-1)$. So $p(N-1)$ is the chance that Kai wins in this case.
KevinCarde
2021-05-19 19:39:54
Putting these together, the total probability that Kai wins is
Putting these together, the total probability that Kai wins is
KevinCarde
2021-05-19 19:40:01
$$
p(N) = \frac{1}{N} (1 - p(N)) + \frac{N-1}{N} p(N-1)
$$
$$
p(N) = \frac{1}{N} (1 - p(N)) + \frac{N-1}{N} p(N-1)
$$
KevinCarde
2021-05-19 19:40:19
This is great, as we can now solve for $p(N)$ in terms of $p(N-1)$!
This is great, as we can now solve for $p(N)$ in terms of $p(N-1)$!
KevinCarde
2021-05-19 19:40:26
$$
p(N) = \frac{1}{N+1} + \frac{N-1}{N+1} p(N-1)
$$
$$
p(N) = \frac{1}{N+1} + \frac{N-1}{N+1} p(N-1)
$$
KevinCarde
2021-05-19 19:41:28
Recurrence relations like this are an excellent place to use induction to prove that it works for all possible values of $N$. If you're unfamiliar with induction, we won't be able to do a full introduction here, but the strategy is to prove a "base case" (generally the smallest value of $N$ we need to show), then prove that if it works for $N-1$, it works for $N$.
Recurrence relations like this are an excellent place to use induction to prove that it works for all possible values of $N$. If you're unfamiliar with induction, we won't be able to do a full introduction here, but the strategy is to prove a "base case" (generally the smallest value of $N$ we need to show), then prove that if it works for $N-1$, it works for $N$.
KevinCarde
2021-05-19 19:41:39
What's our base case?
What's our base case?
gordonhero
2021-05-19 19:42:05
N=1
N=1
bronzetruck2016
2021-05-19 19:42:05
$N=1$
$N=1$
physicsbaby
2021-05-19 19:42:05
n=2
n=2
KevinCarde
2021-05-19 19:42:43
Either $N=1$ or $N=2$ is fine! (As long as you've shown it for both $N=1$ and $N=2$, it doesn't really matter which you choose as your base case.)
Either $N=1$ or $N=2$ is fine! (As long as you've shown it for both $N=1$ and $N=2$, it doesn't really matter which you choose as your base case.)
KevinCarde
2021-05-19 19:43:15
for $N=1$, we have $p(1) = 0$ (since Kai immediately loses), which does agree with bronzetruck2016's conjectured formula (which I've pinned)
for $N=1$, we have $p(1) = 0$ (since Kai immediately loses), which does agree with bronzetruck2016's conjectured formula (which I've pinned)
KevinCarde
2021-05-19 19:43:28
for $N=2$, we computed $p(2) = 1/3$, which also agrees with the formula.
for $N=2$, we computed $p(2) = 1/3$, which also agrees with the formula.
KevinCarde
2021-05-19 19:43:33
Now we must carry out the inductive step: assuming our conjecture is true for $p(N-1)$, show that it's true for $p(N)$.
Now we must carry out the inductive step: assuming our conjecture is true for $p(N-1)$, show that it's true for $p(N)$.
KevinCarde
2021-05-19 19:44:18
So let's plug in $p(N-1) = \frac{1}{2} - \frac{1}{(N-1)*N}$ into our recurrence!
So let's plug in $p(N-1) = \frac{1}{2} - \frac{1}{(N-1)*N}$ into our recurrence!
KevinCarde
2021-05-19 19:44:38
$$
p(N) = \frac{1}{N+1} + \frac{N-1}{N+1} \left(\frac{1}{2} - \frac{1}{(N-1)N}\right)
$$
$$
p(N) = \frac{1}{N+1} + \frac{N-1}{N+1} \left(\frac{1}{2} - \frac{1}{(N-1)N}\right)
$$
llddmmtt1
2021-05-19 19:44:47
why $*$
why $*$
KevinCarde
2021-05-19 19:44:54
I keep being bad at latex -- I just mean multiplication
I keep being bad at latex -- I just mean multiplication
KevinCarde
2021-05-19 19:45:14
We've plugged in $p(N-1)$ and now we can simplify:
We've plugged in $p(N-1)$ and now we can simplify:
KevinCarde
2021-05-19 19:45:16
$$
p(N) = \frac{N+1}{2(N+1)} - \frac{1}{(N+1)N} = \frac{1}{2} - \frac{1}{N(N+1)}
$$
$$
p(N) = \frac{N+1}{2(N+1)} - \frac{1}{(N+1)N} = \frac{1}{2} - \frac{1}{N(N+1)}
$$
KevinCarde
2021-05-19 19:45:26
And that's exactly the formula we wanted to compute for $p(N)$, which completes the inductive step and the proof!
And that's exactly the formula we wanted to compute for $p(N)$, which completes the inductive step and the proof!
KevinCarde
2021-05-19 19:45:58
Okay! If induction is unfamiliar to you, that might have been fast and/or mysterious. But we'll skip induction for this last part
Okay! If induction is unfamiliar to you, that might have been fast and/or mysterious. But we'll skip induction for this last part
KevinCarde
2021-05-19 19:46:04
Part e: Suppose now that Kai and Helena modify their game: the first person to roll one of the numbers 1, 2, …, $k$ loses. If they start with an $N$-sided green die, what is the probability that Kai wins?
Part e: Suppose now that Kai and Helena modify their game: the first person to roll one of the numbers 1, 2, …, $k$ loses. If they start with an $N$-sided green die, what is the probability that Kai wins?
gordonhero
2021-05-19 19:46:33
isn't the base case k now..???
isn't the base case k now..???
KevinCarde
2021-05-19 19:46:41
Yes! That is the key difference in how the math will play out.
Yes! That is the key difference in how the math will play out.
KevinCarde
2021-05-19 19:46:50
If $p(N)$ is Kai's probability of winning in this new game, the exact same logic that led to our recurrence relation still holds as long as $N > k$, and so the exact same recurrence relation holds for $N > k$!
If $p(N)$ is Kai's probability of winning in this new game, the exact same logic that led to our recurrence relation still holds as long as $N > k$, and so the exact same recurrence relation holds for $N > k$!
KevinCarde
2021-05-19 19:47:01
So indeed, the recurrence relation is the same, but our starting point is now $N = k$, not $N=1$.
So indeed, the recurrence relation is the same, but our starting point is now $N = k$, not $N=1$.
KevinCarde
2021-05-19 19:47:12
So since the smallest instance of our recurrence relation writes $p(k+1)$ in terms of $p(k)$, we'll need to know $p(k)$ to get started. What is it?
So since the smallest instance of our recurrence relation writes $p(k+1)$ in terms of $p(k)$, we'll need to know $p(k)$ to get started. What is it?
llddmmtt1
2021-05-19 19:47:45
0?
0?
mayasu
2021-05-19 19:47:45
0
0
gordonhero
2021-05-19 19:47:45
0%
0%
Batee5a
2021-05-19 19:47:45
0
0
physicsbaby
2021-05-19 19:47:45
0
0
KevinCarde
2021-05-19 19:48:01
Right: in this new game, any roll from 1 through $k$ is an instant loss, so Kai cannot survive the first roll of a $k$-sided die!
Right: in this new game, any roll from 1 through $k$ is an instant loss, so Kai cannot survive the first roll of a $k$-sided die!
KevinCarde
2021-05-19 19:48:26
Starting with $p(k) = 0$ and using the recurrence for $p(k+1)$, we see $p(k+1) = 1/(k+2)$, and it gets messier from there. With enough experimentation, we could come up with a correct conjecture, but we're going to use a bit of a trick to simplify our recurrence.
Starting with $p(k) = 0$ and using the recurrence for $p(k+1)$, we see $p(k+1) = 1/(k+2)$, and it gets messier from there. With enough experimentation, we could come up with a correct conjecture, but we're going to use a bit of a trick to simplify our recurrence.
KevinCarde
2021-05-19 19:48:56
In Part d, the answer turned out to be that Kai wins $1/(N(N+1))$ less than a fair game. Inspired by this, let's define $q(N) = 1/2 - p(N)$, so that $q(N)$ measures how far from fair the game is. We can rewrite our recurrence
In Part d, the answer turned out to be that Kai wins $1/(N(N+1))$ less than a fair game. Inspired by this, let's define $q(N) = 1/2 - p(N)$, so that $q(N)$ measures how far from fair the game is. We can rewrite our recurrence
KevinCarde
2021-05-19 19:49:03
$$
p(N) = \frac{1}{N} (1 - p(N)) + \frac{N-1}{N} p(N-1)
$$
$$
p(N) = \frac{1}{N} (1 - p(N)) + \frac{N-1}{N} p(N-1)
$$
KevinCarde
2021-05-19 19:49:10
by substituting $p(N) = 1/2 - q(N)$, and we hope it'll look nicer:
by substituting $p(N) = 1/2 - q(N)$, and we hope it'll look nicer:
KevinCarde
2021-05-19 19:49:20
$$
1/2 - q(N) = \frac{1}{N} (1/2 + q(N)) + \frac{N-1}{N} (1/2 - q(N-1))
$$
$$
1/2 - q(N) = \frac{1}{N} (1/2 + q(N)) + \frac{N-1}{N} (1/2 - q(N-1))
$$
KevinCarde
2021-05-19 19:49:34
And indeed, after simplifying:
$$
q(N) = \frac{N-1}{N+1} q(N-1)
$$
And indeed, after simplifying:
$$
q(N) = \frac{N-1}{N+1} q(N-1)
$$
KevinCarde
2021-05-19 19:50:02
This is fantastic, as we can build up values of $q$ via a telescoping product! Working our way from $q(N)$ down to $q(k) = 1/2$ (corresponding to $p(k) = 0$ that we talked about earlier),
This is fantastic, as we can build up values of $q$ via a telescoping product! Working our way from $q(N)$ down to $q(k) = 1/2$ (corresponding to $p(k) = 0$ that we talked about earlier),
KevinCarde
2021-05-19 19:50:27
(oops, let's try that again)
(oops, let's try that again)
KevinCarde
2021-05-19 19:50:35
$$
q(N) = \frac{(N-1)(N-2) \dots (k+1)k}{(N+1)(N) \dots (k+3)(k+2)} q(k)
$$
$$
q(N) = \frac{(N-1)(N-2) \dots (k+1)k}{(N+1)(N) \dots (k+3)(k+2)} q(k)
$$
KevinCarde
2021-05-19 19:50:44
(whew! better this time )
(whew! better this time
)
KevinCarde
2021-05-19 19:51:08
This is the really fun part where you get to cancel (almost) everything!
This is the really fun part where you get to cancel (almost) everything!
KevinCarde
2021-05-19 19:51:21
And plugging in $q(k) = 1/2$, we end up with
$$
q(N) = \frac{k(k+1)}{N(N+1)} \frac{1}{2}.
$$
And plugging in $q(k) = 1/2$, we end up with
$$
q(N) = \frac{k(k+1)}{N(N+1)} \frac{1}{2}.
$$
KevinCarde
2021-05-19 19:51:36
Since Kai's win probability is $p(N) = 1/2 - q(N)$, we have now shown that this is
Since Kai's win probability is $p(N) = 1/2 - q(N)$, we have now shown that this is
KevinCarde
2021-05-19 19:51:48
$$
p(N) = \frac{1}{2} - \frac{k(k+1)}{2N(N+1)}
$$
$$
p(N) = \frac{1}{2} - \frac{k(k+1)}{2N(N+1)}
$$
KevinCarde
2021-05-19 19:51:52
and we're done!!
and we're done!!
KevinCarde
2021-05-19 19:52:05
No induction needed, because our recurrence in terms of $q$ was so nice
No induction needed, because our recurrence in terms of $q$ was so nice
dan09
2021-05-19 19:52:25
So it is $\frac{k(k+1)}{2N(N+1)}$ from a fair game?
So it is $\frac{k(k+1)}{2N(N+1)}$ from a fair game?
KevinCarde
2021-05-19 19:52:33
Indeed! So it becomes very close to fair as $N$ gets very big
Indeed! So it becomes very close to fair as $N$ gets very big
peace09
2021-05-19 19:52:36
$P(N)=\tfrac{T_n-T_k}{2T_n},$ which is pretty interesting.
$P(N)=\tfrac{T_n-T_k}{2T_n},$ which is pretty interesting.
KevinCarde
2021-05-19 19:52:45
Yes! There are a lot of interesting things to think more about
Yes! There are a lot of interesting things to think more about
KevinCarde
2021-05-19 19:53:01
(There are some really nice ways to go through all this in terms of generating functions, if you've seen those before!)
(There are some really nice ways to go through all this in terms of generating functions, if you've seen those before!)
KevinCarde
2021-05-19 19:53:22
We've had to go quickly, but the transcript will be available online for you to go through the details at a more reasonable pace.
We've had to go quickly, but the transcript will be available online for you to go through the details at a more reasonable pace.
KevinCarde
2021-05-19 19:53:23
But since we have a very finite amount of time tonight, let's pass things on to Sara for Problem 3!
But since we have a very finite amount of time tonight, let's pass things on to Sara for Problem 3!
SMF
2021-05-19 19:53:34
Hi everyone! I’m Sara and I’ll be presenting Problem 3. Here is the problem statement:
Hi everyone! I’m Sara and I’ll be presenting Problem 3. Here is the problem statement:
SMF
2021-05-19 19:53:44
Problem 3: A construction company is designing a new apartment complex. They have an $n \times n$ lot in which each $ 1 \times 1 $ square can either occupy an apartment or a garden.
Problem 3: A construction company is designing a new apartment complex. They have an $n \times n$ lot in which each $ 1 \times 1 $ square can either occupy an apartment or a garden.
SMF
2021-05-19 19:53:48
The apartments must all have a scenic view: if an apartment is not on the edge of the apartment complex, then one of the $4$ adjacent lots must have a garden.
The apartments must all have a scenic view: if an apartment is not on the edge of the apartment complex, then one of the $4$ adjacent lots must have a garden.
SMF
2021-05-19 19:53:52
For reference, consider the first two diagrams below: diagram (i) shows a valid design, while the design in diagram (ii) has one apartment without a scenic view.
For reference, consider the first two diagrams below: diagram (i) shows a valid design, while the design in diagram (ii) has one apartment without a scenic view.
SMF
2021-05-19 19:53:58
SMF
2021-05-19 19:54:17
Problem 3a: What is the minimal number of gardens if $n = 6$?
Problem 3a: What is the minimal number of gardens if $n = 6$?
dan09
2021-05-19 19:54:27
Oh I remember this question, it was my favorite one
Oh I remember this question, it was my favorite one
SMF
2021-05-19 19:54:38
Mine too! That's why I'm happy to be presenting it
Mine too! That's why I'm happy to be presenting it
SMF
2021-05-19 19:55:02
I'm seeing some correct answers already—let's go through the solution together.
I'm seeing some correct answers already—let's go through the solution together.
SMF
2021-05-19 19:55:07
Let's draw a $6 \times 6$ grid:
Let's draw a $6 \times 6$ grid:
SMF
2021-05-19 19:55:11
SMF
2021-05-19 19:55:17
Which squares automatically have scenic views?
Which squares automatically have scenic views?
kxiang
2021-05-19 19:55:36
outside edge
outside edge
kfcruan
2021-05-19 19:55:36
the sides
the sides
CoolCarsOnTheRun
2021-05-19 19:55:36
ones on the border
ones on the border
Lilavigne
2021-05-19 19:55:36
the border
the border
m0bius
2021-05-19 19:55:36
the outer squares
the outer squares
w_aops
2021-05-19 19:55:36
the ones on the border
the ones on the border
m0bius
2021-05-19 19:55:36
the outline
the outline
SMF
2021-05-19 19:55:41
Right! The squares on the outer edge already have scenic views, so we may as well place happy apartments there:
Right! The squares on the outer edge already have scenic views, so we may as well place happy apartments there:
SMF
2021-05-19 19:55:45
SMF
2021-05-19 19:55:54
How many gardens do we need to satisfy the apartments in the inner $4 \times 4$ square? (Some of you beat me to this question.)
How many gardens do we need to satisfy the apartments in the inner $4 \times 4$ square? (Some of you beat me to this question.)
MirmanStudent08
2021-05-19 19:56:16
4
4
kxiang
2021-05-19 19:56:16
4
4
CircleInvert
2021-05-19 19:56:16
4
4
gxxk
2021-05-19 19:56:16
4
4
Arcticturn
2021-05-19 19:56:16
Center 4
Center 4
bronzetruck2016
2021-05-19 19:56:16
4
4
physicsbaby
2021-05-19 19:56:16
4
4
juliankuang
2021-05-19 19:56:16
4
4
Lilavigne
2021-05-19 19:56:16
4
4
CoolCarsOnTheRun
2021-05-19 19:56:16
4
4
w_aops
2021-05-19 19:56:16
4
4
truffle
2021-05-19 19:56:16
4
4
SMF
2021-05-19 19:56:26
Yep! Two ways we can do this are:
Yep! Two ways we can do this are:
SMF
2021-05-19 19:56:33
SMF
2021-05-19 19:56:37
(For an extra challenge, think about why these are the only two ways to minimally satisfy a $4 \times 4$ grid.)
(For an extra challenge, think about why these are the only two ways to minimally satisfy a $4 \times 4$ grid.)
SMF
2021-05-19 19:56:45
So, we've shown that the minimum is at most $4$. A common mistake students made was not showing that the minimum is exactly $4$. Specifically—how can we be sure that $4$ gardens are required? Why can't we satisfy all apartments with $3$ gardens?
So, we've shown that the minimum is at most $4$. A common mistake students made was not showing that the minimum is exactly $4$. Specifically—how can we be sure that $4$ gardens are required? Why can't we satisfy all apartments with $3$ gardens?
peace09
2021-05-19 19:56:53
One for each of the corners!
One for each of the corners!
SMF
2021-05-19 19:56:56
One way to show this is by looking at the corners of the $4 \times 4$ square.
One way to show this is by looking at the corners of the $4 \times 4$ square.
SMF
2021-05-19 19:57:01
SMF
2021-05-19 19:57:07
Can one garden satisfy more than one corner?
Can one garden satisfy more than one corner?
juliankuang
2021-05-19 19:57:21
no
no
bronzetruck2016
2021-05-19 19:57:21
noo
noo
SHZhang
2021-05-19 19:57:21
No!
No!
m0bius
2021-05-19 19:57:21
No
No
truffle
2021-05-19 19:57:21
No
No
fancyamazon
2021-05-19 19:57:21
no
no
Lilavigne
2021-05-19 19:57:21
no
no
SMF
2021-05-19 19:57:26
Right! No garden can satisfy more than one corner, because any two corners have at least two squares between them, and any two squares satisfied by a garden have at most one square between them.
Right! No garden can satisfy more than one corner, because any two corners have at least two squares between them, and any two squares satisfied by a garden have at most one square between them.
SMF
2021-05-19 19:57:31
SMF
2021-05-19 19:57:36
So, we've proven that the minimal number of gardens needed for a $6 \times 6$ apartment complex is $4$.
So, we've proven that the minimal number of gardens needed for a $6 \times 6$ apartment complex is $4$.
CircleInvert
2021-05-19 19:57:39
Do part B first and apply it to part A
Do part B first and apply it to part A
SMF
2021-05-19 19:57:42
Another way to show it is to just use part (b), which we'll prove now.
Another way to show it is to just use part (b), which we'll prove now.
SMF
2021-05-19 19:57:47
Problem 3b: Prove that the number of gardens must be at least $\frac{1}{5} (n-2)^2$.
Problem 3b: Prove that the number of gardens must be at least $\frac{1}{5} (n-2)^2$.
SMF
2021-05-19 19:58:08
We can start by drawing a $n \times n$ grid:
We can start by drawing a $n \times n$ grid:
SMF
2021-05-19 19:58:13
SMF
2021-05-19 19:58:19
Let's start by looking at the $(n-2)^2$ term. What might it represent in terms of this problem?
Let's start by looking at the $(n-2)^2$ term. What might it represent in terms of this problem?
Lilavigne
2021-05-19 19:58:41
the inner square
the inner square
peace09
2021-05-19 19:58:41
The central $n-2$ by $n-2$ grid.
The central $n-2$ by $n-2$ grid.
conantwiz2023
2021-05-19 19:58:41
the number of non-boundary spaces to be covered
the number of non-boundary spaces to be covered
fancyamazon
2021-05-19 19:58:41
the squares not on the borders
the squares not on the borders
CoolCarsOnTheRun
2021-05-19 19:58:41
the number of squares in the non-border lots
the number of squares in the non-border lots
pritiks
2021-05-19 19:58:41
all the squares without the bordering squares
all the squares without the bordering squares
mathy88
2021-05-19 19:58:41
The squares excluding the borders
The squares excluding the borders
SMF
2021-05-19 19:58:48
Right. As in part (a), the outer squares already have a scenic view. So it suffices to place gardens to satisfy the inner squares—and there are $(n-2)^2$ of them.
Right. As in part (a), the outer squares already have a scenic view. So it suffices to place gardens to satisfy the inner squares—and there are $(n-2)^2$ of them.
SMF
2021-05-19 19:58:53
SMF
2021-05-19 19:58:57
Now, where could the $\frac{1}{5}$ come from?
Now, where could the $\frac{1}{5}$ come from?
CoolCarsOnTheRun
2021-05-19 19:59:31
each garden makes at most 5 squares happy
each garden makes at most 5 squares happy
Lilavigne
2021-05-19 19:59:31
the center of a "cross"
the center of a "cross"
dan09
2021-05-19 19:59:31
There are multiple houses that get a scenic view from one garden
There are multiple houses that get a scenic view from one garden
bronzetruck2016
2021-05-19 19:59:31
Each garden "takes care of" at most 5 squares.
Each garden "takes care of" at most 5 squares.
m0bius
2021-05-19 19:59:31
4 spaces for 1 apartment 1/5
4 spaces for 1 apartment 1/5
kxiang
2021-05-19 19:59:31
The number of lots a garden provides scenes to (5)
The number of lots a garden provides scenes to (5)
fancyamazon
2021-05-19 19:59:31
when you place a tree it can at most take care of itself and the edges
when you place a tree it can at most take care of itself and the edges
mathy88
2021-05-19 19:59:31
The garden satisfies 5 spaces, including the square it is in
The garden satisfies 5 spaces, including the square it is in
SMF
2021-05-19 19:59:40
Yes. Each garden satisfies at most $4$ apartments. So, for every $4$ apartments we need at least $1$ garden. So at least $\frac{1}{5}$ of the squares in the inside must be gardens.
Yes. Each garden satisfies at most $4$ apartments. So, for every $4$ apartments we need at least $1$ garden. So at least $\frac{1}{5}$ of the squares in the inside must be gardens.
SMF
2021-05-19 19:59:45
This proves that any valid $n \times n$ apartment complex must have at least $\tfrac{1}{5} (n-2)^2$ gardens.
This proves that any valid $n \times n$ apartment complex must have at least $\tfrac{1}{5} (n-2)^2$ gardens.
SMF
2021-05-19 19:59:52
On to part c!
On to part c!
SMF
2021-05-19 19:59:57
Problem 3c: Prove that it is possible to construct an apartment complex with no more than $\frac{1}{5} n^2$ gardens for any n.
Problem 3c: Prove that it is possible to construct an apartment complex with no more than $\frac{1}{5} n^2$ gardens for any n.
SMF
2021-05-19 20:00:13
This question is asking for a construction. Since we just proved in part (b) that any construction must use at least $\frac{1}{5} (n-2)^2$ gardens, we will have to place the gardens efficiently in order to use only $\frac{1}{5} n^2$ of them.
This question is asking for a construction. Since we just proved in part (b) that any construction must use at least $\frac{1}{5} (n-2)^2$ gardens, we will have to place the gardens efficiently in order to use only $\frac{1}{5} n^2$ of them.
SMF
2021-05-19 20:00:19
In particular, we want to avoid situations where a single apartment has a view of multiple gardens, since those gardens are being “wasted”.
In particular, we want to avoid situations where a single apartment has a view of multiple gardens, since those gardens are being “wasted”.
SMF
2021-05-19 20:00:28
For example, here is an inefficient construction which uses approximately $\frac{1}{4} n^2$ gardens. The apartment highlighted green has a view of $2$ gardens, which is more than strictly necessary.
For example, here is an inefficient construction which uses approximately $\frac{1}{4} n^2$ gardens. The apartment highlighted green has a view of $2$ gardens, which is more than strictly necessary.
SMF
2021-05-19 20:00:33
SMF
2021-05-19 20:00:51
So, how can we lay out the gardens efficiently?
So, how can we lay out the gardens efficiently?
kxiang
2021-05-19 20:01:35
tetrate the crosses.
tetrate the crosses.
CoolCarsOnTheRun
2021-05-19 20:01:35
tesselate the crosses that they affect
tesselate the crosses that they affect
w_aops
2021-05-19 20:01:35
Connect them like jigsaw pieces
Connect them like jigsaw pieces
bronzetruck2016
2021-05-19 20:01:35
"knight's move away"
"knight's move away"
artistic_girl
2021-05-19 20:01:35
tesselate
tesselate
SMF
2021-05-19 20:01:40
Great! We can think about a garden satisfying 4 apartments neighboring it:
Great! We can think about a garden satisfying 4 apartments neighboring it:
SMF
2021-05-19 20:01:53
SMF
2021-05-19 20:02:02
To design a valid apartment complex, all we need to do is place these + shapes so that no square is left uncovered. We can do this by tiling the + shapes in the following way:
To design a valid apartment complex, all we need to do is place these + shapes so that no square is left uncovered. We can do this by tiling the + shapes in the following way:
SMF
2021-05-19 20:02:08
SMF
2021-05-19 20:02:14
Awesome! This is super space efficient. Are we done yet?
Awesome! This is super space efficient. Are we done yet?
bronzetruck2016
2021-05-19 20:02:36
no
no
dan09
2021-05-19 20:02:36
No
No
Lilavigne
2021-05-19 20:02:36
not yet
not yet
mathy88
2021-05-19 20:02:36
No, it isnt a square
No, it isnt a square
kxiang
2021-05-19 20:02:36
No, some might go off the edge
No, some might go off the edge
peace09
2021-05-19 20:02:36
Not yet... this shape isn't a square!
Not yet... this shape isn't a square!
RedFireTruck
2021-05-19 20:02:36
no
no
artistic_girl
2021-05-19 20:02:36
jagged edges
jagged edges
SMF
2021-05-19 20:02:50
Right! We want to place gardens and apartments into a $n \times n$ square, not a blocky blob. When we turn the above configuration into a square, we encounter two problems.
Right! We want to place gardens and apartments into a $n \times n$ square, not a blocky blob. When we turn the above configuration into a square, we encounter two problems.
SMF
2021-05-19 20:02:59
SMF
2021-05-19 20:03:08
(1) Some gardens end up outside the square. We need to be sure that the apartments they used to cover are still OK.
(1) Some gardens end up outside the square. We need to be sure that the apartments they used to cover are still OK.
SMF
2021-05-19 20:03:14
(2) Some gardens are no longer covering $4$ apartments, so we can no longer guarantee the $\frac{1}{5}$ fraction.
(2) Some gardens are no longer covering $4$ apartments, so we can no longer guarantee the $\frac{1}{5}$ fraction.
SMF
2021-05-19 20:03:20
How do we deal with (1)?
How do we deal with (1)?
physicsbaby
2021-05-19 20:04:07
ones they used to cover are on the sides so they are asfe
ones they used to cover are on the sides so they are asfe
physicsbaby
2021-05-19 20:04:07
safe
safe
Batee5a
2021-05-19 20:04:07
nothing, they're already on the edge so they have a view
nothing, they're already on the edge so they have a view
m0bius
2021-05-19 20:04:07
It's okay because all the outer squares have a view
It's okay because all the outer squares have a view
SMF
2021-05-19 20:04:19
Yep—we don’t have to do anything! Any garden which gets cut off would have only covered apartments on the border of the square. But, apartments on the border are already satisfied. Crisis averted!
Yep—we don’t have to do anything! Any garden which gets cut off would have only covered apartments on the border of the square. But, apartments on the border are already satisfied. Crisis averted!
SMF
2021-05-19 20:04:26
Dealing with (2) is a bit trickier. In our above example, when we took a $6 \times 6$ square chunk from the tiling, we ended up with an apartment complex with $8$ gardens. But $\frac{1}{5} 6^2 = 7.2 < 8,$ so we are using too many gardens.
Dealing with (2) is a bit trickier. In our above example, when we took a $6 \times 6$ square chunk from the tiling, we ended up with an apartment complex with $8$ gardens. But $\frac{1}{5} 6^2 = 7.2 < 8,$ so we are using too many gardens.
SMF
2021-05-19 20:04:34
SMF
2021-05-19 20:04:43
So, we'll need to somehow adjust the tiling so that every apartment in our $n \times n$ grid is covered, and only $\frac{1}{5} n^2$ squares are used. How might we go about this?
So, we'll need to somehow adjust the tiling so that every apartment in our $n \times n$ grid is covered, and only $\frac{1}{5} n^2$ squares are used. How might we go about this?
SMF
2021-05-19 20:06:19
Lots of different ideas!
Lots of different ideas!
artistic_girl
2021-05-19 20:06:34
there is a pattern of the spilled over squares
there is a pattern of the spilled over squares
SMF
2021-05-19 20:06:39
One way to solve this problem is to study the + tiling pattern carefully and look for patterns in how the inefficient red + signs "spill over".
One way to solve this problem is to study the + tiling pattern carefully and look for patterns in how the inefficient red + signs "spill over".
SMF
2021-05-19 20:06:43
For each possible remainder of $n \mod 5$, a different pattern emerges. In each case, it can be shown that fewer than $\frac{1}{5} n^2$ gardens are needed.
For each possible remainder of $n \mod 5$, a different pattern emerges. In each case, it can be shown that fewer than $\frac{1}{5} n^2$ gardens are needed.
SMF
2021-05-19 20:06:52
Some of you suggested a different approach which doesn't require casework:
Some of you suggested a different approach which doesn't require casework:
wbender25
2021-05-19 20:07:02
We can translate the gardens and apply the pigeonhole principle.
We can translate the gardens and apply the pigeonhole principle.
kxiang
2021-05-19 20:07:02
shift it over 1
shift it over 1
SMF
2021-05-19 20:07:11
Let's go back to the tiling we had of a $6 \times 6$ square.
Let's go back to the tiling we had of a $6 \times 6$ square.
SMF
2021-05-19 20:07:22
Label each part of the + sign with a $1,2,3,4,$ or $5$:
Label each part of the + sign with a $1,2,3,4,$ or $5$:
SMF
2021-05-19 20:07:27
SMF
2021-05-19 20:07:33
Now back to the full picture:
Now back to the full picture:
SMF
2021-05-19 20:07:52
SMF
2021-05-19 20:08:01
Notice that if we remove the green outlines, there is nothing special about the number $3.$ We can place gardens on any other number and they would satisfy all of the apartments in the grid.
Notice that if we remove the green outlines, there is nothing special about the number $3.$ We can place gardens on any other number and they would satisfy all of the apartments in the grid.
SMF
2021-05-19 20:08:07
SMF
2021-05-19 20:08:14
How can we make a construction with fewer than $\tfrac{1}{5} 6^2$ gardens from here?
How can we make a construction with fewer than $\tfrac{1}{5} 6^2$ gardens from here?
w_aops
2021-05-19 20:09:33
5 as the center
5 as the center
mayasu
2021-05-19 20:09:33
the gardens should be on 4s
the gardens should be on 4s
SHZhang
2021-05-19 20:09:33
Choose the least frequently occurring number and put gardens in squares with that number
Choose the least frequently occurring number and put gardens in squares with that number
SMF
2021-05-19 20:09:47
Right! Here, any number except $3$ appears $7$ times, which is less than $\tfrac{1}{5} 6^2 = 7.2.$ So, for example, we could place gardens on all of the $2$s, which would satisfy all apartments using only $7$ gardens.
Right! Here, any number except $3$ appears $7$ times, which is less than $\tfrac{1}{5} 6^2 = 7.2.$ So, for example, we could place gardens on all of the $2$s, which would satisfy all apartments using only $7$ gardens.
SMF
2021-05-19 20:10:17
(Many of you mentioned that the problem with the previous arrangement of gardens was that we were wasting $4$ gardens on corners. Indeed, this problem goes away when we use a different number as the center of the + sign!)
(Many of you mentioned that the problem with the previous arrangement of gardens was that we were wasting $4$ gardens on corners. Indeed, this problem goes away when we use a different number as the center of the + sign!)
SMF
2021-05-19 20:10:24
This works because of the way we numbered the squares—no matter which number we place the gardens on, all apartments except those on the boundary will be covered.
This works because of the way we numbered the squares—no matter which number we place the gardens on, all apartments except those on the boundary will be covered.
SMF
2021-05-19 20:10:41
SMF
2021-05-19 20:11:22
Note that it's sometimes helpful to put a garden on the edge, even if it's not being used efficiently—that garden can cover apartments not on the edge.
Note that it's sometimes helpful to put a garden on the edge, even if it's not being used efficiently—that garden can cover apartments not on the edge.
SMF
2021-05-19 20:11:29
Now let's analyze the general $n \times n$ case. Let's label the squares of an $n \times n$ grid with the numbers $1, 2, 3, 4, 5$ in the same pattern.
Now let's analyze the general $n \times n$ case. Let's label the squares of an $n \times n$ grid with the numbers $1, 2, 3, 4, 5$ in the same pattern.
SMF
2021-05-19 20:11:35
SMF
2021-05-19 20:11:41
Suppose there are $x_i$ squares labeled $i$ for $1 \leq i \leq 5.$ What is $x_1 + \dots + x_5$?
Suppose there are $x_i$ squares labeled $i$ for $1 \leq i \leq 5.$ What is $x_1 + \dots + x_5$?
peace09
2021-05-19 20:12:27
$x_1 + x_2 + x_3 + x_4 + x_5 = n^2.$
$x_1 + x_2 + x_3 + x_4 + x_5 = n^2.$
bronzetruck2016
2021-05-19 20:12:27
$n^2$
$n^2$
kxiang
2021-05-19 20:12:27
$n^2$
$n^2$
iamhungry
2021-05-19 20:12:27
$n^2$
$n^2$
SMF
2021-05-19 20:12:32
Good, we have $x_1 + \dots + x_5 = n^2.$ Now, let $x_{min}$ be the smallest $x_1, ..., x_5$. What can we say about $x_{min}$?
Good, we have $x_1 + \dots + x_5 = n^2.$ Now, let $x_{min}$ be the smallest $x_1, ..., x_5$. What can we say about $x_{min}$?
robot317
2021-05-19 20:13:40
It is smaller than n^2/5
It is smaller than n^2/5
peace09
2021-05-19 20:13:40
By the Pigeonhole, the largest possible smallest $x_i$ is $\tfrac{n^2}{5}.$
By the Pigeonhole, the largest possible smallest $x_i$ is $\tfrac{n^2}{5}.$
SMF
2021-05-19 20:13:48
Yes! There will exist a number which has $\leq \frac15 n^2 $ squares, and we can place the gardens there.
Yes! There will exist a number which has $\leq \frac15 n^2 $ squares, and we can place the gardens there.
SMF
2021-05-19 20:13:52
For example, if $2$ appears less than $\frac{1}{5} n^2$ times, then our construction would look like this:
For example, if $2$ appears less than $\frac{1}{5} n^2$ times, then our construction would look like this:
SMF
2021-05-19 20:13:57
SMF
2021-05-19 20:14:04
We have a valid construction which uses $\leq \frac15 n^2 $ gardens. We're done with part (c)!
We have a valid construction which uses $\leq \frac15 n^2 $ gardens. We're done with part (c)!
SMF
2021-05-19 20:14:16
Problem 3d: Now suppose that gardens have very tall trees that provide a scenic view to up to $20$ nearby lots. Specifically, if a garden is placed at the center of a $5 \times 5$ square, then every apartment in that square except the four $1 \times 1$ corners will have a scenic view of the garden.
Problem 3d: Now suppose that gardens have very tall trees that provide a scenic view to up to $20$ nearby lots. Specifically, if a garden is placed at the center of a $5 \times 5$ square, then every apartment in that square except the four $1 \times 1$ corners will have a scenic view of the garden.
SMF
2021-05-19 20:14:24
SMF
2021-05-19 20:14:30
In other words, a single garden satisfies the following apartments:
In other words, a single garden satisfies the following apartments:
SMF
2021-05-19 20:14:34
SMF
2021-05-19 20:14:37
What upper and lower bounds can you prove on the number of gardens needed?
What upper and lower bounds can you prove on the number of gardens needed?
SMF
2021-05-19 20:15:00
So the question is asking for two things: an upper bound and a lower bound. Let's unpack that a little bit.
So the question is asking for two things: an upper bound and a lower bound. Let's unpack that a little bit.
SMF
2021-05-19 20:15:05
What does it mean to prove that some number $L$ is a lower bound for this problem?
What does it mean to prove that some number $L$ is a lower bound for this problem?
SwimWithDolphin
2021-05-19 20:15:50
not possible for there to be less than $L$ gardens
not possible for there to be less than $L$ gardens
kxiang
2021-05-19 20:15:50
There will be at least $L$ gardens in any arrangement
There will be at least $L$ gardens in any arrangement
dan09
2021-05-19 20:15:50
There is no setting that has less gardens than $L$, so $L$ is the most optimal setting of gardens
There is no setting that has less gardens than $L$, so $L$ is the most optimal setting of gardens
mayasu
2021-05-19 20:15:50
the least numer of gardebs needed
the least numer of gardebs needed
peace09
2021-05-19 20:15:54
We need at least $L$ gardens to make everyone happy!
We need at least $L$ gardens to make everyone happy!
SMF
2021-05-19 20:15:59
Right, you need to prove that at least $L$ gardens are required to make it work. This is like what we did in 3b, where we proved you need at least $\frac{1}{(n-2)^2}$ gardens to make it work.
Right, you need to prove that at least $L$ gardens are required to make it work. This is like what we did in 3b, where we proved you need at least $\frac{1}{(n-2)^2}$ gardens to make it work.
SMF
2021-05-19 20:16:12
What does it mean to prove that some number $U$ is an upper bound?
What does it mean to prove that some number $U$ is an upper bound?
kxiang
2021-05-19 20:17:16
In any case, there will be at least one arrangement that uses no more than $U$ gardens.
In any case, there will be at least one arrangement that uses no more than $U$ gardens.
robot317
2021-05-19 20:17:16
We can place a max of U number of gardens to make everybody Happy
We can place a max of U number of gardens to make everybody Happy
dan09
2021-05-19 20:17:16
We cannot possibly do worse than $U$, so $U$ is the least optimal setting of gardens
We cannot possibly do worse than $U$, so $U$ is the least optimal setting of gardens
SMF
2021-05-19 20:17:26
Right, you need to show that it's possible to do it using only $U$ gardens. This is like what we did in 3c, where we showed that $\frac{1}{5} n^2$ is an upper bound by showing how to construct a pattern with that many gardens.
Right, you need to show that it's possible to do it using only $U$ gardens. This is like what we did in 3c, where we showed that $\frac{1}{5} n^2$ is an upper bound by showing how to construct a pattern with that many gardens.
SMF
2021-05-19 20:17:44
So part 3d is asking you to do what you did in 3b and 3c, but for this more complicated situation.
So part 3d is asking you to do what you did in 3b and 3c, but for this more complicated situation.
SMF
2021-05-19 20:17:53
Let's start with the most straightforward lower bound, similar to 3b. How many gardens must we use at least, in order to give every apartment in a $n \times n$ grid a scenic view?
Let's start with the most straightforward lower bound, similar to 3b. How many gardens must we use at least, in order to give every apartment in a $n \times n$ grid a scenic view?
mathy88
2021-05-19 20:19:14
(n-2)^2/21
(n-2)^2/21
bronzetruck2016
2021-05-19 20:19:14
$\frac{1}{21}(n-2)^2$
$\frac{1}{21}(n-2)^2$
SwimWithDolphin
2021-05-19 20:19:14
$\frac{(n-2)^2}{21}$?
$\frac{(n-2)^2}{21}$?
SHZhang
2021-05-19 20:19:14
$\frac{1}{21}(n-2)^2$
$\frac{1}{21}(n-2)^2$
Lilavigne
2021-05-19 20:19:14
1/21(n-2)^2
1/21(n-2)^2
ingmom
2021-05-19 20:19:14
(1/21)(n-2)^2
(1/21)(n-2)^2
SMF
2021-05-19 20:19:19
Excellent!
Excellent!
SMF
2021-05-19 20:19:33
The solution is similar to what we did in part (b)—try and apply similar ideas to get this bound.
The solution is similar to what we did in part (b)—try and apply similar ideas to get this bound.
SMF
2021-05-19 20:19:47
Now, let's take a quick look at the upper bound.
Now, let's take a quick look at the upper bound.
SMF
2021-05-19 20:20:17
To prove an upper bound on the minimum number of gardens needed, we need to provide an explicit construction using as few gardens as possible.
To prove an upper bound on the minimum number of gardens needed, we need to provide an explicit construction using as few gardens as possible.
SMF
2021-05-19 20:20:23
What makes this problem tricky is that the shapes don't perfectly tile, unlike the + signs we worked with in part (c).
What makes this problem tricky is that the shapes don't perfectly tile, unlike the + signs we worked with in part (c).
SMF
2021-05-19 20:20:30
SMF
2021-05-19 20:20:37
No matter how we place the shapes, if we try to get them not to overlap, "gaps" will occur (marked red in the above picture).
No matter how we place the shapes, if we try to get them not to overlap, "gaps" will occur (marked red in the above picture).
SMF
2021-05-19 20:20:49
Even if we can't make a perfectly efficient construction, we can get pretty close by letting the shapes slightly overlap:
Even if we can't make a perfectly efficient construction, we can get pretty close by letting the shapes slightly overlap:
SMF
2021-05-19 20:20:56
SMF
2021-05-19 20:21:09
If we use this tiling to place gardens in an $n \times n$ grid, roughly how many gardens do we need? In other words, which upper bound does this idea give us?
If we use this tiling to place gardens in an $n \times n$ grid, roughly how many gardens do we need? In other words, which upper bound does this idea give us?
SwimWithDolphin
2021-05-19 20:22:10
$\frac{n^2}{20}$
$\frac{n^2}{20}$
bronzetruck2016
2021-05-19 20:22:10
$\frac{n^2}{20}$
$\frac{n^2}{20}$
SMF
2021-05-19 20:22:22
Right! It's possible to do a lot of detail-oriented work to get this bound very close to $\frac{1}{20} n^2.$
Right! It's possible to do a lot of detail-oriented work to get this bound very close to $\frac{1}{20} n^2.$
SMF
2021-05-19 20:22:30
It turns out that the nice pigeonhole argument that we had in 3c doesn't quite work any more—I'll leave it as an exercise for you to figure out why. But you can use it to get a construction with $\frac{1}{20} n^2 + 4n - 12$.
It turns out that the nice pigeonhole argument that we had in 3c doesn't quite work any more—I'll leave it as an exercise for you to figure out why. But you can use it to get a construction with $\frac{1}{20} n^2 + 4n - 12$.
SMF
2021-05-19 20:23:12
So let's recap where we are so far in Problem 3d.
So let's recap where we are so far in Problem 3d.
SMF
2021-05-19 20:23:18
We showed that you need at least $\frac{1}{21}(n-2)^2$ gardens.
We showed that you need at least $\frac{1}{21}(n-2)^2$ gardens.
SMF
2021-05-19 20:23:25
We showed that you can definitely do it with $\frac{1}{20} n^2$ plus something linear in $n$.
We showed that you can definitely do it with $\frac{1}{20} n^2$ plus something linear in $n$.
SMF
2021-05-19 20:23:38
That's kind of unsatisfying! It's very different from 3b and 3c, where the leading term in both the upper and the lower bound was $\frac{1}{5}n^2$. So in that case, we basically figured out the true minimum number of gardens required, up to some lower order terms.
That's kind of unsatisfying! It's very different from 3b and 3c, where the leading term in both the upper and the lower bound was $\frac{1}{5}n^2$. So in that case, we basically figured out the true minimum number of gardens required, up to some lower order terms.
SMF
2021-05-19 20:23:45
But here, all we know is that the true minimum is somewhere between $\frac{n^2}{21}$ and $\frac{n^2}{20}$.
But here, all we know is that the true minimum is somewhere between $\frac{n^2}{21}$ and $\frac{n^2}{20}$.
SMF
2021-05-19 20:23:57
There is no easy way to close the gap here, and before Mathcamp staff published this year's Quiz, we also had no clue what the exact growth rate of $(\text{minimum \# gardens})$ should be for this part.
There is no easy way to close the gap here, and before Mathcamp staff published this year's Quiz, we also had no clue what the exact growth rate of $(\text{minimum \# gardens})$ should be for this part.
SMF
2021-05-19 20:24:12
A few students went above and beyond in making progress toward an improved lower bound.
A few students went above and beyond in making progress toward an improved lower bound.
SMF
2021-05-19 20:24:15
Ethan from Vienna, VA improved the lower bound to roughly $\frac{n^2}{20.5}$.
Ethan from Vienna, VA improved the lower bound to roughly $\frac{n^2}{20.5}$.
SMF
2021-05-19 20:24:20
And Kevin from North Potomac, MD as well as Edwin from Cupertino, CA managed to improve the lower bound to roughly $\frac{n^2}{20}$, matching the upper bound up to lower-order terms!
And Kevin from North Potomac, MD as well as Edwin from Cupertino, CA managed to improve the lower bound to roughly $\frac{n^2}{20}$, matching the upper bound up to lower-order terms!
SMF
2021-05-19 20:24:24
Their proofs use different techniques ranging from graph theory and convex geometry to show that there's no way to arrange the tiles perfectly so that each one satisfies more than $20.5$ or $20$ of the apartments.
Their proofs use different techniques ranging from graph theory and convex geometry to show that there's no way to arrange the tiles perfectly so that each one satisfies more than $20.5$ or $20$ of the apartments.
SMF
2021-05-19 20:24:28
All three of these proofs are extremely impressive and creative! They're also quite complicated, so unfortunately, we don't have time to go through them now.
All three of these proofs are extremely impressive and creative! They're also quite complicated, so unfortunately, we don't have time to go through them now.
SMF
2021-05-19 20:25:25
That's it for this problem! If you enjoyed it, you might have fun playing around with different ways the garden can satisfy nearby apartments. For example:
That's it for this problem! If you enjoyed it, you might have fun playing around with different ways the garden can satisfy nearby apartments. For example:
SMF
2021-05-19 20:25:32
SMF
2021-05-19 20:25:38
And now I’ll pass it on to Laura, who’ll talk about the solution to Problem 4.
And now I’ll pass it on to Laura, who’ll talk about the solution to Problem 4.
Ellie1729
2021-05-19 20:25:47
Hi everyone! I’m Laura, and I’ll be presenting the solution to problem 4. Part (b) will require using some inversive geometry, but we don’t need to know too much except that inversion can turn circles into lines and vice versa. We won’t need that for part (a), though, so let’s start with that.
Hi everyone! I’m Laura, and I’ll be presenting the solution to problem 4. Part (b) will require using some inversive geometry, but we don’t need to know too much except that inversion can turn circles into lines and vice versa. We won’t need that for part (a), though, so let’s start with that.
Ellie1729
2021-05-19 20:25:59
Problem 4 Statement:
Let $S$ be a set of $8$ points in the plane. Call a circle abundant if it passes through at least $4$ points of $S$.
Problem 4 Statement:
Let $S$ be a set of $8$ points in the plane. Call a circle abundant if it passes through at least $4$ points of $S$.
Ellie1729
2021-05-19 20:26:10
Part (a): Show that there can be at most $14$ abundant circles.
Part (a): Show that there can be at most $14$ abundant circles.
Ellie1729
2021-05-19 20:26:22
Problem 4a Solution:
Problem 4a Solution:
Ellie1729
2021-05-19 20:26:29
For this part, we can just use a counting argument. We know that a circle can be defined by $3$ points. So how many ways are there to choose $3$ points out of the $8$ points in $S$ to form a circle?
For this part, we can just use a counting argument. We know that a circle can be defined by $3$ points. So how many ways are there to choose $3$ points out of the $8$ points in $S$ to form a circle?
RedFireTruck
2021-05-19 20:26:54
$\binom83=56$
$\binom83=56$
kxiang
2021-05-19 20:26:54
8c3
8c3
CoolCarsOnTheRun
2021-05-19 20:26:54
8c3=56
8c3=56
peace09
2021-05-19 20:26:54
$\tbinom{8}{3}=56.$
$\tbinom{8}{3}=56.$
iamhungry
2021-05-19 20:26:54
$\binom{8}{3}=56$
$\binom{8}{3}=56$
pritiks
2021-05-19 20:26:54
8C3 = 56
8C3 = 56
Ellie1729
2021-05-19 20:27:01
Right! Since we don’t care about order, there are a total of $\binom{8}{3}=\frac{8\cdot 7 \cdot 6}{3\cdot 2 \cdot 1} = 56$ ways to choose $3$ points from $S$. So there are at most $56$ circles formed by points in $S$.
Right! Since we don’t care about order, there are a total of $\binom{8}{3}=\frac{8\cdot 7 \cdot 6}{3\cdot 2 \cdot 1} = 56$ ways to choose $3$ points from $S$. So there are at most $56$ circles formed by points in $S$.
Ellie1729
2021-05-19 20:27:09
However, if some of the circles are abundant, they would be counted multiple times by this, since abundant circles have more than $3$ points on them. How many times has each abundant circle been counted?
However, if some of the circles are abundant, they would be counted multiple times by this, since abundant circles have more than $3$ points on them. How many times has each abundant circle been counted?
kxiang
2021-05-19 20:27:33
4
4
RedFireTruck
2021-05-19 20:27:33
$4$ because 4 points
$4$ because 4 points
stonkpotato
2021-05-19 20:27:33
4
4
iamhungry
2021-05-19 20:27:33
$4$ times
$4$ times
peace09
2021-05-19 20:27:33
$\tbinom{4}{3}=4.$
$\tbinom{4}{3}=4.$
CoolCarsOnTheRun
2021-05-19 20:27:33
4c3=4
4c3=4
artistic_girl
2021-05-19 20:27:33
4
4
Arcticturn
2021-05-19 20:27:33
4
4
Ellie1729
2021-05-19 20:27:42
Yes! Since each abundant circle has at least $4$ points on it, there are at least $\binom{4}{3}=4$ ways to choose $3$ points to define an abundant circle. Thus, we’ve counted each abundant circle at least $4$ times.
Yes! Since each abundant circle has at least $4$ points on it, there are at least $\binom{4}{3}=4$ ways to choose $3$ points to define an abundant circle. Thus, we’ve counted each abundant circle at least $4$ times.
Ellie1729
2021-05-19 20:27:49
Since we counted $56$ circles total and each abundant circle has been counted at least $4$ times, there can be at most $\frac{56}{4} = 14$ abundant circles.
Since we counted $56$ circles total and each abundant circle has been counted at least $4$ times, there can be at most $\frac{56}{4} = 14$ abundant circles.
Ellie1729
2021-05-19 20:28:00
Part (b): Can there be $14$ abundant circles? If not, what is the maximum number possible?
Part (b): Can there be $14$ abundant circles? If not, what is the maximum number possible?
Ellie1729
2021-05-19 20:28:10
To solve this part, we’ll need to know a little about inversion. For the sake of time we won’t go through the proofs here, but let’s review the definition and some key properties of inversion from the handout. You can read through the handout for the proofs.
To solve this part, we’ll need to know a little about inversion. For the sake of time we won’t go through the proofs here, but let’s review the definition and some key properties of inversion from the handout. You can read through the handout for the proofs.
Ellie1729
2021-05-19 20:28:24
Inversion is sort of like “reflection across a circle.” It takes everything inside the circle and swaps it with everything outside the circle. Points on the circle are fixed, and the center of the circle maps to the “point at infinity.” Inversion can distort images in weird ways! Here are some examples of pictures and their inverted images:
Inversion is sort of like “reflection across a circle.” It takes everything inside the circle and swaps it with everything outside the circle. Points on the circle are fixed, and the center of the circle maps to the “point at infinity.” Inversion can distort images in weird ways! Here are some examples of pictures and their inverted images:
Ellie1729
2021-05-19 20:28:33
Ellie1729
2021-05-19 20:28:39
Ellie1729
2021-05-19 20:28:46
Ellie1729
2021-05-19 20:28:53
More formally, the inverse of a point $P$ about a circle with center $O$ and radius $r$ is the point $P’$ on ray $OP$ such that $OP\cdot OP’ = r^2$.
More formally, the inverse of a point $P$ about a circle with center $O$ and radius $r$ is the point $P’$ on ray $OP$ such that $OP\cdot OP’ = r^2$.
Ellie1729
2021-05-19 20:29:02
Ellie1729
2021-05-19 20:29:09
Thus, the closer a point is to the circle, the closer its image will be to the circle. Some more examples of points and their inverted images are shown below.
Thus, the closer a point is to the circle, the closer its image will be to the circle. Some more examples of points and their inverted images are shown below.
Ellie1729
2021-05-19 20:29:17
Ellie1729
2021-05-19 20:29:26
Ellie1729
2021-05-19 20:29:37
The key property of inversion we’ll need here is that it can sometimes swap circles with lines. Let’s be a bit more specific about that, though, because there are a few different cases.
The key property of inversion we’ll need here is that it can sometimes swap circles with lines. Let’s be a bit more specific about that, though, because there are a few different cases.
Ellie1729
2021-05-19 20:29:48
Inversion sends “generalized circles” to “generalized circles,” where “generalized circles” include lines, because they are like circles through the point at infinity.
Inversion sends “generalized circles” to “generalized circles,” where “generalized circles” include lines, because they are like circles through the point at infinity.
Ellie1729
2021-05-19 20:30:01
Let’s say we’re inverting about a circle with center $O$. What should happen to a line through $O$?
Let’s say we’re inverting about a circle with center $O$. What should happen to a line through $O$?
CoolCarsOnTheRun
2021-05-19 20:30:30
it doesn't change
it doesn't change
bronzetruck2016
2021-05-19 20:30:30
Stays the same
Stays the same
RedFireTruck
2021-05-19 20:30:34
it stays the same?
it stays the same?
Ellie1729
2021-05-19 20:30:45
Right! From the definition of inversion, a line through $O$ will be fixed under inversion, so its inverse is the same line through $O$. Every point on the line just goes to another point on the same line.
Right! From the definition of inversion, a line through $O$ will be fixed under inversion, so its inverse is the same line through $O$. Every point on the line just goes to another point on the same line.
peace09
2021-05-19 20:30:50
$O$ Disappears?
$O$ Disappears?
Ellie1729
2021-05-19 20:31:03
Yes! $O$ gets mapped to the "point at infinity."
Yes! $O$ gets mapped to the "point at infinity."
Ellie1729
2021-05-19 20:31:19
But the "point at infinity" gets mapped to $O$.
But the "point at infinity" gets mapped to $O$.
Ellie1729
2021-05-19 20:31:30
Ellie1729
2021-05-19 20:31:40
Okay, what do you think will happen if we invert a circle that doesn’t pass through $O$?
Okay, what do you think will happen if we invert a circle that doesn’t pass through $O$?
RedFireTruck
2021-05-19 20:32:16
it becomes another circle
it becomes another circle
CoolCarsOnTheRun
2021-05-19 20:32:16
becomes another circle
becomes another circle
artistic_girl
2021-05-19 20:32:16
another circle
another circle
SwimWithDolphin
2021-05-19 20:32:16
another circle
another circle
Ellie1729
2021-05-19 20:32:26
Yes! We are starting with a circle that doesn’t pass through either $O$ or the point at infinity, so its inverse also won’t pass through either of those points. Thus, the inverse is still a circle not through point $O$.
Yes! We are starting with a circle that doesn’t pass through either $O$ or the point at infinity, so its inverse also won’t pass through either of those points. Thus, the inverse is still a circle not through point $O$.
Ellie1729
2021-05-19 20:32:35
Ellie1729
2021-05-19 20:32:50
Here are some more examples of how this might look. In each case, the solid circles are images of each other under inversion about the dashed circle. If the starting circle is entirely inside the circle of inversion, its inverse will be entirely outside and vice versa. If the starting circle intersects the circle of inversion, so will its inverse.
Here are some more examples of how this might look. In each case, the solid circles are images of each other under inversion about the dashed circle. If the starting circle is entirely inside the circle of inversion, its inverse will be entirely outside and vice versa. If the starting circle intersects the circle of inversion, so will its inverse.
Ellie1729
2021-05-19 20:33:36
What do we get if instead we invert a circle through $O$?
What do we get if instead we invert a circle through $O$?
CoolCarsOnTheRun
2021-05-19 20:34:09
a line
a line
bronzetruck2016
2021-05-19 20:34:09
Line
Line
SwimWithDolphin
2021-05-19 20:34:09
line?
line?
artistic_girl
2021-05-19 20:34:09
a line
a line
wwwy
2021-05-19 20:34:19
a line
a line
BlueyStudiosYT
2021-05-19 20:34:19
a line
a line
Ellie1729
2021-05-19 20:34:22
Exactly! The inverse of $O$ is the point at infinity, so a circle through $O$ inverts to a “circle” through the point at infinity - that is, a line!
Exactly! The inverse of $O$ is the point at infinity, so a circle through $O$ inverts to a “circle” through the point at infinity - that is, a line!
Ellie1729
2021-05-19 20:34:31
Thus, the inverse of a circle through $O$ is a line not through $O$. Likewise, the inverse of a line not through $O$ is a circle through $O$. This is the way we swap lines with circles!
Thus, the inverse of a circle through $O$ is a line not through $O$. Likewise, the inverse of a line not through $O$ is a circle through $O$. This is the way we swap lines with circles!
Ellie1729
2021-05-19 20:34:45
Ellie1729
2021-05-19 20:34:55
For example, in the picture below, the blue and orange circles invert to lines, because they pass through $O$, while the red circle inverts to a circle, because it doesn’t pass through $O$.
For example, in the picture below, the blue and orange circles invert to lines, because they pass through $O$, while the red circle inverts to a circle, because it doesn’t pass through $O$.
Ellie1729
2021-05-19 20:35:00
Ellie1729
2021-05-19 20:35:13
That covers all our cases! Any questions so far?
That covers all our cases! Any questions so far?
wwwy
2021-05-19 20:35:49
in the first scenario, what does o disappear mean
in the first scenario, what does o disappear mean
Ellie1729
2021-05-19 20:36:08
In all the scenarios, $O$ gets mapped to the point at infinity, which isn't really a point.
In all the scenarios, $O$ gets mapped to the point at infinity, which isn't really a point.
dan09
2021-05-19 20:36:27
$O$ goes to infinity
$O$ goes to infinity
Ellie1729
2021-05-19 20:36:43
Great! Now, onto the solution to part (b).
Great! Now, onto the solution to part (b).
Ellie1729
2021-05-19 20:36:49
Problem 4b Solution:
Problem 4b Solution:
Ellie1729
2021-05-19 20:36:56
We claim that in fact the maximum is not $14$ abundant circles, but $12$. To show this, there are two things we need to prove:
We claim that in fact the maximum is not $14$ abundant circles, but $12$. To show this, there are two things we need to prove:
Ellie1729
2021-05-19 20:37:06
1. Upper bound: More than $12$ abundant circles is not possible.
1. Upper bound: More than $12$ abundant circles is not possible.
Ellie1729
2021-05-19 20:37:16
2. Lower bound: At least $12$ abundant circles is possible.
2. Lower bound: At least $12$ abundant circles is possible.
Ellie1729
2021-05-19 20:37:22
First let’s prove the upper bound. To do so, we’ll think about how many abundant circles can pass through each point in $S$.
First let’s prove the upper bound. To do so, we’ll think about how many abundant circles can pass through each point in $S$.
Ellie1729
2021-05-19 20:37:29
Let’s count the number of point/circle pairs consisting of a point in $S$ and an abundant circle through that point. If we assume there are $14$ abundant circles and we know each abundant circle passes through $4$ points, how many such pairs would there be?
Let’s count the number of point/circle pairs consisting of a point in $S$ and an abundant circle through that point. If we assume there are $14$ abundant circles and we know each abundant circle passes through $4$ points, how many such pairs would there be?
peace09
2021-05-19 20:38:21
56
56
dan09
2021-05-19 20:38:21
$14*4=56$?
$14*4=56$?
Ellie1729
2021-05-19 20:38:40
Right, there would be at least $4\cdot 14 = 56$ pairs. So how many circles must there be through each of the $8$ points, on average?
Right, there would be at least $4\cdot 14 = 56$ pairs. So how many circles must there be through each of the $8$ points, on average?
SwimWithDolphin
2021-05-19 20:39:13
7
7
peace09
2021-05-19 20:39:13
7
7
dan09
2021-05-19 20:39:13
$\frac{56}{8}=7$
$\frac{56}{8}=7$
mayasu
2021-05-19 20:39:13
7?
7?
Ellie1729
2021-05-19 20:39:27
Yes! Since there are $8$ points in $S$, on average each point should be on at least $\frac{56}{8} = 7$ abundant circles. In particular, some point would have to be on at least $7$ abundant circles.
Yes! Since there are $8$ points in $S$, on average each point should be on at least $\frac{56}{8} = 7$ abundant circles. In particular, some point would have to be on at least $7$ abundant circles.
Ellie1729
2021-05-19 20:39:40
However, we’ll show that this isn’t possible. Instead, we claim that each point can be on at most $6$ abundant circles. How many point/circle pairs and how many abundant circles would that give us, at most?
However, we’ll show that this isn’t possible. Instead, we claim that each point can be on at most $6$ abundant circles. How many point/circle pairs and how many abundant circles would that give us, at most?
RedFireTruck
2021-05-19 20:40:16
$12$
$12$
bronzetruck2016
2021-05-19 20:40:16
12
12
Noah23
2021-05-19 20:40:16
48
48
artistic_girl
2021-05-19 20:40:16
48
48
mayasu
2021-05-19 20:40:16
48
48
peace09
2021-05-19 20:40:16
48
48
kxiang
2021-05-19 20:40:16
48
48
CoolCarsOnTheRun
2021-05-19 20:40:21
48 and 12
48 and 12
dan09
2021-05-19 20:40:21
That would be $6*8=48$
That would be $6*8=48$
Ellie1729
2021-05-19 20:40:55
Exactly! If each of the $8$ points is on at most $6$ circles, there are at most $6 \cdot 8 = 48$ point-circle pairs. Since each abundant circle contains at least $4$ points, there can be at most $\frac{48}{4} = 12$ abundant circles.
Exactly! If each of the $8$ points is on at most $6$ circles, there are at most $6 \cdot 8 = 48$ point-circle pairs. Since each abundant circle contains at least $4$ points, there can be at most $\frac{48}{4} = 12$ abundant circles.
dan09
2021-05-19 20:41:10
But we need to prove that each point can be on at most $6$ abundant circles
But we need to prove that each point can be on at most $6$ abundant circles
Ellie1729
2021-05-19 20:41:14
Right!
Right!
Ellie1729
2021-05-19 20:41:20
To prove our claim that each point is on at most $6$ abundant circles, let’s imagine inverting about a circle centered at one of the points. After inversion, what will happen to the abundant circles that don’t pass through that point?
To prove our claim that each point is on at most $6$ abundant circles, let’s imagine inverting about a circle centered at one of the points. After inversion, what will happen to the abundant circles that don’t pass through that point?
kxiang
2021-05-19 20:42:01
still are circles
still are circles
CircleInvert
2021-05-19 20:42:01
They remain circles
They remain circles
artistic_girl
2021-05-19 20:42:01
another circle
another circle
peace09
2021-05-19 20:42:01
They will become... Circles
They will become... Circles
llddmmtt1
2021-05-19 20:42:01
becomes another circle?
becomes another circle?
Ellie1729
2021-05-19 20:42:12
Right! These are circles not through the center of inversion, so they’ll stay circles.
Right! These are circles not through the center of inversion, so they’ll stay circles.
Ellie1729
2021-05-19 20:42:20
What about the abundant circles that do pass through our point?
What about the abundant circles that do pass through our point?
CoolCarsOnTheRun
2021-05-19 20:42:36
become lines
become lines
artistic_girl
2021-05-19 20:42:36
lines
lines
bronzetruck2016
2021-05-19 20:42:36
line
line
dan09
2021-05-19 20:42:36
become a line?
become a line?
wwwy
2021-05-19 20:42:36
line
line
kxiang
2021-05-19 20:42:36
turns into lines
turns into lines
llddmmtt1
2021-05-19 20:42:36
become a line
become a line
BlueyStudiosYT
2021-05-19 20:42:36
they become a straight line
they become a straight line
Batee5a
2021-05-19 20:42:41
Turns to lines!
Turns to lines!
Ellie1729
2021-05-19 20:42:50
Yes! These circles pass through the center of inversion, so they’ll invert to lines, each containing the images of at least $3$ of the $7$ remaining points.
Yes! These circles pass through the center of inversion, so they’ll invert to lines, each containing the images of at least $3$ of the $7$ remaining points.
Ellie1729
2021-05-19 20:42:59
So we can now rephrase our claim as follows:
So we can now rephrase our claim as follows:
Ellie1729
2021-05-19 20:43:06
Claim: Through $7$ points, we can draw at most $6$ lines such that each line contains $3$ of the points.
Claim: Through $7$ points, we can draw at most $6$ lines such that each line contains $3$ of the points.
Ellie1729
2021-05-19 20:43:20
Proof: First, we claim that there can be at most $7$ such lines.
Proof: First, we claim that there can be at most $7$ such lines.
Ellie1729
2021-05-19 20:43:31
This uses a similar argument as in part (a). How many lines can there be that pass through at least $2$ of the $7$ points?
This uses a similar argument as in part (a). How many lines can there be that pass through at least $2$ of the $7$ points?
peace09
2021-05-19 20:44:15
$\tbinom{7}{2}=21.$
$\tbinom{7}{2}=21.$
artistic_girl
2021-05-19 20:44:15
21
21
CoolCarsOnTheRun
2021-05-19 20:44:15
7c2=21
7c2=21
wwwy
2021-05-19 20:44:19
21?
21?
Ellie1729
2021-05-19 20:44:26
Right, there are $\binom{7}{2}=21$ ways to choose $2$ of the $7$ points, and any $2$ points define a line, giving at most $21$ lines passing through at least $2$ of the points.
Right, there are $\binom{7}{2}=21$ ways to choose $2$ of the $7$ points, and any $2$ points define a line, giving at most $21$ lines passing through at least $2$ of the points.
Ellie1729
2021-05-19 20:44:46
If a line passes through $3$ points, it would be counted $\binom{3}{2} = 3$ times by this, so there can be at most $\frac{21}{3} = 7$ such lines.
If a line passes through $3$ points, it would be counted $\binom{3}{2} = 3$ times by this, so there can be at most $\frac{21}{3} = 7$ such lines.
Ellie1729
2021-05-19 20:44:57
Note that this actually gives us an alternate proof of part (a)! We’ve shown that each point is on at most $7$ abundant circles, which makes at most $8\cdot 7 = 56$ point-circle pairs, and so at most $\frac{56}{4} = 14$ abundant circles.
Note that this actually gives us an alternate proof of part (a)! We’ve shown that each point is on at most $7$ abundant circles, which makes at most $8\cdot 7 = 56$ point-circle pairs, and so at most $\frac{56}{4} = 14$ abundant circles.
Ellie1729
2021-05-19 20:45:14
One way to complete the proof from here is using the Sylvester-Gallai theorem, which says that for any finite set of points in the plane, there must be a line through all of them or a line through exactly $2$ of them.
One way to complete the proof from here is using the Sylvester-Gallai theorem, which says that for any finite set of points in the plane, there must be a line through all of them or a line through exactly $2$ of them.
Ellie1729
2021-05-19 20:45:29
The only way we could have gotten $7$ lines above is if every line containing $2$ of the points actually contains $3$ of them. By the Sylvester-Gallai theorem, that can’t happen, so there can be at most $6$ such lines.
The only way we could have gotten $7$ lines above is if every line containing $2$ of the points actually contains $3$ of them. By the Sylvester-Gallai theorem, that can’t happen, so there can be at most $6$ such lines.
dan09
2021-05-19 20:46:17
*What is the proof of that theorem?
*What is the proof of that theorem?
Ellie1729
2021-05-19 20:46:36
We won't have time to go through that here, but you can look it up after class if you're interested!
We won't have time to go through that here, but you can look it up after class if you're interested!
Ellie1729
2021-05-19 20:46:52
However, if you’re not familiar with that theorem, another way to prove this is by drawing a picture and thinking carefully about how the points and lines could be positioned.
However, if you’re not familiar with that theorem, another way to prove this is by drawing a picture and thinking carefully about how the points and lines could be positioned.
Ellie1729
2021-05-19 20:47:00
If there were $7$ lines, like we saw above, each of them would have to contain exactly $3$ of the points. Likewise, each of the $7$ points would have to lie on exactly $3$ of the lines.
If there were $7$ lines, like we saw above, each of them would have to contain exactly $3$ of the points. Likewise, each of the $7$ points would have to lie on exactly $3$ of the lines.
Ellie1729
2021-05-19 20:47:13
Let’s say $A$ is the leftmost point, $B$ is the farthest point from $A$ on the top line, and $C$ is the farthest from $A$ on the bottom line. Then we will get something like the picture below:
Let’s say $A$ is the leftmost point, $B$ is the farthest point from $A$ on the top line, and $C$ is the farthest from $A$ on the bottom line. Then we will get something like the picture below:
Ellie1729
2021-05-19 20:47:18
Ellie1729
2021-05-19 20:47:25
Because of how we defined the points, there must be a third point $E$ in our set on line $AB$ between $A$ and $B$ and a third point $G$ in our set on line $AC$ between $A$ and $C$.
Because of how we defined the points, there must be a third point $E$ in our set on line $AB$ between $A$ and $B$ and a third point $G$ in our set on line $AC$ between $A$ and $C$.
Ellie1729
2021-05-19 20:47:35
There also has to be a point $F$ in our set where line $BC$ intersects the third line through $A$. Finally, lines $BG$, $CE$, and $AF$ must all meet at the final point $D$ in our set.
There also has to be a point $F$ in our set where line $BC$ intersects the third line through $A$. Finally, lines $BG$, $CE$, and $AF$ must all meet at the final point $D$ in our set.
Ellie1729
2021-05-19 20:47:49
But we can now see that there’s no way for the three points $E, G,$ and $F$ to lie on a line, because $F$ is on the wrong side of $D$ from $E$ and $G$! Thus, there’s no way to add a $7$th line to the picture that passes through $3$ of the points.
But we can now see that there’s no way for the three points $E, G,$ and $F$ to lie on a line, because $F$ is on the wrong side of $D$ from $E$ and $G$! Thus, there’s no way to add a $7$th line to the picture that passes through $3$ of the points.
Ellie1729
2021-05-19 20:48:02
Another way to prove this is using Ceva’s Theorem and Menelaus's Theorem. Ceva’s Theorem tells us that if the lines $AF$, $BG$, and $CE$ are concurrent, then $$\frac{AG}{GC} \cdot \frac{CF}{FB} \cdot \frac{BE}{EA} = 1.$$
Another way to prove this is using Ceva’s Theorem and Menelaus's Theorem. Ceva’s Theorem tells us that if the lines $AF$, $BG$, and $CE$ are concurrent, then $$\frac{AG}{GC} \cdot \frac{CF}{FB} \cdot \frac{BE}{EA} = 1.$$
Ellie1729
2021-05-19 20:48:13
But Menalaus’s Theorem tells us that if the points $G, F,$ and $E$ are collinear, then $$\frac{AG}{GC} \cdot \frac{CF}{FB} \cdot \frac{BE}{EA} = -1.$$ We’re using directed lengths here, which is why the product can be negative.
But Menalaus’s Theorem tells us that if the points $G, F,$ and $E$ are collinear, then $$\frac{AG}{GC} \cdot \frac{CF}{FB} \cdot \frac{BE}{EA} = -1.$$ We’re using directed lengths here, which is why the product can be negative.
Ellie1729
2021-05-19 20:48:26
The same product can’t equal both $1$ and $-1$, so we’re done!
The same product can’t equal both $1$ and $-1$, so we’re done!
Ellie1729
2021-05-19 20:48:37
This proves our claim, so we’re done with the upper bound! Any questions so far?
This proves our claim, so we’re done with the upper bound! Any questions so far?
kfcruan
2021-05-19 20:48:55
what is the menalaus's theorm
what is the menalaus's theorm
Ellie1729
2021-05-19 20:49:27
It gives a condition for when three points are collinear, using ratios like above.
It gives a condition for when three points are collinear, using ratios like above.
kfcruan
2021-05-19 20:49:31
what is the Ceva theorm
what is the Ceva theorm
Ellie1729
2021-05-19 20:49:50
Ceva's Theorem gives a condition for when three lines are concurrent, using the product of ratios above.
Ceva's Theorem gives a condition for when three lines are concurrent, using the product of ratios above.
wwwy
2021-05-19 20:49:54
what do you mean by directed lengths
what do you mean by directed lengths
Ellie1729
2021-05-19 20:50:31
Directed lengths basically mean line segments are assigned a direction and can be positive or negative depending on which direction they're in.
Directed lengths basically mean line segments are assigned a direction and can be positive or negative depending on which direction they're in.
mayasu
2021-05-19 20:50:42
what does concurrent mean?
what does concurrent mean?
Ellie1729
2021-05-19 20:50:50
Concurrent means the lines pass through the same point.
Concurrent means the lines pass through the same point.
Batee5a
2021-05-19 20:51:06
Are there any recommended sources to check up on these theorems and practice with them?
Are there any recommended sources to check up on these theorems and practice with them?
Ellie1729
2021-05-19 20:51:31
I think there is probably some information about them on the Aops website, or you can try googling them!
I think there is probably some information about them on the Aops website, or you can try googling them!
wwwy
2021-05-19 20:51:54
so which direction yields negative sign
so which direction yields negative sign
Ellie1729
2021-05-19 20:52:07
You get to choose the direction, you just have to be consistent about it.
You get to choose the direction, you just have to be consistent about it.
dan09
2021-05-19 20:52:37
But all we did is prove there isn't 7 lines, not that there is 6 lines
But all we did is prove there isn't 7 lines, not that there is 6 lines
Ellie1729
2021-05-19 20:52:51
That's true! All we've shown so far is that there can be at most $12$ abundant circles.
That's true! All we've shown so far is that there can be at most $12$ abundant circles.
Ellie1729
2021-05-19 20:53:11
So to finish the problem, we need to show that $12$ abundant circles actually is possible!
So to finish the problem, we need to show that $12$ abundant circles actually is possible!
Ellie1729
2021-05-19 20:53:36
For the lower bound, we need an example of how we can have $12$ abundant circles. There are a couple possible constructions here.
For the lower bound, we need an example of how we can have $12$ abundant circles. There are a couple possible constructions here.
Ellie1729
2021-05-19 20:53:43
For the construction we’ll show here, we’ll use inversion through a point in $S$ again. This means we’ll start with $7$ points, and either lines through $3$ of the points or circles through $4$ of the points will become abundant circles after inversion.
For the construction we’ll show here, we’ll use inversion through a point in $S$ again. This means we’ll start with $7$ points, and either lines through $3$ of the points or circles through $4$ of the points will become abundant circles after inversion.
Ellie1729
2021-05-19 20:53:54
Our construction is to use a triangle, the feet of its altitudes, and its orthocenter as our points.
Our construction is to use a triangle, the feet of its altitudes, and its orthocenter as our points.
Ellie1729
2021-05-19 20:53:59
Ellie1729
2021-05-19 20:54:05
How many circles are there that pass through at least $4$ of these points?
How many circles are there that pass through at least $4$ of these points?
RedFireTruck
2021-05-19 20:54:50
6 because 6 cyclic quads?
6 because 6 cyclic quads?
bronzetruck2016
2021-05-19 20:54:50
6
6
artistic_girl
2021-05-19 20:54:50
6
6
kxiang
2021-05-19 20:54:50
6?
6?
CircleInvert
2021-05-19 20:54:50
6
6
Ellie1729
2021-05-19 20:55:02
Right! There are $6$ abundant circles in this picture, specifically $ADHF, CFHE, BEHD, AFEB, BDFC,$ and $CEDA$. We can show each of these is cyclic because they all have two right angles that would be inscribed in the either same arc or opposite arcs.
Right! There are $6$ abundant circles in this picture, specifically $ADHF, CFHE, BEHD, AFEB, BDFC,$ and $CEDA$. We can show each of these is cyclic because they all have two right angles that would be inscribed in the either same arc or opposite arcs.
Ellie1729
2021-05-19 20:55:16
And how many lines are there through at least $3$ of the points?
And how many lines are there through at least $3$ of the points?
RedFireTruck
2021-05-19 20:55:54
6
6
Irving1004
2021-05-19 20:55:54
6
6
Ellie1729
2021-05-19 20:56:08
Exactly, there are $6$ such lines: the three sides of the triangle and the three altitudes.
Exactly, there are $6$ such lines: the three sides of the triangle and the three altitudes.
Ellie1729
2021-05-19 20:56:15
So when we invert this picture, we’ll get $6 + 6 = 12$ abundant circles. That proves our lower bound!
So when we invert this picture, we’ll get $6 + 6 = 12$ abundant circles. That proves our lower bound!
Ellie1729
2021-05-19 20:56:24
Any questions on Problem 4?
Any questions on Problem 4?
dan09
2021-05-19 20:56:31
Yay, we did it!
Yay, we did it!
mayasu
2021-05-19 20:56:39
i thought it was 8 pts?
i thought it was 8 pts?
Ellie1729
2021-05-19 20:57:08
Right. The 8th point is the one we're inverting about. So in our original picture with the triangle it's actually at the point at infinity.
Right. The 8th point is the one we're inverting about. So in our original picture with the triangle it's actually at the point at infinity.
peace09
2021-05-19 20:57:15
No, but what a nice problem!
No, but what a nice problem!
Ellie1729
2021-05-19 20:57:19
I think so too
I think so too
avasireddy056
2021-05-19 20:57:32
about how many lines are through at least 3 of the points
about how many lines are through at least 3 of the points
Ellie1729
2021-05-19 20:57:53
I meant on the picture with the triangle, how many lines pass through 3 of the 7 labelled points.
I meant on the picture with the triangle, how many lines pass through 3 of the 7 labelled points.
Ellie1729
2021-05-19 20:58:14
Each of those lines also passes through the point at infinity and so will invert to an abundant circle.
Each of those lines also passes through the point at infinity and so will invert to an abundant circle.
Ellie1729
2021-05-19 20:58:50
Alright! On to Problem 5!
Alright! On to Problem 5!
MiraBernstein
2021-05-19 20:59:00
Hi everyone, I’m Mira. I’m going to present the solution to Problem #5.
Hi everyone, I’m Mira. I’m going to present the solution to Problem #5.
MiraBernstein
2021-05-19 20:59:07
Before I start, I should say that this Math Jam is taking a bit longer than we were expecting. The problems are long and complicated (as you might have noticed when you tried to solve them for the Mathcamp application).
Before I start, I should say that this Math Jam is taking a bit longer than we were expecting. The problems are long and complicated (as you might have noticed when you tried to solve them for the Mathcamp application).
MiraBernstein
2021-05-19 20:59:17
But we definitely expect to be done by about 7 PT/ 10 ET, hopefully earlier. If you need to go before then, you can find the transcript later at https://www.mathcamp.org/qualifying_quiz/solutions/ (or just on the Math Jams archive: https://artofproblemsolving.com/school/mathjams-transcripts).
But we definitely expect to be done by about 7 PT/ 10 ET, hopefully earlier. If you need to go before then, you can find the transcript later at https://www.mathcamp.org/qualifying_quiz/solutions/ (or just on the Math Jams archive: https://artofproblemsolving.com/school/mathjams-transcripts).
MiraBernstein
2021-05-19 20:59:26
OK, on to Problem 5!
OK, on to Problem 5!
MiraBernstein
2021-05-19 20:59:42
Problem 5, Part a (paraphrased for brevity):
A small town of 192 people has exactly 2 people with COVID19. We want to find them. Instead of testing everyone individually, we can test up to 32 people at once in a “pooled sample”. If the test comes out negative, none of the people in the pooled sample are sick. If the test comes out positive, one or more of the people are sick, but you don’t know who or how many. Can you find the town’s 2 sick people using 16 tests?
Problem 5, Part a (paraphrased for brevity):
A small town of 192 people has exactly 2 people with COVID19. We want to find them. Instead of testing everyone individually, we can test up to 32 people at once in a “pooled sample”. If the test comes out negative, none of the people in the pooled sample are sick. If the test comes out positive, one or more of the people are sick, but you don’t know who or how many. Can you find the town’s 2 sick people using 16 tests?
MiraBernstein
2021-05-19 20:59:54
Let’s show that the answer is “yes” by finding an algorithm that works. What’s our first step?
Let’s show that the answer is “yes” by finding an algorithm that works. What’s our first step?
Lilavigne
2021-05-19 21:00:35
separate into groups of 32
separate into groups of 32
artistic_girl
2021-05-19 21:00:35
test 32 people
test 32 people
mayasu
2021-05-19 21:00:48
separate 192 into groups of 32
separate 192 into groups of 32
MiraBernstein
2021-05-19 21:00:51
OK, we’ve divided the 192 people into 6 groups of 32 and tested each group. This used up 6 tests. What are the two possible outcomes?
OK, we’ve divided the 192 people into 6 groups of 32 and tested each group. This used up 6 tests. What are the two possible outcomes?
SHZhang
2021-05-19 21:01:34
One test positive, or 2 tests are positive
One test positive, or 2 tests are positive
Rubikscube3.1415
2021-05-19 21:01:34
1 yes, 2 yeses
1 yes, 2 yeses
bronzetruck2016
2021-05-19 21:01:34
Same group or different group
Same group or different group
artistic_girl
2021-05-19 21:01:34
both in the same group or 2 groups
both in the same group or 2 groups
CoolCarsOnTheRun
2021-05-19 21:01:34
only one group is positive or two groups test positive
only one group is positive or two groups test positive
wwwy
2021-05-19 21:01:34
two positive in one pool or two positive in two pools
two positive in one pool or two positive in two pools
kxiang
2021-05-19 21:01:34
two or one groups are positive
two or one groups are positive
Batee5a
2021-05-19 21:01:34
2 separate positives or both being in the same group
2 separate positives or both being in the same group
twotothetenthis1024
2021-05-19 21:01:34
one group tests positive or two groups
one group tests positive or two groups
gordonhero
2021-05-19 21:01:34
2 positive groups or 1 positive group
2 positive groups or 1 positive group
MiraBernstein
2021-05-19 21:01:41
Right, we have two cases:
A) two groups test positive, which means they have one sick person each;
B) one group tests positive, which means it has both of the sick people.
Right, we have two cases:
A) two groups test positive, which means they have one sick person each;
B) one group tests positive, which means it has both of the sick people.
MiraBernstein
2021-05-19 21:01:49
Let’s deal with case A first. Time for a lemma!
Let’s deal with case A first. Time for a lemma!
MiraBernstein
2021-05-19 21:01:56
Lemma 1: If you know that a group of $2^n$ has exactly one sick person, you can find that person with $n$ tests.
Lemma 1: If you know that a group of $2^n$ has exactly one sick person, you can find that person with $n$ tests.
MiraBernstein
2021-05-19 21:02:05
Proof: Split your $2^n$ people in half and test the first half. The result of the test tells you whether the sick person is in that half or in the other half.
Proof: Split your $2^n$ people in half and test the first half. The result of the test tells you whether the sick person is in that half or in the other half.
MiraBernstein
2021-05-19 21:02:13
In either case, you’ve used 1 test to narrow down your list of ``suspects” from $2^n$ to $2^{n-1}$. Keep going this way, and you’ll use $n$ tests to narrow it down to 1 person -- the sick one. QED
In either case, you’ve used 1 test to narrow down your list of ``suspects” from $2^n$ to $2^{n-1}$. Keep going this way, and you’ll use $n$ tests to narrow it down to 1 person -- the sick one. QED
wwwy
2021-05-19 21:02:22
I use binary
I use binary
MiraBernstein
2021-05-19 21:02:28
Exactly!
Exactly!
MiraBernstein
2021-05-19 21:02:34
(For those who know some CS: this is just binary search. For those who know induction: this is basically a proof by induction, but it’s such a simple case that I skipped the formalism. The next proof will be more formal.)
(For those who know some CS: this is just binary search. For those who know induction: this is basically a proof by induction, but it’s such a simple case that I skipped the formalism. The next proof will be more formal.)
MiraBernstein
2021-05-19 21:02:45
Getting back to our situation: If two of your 6 groups of 32 test positive, you’ll need 5 more tests to find the sick person in each group. So how many tests have you used in total?
Getting back to our situation: If two of your 6 groups of 32 test positive, you’ll need 5 more tests to find the sick person in each group. So how many tests have you used in total?
bronzetruck2016
2021-05-19 21:03:15
16!!!
16!!!
Rubikscube3.1415
2021-05-19 21:03:15
16, so it works
16, so it works
gordonhero
2021-05-19 21:03:15
16 tests
16 tests
twotothetenthis1024
2021-05-19 21:03:15
16
16
MiraBernstein
2021-05-19 21:03:22
Yup, $32 = 2^5$, so we’ll need 5 tests for each group that tested positive. So we can find the two sick people using $6+5+5 = 16$ tests, as required.
Yup, $32 = 2^5$, so we’ll need 5 tests for each group that tested positive. So we can find the two sick people using $6+5+5 = 16$ tests, as required.
MiraBernstein
2021-05-19 21:03:34
Now let’s do case B: both sick people are in the same group of 32.
Time for another lemma! This one is a little more complicated, so I’ll use formal induction:
Now let’s do case B: both sick people are in the same group of 32.
Time for another lemma! This one is a little more complicated, so I’ll use formal induction:
MiraBernstein
2021-05-19 21:03:45
Lemma 2: If you know that a group of $2^n$ people has 2 sick people, you can always find them using $2n$ tests (or fewer).
Lemma 2: If you know that a group of $2^n$ people has 2 sick people, you can always find them using $2n$ tests (or fewer).
MiraBernstein
2021-05-19 21:03:56
Proof: Induction on $n$.
Base case: When $n=1$, you have 2 people and you already know that both are sick, so you need 0 tests. And indeed, $0<2\cdot 1$.
Proof: Induction on $n$.
Base case: When $n=1$, you have 2 people and you already know that both are sick, so you need 0 tests. And indeed, $0<2\cdot 1$.
MiraBernstein
2021-05-19 21:04:07
Inductive hypothesis: Suppose the statement is true for $n = k-1$. Now say you have a group of $2^k$ people in which you know that 2 are sick. We need to show that you can find those 2 people with $2k$ tests.
Inductive hypothesis: Suppose the statement is true for $n = k-1$. Now say you have a group of $2^k$ people in which you know that 2 are sick. We need to show that you can find those 2 people with $2k$ tests.
MiraBernstein
2021-05-19 21:04:18
Split your $2^k$ people in half (two groups of $2^{k-1}$) and test both halves. We’ve now used 2 tests. Like before, there are two possibilities:
Split your $2^k$ people in half (two groups of $2^{k-1}$) and test both halves. We’ve now used 2 tests. Like before, there are two possibilities:
MiraBernstein
2021-05-19 21:04:28
Case 1: Both halves test positive. [\i] This means each of them contains one sick person. What can we say now?
Case 1: Both halves test positive. [\i] This means each of them contains one sick person. What can we say now?
MiraBernstein
2021-05-19 21:04:44
(oops, sorry about the formatting)
(oops, sorry about the formatting)
MiraBernstein
2021-05-19 21:05:03
But the question still stands
But the question still stands
the_mathmagician
2021-05-19 21:05:18
We can use our first lemma
We can use our first lemma
dan09
2021-05-19 21:05:18
Do another binary search on each one
Do another binary search on each one
twotothetenthis1024
2021-05-19 21:05:18
this becomes essentially case A once one test has been done per group (so it works!)
this becomes essentially case A once one test has been done per group (so it works!)
peace09
2021-05-19 21:05:18
It takes $k$ tests to identify a sick person in each group, and since we have two groups, we need $2k$ tests.
It takes $k$ tests to identify a sick person in each group, and since we have two groups, we need $2k$ tests.
MiraBernstein
2021-05-19 21:05:27
By Lemma 1, we’ll need $k-1$ more tests for each of the two groups. So the total number of tests we used for our group of $2^k$ is:
By Lemma 1, we’ll need $k-1$ more tests for each of the two groups. So the total number of tests we used for our group of $2^k$ is:
MiraBernstein
2021-05-19 21:05:41
$\quad$* 2 at the beginning, to test each half.
$\quad$* $k-1$ to find the sick person in the first half (by Lemma 1)
$\quad$* $k-1$ to find the sick person in the second half (by Lemma 1)
$\quad$* 2 at the beginning, to test each half.
$\quad$* $k-1$ to find the sick person in the first half (by Lemma 1)
$\quad$* $k-1$ to find the sick person in the second half (by Lemma 1)
MiraBernstein
2021-05-19 21:05:48
This adds up to $2k$ tests, as required.
This adds up to $2k$ tests, as required.
MiraBernstein
2021-05-19 21:06:00
Case 2: Only one of the two groups of $2^{k-1}$ tests positive. Then this group has both sick people in it. What do we do now?
Case 2: Only one of the two groups of $2^{k-1}$ tests positive. Then this group has both sick people in it. What do we do now?
MiraBernstein
2021-05-19 21:06:14
(hey look, better formatting!)
(hey look, better formatting!)
twotothetenthis1024
2021-05-19 21:06:48
then split it in half and try again!
then split it in half and try again!
dan09
2021-05-19 21:06:48
do another binary test only on the group with both!
do another binary test only on the group with both!
Batee5a
2021-05-19 21:06:48
Split in half again and repeat the strategy
Split in half again and repeat the strategy
gxxk
2021-05-19 21:06:48
Keep on binary searching
Keep on binary searching
the_mathmagician
2021-05-19 21:06:48
Repeat, split in half, check again, recursively, until you either chop it into 2 people, or you get 2 people in different groups sick, then proceed with the first lemma.
Repeat, split in half, check again, recursively, until you either chop it into 2 people, or you get 2 people in different groups sick, then proceed with the first lemma.
MiraBernstein
2021-05-19 21:06:57
You guys are all on the right track
You guys are all on the right track
MiraBernstein
2021-05-19 21:07:05
But remember, we're in the middle of a proof by induction!
But remember, we're in the middle of a proof by induction!
peace09
2021-05-19 21:07:32
Apply the inductive hypothesis!
Apply the inductive hypothesis!
MiraBernstein
2021-05-19 21:07:41
Hurrah, apply the inductive hypothesis!
We have a group of $2^{k-1}$ people, so we know we can find the 2 sick people in $2(k-1)$ tests.
Hurrah, apply the inductive hypothesis!
We have a group of $2^{k-1}$ people, so we know we can find the 2 sick people in $2(k-1)$ tests.
MiraBernstein
2021-05-19 21:07:53
(That IS the inductive hypothesis.)
(That IS the inductive hypothesis.)
MiraBernstein
2021-05-19 21:08:04
And we already used 2 tests.
And we already used 2 tests.
the_mathmagician
2021-05-19 21:08:20
$2k-2+2=2k$
$2k-2+2=2k$
MiraBernstein
2021-05-19 21:08:27
yup!
yup!
MiraBernstein
2021-05-19 21:08:33
Applying this to Problem 5a, Case B: If one of your 6 groups of 32 tests positive, Lemma 2 says you can find the two sick people in that group in 10 tests. So in total, you will have used 6+10 = 16 tests, as required.
Applying this to Problem 5a, Case B: If one of your 6 groups of 32 tests positive, Lemma 2 says you can find the two sick people in that group in 10 tests. So in total, you will have used 6+10 = 16 tests, as required.
MiraBernstein
2021-05-19 21:08:47
Questions on 5a?
Questions on 5a?
MiraBernstein
2021-05-19 21:09:05
OK, onto 5b.
OK, onto 5b.
MiraBernstein
2021-05-19 21:09:17
Part b (paraphrased): Now you need to find 2 people out of 1000, but you have to specify your pooled samples ahead of time. You can’t decide whom to test next based on the results of earlier tests.
Find the minimum number of pooled samples needed to identify who is sick, to within a factor of 2. That is, find an $n$-sample strategy, and prove that $n/2$ samples are not enough, for some value of $n$.
Part b (paraphrased): Now you need to find 2 people out of 1000, but you have to specify your pooled samples ahead of time. You can’t decide whom to test next based on the results of earlier tests.
Find the minimum number of pooled samples needed to identify who is sick, to within a factor of 2. That is, find an $n$-sample strategy, and prove that $n/2$ samples are not enough, for some value of $n$.
MiraBernstein
2021-05-19 21:09:45
This is a very different problem!
This is a very different problem!
MiraBernstein
2021-05-19 21:09:52
Finding the actual minimal number of tests needed in this case is an open problem! We ourselves don’t know the answer.
Finding the actual minimal number of tests needed in this case is an open problem! We ourselves don’t know the answer.
MiraBernstein
2021-05-19 21:10:01
When we put this problem on the Quiz, here’s what we knew how to do:
$\quad$* We could prove that you need at least 61 tests (a lower bound) .
$\quad$* We knew a strategy for finding the 2 sick people using 93 tests (an upper bound) .
When we put this problem on the Quiz, here’s what we knew how to do:
$\quad$* We could prove that you need at least 61 tests (a lower bound) .
$\quad$* We knew a strategy for finding the 2 sick people using 93 tests (an upper bound) .
MiraBernstein
2021-05-19 21:10:15
These two things are enough to answer the specific question that we asked on the Quiz, since $n=93$ works and $n/2=47 < 61$ doesn’t work. That’s why we posed the problem this way!
These two things are enough to answer the specific question that we asked on the Quiz, since $n=93$ works and $n/2=47 < 61$ doesn’t work. That’s why we posed the problem this way!
MiraBernstein
2021-05-19 21:10:26
So we knew that the true minimum was somewhere between 61 and 93, but we didn’t know how to narrow it down within that interval.
So we knew that the true minimum was somewhere between 61 and 93, but we didn’t know how to narrow it down within that interval.
MiraBernstein
2021-05-19 21:10:35
We love putting open problems on the Qualifying Quiz, because we’re always hoping that someone will come up with a better partial solution than ours.
Almost always, somebody does -- including this time! You guys (collectively) beat us by a teeny-tiny bit.
We love putting open problems on the Qualifying Quiz, because we’re always hoping that someone will come up with a better partial solution than ours.
Almost always, somebody does -- including this time! You guys (collectively) beat us by a teeny-tiny bit.
MiraBernstein
2021-05-19 21:10:47
No one came up with a strategy with fewer than 93 tests, but an applicant named Andrew, from Boyds, MD proved that you need at least 62 tests.
Andrew used essentially the same approach as us (and as the rest of the people who solved this problem), but he managed to raise the lower bound from 61 to 62 with some clever casework.
No one came up with a strategy with fewer than 93 tests, but an applicant named Andrew, from Boyds, MD proved that you need at least 62 tests.
Andrew used essentially the same approach as us (and as the rest of the people who solved this problem), but he managed to raise the lower bound from 61 to 62 with some clever casework.
MiraBernstein
2021-05-19 21:10:58
I won’t present Andrew’s proof here, because the casework is a little too messy to do in real time. But I did want to give him a shoutout!
I won’t present Andrew’s proof here, because the casework is a little too messy to do in real time. But I did want to give him a shoutout!
MiraBernstein
2021-05-19 21:11:07
OK, to recap: the solution to Problem 5b has two parts -- proving a lower bound and constructing an upper bound. Let’s do the lower bound first:
OK, to recap: the solution to Problem 5b has two parts -- proving a lower bound and constructing an upper bound. Let’s do the lower bound first:
MiraBernstein
2021-05-19 21:11:20
Claim: You need at least 61 tests to find the two sick people.
Claim: You need at least 61 tests to find the two sick people.
MiraBernstein
2021-05-19 21:11:33
Proof: Suppose you can do it with $k$ tests. We want to show that $k \geq 61$.
Here’s the key observation: You can’t have two people in exactly the same set of tests. Why not?
Proof: Suppose you can do it with $k$ tests. We want to show that $k \geq 61$.
Here’s the key observation: You can’t have two people in exactly the same set of tests. Why not?
wbender25
2021-05-19 21:12:47
We wouldn't be able to tell which one is sick.
We wouldn't be able to tell which one is sick.
dolphin06670
2021-05-19 21:12:47
You wouldn't know which one is sick?
You wouldn't know which one is sick?
SHZhang
2021-05-19 21:12:50
Let these people be A and B, choose a third person C, then A and C infected is indistinguishable from B and C infected
Let these people be A and B, choose a third person C, then A and C infected is indistinguishable from B and C infected
Batee5a
2021-05-19 21:13:05
if one is infected and the other isn't there'll be no way to differentiate them
if one is infected and the other isn't there'll be no way to differentiate them
MiraBernstein
2021-05-19 21:13:28
Right! If exactly one of those two people is sick, you have no way of knowing from the test results which one it is. I’m going to call this the distinct test principle .
Right! If exactly one of those two people is sick, you have no way of knowing from the test results which one it is. I’m going to call this the distinct test principle .
MiraBernstein
2021-05-19 21:13:40
OK, so what’s the maximal number of people that can be in zero tests?
OK, so what’s the maximal number of people that can be in zero tests?
wwwy
2021-05-19 21:14:21
you mean zero-positive test?
you mean zero-positive test?
MiraBernstein
2021-05-19 21:14:30
No, I mean people who are not tested at all
No, I mean people who are not tested at all
CircleInvert
2021-05-19 21:15:06
1
1
artistic_girl
2021-05-19 21:15:06
1
1
SHZhang
2021-05-19 21:15:06
one person
one person
conantwiz2023
2021-05-19 21:15:06
1&
1&
MiraBernstein
2021-05-19 21:15:11
Yup, there’s only one set of size 0 (the empty set). So by the distinct test principle, we can leave at most 1 person untested. At least 999 people must be tested.
Yup, there’s only one set of size 0 (the empty set). So by the distinct test principle, we can leave at most 1 person untested. At least 999 people must be tested.
MiraBernstein
2021-05-19 21:15:23
A lot of people said 0, but it IS OK to leave one person out
A lot of people said 0, but it IS OK to leave one person out
MiraBernstein
2021-05-19 21:15:41
if you find only one sick person among the other 999, then you know the one you left out is also sick
if you find only one sick person among the other 999, then you know the one you left out is also sick
MiraBernstein
2021-05-19 21:16:07
What’s the maximal number of people whom we can test just once?
What’s the maximal number of people whom we can test just once?
MiraBernstein
2021-05-19 21:17:15
Remember, we are assuming we're doing $k$ tests total.
Remember, we are assuming we're doing $k$ tests total.
MiraBernstein
2021-05-19 21:17:26
(We're trying to show $k>=61$)
(We're trying to show $k>=61$)
MiraBernstein
2021-05-19 21:18:01
What happens if we put two people in the same test, and that's the only test for both of them?
What happens if we put two people in the same test, and that's the only test for both of them?
ChrisalonaLiverspur
2021-05-19 21:18:45
Well if its positive, how can we find it out for them?
Well if its positive, how can we find it out for them?
peace09
2021-05-19 21:18:45
If positive then how do we know if 1 or 2 of those people are positive?
If positive then how do we know if 1 or 2 of those people are positive?
MiraBernstein
2021-05-19 21:18:59
Right, so that doesn't work: we can't have two once-tested people in the same test.
Right, so that doesn't work: we can't have two once-tested people in the same test.
MiraBernstein
2021-05-19 21:19:10
So: What’s the maximal number of people whom we can test just once?
So: What’s the maximal number of people whom we can test just once?
MiraBernstein
2021-05-19 21:20:06
A lot of people are saying 1, but that's 1 per each test. Remember, we're doing $k$ tests!
A lot of people are saying 1, but that's 1 per each test. Remember, we're doing $k$ tests!
dolphin06670
2021-05-19 21:20:34
k?
k?
Eng123
2021-05-19 21:20:34
k.
k.
wwwy
2021-05-19 21:20:34
k
k
artistic_girl
2021-05-19 21:20:34
k
k
MiraBernstein
2021-05-19 21:20:40
Yes! Since there are $k$ tests, the distinct test principle tells us that there can be at most $k$ people who are tested once (and all of them have to be in different tests). If there were two such people in the same test, then there would be no way for us to tell them apart.
Yes! Since there are $k$ tests, the distinct test principle tells us that there can be at most $k$ people who are tested once (and all of them have to be in different tests). If there were two such people in the same test, then there would be no way for us to tell them apart.
MiraBernstein
2021-05-19 21:21:10
OK, so at most 1 person gets tested zero times and at most $k$ people get tested once.
OK, so at most 1 person gets tested zero times and at most $k$ people get tested once.
MiraBernstein
2021-05-19 21:21:17
OK, say there are $a$ people who get tested only once. (We just showed that $a \leq k$.) Then we’re testing at least $999-a$ people two or more times.
OK, say there are $a$ people who get tested only once. (We just showed that $a \leq k$.) Then we’re testing at least $999-a$ people two or more times.
MiraBernstein
2021-05-19 21:21:25
That’s a total of at least $a + 2(999 - a) = 1998 - a$ individual samples to put into our tests.
That’s a total of at least $a + 2(999 - a) = 1998 - a$ individual samples to put into our tests.
MiraBernstein
2021-05-19 21:21:38
Since $a \leq k$, we conclude that the number of individual samples we’ll need to process in our $k$ pooled tests is at least $1999 - k$.
Since $a \leq k$, we conclude that the number of individual samples we’ll need to process in our $k$ pooled tests is at least $1999 - k$.
MiraBernstein
2021-05-19 21:21:50
Now, how can we get an inequality in the other direction?
Now, how can we get an inequality in the other direction?
MiraBernstein
2021-05-19 21:22:39
We can include at most 32 individual samples in one test
We can include at most 32 individual samples in one test
MiraBernstein
2021-05-19 21:22:54
So how many individual samples can we process total?
So how many individual samples can we process total?
MiraBernstein
2021-05-19 21:23:55
Uh-oh, I think I'm losing you guys.
Uh-oh, I think I'm losing you guys.
MiraBernstein
2021-05-19 21:24:03
Forget the $1999-k$.
Forget the $1999-k$.
MiraBernstein
2021-05-19 21:24:09
We're doing $k$ tests.
We're doing $k$ tests.
MiraBernstein
2021-05-19 21:24:19
Each one can process at most 32 individual samples
Each one can process at most 32 individual samples
MiraBernstein
2021-05-19 21:24:33
So what's an upper bound on the number of individual samples?
So what's an upper bound on the number of individual samples?
Batee5a
2021-05-19 21:24:47
why 32?
why 32?
MiraBernstein
2021-05-19 21:24:59
That's in the problem statement
That's in the problem statement
MiraBernstein
2021-05-19 21:25:04
(sorry, it was in Part a)
(sorry, it was in Part a)
MiraBernstein
2021-05-19 21:25:44
In our $k$ tests, we can't include more than $32k$ individual samples
In our $k$ tests, we can't include more than $32k$ individual samples
artistic_girl
2021-05-19 21:26:02
$32 \dot k$
$32 \dot k$
MiraBernstein
2021-05-19 21:26:06
Yup!
Yup!
MiraBernstein
2021-05-19 21:26:32
But we said that we had to test at least $1998-k$ individual samples.
But we said that we had to test at least $1998-k$ individual samples.
MiraBernstein
2021-05-19 21:26:47
(Sorry, the 1999 before was a typo.)
(Sorry, the 1999 before was a typo.)
MiraBernstein
2021-05-19 21:27:14
This gives us the inequality $32k \geq 1998 - k$.
This gives us the inequality $32k \geq 1998 - k$.
artistic_girl
2021-05-19 21:27:21
1998 / 33
1998 / 33
MiraBernstein
2021-05-19 21:27:25
Right!
Right!
MiraBernstein
2021-05-19 21:27:32
Solving for $k$, we get $k \geq 1998/33 \approx 60.5$.
Since $k$ is an integer, we conclude that $k \geq 61$, QED.
Solving for $k$, we get $k \geq 1998/33 \approx 60.5$.
Since $k$ is an integer, we conclude that $k \geq 61$, QED.
MiraBernstein
2021-05-19 21:27:45
How're you guys doing? Any questions?
How're you guys doing? Any questions?
peace09
2021-05-19 21:28:07
When you say it, it makes sense, but I can't find it on my own! :o
When you say it, it makes sense, but I can't find it on my own! :o
Eng123
2021-05-19 21:28:07
Confused but alive. Doable.
Confused but alive. Doable.
MiraBernstein
2021-05-19 21:28:10
MiraBernstein
2021-05-19 21:28:38
OK, that was the lower bound: we know we need at least 61 tests.
OK, that was the lower bound: we know we need at least 61 tests.
MiraBernstein
2021-05-19 21:29:04
(People who are confused: the ipper bound proof is easier to follow.)
(People who are confused: the ipper bound proof is easier to follow.)
MiraBernstein
2021-05-19 21:29:09
*upper
*upper
MiraBernstein
2021-05-19 21:29:20
So let’s show how we can actually find the 2 sick people using $93$ tests.
So let’s show how we can actually find the 2 sick people using $93$ tests.
SHZhang
2021-05-19 21:29:39
Put the people into a 32 by 32 grid
Put the people into a 32 by 32 grid
MiraBernstein
2021-05-19 21:30:12
One approach is to imagine our 1000 people arranged in a $32 \times 32$ square. (Some of the places in the square will be unoccupied, since $32 \cdot 32 > 1000$. It doesn’t matter.)
One approach is to imagine our 1000 people arranged in a $32 \times 32$ square. (Some of the places in the square will be unoccupied, since $32 \cdot 32 > 1000$. It doesn’t matter.)
MiraBernstein
2021-05-19 21:30:19
We can now refer to individuals by their location in this square array: for example $(a,b)$ is the individual whose sample is in row $a$ and column $b$.
We can now refer to individuals by their location in this square array: for example $(a,b)$ is the individual whose sample is in row $a$ and column $b$.
MiraBernstein
2021-05-19 21:30:26
Now we can do a pooled test on the people in each column and a pooled test on the people in each row, for a total of $32 + 32 = 64$ tests. How many positive row-tests will we get?
Now we can do a pooled test on the people in each column and a pooled test on the people in each row, for a total of $32 + 32 = 64$ tests. How many positive row-tests will we get?
SHZhang
2021-05-19 21:31:09
Either 1 or 2
Either 1 or 2
gordonhero
2021-05-19 21:31:09
2 or 1
2 or 1
MiraBernstein
2021-05-19 21:31:19
Right, it can be 1 or 2, depending on whether the sick people are in the same row or in different rows. And similarly, we’ll get either 1 or 2 positive column tests.
Right, it can be 1 or 2, depending on whether the sick people are in the same row or in different rows. And similarly, we’ll get either 1 or 2 positive column tests.
MiraBernstein
2021-05-19 21:31:27
So there are three possibilities:
Outcome 1: Row $a$ tests positive, columns $c$ and $d$ test positive. What does that tell us?
So there are three possibilities:
Outcome 1: Row $a$ tests positive, columns $c$ and $d$ test positive. What does that tell us?
MiraBernstein
2021-05-19 21:31:46
(What are the coordinates of the sick people?)
(What are the coordinates of the sick people?)
Batee5a
2021-05-19 21:32:03
(a,c) and (a,d) are infected
(a,c) and (a,d) are infected
peace09
2021-05-19 21:32:03
$(a,c)$ and $(a,d)$
$(a,c)$ and $(a,d)$
gordonhero
2021-05-19 21:32:03
there are two people (a,c) and (a,d) who are sick
there are two people (a,c) and (a,d) who are sick
wbender25
2021-05-19 21:32:03
$(a,c)$ and $(a,d)$ are sick.
$(a,c)$ and $(a,d)$ are sick.
SHZhang
2021-05-19 21:32:03
(a, c), (a, d)
(a, c), (a, d)
Mathdreams
2021-05-19 21:32:11
(a,c) and (a,d)
(a,c) and (a,d)
MiraBernstein
2021-05-19 21:32:19
Right, the sick people have to be $(a,c)$ and $(a,d)$.
Outcome 2: Rows $a$ and $b$ test positive, column $c$ tests positive. This tells us that the sick people must be $(a,c)$ and $(b,c)$.
Right, the sick people have to be $(a,c)$ and $(a,d)$.
Outcome 2: Rows $a$ and $b$ test positive, column $c$ tests positive. This tells us that the sick people must be $(a,c)$ and $(b,c)$.
MiraBernstein
2021-05-19 21:32:34
Now here’s the interesting case:
Outcome 3: Rows $a$ and $b$ test positive, columns $c$ and $d$ test positive. What does that tell us?
Now here’s the interesting case:
Outcome 3: Rows $a$ and $b$ test positive, columns $c$ and $d$ test positive. What does that tell us?
w_aops
2021-05-19 21:33:16
Either (a, d) and (b, c); or (a, c) and (b, d)
Either (a, d) and (b, c); or (a, c) and (b, d)
wbender25
2021-05-19 21:33:16
Either $(a,c)$ and $(b,d)$ are sick, or $(a,d)$ and $(b,c)$ are sick.
Either $(a,c)$ and $(b,d)$ are sick, or $(a,d)$ and $(b,c)$ are sick.
SHZhang
2021-05-19 21:33:16
Either (a, c) and (b, d), or (a, d) and (b, c)
Either (a, c) and (b, d), or (a, d) and (b, c)
Batee5a
2021-05-19 21:33:31
(a,c), (b,d) or (a,d), (b,c)
(a,c), (b,d) or (a,d), (b,c)
MiraBernstein
2021-05-19 21:33:34
Right, there are two options for who the sick people are. It could be either the pair $(a,c)$ and $(b,d)$ or the pair $(a,d)$ and $(b,c)$.
Here’s a picture ($10\times10$ instead of $32\times32$, but same idea):
Right, there are two options for who the sick people are. It could be either the pair $(a,c)$ and $(b,d)$ or the pair $(a,d)$ and $(b,c)$.
Here’s a picture ($10\times10$ instead of $32\times32$, but same idea):
MiraBernstein
2021-05-19 21:33:51
We know that the sick people are either the two blue squares or the two green squares. Now we just need some way to tell which pair of squares it is!
But remember, we’re designing all these tests in advance, so we don’t know ahead of time which two pairs we’ll be confused between. What can we do?
We know that the sick people are either the two blue squares or the two green squares. Now we just need some way to tell which pair of squares it is!
But remember, we’re designing all these tests in advance, so we don’t know ahead of time which two pairs we’ll be confused between. What can we do?
BobsonJoe
2021-05-19 21:34:39
test the diagonals
test the diagonals
Batee5a
2021-05-19 21:34:39
diagonals?
diagonals?
gordonhero
2021-05-19 21:34:39
test diagonals?
test diagonals?
MiraBernstein
2021-05-19 21:34:52
Yes! I think this is the hardest idea to come up with.
Yes! I think this is the hardest idea to come up with.
MiraBernstein
2021-05-19 21:35:02
So, maybe like this:
We do a pooled test on the squares through which each diagonal passes. (I drew all my diagonals going from top-left to bottom-right, but you can also have them going in the other direction.)
So, maybe like this:
We do a pooled test on the squares through which each diagonal passes. (I drew all my diagonals going from top-left to bottom-right, but you can also have them going in the other direction.)
MiraBernstein
2021-05-19 21:35:10
In our picture, if the people in the bright-blue squares are sick, then the two light-blue diagonals will test positive. If the people in the bright-green squares are sick, then the light-green diagonal will test positive.
In our picture, if the people in the bright-blue squares are sick, then the two light-blue diagonals will test positive. If the people in the bright-green squares are sick, then the light-green diagonal will test positive.
Annabeth_
2021-05-19 21:35:17
why diagonals?
why diagonals?
MiraBernstein
2021-05-19 21:35:23
Just because it works!
Just because it works!
MiraBernstein
2021-05-19 21:35:38
Notice that the two sick people might be on the same diagonal as each other (like the green squares) or they might not (like the blue squares). It doesn’t matter.
The important thing is that the blue squares can never be on the same diagonal(s) as the green squares! So knowing which diagonal(s) tested positive will tell you which of the two possible pairs of people (green or blue) is sick.
Notice that the two sick people might be on the same diagonal as each other (like the green squares) or they might not (like the blue squares). It doesn’t matter.
The important thing is that the blue squares can never be on the same diagonal(s) as the green squares! So knowing which diagonal(s) tested positive will tell you which of the two possible pairs of people (green or blue) is sick.
peace09
2021-05-19 21:35:45
Why do we do it in the first place though? What's the motivation?
Why do we do it in the first place though? What's the motivation?
MiraBernstein
2021-05-19 21:36:06
Well, we have to distinguish between the two pairs of squares.
Well, we have to distinguish between the two pairs of squares.
MiraBernstein
2021-05-19 21:36:24
Rows and columns don't work any more, but this does.
Rows and columns don't work any more, but this does.
MiraBernstein
2021-05-19 21:36:44
You could do other things -- e.g. diagonals of other slopes could also work
You could do other things -- e.g. diagonals of other slopes could also work
MiraBernstein
2021-05-19 21:37:00
Anything where the blue and green squares would not be in the same tests
Anything where the blue and green squares would not be in the same tests
BlueyStudiosYT
2021-05-19 21:37:04
Who came up with the idea to use diagnals?
Who came up with the idea to use diagnals?
MiraBernstein
2021-05-19 21:37:23
Apparently many people independently!
Apparently many people independently!
MiraBernstein
2021-05-19 21:37:35
But it's a very clever idea that probably took them a while to come up with.
But it's a very clever idea that probably took them a while to come up with.
MiraBernstein
2021-05-19 21:37:40
It certainly took me a while!
It certainly took me a while!
MiraBernstein
2021-05-19 21:37:50
OK, so we’ve decided to test all the diagonals. How many tests does this take? How many diagonals are there in our picture (the $10\times10$ version)?
OK, so we’ve decided to test all the diagonals. How many tests does this take? How many diagonals are there in our picture (the $10\times10$ version)?
peace09
2021-05-19 21:38:16
19.
19.
gordonhero
2021-05-19 21:38:16
10 + 9 = 19
10 + 9 = 19
MiraBernstein
2021-05-19 21:38:27
Right, the $10\times10$ square has $10+10-1$ diagonals. And in the same way, the $32\times32$ square has 63 diagonals.
But we already did 64 tests on the rows and columns, so it looks like our strategy requires 127 tests. That’s too many! I promised you 93.
Right, the $10\times10$ square has $10+10-1$ diagonals. And in the same way, the $32\times32$ square has 63 diagonals.
But we already did 64 tests on the rows and columns, so it looks like our strategy requires 127 tests. That’s too many! I promised you 93.
MiraBernstein
2021-05-19 21:38:43
Let’s get it down to 96 tests first, and then we can talk about how to get further down to 93. What can we do to decrease the number of diagonal tests from 63 to 32?
Let’s get it down to 96 tests first, and then we can talk about how to get further down to 93. What can we do to decrease the number of diagonal tests from 63 to 32?
Smileyklaws
2021-05-19 21:38:54
diagonals can wrap around
diagonals can wrap around
MiraBernstein
2021-05-19 21:39:08
Yes! Here’s a picture:
Yes! Here’s a picture:
MiraBernstein
2021-05-19 21:39:18
We let the diagonals “wrap around” and combine the pieces of the same color into the same pooled test. So all the squares covered by the red diagonal are in one test, all the squares covered by the orange diagonal are in another test, etc.
We let the diagonals “wrap around” and combine the pieces of the same color into the same pooled test. So all the squares covered by the red diagonal are in one test, all the squares covered by the orange diagonal are in another test, etc.
MiraBernstein
2021-05-19 21:39:30
Another clever idea!
Another clever idea!
MiraBernstein
2021-05-19 21:39:36
You can think of this as combining all squares $(x,y)$ that satisfy the linear equation
$$
x+y = i mod 32,
$$
for each value $i = 0,1,\dots,31$. (Or, in our picture, mod 10.)
For example, if the bottom left square is $(0,0)$, then what is $i$ for the orange diagonal?
You can think of this as combining all squares $(x,y)$ that satisfy the linear equation
$$
x+y = i mod 32,
$$
for each value $i = 0,1,\dots,31$. (Or, in our picture, mod 10.)
For example, if the bottom left square is $(0,0)$, then what is $i$ for the orange diagonal?
MiraBernstein
2021-05-19 21:40:17
$$
x+y = i \mod 32,
$$
$$
x+y = i \mod 32,
$$
MiraBernstein
2021-05-19 21:40:29
peace09
2021-05-19 21:41:28
6
6
MiraBernstein
2021-05-19 21:41:30
If the bottom left is $(0,0)$, then the orange diagonal has points $(0,6)$, $(1,5)$, etc.
If the bottom left is $(0,0)$, then the orange diagonal has points $(0,6)$, $(1,5)$, etc.
MiraBernstein
2021-05-19 21:41:49
The orange diagonal consists of all squares $(x,y)$ satisfying $x+y = 6 \mod 10$.
The orange diagonal consists of all squares $(x,y)$ satisfying $x+y = 6 \mod 10$.
MiraBernstein
2021-05-19 21:41:58
If you let the diagonals wrap around this way, a $32\times 32$ square will have only $32$ of them, since $i$ ranges from 0 to 31.
So now we’ve used 32 row tests, 32 column tests, and 32 diagonal tests, for a total of 96 tests.
If you let the diagonals wrap around this way, a $32\times 32$ square will have only $32$ of them, since $i$ ranges from 0 to 31.
So now we’ve used 32 row tests, 32 column tests, and 32 diagonal tests, for a total of 96 tests.
MiraBernstein
2021-05-19 21:42:07
This already solves the problem as posed on the Quiz, since 96 works and $96/2 = 48$ doesn’t work. But just for fun, how can we get it further down to 93?
This already solves the problem as posed on the Quiz, since 96 works and $96/2 = 48$ doesn’t work. But just for fun, how can we get it further down to 93?
MiraBernstein
2021-05-19 21:42:39
We're running late, so I'll just give it away.
We're running late, so I'll just give it away.
MiraBernstein
2021-05-19 21:42:47
We can skip one row, one column, and one diagonal.
Then, for example, if only one row tests positive, you don’t know if it’s because both sick people are in that row or because one is in that row and the other is in the row that wasn’t tested. But the columns and the diagonals will always let you disambiguate that.
There are a bunch of cases to check here, but it always works.
We can skip one row, one column, and one diagonal.
Then, for example, if only one row tests positive, you don’t know if it’s because both sick people are in that row or because one is in that row and the other is in the row that wasn’t tested. But the columns and the diagonals will always let you disambiguate that.
There are a bunch of cases to check here, but it always works.
MiraBernstein
2021-05-19 21:43:04
(Check it for homework! )
(Check it for homework!
)
MiraBernstein
2021-05-19 21:43:13
Any questions about this strategy?
Any questions about this strategy?
peace09
2021-05-19 21:43:39
Nope! (Except the 93 part... I'll have to take a look at that some other time)
Nope! (Except the 93 part... I'll have to take a look at that some other time
)
MiraBernstein
2021-05-19 21:43:54
It's kind of like the way we could leave one person out of 1000 untested.
It's kind of like the way we could leave one person out of 1000 untested.
MiraBernstein
2021-05-19 21:44:08
We can leave one row, one column, and one diagonal untested.
We can leave one row, one column, and one diagonal untested.
SHZhang
2021-05-19 21:44:14
The wraparound idea is beautiful! I didn't find it, but managed to get down to 119 tests by moving people away from the corner...
The wraparound idea is beautiful! I didn't find it, but managed to get down to 119 tests by moving people away from the corner...
MiraBernstein
2021-05-19 21:44:22
yes, 119 was good enoughg!
yes, 119 was good enoughg!
MiraBernstein
2021-05-19 21:44:30
Before we wrap up with Problem 5b, I wanted to mention a really nice alternative testing strategy that a lot of people used:
Choose three pairwise relatively prime numbers (e.g. 32, 33, and 35) and do three sets of pooled tests: one set pooling all numbers that are the same mod 32, one for mod 33, and one for mod 35. Then apply the Chinese Remainder Theorem. Do a little modular arithmetic and you’re done.
Before we wrap up with Problem 5b, I wanted to mention a really nice alternative testing strategy that a lot of people used:
Choose three pairwise relatively prime numbers (e.g. 32, 33, and 35) and do three sets of pooled tests: one set pooling all numbers that are the same mod 32, one for mod 33, and one for mod 35. Then apply the Chinese Remainder Theorem. Do a little modular arithmetic and you’re done.
MiraBernstein
2021-05-19 21:44:41
If you think about it, this is actually very similar to our row-column-diagonal strategy in spirit, even though one uses geometry and one uses number theory.
If you think about it, this is actually very similar to our row-column-diagonal strategy in spirit, even though one uses geometry and one uses number theory.
MiraBernstein
2021-05-19 21:45:18
OK, on to 5c! (Sorry, this is running so late folks!)
OK, on to 5c! (Sorry, this is running so late folks!)
MiraBernstein
2021-05-19 21:45:36
(But 5c is very cool, so I hope you'll stay!)
(But 5c is very cool, so I hope you'll stay!)
MiraBernstein
2021-05-19 21:45:42
Problem 5c (paraphrased). A city wants to test 10,000 people. You know that each person has a 5% chance of being sick, but you don’t know the exact number of sick people. This time, you don’t have to design the tests in advance (as in Part b); you can base each test on your previous results (as in Part a).
Find a strategy to reduce the number of tests that need to be done; it doesn't need to be provably optimal, but do your best. On average, how many tests will be required?
Problem 5c (paraphrased). A city wants to test 10,000 people. You know that each person has a 5% chance of being sick, but you don’t know the exact number of sick people. This time, you don’t have to design the tests in advance (as in Part b); you can base each test on your previous results (as in Part a).
Find a strategy to reduce the number of tests that need to be done; it doesn't need to be provably optimal, but do your best. On average, how many tests will be required?
MiraBernstein
2021-05-19 21:46:01
Problem 5c was probably the most fun problem on the Quiz for us to read, and also the hardest for us to evaluate!
Problem 5c was probably the most fun problem on the Quiz for us to read, and also the hardest for us to evaluate!
MiraBernstein
2021-05-19 21:46:09
People came up with so many different strategies and really clever ways of computing the expected number of tests for their strategies. But we also had to scrutinize each strategy carefully, because some of them had subtle probability mistakes that were really hard to spot.
People came up with so many different strategies and really clever ways of computing the expected number of tests for their strategies. But we also had to scrutinize each strategy carefully, because some of them had subtle probability mistakes that were really hard to spot.
MiraBernstein
2021-05-19 21:46:21
And once again, you guys collectively beat us! Three applicants independently came up with a really elegant strategy that was both simpler and more efficient than our own best strategy.
And once again, you guys collectively beat us! Three applicants independently came up with a really elegant strategy that was both simpler and more efficient than our own best strategy.
MiraBernstein
2021-05-19 21:46:29
This is the strategy I’ll present today -- the most efficient strategy of all the ones that were submitted by our 540 applicants and ourselves!
This is the strategy I’ll present today -- the most efficient strategy of all the ones that were submitted by our 540 applicants and ourselves!
MiraBernstein
2021-05-19 21:46:37
It is due to:
$\quad$Sumedh, from San Jose, CA
$\quad$Andrew, from Pennington, NJ
$\quad$Giorgi, from Tbilisi, Republic of Georgia
It is due to:
$\quad$Sumedh, from San Jose, CA
$\quad$Andrew, from Pennington, NJ
$\quad$Giorgi, from Tbilisi, Republic of Georgia
MiraBernstein
2021-05-19 21:46:45
(There were also many other awesome approaches that were only a tiny bit less efficient. It makes me want to teach a whole Mathcamp class on the different solutions to this problem -- both the correct ones and the very subtly wrong ones!)
(There were also many other awesome approaches that were only a tiny bit less efficient. It makes me want to teach a whole Mathcamp class on the different solutions to this problem -- both the correct ones and the very subtly wrong ones!)
GeronimoStilton
2021-05-19 21:47:02
wow, 540 applicants!
wow, 540 applicants!
MiraBernstein
2021-05-19 21:47:07
Indeed.
Indeed.
MiraBernstein
2021-05-19 21:47:09
Ready for the “winning” strategy? Here we go.
Ready for the “winning” strategy? Here we go.
MiraBernstein
2021-05-19 21:47:19
First, divide your 10000 people into 625 groups of 16. We’ll call these 625 groups the Big Groups..
(BTW, by “groups” I just mean “sets”; this has nothing to do with group theory. )
First, divide your 10000 people into 625 groups of 16. We’ll call these 625 groups the Big Groups..
(BTW, by “groups” I just mean “sets”; this has nothing to do with group theory.
)
w_aops
2021-05-19 21:47:23
tests of 32 people are not necessarily optimal?
tests of 32 people are not necessarily optimal?
MiraBernstein
2021-05-19 21:47:31
Yeah, we'll see why soon.
Yeah, we'll see why soon.
MiraBernstein
2021-05-19 21:47:41
For each Big Group, do the following:
For each Big Group, do the following:
MiraBernstein
2021-05-19 21:47:53
$\quad$* Let $G_0$ be the entire group.
$\quad$* Do one test on all of $G_0$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, use the approach from Lemma 1 in 5a (binary search) to find just one sick person in $G_0$.
$\quad$* Let $G_0$ be the entire group.
$\quad$* Do one test on all of $G_0$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, use the approach from Lemma 1 in 5a (binary search) to find just one sick person in $G_0$.
MiraBernstein
2021-05-19 21:48:01
What’s the fastest way to do this?
What’s the fastest way to do this?
MiraBernstein
2021-05-19 21:48:10
(to find one sick person)
(to find one sick person)
gordonhero
2021-05-19 21:48:48
binary search
binary search
peace09
2021-05-19 21:48:48
$\left \lceil \log_{2} G_0 \right \rceil.$
$\left \lceil \log_{2} G_0 \right \rceil.$
MiraBernstein
2021-05-19 21:49:00
Right, it’s just like Lemma 1 in 5a: you split your group in half and test the first half. If it tests positive, proceed with that half. If it tests negative, proceed with the other half. Keep splitting in half until you’re done.
So you’ll test 8 people, then 4 people, then 2 people, then 1 person: 4 tests.
Right, it’s just like Lemma 1 in 5a: you split your group in half and test the first half. If it tests positive, proceed with that half. If it tests negative, proceed with the other half. Keep splitting in half until you’re done.
So you’ll test 8 people, then 4 people, then 2 people, then 1 person: 4 tests.
MiraBernstein
2021-05-19 21:49:20
( $|G_0| = 4$)
( $|G_0| = 4$)
MiraBernstein
2021-05-19 21:49:27
Are we done with this Big Group now? Can we move to the next one?
Are we done with this Big Group now? Can we move to the next one?
artistic_girl
2021-05-19 21:50:07
how about more than 1 sick
how about more than 1 sick
SHZhang
2021-05-19 21:50:07
No - need to find all infected people in group
No - need to find all infected people in group
MiraBernstein
2021-05-19 21:50:13
That’s right, there may be other sick people in our Big Group $G_0$. So let’s remove the sick person we just, and call the remaining group of 15 people $G_1$.
That’s right, there may be other sick people in our Big Group $G_0$. So let’s remove the sick person we just, and call the remaining group of 15 people $G_1$.
MiraBernstein
2021-05-19 21:50:23
Now we go back and repeat all the preceding steps with $G_1$:
$\quad$* Do one test on all of $G_1$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, find one sick person in $G_1$.
Now we go back and repeat all the preceding steps with $G_1$:
$\quad$* Do one test on all of $G_1$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, find one sick person in $G_1$.
MiraBernstein
2021-05-19 21:50:36
How many tests does it take to find one sick person in $G_1$?
How many tests does it take to find one sick person in $G_1$?
GeronimoStilton
2021-05-19 21:50:55
4?
4?
twotothetenthis1024
2021-05-19 21:50:55
4
4
MiraBernstein
2021-05-19 21:51:00
Sort of.
Sort of.
MiraBernstein
2021-05-19 21:51:02
$G_1$ has 15 people, which is not a power of 2. But you can still keep splitting it in (approximately) half, over and over until you reach 1.
$G_1$ has 15 people, which is not a power of 2. But you can still keep splitting it in (approximately) half, over and over until you reach 1.
MiraBernstein
2021-05-19 21:51:11
Depending on luck, it might take you either 3 or 4 splits (tests) until you find the sick person. But it’s definitely no worse than with 16 people, so we know it’s at most 4 tests.
Depending on luck, it might take you either 3 or 4 splits (tests) until you find the sick person. But it’s definitely no worse than with 16 people, so we know it’s at most 4 tests.
MiraBernstein
2021-05-19 21:51:22
OK, say we’ve found a sick person in $G_1$. What do you think we should do next?
OK, say we’ve found a sick person in $G_1$. What do you think we should do next?
gordonhero
2021-05-19 21:51:46
check g_2 which as 14 people
check g_2 which as 14 people
twotothetenthis1024
2021-05-19 21:51:46
take them out, then we have G_3 and repeat the process
take them out, then we have G_3 and repeat the process
MiraBernstein
2021-05-19 21:51:50
You guessed it! We form $G_2$ by removing the sick person we just found from $G_1$. And then we just keep going in the same way:
You guessed it! We form $G_2$ by removing the sick person we just found from $G_1$. And then we just keep going in the same way:
MiraBernstein
2021-05-19 21:52:00
$\quad$* Do a pooled test on all of $G_i$, for whichever $i$ you’re on.
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive:
$\quad\qquad$* Find one sick person in $G_i$.
$\quad\qquad$* Form $G_{i+1}$ by removing this sick person from $G_i$.
$\quad\qquad$* Do it all again for $G_{i+1}$.
$\quad$* Do a pooled test on all of $G_i$, for whichever $i$ you’re on.
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive:
$\quad\qquad$* Find one sick person in $G_i$.
$\quad\qquad$* Form $G_{i+1}$ by removing this sick person from $G_i$.
$\quad\qquad$* Do it all again for $G_{i+1}$.
MiraBernstein
2021-05-19 21:52:44
So we start with a group of 16. We keep finding sick people one at a time, removing them, and checking whether the remaining group still tests positive.
So we start with a group of 16. We keep finding sick people one at a time, removing them, and checking whether the remaining group still tests positive.
MiraBernstein
2021-05-19 21:53:00
When does this process end?
When does this process end?
Batee5a
2021-05-19 21:53:28
when the whole $G_i$ tests negative
when the whole $G_i$ tests negative
MiraBernstein
2021-05-19 21:53:34
Once some $G_i$ tests negative, we can be sure that we’ve found and removed all the sick people from our original big group $G_0$. So we move on to the next Big Group.
Once some $G_i$ tests negative, we can be sure that we’ve found and removed all the sick people from our original big group $G_0$. So we move on to the next Big Group.
MiraBernstein
2021-05-19 21:53:44
We go through all the Big Groups this way and we’re done. That’s the whole strategy.
We go through all the Big Groups this way and we’re done. That’s the whole strategy.
llddmmtt1
2021-05-19 21:54:07
what about the 5%
what about the 5%
MiraBernstein
2021-05-19 21:54:21
Right, the 5% becomes relevant when you try to compute the expected number of tests for this strategy
Right, the 5% becomes relevant when you try to compute the expected number of tests for this strategy
MiraBernstein
2021-05-19 21:54:33
I don’t know about you, but when I first read this strategy, I thought: “This is SO inefficient!”
I don’t know about you, but when I first read this strategy, I thought: “This is SO inefficient!”
MiraBernstein
2021-05-19 21:54:43
It seems so silly to retest all of $G_{i+1}$ each time!
It seems so silly to retest all of $G_{i+1}$ each time!
MiraBernstein
2021-05-19 21:54:58
For instance, why are we retesting all 15 people in $G_1$ as if we know nothing about them? Most likely, we’ve already ruled some of them out when we were looking for our first sick person in $G_0$.
E.g., if the first group of 8 that we tested came out negative, why include these 8 people in $G_1$?
For instance, why are we retesting all 15 people in $G_1$ as if we know nothing about them? Most likely, we’ve already ruled some of them out when we were looking for our first sick person in $G_0$.
E.g., if the first group of 8 that we tested came out negative, why include these 8 people in $G_1$?
MiraBernstein
2021-05-19 21:55:10
So it’s clear that this strategy can be improved, possibly by a lot.
The problem is, adding all that extra complexity makes it more difficult to compute the expected number of tests that will be required. This is why all three people who came up with this strategy chose to keep it as simple as possible.
So it’s clear that this strategy can be improved, possibly by a lot.
The problem is, adding all that extra complexity makes it more difficult to compute the expected number of tests that will be required. This is why all three people who came up with this strategy chose to keep it as simple as possible.
MiraBernstein
2021-05-19 21:55:20
But it turns out that even this simplistic version, which seems so inefficient at first glance, does better in expectation than any other strategy proposed by our 540 applicants (or ourselves)!
But it turns out that even this simplistic version, which seems so inefficient at first glance, does better in expectation than any other strategy proposed by our 540 applicants (or ourselves)!
MiraBernstein
2021-05-19 21:55:51
I think in the interest of time, I should stop here?
I think in the interest of time, I should stop here?
MiraBernstein
2021-05-19 21:56:12
Computing the expected number is the best part, but we really need to get to problem 6
Computing the expected number is the best part, but we really need to get to problem 6
MiraBernstein
2021-05-19 21:56:35
I'll stay afterwards for anyone who wants to see it, but I feel bad about Misha waiting to do #6.
I'll stay afterwards for anyone who wants to see it, but I feel bad about Misha waiting to do #6.
MiraBernstein
2021-05-19 21:56:39
So let's pass it on to him!
So let's pass it on to him!
MiraBernstein
2021-05-19 21:56:54
The answer is 3125, as an upper bound
The answer is 3125, as an upper bound
Misha
2021-05-19 21:57:03
Okay. Hi everyone! I'm Misha, and I will tell you how to solve problem #6.
Okay. Hi everyone! I'm Misha, and I will tell you how to solve problem #6.
Misha
2021-05-19 21:57:09
Problem 6. Infinitely many campers line up in a row for a Competitive Hanabi Set (CHS) tournament. Each camper has an unknown, numerical skill level in playing CHS. A more skilled player will always beat a less skilled one, but the game is very subtle; it is impossible to compare skill levels, except in a one-on-one match. We will write $A \prec B$ if camper $A$ loses to camper $B$ in CHS (which means that $A$'s skill level is a lower number than $B$'s).
Problem 6. Infinitely many campers line up in a row for a Competitive Hanabi Set (CHS) tournament. Each camper has an unknown, numerical skill level in playing CHS. A more skilled player will always beat a less skilled one, but the game is very subtle; it is impossible to compare skill levels, except in a one-on-one match. We will write $A \prec B$ if camper $A$ loses to camper $B$ in CHS (which means that $A$'s skill level is a lower number than $B$'s).
Misha
2021-05-19 21:57:15
A subsequence of $n$ campers is an $n$-tuple of campers $(A_1, A_2, \dots, A_n)$ such that the campers are standing in the infinite row in that order, not necessarily consecutively. ($A_1$ is to the left of $A_2$, who is to the left of $A_3$, and so on.)
A subsequence of $n$ campers is an $n$-tuple of campers $(A_1, A_2, \dots, A_n)$ such that the campers are standing in the infinite row in that order, not necessarily consecutively. ($A_1$ is to the left of $A_2$, who is to the left of $A_3$, and so on.)
Misha
2021-05-19 21:57:23
(a) You must schedule CHS games between the campers to find a subsequence $(A_1,A_2,A_3)$ of three campers such that either $A_1 \prec A_2 \prec A_3$ or $A_1 \succ A_2 \succ A_3$. You can use the results of each game to schedule the next.
(a) You must schedule CHS games between the campers to find a subsequence $(A_1,A_2,A_3)$ of three campers such that either $A_1 \prec A_2 \prec A_3$ or $A_1 \succ A_2 \succ A_3$. You can use the results of each game to schedule the next.
Misha
2021-05-19 21:57:31
How can you minimize the number of games required in the worst case? Prove that your answer is optimal.
How can you minimize the number of games required in the worst case? Prove that your answer is optimal.
Misha
2021-05-19 21:58:14
(I'll give you a moment to refresh your memory of this problem. Another optimization problem - like problem #3 and problem #5 were.)
(I'll give you a moment to refresh your memory of this problem. Another optimization problem - like problem #3 and problem #5 were.)
Misha
2021-05-19 21:58:37
Problem 6(a) solution.
Problem 6(a) solution.
Misha
2021-05-19 21:58:46
Let's first go over the definitions and how to think about them. Here's a diagram of the outcomes of a few games: an arrow $A \to B$ means $A$ beats $B$, and I colored arrows red if they point right and blue if they point left.
Let's first go over the definitions and how to think about them. Here's a diagram of the outcomes of a few games: an arrow $A \to B$ means $A$ beats $B$, and I colored arrows red if they point right and blue if they point left.
Misha
2021-05-19 21:58:51
Misha
2021-05-19 21:58:58
Just to check that everyone's on the same page, where are the subsequences we want?
Just to check that everyone's on the same page, where are the subsequences we want?
artistic_girl
2021-05-19 22:00:07
ACD or BCE
ACD or BCE
BobsonJoe
2021-05-19 22:00:07
ACD, ECB
ACD, ECB
llddmmtt1
2021-05-19 22:00:07
ACD and BCE?
ACD and BCE?
Misha
2021-05-19 22:00:15
We are happy with $(A,C,D)$ because $A \succ C \succ D$, and with $(B,C,E)$ because $B \prec C \prec E$. We are not happy with $(A,C,B)$ or $(E,C,D)$, because they're not subsequences!
We are happy with $(A,C,D)$ because $A \succ C \succ D$, and with $(B,C,E)$ because $B \prec C \prec E$. We are not happy with $(A,C,B)$ or $(E,C,D)$, because they're not subsequences!
Misha
2021-05-19 22:00:29
Anyway, we can find one of these subsequences in 4 games. Here's one way to do that. Begin with two games $A$ vs. $B$ and $D$ vs. $E$, which can have four outcomes:
Anyway, we can find one of these subsequences in 4 games. Here's one way to do that. Begin with two games $A$ vs. $B$ and $D$ vs. $E$, which can have four outcomes:
Misha
2021-05-19 22:00:35
Misha
2021-05-19 22:00:50
What should we do in case (ii) - or case (iii), which is symmetric? Here, one more game is enough.
What should we do in case (ii) - or case (iii), which is symmetric? Here, one more game is enough.
BobsonJoe
2021-05-19 22:01:58
Schedule a game between B and D
Schedule a game between B and D
Misha
2021-05-19 22:02:05
We play B vs D. Either $(A,B,D)$ or $(B,D,E)$ will be the subsequence we want.
We play B vs D. Either $(A,B,D)$ or $(B,D,E)$ will be the subsequence we want.
Misha
2021-05-19 22:02:31
(The color varies depending on which case we're in, but the two cases are otherwise identical.)
(The color varies depending on which case we're in, but the two cases are otherwise identical.)
Misha
2021-05-19 22:02:36
What about cases (i) and (iv)? Here, we'll need two more games.
What about cases (i) and (iv)? Here, we'll need two more games.
CircleInvert
2021-05-19 22:03:41
B vs C and C vs D
B vs C and C vs D
artistic_girl
2021-05-19 22:03:41
compare C with B and D
compare C with B and D
Misha
2021-05-19 22:03:49
We play B vs C and C vs D. In case (i), we either have $A \prec B \prec C$, or $B \succ C \succ D$, or $C \prec D \prec E$. In case (iv), we get the opposite of one of these.
We play B vs C and C vs D. In case (i), we either have $A \prec B \prec C$, or $B \succ C \succ D$, or $C \prec D \prec E$. In case (iv), we get the opposite of one of these.
Misha
2021-05-19 22:04:17
Maybe an easy way to see this case is: we've ended up playing 4 games - A vs B, B vs C, C vs D, and D vs E.
Maybe an easy way to see this case is: we've ended up playing 4 games - A vs B, B vs C, C vs D, and D vs E.
Misha
2021-05-19 22:04:32
If we don't get the subsequence we wanted, the arrows must alternate red-blue-red-blue
If we don't get the subsequence we wanted, the arrows must alternate red-blue-red-blue
Misha
2021-05-19 22:04:51
but we're looking at cases (i) and (iv) - where the first and last arrows are the same color!
but we're looking at cases (i) and (iv) - where the first and last arrows are the same color!
Misha
2021-05-19 22:05:10
There's more to the problem: verifying that 3 games are not enough. For reasons of time, I'll skip this; there's clean and less clean ways to do the casework. I'll just say that a common pitfall was to assume that the first two games have a player in common - the strategy above shows that other approaches are valid!
There's more to the problem: verifying that 3 games are not enough. For reasons of time, I'll skip this; there's clean and less clean ways to do the casework. I'll just say that a common pitfall was to assume that the first two games have a player in common - the strategy above shows that other approaches are valid!
Misha
2021-05-19 22:05:46
That's part (a) and I want to pause here for a bit for questions, just to make sure everything makes sense before we make everything more complicated. Everyone with me?
That's part (a) and I want to pause here for a bit for questions, just to make sure everything makes sense before we make everything more complicated. Everyone with me?
Misha
2021-05-19 22:06:46
Problem 6(b). Now, suppose you want to find either a subsequence $(A_1, A_2, A_3)$ such that $A_1 \prec A_2 \prec A_3$, or a subsequence $(A_1, A_2, \dots, A_n)$ such that $A_1 \succ A_2 \succ \dots \succ A_n$.
Problem 6(b). Now, suppose you want to find either a subsequence $(A_1, A_2, A_3)$ such that $A_1 \prec A_2 \prec A_3$, or a subsequence $(A_1, A_2, \dots, A_n)$ such that $A_1 \succ A_2 \succ \dots \succ A_n$.
Misha
2021-05-19 22:06:51
Show that you can always do this in less than $10n$ games. (As a challenge, how much can you improve this bound?)
Show that you can always do this in less than $10n$ games. (As a challenge, how much can you improve this bound?)
Misha
2021-05-19 22:07:01
Problem 6(b) solution.
Problem 6(b) solution.
Misha
2021-05-19 22:07:07
We gave you $10n$ games for flexibility, but there are shorter solutions. I'll present the best bound anyone actually found (though it's possible to do better).
We gave you $10n$ games for flexibility, but there are shorter solutions. I'll present the best bound anyone actually found (though it's possible to do better).
Misha
2021-05-19 22:07:47
One way to try to find the long subsequence we want is to keep trying to extend a sequence. Have a camper play against other campers to their left until they win a game, then repeat this with the loser of that game. After a while, we get a picture like the following:
One way to try to find the long subsequence we want is to keep trying to extend a sequence. Have a camper play against other campers to their left until they win a game, then repeat this with the loser of that game. After a while, we get a picture like the following:
Misha
2021-05-19 22:07:53
Misha
2021-05-19 22:08:27
(So for example 1 lost to 2, so 1 kept playing and lost to 3, so 1 kept playing and finally beat 4.)
(So for example 1 lost to 2, so 1 kept playing and lost to 3, so 1 kept playing and finally beat 4.)
artistic_girl
2021-05-19 22:09:28
this can go on forever
this can go on forever
Misha
2021-05-19 22:09:38
Okay so we have a problem if lots of people keep losing a lot.
Okay so we have a problem if lots of people keep losing a lot.
Misha
2021-05-19 22:09:40
So we need a backup plan to get the long subsequence we want a different way. Can anyone spot some games we can play in the diagram above whose outcomes are more or less forced?
So we need a backup plan to get the long subsequence we want a different way. Can anyone spot some games we can play in the diagram above whose outcomes are more or less forced?
BobsonJoe
2021-05-19 22:11:19
2, 3 and 3, 4
2, 3 and 3, 4
Batee5a
2021-05-19 22:11:19
3,4,6?
3,4,6?
Misha
2021-05-19 22:11:29
Campers with a blue arrow out of them must beat everyone to their right, or else we get the three-camper subsequence we wanted. For example, camper 3 must beat camper 5, or else we get $1 \prec 3 \prec 5$.
Campers with a blue arrow out of them must beat everyone to their right, or else we get the three-camper subsequence we wanted. For example, camper 3 must beat camper 5, or else we get $1 \prec 3 \prec 5$.
Misha
2021-05-19 22:11:58
That's the "almost forced" games I mean: those outcomes are fixed, or else we're done immediately.
That's the "almost forced" games I mean: those outcomes are fixed, or else we're done immediately.
Misha
2021-05-19 22:12:04
With this in mind, what's a long "backup" sequence of red arrows we can force?
With this in mind, what's a long "backup" sequence of red arrows we can force?
Misha
2021-05-19 22:12:33
(Still in the same diagram if you like, or you can try for a general claim.)
(Still in the same diagram if you like, or you can try for a general claim.)
Misha
2021-05-19 22:14:44
Well, this is tricky, especially late at night - so let me spoil the secret for you. Here's the diagram again:
Well, this is tricky, especially late at night - so let me spoil the secret for you. Here's the diagram again:
Misha
2021-05-19 22:14:45
Misha
2021-05-19 22:14:56
Take all the "skipped" campers with a blue arrow pointing out of them, and have them play in order! If any of the outcomes give us another blue arrow, we're done. Otherwise, we get a long subsequence with $A_1 \succ A_2 \succ A_3 \succ \dots$: in this case, $2 \succ 3 \succ 5 \succ 8 \succ 9$.
Take all the "skipped" campers with a blue arrow pointing out of them, and have them play in order! If any of the outcomes give us another blue arrow, we're done. Otherwise, we get a long subsequence with $A_1 \succ A_2 \succ A_3 \succ \dots$: in this case, $2 \succ 3 \succ 5 \succ 8 \succ 9$.
Misha
2021-05-19 22:15:14
so that's saying "play 2 vs 3, 3 vs 5, 5 vs 8, 8 vs 9" in this case.
so that's saying "play 2 vs 3, 3 vs 5, 5 vs 8, 8 vs 9" in this case.
artistic_girl
2021-05-19 22:16:22
they all have to be red
they all have to be red
Misha
2021-05-19 22:16:34
Exactly! If one of those games gives us a blue arrow, we're done immediately.
Exactly! If one of those games gives us a blue arrow, we're done immediately.
Misha
2021-05-19 22:17:21
So we have two ways to win with a long subsequence. How many turns will this take?
So we have two ways to win with a long subsequence. How many turns will this take?
Misha
2021-05-19 22:17:41
(Either we get a long subsequence right away, or we skip lots of campers and get a long "backup" subsequence.)
(Either we get a long subsequence right away, or we skip lots of campers and get a long "backup" subsequence.)
Misha
2021-05-19 22:19:51
So I'm seeing a good partial answer here that's missing one step. Think of it this way: we're happy if we get $n-1$ red arrows, or we can execute our backup plan if we get $n-1$ blue arrows. How many games until one of these happens?
So I'm seeing a good partial answer here that's missing one step. Think of it this way: we're happy if we get $n-1$ red arrows, or we can execute our backup plan if we get $n-1$ blue arrows. How many games until one of these happens?
artistic_girl
2021-05-19 22:20:56
2n
2n
peace09
2021-05-19 22:20:56
$2n-2?$
$2n-2?$
Misha
2021-05-19 22:21:10
Around $2n$, if we don't worry about the constants. (Actually, $2n-3$ is enough.)
Around $2n$, if we don't worry about the constants. (Actually, $2n-3$ is enough.)
Misha
2021-05-19 22:21:48
But that doesn't mean that $2n-3$ games are all we need! What else is missing?
But that doesn't mean that $2n-3$ games are all we need! What else is missing?
BobsonJoe
2021-05-19 22:22:32
$n$ games for the backup plan
$n$ games for the backup plan
Gogobao
2021-05-19 22:22:32
you still need n more games
you still need n more games
Misha
2021-05-19 22:23:01
Well, $n-1$ more games - there are $n-1$ $\succ$ signs between $n$ campers.
Well, $n-1$ more games - there are $n-1$ $\succ$ signs between $n$ campers.
Misha
2021-05-19 22:23:09
But who cares about the constant, anyway.
But who cares about the constant, anyway.
Misha
2021-05-19 22:23:20
So this strategy's worst case is $3n-4$ games total!
So this strategy's worst case is $3n-4$ games total!
conantwiz2023
2021-05-19 22:24:15
whats the runtime for the fastest known strategy?
whats the runtime for the fastest known strategy?
Misha
2021-05-19 22:24:25
(The best bound I know of is around $\frac83 n$, which involves doing this strategy at the same time as a mirror image of it, and playing them off against each other to take a shortcut. The only lower bound I know is $2n$, so we're not sure what the best possible answer is!)
(The best bound I know of is around $\frac83 n$, which involves doing this strategy at the same time as a mirror image of it, and playing them off against each other to take a shortcut. The only lower bound I know is $2n$, so we're not sure what the best possible answer is!)
Misha
2021-05-19 22:24:47
Alright, now on to the last part of the last problem!
Alright, now on to the last part of the last problem!
Misha
2021-05-19 22:24:54
Problem 6(c). Next, the campers come together in an unorganized crowd, and decide to hold a Two-Player Castlefall (TPC) competition. TPC is a highly strategic and complex game, so it cannot be reduced to a single skill level: in TPC, it is possible that $A \prec B$ and $B \prec C$, but $A \succ C$.
Problem 6(c). Next, the campers come together in an unorganized crowd, and decide to hold a Two-Player Castlefall (TPC) competition. TPC is a highly strategic and complex game, so it cannot be reduced to a single skill level: in TPC, it is possible that $A \prec B$ and $B \prec C$, but $A \succ C$.
Misha
2021-05-19 22:25:00
You want to find $n$ campers $A_1, A_2, \dots, A_n$ such that whenever $i < j$, $A_i \prec A_j$. How can you minimize the number of TPC games required in the worst case?
You want to find $n$ campers $A_1, A_2, \dots, A_n$ such that whenever $i < j$, $A_i \prec A_j$. How can you minimize the number of TPC games required in the worst case?
Misha
2021-05-19 22:25:07
Problem 6(c) solution.
Problem 6(c) solution.
Misha
2021-05-19 22:25:13
I want to point that two things change in this problem. First, skill in TPC is not transitive, so we have to play $\binom n2$ games just to verify that $n$ campers are sorted by skill. Second, no more "subsequences": the campers are in an "unorganized crowd", and we can reorder them however we like!
I want to point that two things change in this problem. First, skill in TPC is not transitive, so we have to play $\binom n2$ games just to verify that $n$ campers are sorted by skill. Second, no more "subsequences": the campers are in an "unorganized crowd", and we can reorder them however we like!
Misha
2021-05-19 22:25:25
So forget most things that happened in part (a) and (b)
So forget most things that happened in part (a) and (b)
Misha
2021-05-19 22:25:41
Here's a kind of setup that will work for us. Take a camper $X$ and have them play LOTS AND LOTS of games. Either $X$ wins many of them, or $X$ loses many of them; these are symmetric, so let's say $X$ wins lots of games. How do we want to use this?
Here's a kind of setup that will work for us. Take a camper $X$ and have them play LOTS AND LOTS of games. Either $X$ wins many of them, or $X$ loses many of them; these are symmetric, so let's say $X$ wins lots of games. How do we want to use this?
SHZhang
2021-05-19 22:27:05
Use the campers losing against X to build a sequence, then add X to it
Use the campers losing against X to build a sequence, then add X to it
Misha
2021-05-19 22:27:14
We want to find $n-1$ campers $A_1, A_2, \dots, A_{n-1}$ among the campers $X$ beats. Then $X$ can be camper $A_n$, because $X$ beats each of $A_1$ through $A_{n-1}$.
We want to find $n-1$ campers $A_1, A_2, \dots, A_{n-1}$ among the campers $X$ beats. Then $X$ can be camper $A_n$, because $X$ beats each of $A_1$ through $A_{n-1}$.
Misha
2021-05-19 22:27:42
(If $X$ lost a bunch of games, we'd find $n-1$ campers $A_2, \dots, A_n$ among the people that beat $X$, and then $X$ could be camper $A_1$. Symmetric!)
(If $X$ lost a bunch of games, we'd find $n-1$ campers $A_2, \dots, A_n$ among the people that beat $X$, and then $X$ could be camper $A_1$. Symmetric!)
Misha
2021-05-19 22:27:53
To properly analyze this strategy, we have to keep track of two things. Let's say that finding a group of $k$ campers ordered by skill took us $N_k$ games involving $C_k$ campers; we want to find a formula for $N_k$, but we'll need to know $C_k$ as well.
To properly analyze this strategy, we have to keep track of two things. Let's say that finding a group of $k$ campers ordered by skill took us $N_k$ games involving $C_k$ campers; we want to find a formula for $N_k$, but we'll need to know $C_k$ as well.
Misha
2021-05-19 22:28:15
To find $C_k$ campers that either all lose to $X$ or all beat $X$, we should play $2C_k-1$ more games (involving $C_{k+1} = 2C_k$ campers total). The total number of games is $N_{k+1} = N_k + 2C_k - 1$. This gives us a recurrence to solve for $N_k$ and $C_k$. First of all, what's $C_k$?
To find $C_k$ campers that either all lose to $X$ or all beat $X$, we should play $2C_k-1$ more games (involving $C_{k+1} = 2C_k$ campers total). The total number of games is $N_{k+1} = N_k + 2C_k - 1$. This gives us a recurrence to solve for $N_k$ and $C_k$. First of all, what's $C_k$?
yofro
2021-05-19 22:30:10
$2^{k-1}$
$2^{k-1}$
Misha
2021-05-19 22:30:17
We start with $C_1 = 1$ camper necessary to find a group of $k=1$ campers. Then $C_{k+1} = 2C_k$, so it doubles each time: we have $C_k = 2^{k-1}$.
We start with $C_1 = 1$ camper necessary to find a group of $k=1$ campers. Then $C_{k+1} = 2C_k$, so it doubles each time: we have $C_k = 2^{k-1}$.
Misha
2021-05-19 22:30:32
(I saw several $2^k$ answers, but watch out for the base case.)
(I saw several $2^k$ answers, but watch out for the base case.)
peace09
2021-05-19 22:30:51
Where did we find that $C_{k+1}=2C_k?$
Where did we find that $C_{k+1}=2C_k?$
Misha
2021-05-19 22:31:08
That's our strategy for playing lots of games involving $X$ at work!
That's our strategy for playing lots of games involving $X$ at work!
Misha
2021-05-19 22:31:22
We need to wait until $X$ either loses to $C_k$ campers or beats $C_k$ campers.
We need to wait until $X$ either loses to $C_k$ campers or beats $C_k$ campers.
Misha
2021-05-19 22:31:48
So we should have $X$ play against $2C_k - 1$ other campers, and then the total number of campers together with $X$ is $2C_k$.
So we should have $X$ play against $2C_k - 1$ other campers, and then the total number of campers together with $X$ is $2C_k$.
Misha
2021-05-19 22:32:04
Anyway, after all that work, our other recurrence is now $N_{k+1} = N_k + 2^k - 1$.
Anyway, after all that work, our other recurrence is now $N_{k+1} = N_k + 2^k - 1$.
Misha
2021-05-19 22:32:23
That's going to tell us the number of games to find a group of $k$ campers ordered by skill.
That's going to tell us the number of games to find a group of $k$ campers ordered by skill.
Misha
2021-05-19 22:32:34
This one's a bit trickier, and we already got a lot of practice solving recurrence relations way back in Question 2. So I'm just going to tell you that $N_k = 2^k - k - 1$; we can prove this by induction. To find a group of $n$ campers ordered by skill, we'll need $2^n-n-1$ games.
This one's a bit trickier, and we already got a lot of practice solving recurrence relations way back in Question 2. So I'm just going to tell you that $N_k = 2^k - k - 1$; we can prove this by induction. To find a group of $n$ campers ordered by skill, we'll need $2^n-n-1$ games.
Misha
2021-05-19 22:33:06
If you're familiar with Ramsey's theorem, you may recognize this argument! A result called "Ramsey's theorem for tournaments" tells us that if you play all possible games between $2^{n-1}$ campers, we find the group we wanted. But just citing this theorem gives a worse bound: there are $\binom{2^{n-1}}{2}$ possible games between those campers, which is closer to $4^n$ than $2^n$.
If you're familiar with Ramsey's theorem, you may recognize this argument! A result called "Ramsey's theorem for tournaments" tells us that if you play all possible games between $2^{n-1}$ campers, we find the group we wanted. But just citing this theorem gives a worse bound: there are $\binom{2^{n-1}}{2}$ possible games between those campers, which is closer to $4^n$ than $2^n$.
Misha
2021-05-19 22:33:32
Anyway, that wraps up 6(c), which I went through a bit quicker because we're 90 minutes late.
Anyway, that wraps up 6(c), which I went through a bit quicker because we're 90 minutes late.
Misha
2021-05-19 22:33:43
Are there any other questions about problem 6?
Are there any other questions about problem 6?
conantwiz2023
2021-05-19 22:33:58
is $2^n - n - 1$ the best known algorithm for the problem?
is $2^n - n - 1$ the best known algorithm for the problem?
Misha
2021-05-19 22:34:16
It's the best thing I knew writing the problem, and the best thing anyone came up with!
It's the best thing I knew writing the problem, and the best thing anyone came up with!
yofro
2021-05-19 22:34:24
does this problem have a name?
does this problem have a name?
Misha
2021-05-19 22:34:36
Find the optimal answer and prove it's optimal, and we can name it after you!
Find the optimal answer and prove it's optimal, and we can name it after you!
Misha
2021-05-19 22:35:15
There is an exponential lower bound, too, which comes from Ramsey's theorem.
There is an exponential lower bound, too, which comes from Ramsey's theorem.
Misha
2021-05-19 22:35:47
Looks like that's it for questions about problem 6, so it's back over to MiraBernstein to wrap things up!
Looks like that's it for questions about problem 6, so it's back over to MiraBernstein to wrap things up!
MiraBernstein
2021-05-19 22:36:02
OK, guys, it's very late!
OK, guys, it's very late!
MiraBernstein
2021-05-19 22:36:17
I promised I'd do 5c if people still wanted, and I'm still game.
I promised I'd do 5c if people still wanted, and I'm still game.
MiraBernstein
2021-05-19 22:36:27
But I can also just post the solution in the same place as this Math Jam
But I can also just post the solution in the same place as this Math Jam
MiraBernstein
2021-05-19 22:36:39
If I get 5 yes'es, I'll do it now.
If I get 5 yes'es, I'll do it now.
MiraBernstein
2021-05-19 22:36:57
Oh wow!
Oh wow!
gordonhero
2021-05-19 22:37:12
yes
yes
peace09
2021-05-19 22:37:12
YES
YES
Supermath123
2021-05-19 22:37:12
yes!
yes!
Jing.Han
2021-05-19 22:37:12
yes
yes
JamesSohigian
2021-05-19 22:37:12
Yes
Yes
w_aops
2021-05-19 22:37:12
yes
yes
Batee5a
2021-05-19 22:37:12
Yes!
Yes!
gordonhero
2021-05-19 22:37:12
yes'es
yes'es
GeronimoStilton
2021-05-19 22:37:12
sure
sure
summersunlight
2021-05-19 22:37:12
yes
yes
MiraBernstein
2021-05-19 22:37:28
I eman 5 yes'es from distinct people
I eman 5 yes'es from distinct people
MiraBernstein
2021-05-19 22:37:37
OK, let's do this thing!!
OK, let's do this thing!!
MiraBernstein
2021-05-19 22:37:56
We want to find the expected number of tests for our strategy.
We want to find the expected number of tests for our strategy.
MiraBernstein
2021-05-19 22:38:03
But you surely forgot what our strategy is
But you surely forgot what our strategy is
MiraBernstein
2021-05-19 22:38:08
So let's review quickly
So let's review quickly
MiraBernstein
2021-05-19 22:38:23
Problem 5c (paraphrased). A city wants to test 10,000 people. You know that each person has a 5% chance of being sick, but you don’t know the exact number of sick people. This time, you don’t have to design the tests in advance (as in Part b); you can base each test on your previous results (as in Part a).
Find a strategy to reduce the number of tests that need to be done; it doesn't need to be provably optimal, but do your best. On average, how many tests will be required?
Problem 5c (paraphrased). A city wants to test 10,000 people. You know that each person has a 5% chance of being sick, but you don’t know the exact number of sick people. This time, you don’t have to design the tests in advance (as in Part b); you can base each test on your previous results (as in Part a).
Find a strategy to reduce the number of tests that need to be done; it doesn't need to be provably optimal, but do your best. On average, how many tests will be required?
MiraBernstein
2021-05-19 22:38:44
Best strategy that we know:
Best strategy that we know:
MiraBernstein
2021-05-19 22:38:55
First, divide your 10000 people into 625 groups of 16. We’ll call these 625 groups the Big Groups..
(BTW, by “groups” I just mean “sets”; this has nothing to do with group theory. )
For each Big Group, do the following:
$\quad$* Let $G_0$ be the entire group.
$\quad$* Do one test on all of $G_0$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, use the approach from Lemma 1 in 5a (binary search) to find just one sick person in $G_0$.
First, divide your 10000 people into 625 groups of 16. We’ll call these 625 groups the Big Groups..
(BTW, by “groups” I just mean “sets”; this has nothing to do with group theory.
)For each Big Group, do the following:
$\quad$* Let $G_0$ be the entire group.
$\quad$* Do one test on all of $G_0$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, use the approach from Lemma 1 in 5a (binary search) to find just one sick person in $G_0$.
MiraBernstein
2021-05-19 22:39:13
There may be other sick people in our Big Group $G_0$. So let’s remove the sick person we just, and call the remaining group of 15 people $G_1$.
There may be other sick people in our Big Group $G_0$. So let’s remove the sick person we just, and call the remaining group of 15 people $G_1$.
MiraBernstein
2021-05-19 22:39:21
Now we go back and repeat all the preceding steps with $G_1$:
$\quad$* Do one test on all of $G_1$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, find one sick person in $G_1$.
Now we go back and repeat all the preceding steps with $G_1$:
$\quad$* Do one test on all of $G_1$:
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive, find one sick person in $G_1$.
MiraBernstein
2021-05-19 22:39:43
OK, say we’ve found a sick person in $G_1$. We form $G_2$ by removing the sick person we just found from $G_1$. And then we just keep going in the same way:
$\quad$* Do a pooled test on all of $G_i$, for whichever $i$ you’re on.
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive:
$\quad\qquad$* Find one sick person in $G_i$.
$\quad\qquad$* Form $G_{i+1}$ by removing this sick person from $G_i$.
$\quad\qquad$* Do it all again for $G_{i+1}$.
OK, say we’ve found a sick person in $G_1$. We form $G_2$ by removing the sick person we just found from $G_1$. And then we just keep going in the same way:
$\quad$* Do a pooled test on all of $G_i$, for whichever $i$ you’re on.
$\qquad$* If it’s negative, you’re done with this Big Group. Go on to the next one.
$\qquad$* If it’s positive:
$\quad\qquad$* Find one sick person in $G_i$.
$\quad\qquad$* Form $G_{i+1}$ by removing this sick person from $G_i$.
$\quad\qquad$* Do it all again for $G_{i+1}$.
MiraBernstein
2021-05-19 22:39:59
Once some $G_i$ tests negative, we can be sure that we’ve found and removed all the sick people from our original big group $G_0$. So we move on to the next Big Group.
We go through all the Big Groups this way and we’re done. That’s the strategy.
Once some $G_i$ tests negative, we can be sure that we’ve found and removed all the sick people from our original big group $G_0$. So we move on to the next Big Group.
We go through all the Big Groups this way and we’re done. That’s the strategy.
MiraBernstein
2021-05-19 22:40:24
Any questions about what the strategy is, before we analyze it?
Any questions about what the strategy is, before we analyze it?
Batee5a
2021-05-19 22:40:55
Do we have to keep the inefficiency from the repeated tests so we can guarantee the average required tests?
Do we have to keep the inefficiency from the repeated tests so we can guarantee the average required tests?
MiraBernstein
2021-05-19 22:41:18
That's exactly right. This strategy is very easy to make more efficient!
That's exactly right. This strategy is very easy to make more efficient!
MiraBernstein
2021-05-19 22:41:32
For instance, why are we retesting all 15 people in $G_1$ as if we know nothing about them? Most likely, we’ve already ruled some of them out when we were looking for our first sick person in $G_0$.
For instance, if the first group of 8 that we tested came out negative, why include these 8 people in $G_1$?
For instance, why are we retesting all 15 people in $G_1$ as if we know nothing about them? Most likely, we’ve already ruled some of them out when we were looking for our first sick person in $G_0$.
For instance, if the first group of 8 that we tested came out negative, why include these 8 people in $G_1$?
MiraBernstein
2021-05-19 22:41:46
So it’s clear that this strategy can be improved, possibly by a lot.
The problem is, adding all that extra complexity makes it more difficult to compute the expected number of tests that will be required. This is why all three people who came up with this strategy chose to keep it as simple as possible.
So it’s clear that this strategy can be improved, possibly by a lot.
The problem is, adding all that extra complexity makes it more difficult to compute the expected number of tests that will be required. This is why all three people who came up with this strategy chose to keep it as simple as possible.
MiraBernstein
2021-05-19 22:42:03
(Sorry, I'm repeating some stuff I said already, but it's good to have the context)
(Sorry, I'm repeating some stuff I said already, but it's good to have the context)
MiraBernstein
2021-05-19 22:42:15
So let’s compute the expected number of tests we’ll need. Actually, we’ll be computing not the exact expectation, but just an upper bound on it.
So let’s compute the expected number of tests we’ll need. Actually, we’ll be computing not the exact expectation, but just an upper bound on it.
MiraBernstein
2021-05-19 22:42:25
From here one, this is new stuff.
From here one, this is new stuff.
MiraBernstein
2021-05-19 22:43:06
So in this strategy, there are two types of tests:
1) Tests that tell you that you’re done with your current Big Group and can move on to the next one.
2) Tests that you use to actually find a sick person.
How many tests of Type 1 are there?
So in this strategy, there are two types of tests:
1) Tests that tell you that you’re done with your current Big Group and can move on to the next one.
2) Tests that you use to actually find a sick person.
How many tests of Type 1 are there?
gordonhero
2021-05-19 22:43:30
625
625
yofro
2021-05-19 22:43:30
625
625
summersunlight
2021-05-19 22:43:48
625
625
MiraBernstein
2021-05-19 22:43:50
In each Big Group, we keep removing sick people one by one, until we get to some $G_i$ that tests negative. So each Big Group will require one final negative test to clear it, after all the sick people have been removed.
That is the test of Type 1! (If the Big Group had no sick people to begin with, then this will be its only test.)
So there’s exactly one test of Type 1 per Big Group, which makes 625 such tests total.
In each Big Group, we keep removing sick people one by one, until we get to some $G_i$ that tests negative. So each Big Group will require one final negative test to clear it, after all the sick people have been removed.
That is the test of Type 1! (If the Big Group had no sick people to begin with, then this will be its only test.)
So there’s exactly one test of Type 1 per Big Group, which makes 625 such tests total.
MiraBernstein
2021-05-19 22:44:10
By the way, what can we say about the results of all these 625 tests?
By the way, what can we say about the results of all these 625 tests?
gordonhero
2021-05-19 22:44:40
they're all negative
they're all negative
MiraBernstein
2021-05-19 22:44:42
Right, it’s important to notice that Type 1 tests are all negative -- they’re the ones that finally clear each Big Group. All positive tests are automatically of Type 2.
Right, it’s important to notice that Type 1 tests are all negative -- they’re the ones that finally clear each Big Group. All positive tests are automatically of Type 2.
MiraBernstein
2021-05-19 22:45:01
To count the tests of Type 2, we’ll look at each sick person in turn. Remember, in this strategy we’re always looking for one sick person at a time!
To count the tests of Type 2, we’ll look at each sick person in turn. Remember, in this strategy we’re always looking for one sick person at a time!
MiraBernstein
2021-05-19 22:45:13
So let’s focus on just one sick person. How many tests did we do that led us to this particular person ?
So let’s focus on just one sick person. How many tests did we do that led us to this particular person ?
yofro
2021-05-19 22:46:04
Depends on its position in the binary tree
Depends on its position in the binary tree
MiraBernstein
2021-05-19 22:46:09
True!
True!
gordonhero
2021-05-19 22:46:14
up to 4
up to 4
MiraBernstein
2021-05-19 22:46:33
Almost! You need to count the original test that told you that $G_i$ still had sick people in it.
Almost! You need to count the original test that told you that $G_i$ still had sick people in it.
MiraBernstein
2021-05-19 22:46:42
To find the first sick person in our Big Group $G_0$, we needed 5 tests of Type 2: we tested the whole group (16 people), then 8 people, then 4, then 2, then 1.
To find the first sick person in our Big Group $G_0$, we needed 5 tests of Type 2: we tested the whole group (16 people), then 8 people, then 4, then 2, then 1.
MiraBernstein
2021-05-19 22:47:06
(Remember, the original test of the whole group $G_0$ is of Type 2. The 625 tests of Type 1 are the ones that tell us that we’re done with a Big Group, not the ones that tell us we need to look further.)
(Remember, the original test of the whole group $G_0$ is of Type 2. The 625 tests of Type 1 are the ones that tell us that we’re done with a Big Group, not the ones that tell us we need to look further.)
MiraBernstein
2021-05-19 22:47:20
$G_1$ has 15 people, so we saw that finding the sick person will take either 4 or 5 tests (including the original test of all of $G_1$). So on average, we’ll need a little less than 5 tests of Type 2, but definitely at most 5.
$G_1$ has 15 people, so we saw that finding the sick person will take either 4 or 5 tests (including the original test of all of $G_1$). So on average, we’ll need a little less than 5 tests of Type 2, but definitely at most 5.
MiraBernstein
2021-05-19 22:47:34
Finding the next sick person, at the $G_2$ stage, will take even fewer tests on average -- and still definitely fewer than 5.
Finding the next sick person, at the $G_2$ stage, will take even fewer tests on average -- and still definitely fewer than 5.
MiraBernstein
2021-05-19 22:47:43
So no matter at what stage we found the particular sick person we’re focusing on right now, it took us at most 5 tests of Type 2 to find them.
So no matter at what stage we found the particular sick person we’re focusing on right now, it took us at most 5 tests of Type 2 to find them.
MiraBernstein
2021-05-19 22:47:52
Say we have $S$ sick people total (in all the Big Groups together). What is an easy upper bound on the number of Type 2 tests that we’ll need to find them all?
Say we have $S$ sick people total (in all the Big Groups together). What is an easy upper bound on the number of Type 2 tests that we’ll need to find them all?
w_aops
2021-05-19 22:48:58
5 * S
5 * S
summersunlight
2021-05-19 22:49:20
5xs
5xs
MiraBernstein
2021-05-19 22:49:31
Right: Finding each sick person requires at most 5 tests of Type 2, for a maximum of $5S$ tests of Type 2.
Right: Finding each sick person requires at most 5 tests of Type 2, for a maximum of $5S$ tests of Type 2.
MiraBernstein
2021-05-19 22:49:40
Now what’s the expected number of sick people, if each person out of 10,000 has a 5% chance of being sick?
Now what’s the expected number of sick people, if each person out of 10,000 has a 5% chance of being sick?
w_aops
2021-05-19 22:50:06
500
500
peace09
2021-05-19 22:50:06
500
500
yofro
2021-05-19 22:50:06
$500$
$500$
w_aops
2021-05-19 22:50:55
so 2500 Type 2 tests maximum
so 2500 Type 2 tests maximum
MiraBernstein
2021-05-19 22:51:12
Yup, on average we expect 500 sick people. Each of these will require at most 5 tests of Type 2. Plus we have the 625 final tests of Type 1, one for each Big Group. So what can we say about the expected total number of tests?
Yup, on average we expect 500 sick people. Each of these will require at most 5 tests of Type 2. Plus we have the 625 final tests of Type 1, one for each Big Group. So what can we say about the expected total number of tests?
gordonhero
2021-05-19 22:51:45
3125
3125
yofro
2021-05-19 22:51:45
3125
3125
yofro
2021-05-19 22:51:49
$\le 3125$
$\le 3125$
MiraBernstein
2021-05-19 22:52:00
To be clear: we don’t know the expected number of tests exactly, but we know it is at most
$625 + 5 \cdot 500 = 3125$.
To be clear: we don’t know the expected number of tests exactly, but we know it is at most
$625 + 5 \cdot 500 = 3125$.
MiraBernstein
2021-05-19 22:52:08
(Finding the maximum of an expectation may sound a little weird. What we’re saying is: the expected number of tests under this strategy is some number $X$. We don’t know what $X$ is, but we know $X <= 3125$.)
(Finding the maximum of an expectation may sound a little weird. What we’re saying is: the expected number of tests under this strategy is some number $X$. We don’t know what $X$ is, but we know $X <= 3125$.)
MiraBernstein
2021-05-19 22:52:18
Believe it or not, even this upper bound is better than the expected number of tests in any other strategy that anyone came up with!
Believe it or not, even this upper bound is better than the expected number of tests in any other strategy that anyone came up with!
peace09
2021-05-19 22:52:37
Really?
Really?
MiraBernstein
2021-05-19 22:52:45
Weird, right? I found it very unintuitive!
Weird, right? I found it very unintuitive!
MiraBernstein
2021-05-19 22:52:52
Even with all the inefficiency.
Even with all the inefficiency.
MiraBernstein
2021-05-19 22:52:55
One last thing to discuss is why we chose 16 as the size of our Big Groups. If your big Groups are of size $N$, then what’s the upper bound you get using the reasoning above?
One last thing to discuss is why we chose 16 as the size of our Big Groups. If your big Groups are of size $N$, then what’s the upper bound you get using the reasoning above?
MiraBernstein
2021-05-19 22:53:30
(think about where the 625 came from, where the 5 came from, and where the 500 came from)
(think about where the 625 came from, where the 5 came from, and where the 500 came from)
peace09
2021-05-19 22:53:37
Maximal power of two!
Maximal power of two!
MiraBernstein
2021-05-19 22:53:42
No, the maximum is 32
No, the maximum is 32
peace09
2021-05-19 22:54:27
??? 16 is the largest power of 2 that divides 10,000
??? 16 is the largest power of 2 that divides 10,000
MiraBernstein
2021-05-19 22:55:25
@peach09: Oh, yes, that's true. But you could do groups of size 32 and one group of size 16.
@peach09: Oh, yes, that's true. But you could do groups of size 32 and one group of size 16.
MiraBernstein
2021-05-19 22:55:42
The formula for the upper bound is $\lceil\frac{10000}{N}\rceil + 500 (\lceil\log_2 N\rceil + 1)$.
The formula for the upper bound is $\lceil\frac{10000}{N}\rceil + 500 (\lceil\log_2 N\rceil + 1)$.
MiraBernstein
2021-05-19 22:55:54
People got close to this, but not quite
People got close to this, but not quite
MiraBernstein
2021-05-19 22:56:23
$\lceil\frac{10000}{N}\rceil$ is the Type 1 tests
$\lceil\frac{10000}{N}\rceil$ is the Type 1 tests
MiraBernstein
2021-05-19 22:56:37
The rest are the type 2 tests
The rest are the type 2 tests
MiraBernstein
2021-05-19 22:56:43
Here’s the graph of this function for $1\leq N \leq 32$:
Here’s the graph of this function for $1\leq N \leq 32$:
MiraBernstein
2021-05-19 22:56:55
As you can see, the upper bound is minimized when $N=16$. (It’s possible that the actual expected value is minimized for a different $N$, but we don’t have a way to compute that at present.)
As you can see, the upper bound is minimized when $N=16$. (It’s possible that the actual expected value is minimized for a different $N$, but we don’t have a way to compute that at present.)
MiraBernstein
2021-05-19 22:57:12
I want to spend a tiny bit of time talking about other strategies, but first, any questions about this one?
I want to spend a tiny bit of time talking about other strategies, but first, any questions about this one?
gordonhero
2021-05-19 22:57:33
how do you even think this up?
how do you even think this up?
MiraBernstein
2021-05-19 22:57:43
Good question! It was not a common answer.
Good question! It was not a common answer.
MiraBernstein
2021-05-19 22:57:53
Other good strategies were much more common.
Other good strategies were much more common.
MiraBernstein
2021-05-19 22:57:59
This one just happened to beat them!
This one just happened to beat them!
MiraBernstein
2021-05-19 22:58:03
So to recap, this “3125 strategy” is the best one we know of for now. Of course, all the improvements that you guys suggested earlier would make it even better, but we don’t know how to measure the improvement.
So to recap, this “3125 strategy” is the best one we know of for now. Of course, all the improvements that you guys suggested earlier would make it even better, but we don’t know how to measure the improvement.
MiraBernstein
2021-05-19 22:58:14
In case you’re curious, the next best strategy that anyone came up with requires about 3196 tests on average. It is very complicated: you have to split your groups not in half but into different proportions each time. This was our own best strategy, and one of the applicants came up with it as well.
In case you’re curious, the next best strategy that anyone came up with requires about 3196 tests on average. It is very complicated: you have to split your groups not in half but into different proportions each time. This was our own best strategy, and one of the applicants came up with it as well.
MiraBernstein
2021-05-19 22:58:23
I wish I could go over more of the strategies that different people came up with -- there were so many good ones! But I’ve been talking for too long already. So I leave you with the following challenge:
I wish I could go over more of the strategies that different people came up with -- there were so many good ones! But I’ve been talking for too long already. So I leave you with the following challenge:
MiraBernstein
2021-05-19 22:58:31
If you solved this problem and came up with a strategy that seems to beat 3125, then we promise you made a mistake somewhere. (We checked all the solutions very carefully; many of the errors were very subtle.) See if you can figure out where the error was!
If you solved this problem and came up with a strategy that seems to beat 3125, then we promise you made a mistake somewhere. (We checked all the solutions very carefully; many of the errors were very subtle.) See if you can figure out where the error was!
MiraBernstein
2021-05-19 22:58:39
If you came up with a strategy that doesn’t beat 3125, but intuitively feels like it should , figure out why it’s actually less efficient. For some of the best strategies, this is not so easy to understand: I still haven’t completely wrapped my mind around it…
If you came up with a strategy that doesn’t beat 3125, but intuitively feels like it should , figure out why it’s actually less efficient. For some of the best strategies, this is not so easy to understand: I still haven’t completely wrapped my mind around it…
MiraBernstein
2021-05-19 22:58:50
(One last thing to remember as you think about this: the optimal strategy depends on the probability of each person being sick. For 5%, this one happens to be the best strategy we know, but other strategies will certainly beat it for other probabilities.)
(One last thing to remember as you think about this: the optimal strategy depends on the probability of each person being sick. For 5%, this one happens to be the best strategy we know, but other strategies will certainly beat it for other probabilities.)
MiraBernstein
2021-05-19 22:59:15
Whew, that's it for #5, though there's lots more to tell!
Whew, that's it for #5, though there's lots more to tell!
MiraBernstein
2021-05-19 22:59:22
Thanks for sticking it out for so long!
Thanks for sticking it out for so long!
MiraBernstein
2021-05-19 22:59:40
If we didn't get to your question, you can also post in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too.
If we didn't get to your question, you can also post in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too.
MiraBernstein
2021-05-19 22:59:48
We hope you enjoyed this year's QQ, and stay tuned for the 2022 Quiz (and the summer 2022 application) coming up 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.
Thanks again, everybody - good night!
We hope you enjoyed this year's QQ, and stay tuned for the 2022 Quiz (and the summer 2022 application) coming up 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.
Thanks again, everybody - good night!
yofro
2021-05-19 23:00:08
But is there any strategy that is better asymptotically? Like something like $O(\log\log n)$ instead of $O(\log n)$
But is there any strategy that is better asymptotically? Like something like $O(\log\log n)$ instead of $O(\log n)$
MiraBernstein
2021-05-19 23:00:13
Not that we know of.
Not that we know of.
MiraBernstein
2021-05-19 23:00:30
But again, it also depends on the probability of being sick
But again, it also depends on the probability of being sick
GeronimoStilton
2021-05-19 23:00:37
Thank you!
Thank you!
HollyFalcon
2021-05-19 23:00:37
Good night!
Good night!
yofro
2021-05-19 23:00:37
Thanks, bye!
Thanks, bye!
JamesSohigian
2021-05-19 23:00:37
Thanks
Thanks
peace09
2021-05-19 23:00:55
TYSM!
TYSM!
Enthurelx
2021-05-19 23:00:55
Thanks
Thanks
Lilavigne
2021-05-19 23:01:02
Thank you!
Thank you!
gordonhero
2021-05-19 23:01:13
Thank you!!
Thank you!!
w_aops
2021-05-19 23:01:13
Thank you!
Thank you!
MiraBernstein
2021-05-19 23:01:16
Thank you guys!
Thank you guys!
MiraBernstein
2021-05-19 23:01:26
I admire your attention span!
I admire your attention span!
AngelBell
2021-05-19 23:02:21
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/
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.
