Mathcamp 2018 Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveMathcamp is an intensive 5-week-long summer program for mathematically talented high school students. More than just a summer camp, Mathcamp is a vibrant community, made up of a wide variety of people who share a common love of learning and passion for mathematics. At Mathcamp, students can explore undergraduate and even graduate-level topics while building problem-solving skills that will help them in any field they choose to study. This Math Jam will discuss solutions to the 2018 Mathcamp Qualifying Quiz.
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:
5space
2018-05-14 19:31:06
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
5space
2018-05-14 19:31:10
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.
5space
2018-05-14 19:31:15
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.
5space
2018-05-14 19:31:26
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
5space
2018-05-14 19:31:33
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: http://www.mathcamp.org
5space
2018-05-14 19:31:40
Many AoPS instructors, assistants, and students are alumni of this outstanding problem!
Many AoPS instructors, assistants, and students are alumni of this outstanding problem!
5space
2018-05-14 19:31:48
Each year, Mathcamp releases a Qualifying Quiz that is the main component of the application process. If you haven't already seen it, you can find the 2018 Qualifying Quiz at http://www.mathcamp.org/prospectiveapplicants/quiz/index.php . In this Math Jam, the following Canada/USA Mathcamp admission committee members will discuss the problems from this year's Qualifying Quiz:
Each year, Mathcamp releases a Qualifying Quiz that is the main component of the application process. If you haven't already seen it, you can find the 2018 Qualifying Quiz at http://www.mathcamp.org/prospectiveapplicants/quiz/index.php . In this Math Jam, the following Canada/USA Mathcamp admission committee members will discuss the problems from this year's Qualifying Quiz:
5space
2018-05-14 19:31:59
Misha Lavrov (Misha) is a postdoc at the University of Illinois and has been teaching topics ranging from graph theory to pillow-throwing at Mathcamp since 2014.
Misha Lavrov (Misha) is a postdoc at the University of Illinois and has been teaching topics ranging from graph theory to pillow-throwing at Mathcamp since 2014.
5space
2018-05-14 19:32:06
Yasha (Yasha) is a postdoc at Washington University in St. Louis. He's been a Mathcamp camper, JC, and visitor.
Yasha (Yasha) is a postdoc at Washington University in St. Louis. He's been a Mathcamp camper, JC, and visitor.
5space
2018-05-14 19:32:14
Yulia Gorlina (ygorlina) was a Mathcamp student in '99 - '01 and staff in '02 - '04. She went to Caltech for undergrad, and then the University of Arizona for grad school, where she got a Ph.D. in math. She's about to start a new job as a Data Architect at a hospital in Chicago.
Yulia Gorlina (ygorlina) was a Mathcamp student in '99 - '01 and staff in '02 - '04. She went to Caltech for undergrad, and then the University of Arizona for grad school, where she got a Ph.D. in math. She's about to start a new job as a Data Architect at a hospital in Chicago.
5space
2018-05-14 19:32:20
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.
5space
2018-05-14 19:32:28
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
Kevin Carde (KevinCarde) is the Assistant Director and CTO of Mathcamp. He's been teaching Algebraic Combinatorics and playing piano at Mathcamp every summer since 2011.
ccx09
2018-05-14 19:32:36
hello!
hello!
Lolol007
2018-05-14 19:32:36
hello
hello
matharcher
2018-05-14 19:32:36
Hello!
Hello!
5space
2018-05-14 19:32:38
Let's turn the room over to Marisa now to get us started!
Let's turn the room over to Marisa now to get us started!
MarisaD
2018-05-14 19:33:08
Hi, everybody, and welcome to the (now annual) Mathcamp Qualifying Quiz Jam!
Hi, everybody, and welcome to the (now annual) Mathcamp Qualifying Quiz Jam!
MarisaD
2018-05-14 19:33:20
A big thanks as always to @5space, @rrusczyk, and the AoPS team for hosting us.
A big thanks as always to @5space, @rrusczyk, and the AoPS team for hosting us.
MarisaD
2018-05-14 19:33:26
We're here to talk about the Mathcamp 2018 Qualifying Quiz. To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/2018/qquiz.php
We're here to talk about the Mathcamp 2018 Qualifying Quiz. To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/2018/qquiz.php
MarisaD
2018-05-14 19:33:32
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
2018-05-14 19:33:46
If you applied this year, I highly recommend having your solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
If you applied this year, I highly recommend having your solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
MarisaD
2018-05-14 19:34:01
Students can use LaTeX in this classroom, just like on the message board. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We know that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We know that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
Students can use LaTeX in this classroom, just like on the message board. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We know that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We know that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
MarisaD
2018-05-14 19:34:17
Also, as @5space 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 @5space 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
2018-05-14 19:34:30
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, you'll find lots of info on our website (e.g., at 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=455
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, you'll find lots of info on our website (e.g., at 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=455
MarisaD
2018-05-14 19:34:45
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
joshuawang
2018-05-14 19:35:01
when does it take place
when does it take place
buckley
2018-05-14 19:35:01
hi!
hi!
maths_fun
2018-05-14 19:35:01
hi
hi
AtlasO
2018-05-14 19:35:01
Hi Marisa!
Hi Marisa!
Vfire
2018-05-14 19:35:01
hello !!!!!
hello !!!!!
reedmj
2018-05-14 19:35:01
Hello!
Hello!
falls
2018-05-14 19:35:01
Hello!
Hello!
AtlasO
2018-05-14 19:35:01
Hi!
Hi!
pretzel
2018-05-14 19:35:01
hello!
hello!
MarisaD
2018-05-14 19:35:04
Hi all!
Hi all!
MarisaD
2018-05-14 19:35:08
We've got a lot to cover, so let's get started! We're aiming to keep it to two hours tonight. With that, I'll turn it over to Yulia to get us started with Problem #1.
We've got a lot to cover, so let's get started! We're aiming to keep it to two hours tonight. With that, I'll turn it over to Yulia to get us started with Problem #1.
maths_fun
2018-05-14 19:35:25
hihi
hihi
AtlasO
2018-05-14 19:35:25
Hi Yulia!
Hi Yulia!
ygorlina
2018-05-14 19:35:55
Hello everyone
Hello everyone
ygorlina
2018-05-14 19:35:57
Problem 1.
Problem 1.
lucaswu
2018-05-14 19:35:59
hello
hello
Vfire
2018-05-14 19:35:59
hi hi hi
hi hi hi
duck_master
2018-05-14 19:35:59
hi yulia
hi yulia
Svj1215
2018-05-14 19:35:59
Hi
Hi
ygorlina
2018-05-14 19:37:10
João and Kinga play a game with a fair $n$-sided die whose faces are numbered $1, 2, 3, \dots, n$. In this game, João is assigned a value $j$ and Kinga is assigned a value $k$, both also in the range $1, 2, 3, \dots, n$. João and Kinga take turns rolling the die; João goes first.
João and Kinga play a game with a fair $n$-sided die whose faces are numbered $1, 2, 3, \dots, n$. In this game, João is assigned a value $j$ and Kinga is assigned a value $k$, both also in the range $1, 2, 3, \dots, n$. João and Kinga take turns rolling the die; João goes first.
ygorlina
2018-05-14 19:37:20
If João rolls a number less than or equal to $j$, the game ends and he wins. If Kinga rolls a number less than or equal to $k$, the game ends and she wins. The game continues until one player wins.
If João rolls a number less than or equal to $j$, the game ends and he wins. If Kinga rolls a number less than or equal to $k$, the game ends and she wins. The game continues until one player wins.
ygorlina
2018-05-14 19:37:32
(a) Show that if $j=k$, then João always has an advantage.
(b) If $n=6$, find all possible values of $j$ and $k$ which make the game fair. (That is, João and Kinga have equal 50% chances of winning.)
(c) If $n=101$, show that no values of $j$ and $k$ will make the game fair.
(a) Show that if $j=k$, then João always has an advantage.
(b) If $n=6$, find all possible values of $j$ and $k$ which make the game fair. (That is, João and Kinga have equal 50% chances of winning.)
(c) If $n=101$, show that no values of $j$ and $k$ will make the game fair.
ygorlina
2018-05-14 19:37:55
Part (a) solution
Part (a) solution
ygorlina
2018-05-14 19:38:08
You might think intuitively, that it is obvious João has an advantage because he goes first.
You might think intuitively, that it is obvious João has an advantage because he goes first.
ygorlina
2018-05-14 19:38:28
Let’s make this precise.
Let’s make this precise.
ygorlina
2018-05-14 19:38:34
On the first roll, João will win immediately with probability $\frac{j}{n}$ and Kinga will get a chance to roll with probability $\frac{n-j}{n}$.
On the first roll, João will win immediately with probability $\frac{j}{n}$ and Kinga will get a chance to roll with probability $\frac{n-j}{n}$.
ygorlina
2018-05-14 19:38:45
After that first roll, João’s and Kinga’s roles become reversed!
After that first roll, João’s and Kinga’s roles become reversed!
ygorlina
2018-05-14 19:38:56
Right before Kinga takes her first roll, her probability of winning the whole game is the same as João’s probability was right before he took his first roll.
Right before Kinga takes her first roll, her probability of winning the whole game is the same as João’s probability was right before he took his first roll.
ygorlina
2018-05-14 19:39:23
Let’s call the probability of João winning $P$ the game. Then the probability of Kinga winning is $$P\cdot\frac{n-j}{n}$$
Let’s call the probability of João winning $P$ the game. Then the probability of Kinga winning is $$P\cdot\frac{n-j}{n}$$
ygorlina
2018-05-14 19:39:40
Since $1\leq j\leq n$, João will always have an advantage.
Since $1\leq j\leq n$, João will always have an advantage.
ygorlina
2018-05-14 19:40:03
You could also compute the $P$ in terms of $j$ and $n$. We’ll use that for parts (b) and (c)!
You could also compute the $P$ in terms of $j$ and $n$. We’ll use that for parts (b) and (c)!
ygorlina
2018-05-14 19:40:27
Part (b) solution
Part (b) solution
ygorlina
2018-05-14 19:40:34
To figure this out, let’s calculate the probability $P$ that João will win the game.
To figure this out, let’s calculate the probability $P$ that João will win the game.
ygorlina
2018-05-14 19:40:44
Just like in Part (a), João will win on the first roll with probability $\frac{j}{n}$ and Kinga will get a chance to roll with probability $\frac{n-j}{n}$.
Just like in Part (a), João will win on the first roll with probability $\frac{j}{n}$ and Kinga will get a chance to roll with probability $\frac{n-j}{n}$.
ygorlina
2018-05-14 19:40:58
Then, Kinga will win on her first roll with probability $\frac{k}{n}$ and João will get a chance to roll again with probability $\frac{n-k}{n}$.
Then, Kinga will win on her first roll with probability $\frac{k}{n}$ and João will get a chance to roll again with probability $\frac{n-k}{n}$.
ygorlina
2018-05-14 19:41:10
That means that the probability that João gets to roll a second time is $\frac{n-j}{n}\cdot\frac{n-k}{n}$.
That means that the probability that João gets to roll a second time is $\frac{n-j}{n}\cdot\frac{n-k}{n}$.
crocodile_40
2018-05-14 19:41:25
so geometric series?
so geometric series?
ygorlina
2018-05-14 19:41:33
You could use geometric series, yes!
You could use geometric series, yes!
ygorlina
2018-05-14 19:41:49
However, the solution I will show you is similar to how we did part (a)
However, the solution I will show you is similar to how we did part (a)
ygorlina
2018-05-14 19:41:57
At that point, the game resets to the beginning, so João’s chance of winning the whole game starting with his second roll is $P$.
At that point, the game resets to the beginning, so João’s chance of winning the whole game starting with his second roll is $P$.
ygorlina
2018-05-14 19:42:11
So,
$$P = \frac{j}{n} + \frac{n-j}{n}\cdot\frac{n-k}{n}P$$
So,
$$P = \frac{j}{n} + \frac{n-j}{n}\cdot\frac{n-k}{n}P$$
ygorlina
2018-05-14 19:42:28
Solving this for $P$, we get
$$P=\frac{jn}{jn+kn-jk}$$
Solving this for $P$, we get
$$P=\frac{jn}{jn+kn-jk}$$
ygorlina
2018-05-14 19:42:40
Now, let $P=\frac{1}{2}$ and simplify:
Now, let $P=\frac{1}{2}$ and simplify:
ygorlina
2018-05-14 19:42:54
$$jk=n(k-j)$$
$$jk=n(k-j)$$
ygorlina
2018-05-14 19:43:05
For Part (b), $n=6$. From here, you can check all possible values of $j$ and $k$. This is made easier if you notice that $k>j$, which we could also conclude from Part (a).
For Part (b), $n=6$. From here, you can check all possible values of $j$ and $k$. This is made easier if you notice that $k>j$, which we could also conclude from Part (a).
ygorlina
2018-05-14 19:43:24
The two solutions are $j=2, k=3$, and $j=3, k=6$.
The two solutions are $j=2, k=3$, and $j=3, k=6$.
ygorlina
2018-05-14 19:43:30
Notice that in the latter case, the game will always be very short, ending either on João’s or Kinga’s first roll.
Notice that in the latter case, the game will always be very short, ending either on João’s or Kinga’s first roll.
ygorlina
2018-05-14 19:43:51
Part (c) solution
Part (c) solution
ygorlina
2018-05-14 19:43:58
We can actually generalize and let $n$ be any prime $p>2$.
We can actually generalize and let $n$ be any prime $p>2$.
ygorlina
2018-05-14 19:44:19
$$jk=p(k-j)$$
$$jk=p(k-j)$$
ygorlina
2018-05-14 19:44:27
Since $p$ divides $jk$, it must divide either $j$ or $k$.
Since $p$ divides $jk$, it must divide either $j$ or $k$.
ygorlina
2018-05-14 19:44:58
We know that $1\leq j < k \leq p$, so $k$ must equal $p$. However, then $j=\frac{p}{2}$, which is not an integer.
We know that $1\leq j < k \leq p$, so $k$ must equal $p$. However, then $j=\frac{p}{2}$, which is not an integer.
ygorlina
2018-05-14 19:45:12
So, when $n$ is prime, the game cannot be fair.
So, when $n$ is prime, the game cannot be fair.
rikhilranjit
2018-05-14 19:45:17
Why can we generate and let n be a prime number? Sorry if this isn't a good question. I am only in 5th grade.
Why can we generate and let n be a prime number? Sorry if this isn't a good question. I am only in 5th grade.
ygorlina
2018-05-14 19:45:31
Thank you for your question!
Thank you for your question!
ygorlina
2018-05-14 19:46:03
The solutions is the same for every prime. So whether we use $n=101$ or $n$ is any odd prime, you can use the same solution.
The solutions is the same for every prime. So whether we use $n=101$ or $n$ is any odd prime, you can use the same solution.
Kreps
2018-05-14 19:46:19
why do we know that k>j?
why do we know that k>j?
ygorlina
2018-05-14 19:46:42
$jk$ is positive, so $(k-j)>0$.
$jk$ is positive, so $(k-j)>0$.
ygorlina
2018-05-14 19:47:10
Alright, I will pass things over to Misha for Problem 2.
Alright, I will pass things over to Misha for Problem 2.
Misha
2018-05-14 19:47:20
ok let's see if I can figure out how to work this
ok let's see if I can figure out how to work this
Misha
2018-05-14 19:47:30
Problem 2.
Problem 2.
Misha
2018-05-14 19:47:31
The pirates of the Cartesian sail an infinite flat sea, with a small island at coordinates $(x,y)$ for every integer $x$ and $y$.
The pirates of the Cartesian sail an infinite flat sea, with a small island at coordinates $(x,y)$ for every integer $x$ and $y$.
Misha
2018-05-14 19:47:33
A pirate's ship has two sails. Every day, the pirate raises one of the sails and travels for the whole day without stopping. With the first sail raised, a pirate at $(x,y)$ can travel to $(x+3,y+5)$ in a single day, or in the reverse direction to $(x-3,y-5)$. With the second sail raised, a pirate at $(x,y)$ can travel to $(x+4,y+6)$ in a single day, or in the reverse direction to $(x-4,y-6)$.
A pirate's ship has two sails. Every day, the pirate raises one of the sails and travels for the whole day without stopping. With the first sail raised, a pirate at $(x,y)$ can travel to $(x+3,y+5)$ in a single day, or in the reverse direction to $(x-3,y-5)$. With the second sail raised, a pirate at $(x,y)$ can travel to $(x+4,y+6)$ in a single day, or in the reverse direction to $(x-4,y-6)$.
Misha
2018-05-14 19:47:36
(a) Which islands can a pirate reach from the island at $(0,0)$, after traveling for any number of days?
(a) Which islands can a pirate reach from the island at $(0,0)$, after traveling for any number of days?
Misha
2018-05-14 19:47:39
(b) The Dread Pirate Riemann replaces the second sail on his ship by a sail that lets him travel from $(x,y)$ to either $(x+a,y+b)$ or $(x-a,y-b)$ in a single day, where $a$ and $b$ are integers. (The first sail stays the same as in part (a).) For which values of $a$ and $b$ will the Dread Pirate Riemann be able to reach any island in the Cartesian sea?
(b) The Dread Pirate Riemann replaces the second sail on his ship by a sail that lets him travel from $(x,y)$ to either $(x+a,y+b)$ or $(x-a,y-b)$ in a single day, where $a$ and $b$ are integers. (The first sail stays the same as in part (a).) For which values of $a$ and $b$ will the Dread Pirate Riemann be able to reach any island in the Cartesian sea?
Misha
2018-05-14 19:47:41
(c) Can you generalize the result in (b) to two arbitrary sails?
(c) Can you generalize the result in (b) to two arbitrary sails?
Misha
2018-05-14 19:47:56
ok that's the problem. here we go!
ok that's the problem. here we go!
Misha
2018-05-14 19:48:03
Problem 2(a) solution.
Problem 2(a) solution.
Misha
2018-05-14 19:48:06
After we look at the first few islands we can visit, which include islands such as $(3,5), (4,6), (1,1), (6,10), (7,11), (2,4)$, and so on, we might notice a pattern. What do all of these have in common?
After we look at the first few islands we can visit, which include islands such as $(3,5), (4,6), (1,1), (6,10), (7,11), (2,4)$, and so on, we might notice a pattern. What do all of these have in common?
Axolotl
2018-05-14 19:48:25
sum of coordinates is even
sum of coordinates is even
Vfire
2018-05-14 19:48:25
same parity
same parity
Kreps
2018-05-14 19:48:25
the coordinate sum to an even number
the coordinate sum to an even number
dihydrogen
2018-05-14 19:48:25
sum of coordinates is even
sum of coordinates is even
hwl0304
2018-05-14 19:48:25
sum is even
sum is even
Misha
2018-05-14 19:48:31
We can express this a bunch of ways: say that $x+y$ is even, or that $x-y$ is even, or that $x$ and $Y$ are both even or both odd. So if this is true, what are the two things we have to prove?
We can express this a bunch of ways: say that $x+y$ is even, or that $x-y$ is even, or that $x$ and $Y$ are both even or both odd. So if this is true, what are the two things we have to prove?
shroomley
2018-05-14 19:49:08
if x+y is even you can reach it, and if x+y is odd you can't reach it
if x+y is even you can reach it, and if x+y is odd you can't reach it
mathfarmer
2018-05-14 19:49:08
you can get to all such points and only such points.
you can get to all such points and only such points.
StyrofoamCup
2018-05-14 19:49:08
1. We can reach all like this and 2. We can reach none not like this
1. We can reach all like this and 2. We can reach none not like this
Kreps
2018-05-14 19:49:08
that we cannot go to points where the coordinate sum is odd
that we cannot go to points where the coordinate sum is odd
reedmj
2018-05-14 19:49:08
That we can reach it and can't reach anywhere else
That we can reach it and can't reach anywhere else
Misha
2018-05-14 19:49:27
(proving only one of these tripped a lot of people up, actually!)
(proving only one of these tripped a lot of people up, actually!)
Misha
2018-05-14 19:49:30
First, we prove that this condition is necessary: if $x-y$ is odd, then we can't reach island $(x,y)$. Then, we prove that this condition is even: if $x-y$ is even, then we can reach the island.
First, we prove that this condition is necessary: if $x-y$ is odd, then we can't reach island $(x,y)$. Then, we prove that this condition is even: if $x-y$ is even, then we can reach the island.
Misha
2018-05-14 19:49:35
To prove that the condition is necessary, it's enough to look at how $x-y$ changes. We can change it by $-2$ with $(3,5)$ or $(4,6)$ or $+2$ with their opposites. These are all even numbers, so the total is even.
To prove that the condition is necessary, it's enough to look at how $x-y$ changes. We can change it by $-2$ with $(3,5)$ or $(4,6)$ or $+2$ with their opposites. These are all even numbers, so the total is even.
Misha
2018-05-14 19:49:54
To prove that the condition is sufficient, it's enough to show that we can take $(+1,+1)$ steps and $(+2,+0)$ steps (and their opposites). A $(+1,+1)$ step is easy: it's $(+4,+6)$ then $(-3,-5)$. $(+2,+0)$ is longer: it's five $(+4,+6)$ steps and six $(-3,-5)$ steps.
To prove that the condition is sufficient, it's enough to show that we can take $(+1,+1)$ steps and $(+2,+0)$ steps (and their opposites). A $(+1,+1)$ step is easy: it's $(+4,+6)$ then $(-3,-5)$. $(+2,+0)$ is longer: it's five $(+4,+6)$ steps and six $(-3,-5)$ steps.
Misha
2018-05-14 19:50:10
Once we have both of them, we can get to any island with even $x-y$. Just go from $(0,0)$ to $(x-y,0)$ and then to $(x,y)$.
Once we have both of them, we can get to any island with even $x-y$. Just go from $(0,0)$ to $(x-y,0)$ and then to $(x,y)$.
Misha
2018-05-14 19:50:28
So that solves part (a).
So that solves part (a).
Misha
2018-05-14 19:50:37
Problem 2(b) solution.
Problem 2(b) solution.
Misha
2018-05-14 19:50:39
If Riemann can reach any island, then Riemann can reach islands $(1,0)$ and $(0,1)$. But if those are reachable, then by repeating these $(+1,+0)$ and $(+0,+1)$ steps and their opposites, Riemann can get to any island. So there's only two islands we have to check.
If Riemann can reach any island, then Riemann can reach islands $(1,0)$ and $(0,1)$. But if those are reachable, then by repeating these $(+1,+0)$ and $(+0,+1)$ steps and their opposites, Riemann can get to any island. So there's only two islands we have to check.
Misha
2018-05-14 19:50:47
Suppose that Riemann reaches $(1,0)$ after $p$ steps of $(+3,+5)$ and $q$ steps of $(+a,+b)$. Then $(3p + aq, 5p + bq) = (1,0)$, which means $$5 = 5(1) - 3(0) = 5(5p+bq) - 3(3p+aq) = (5a-3b)(q).$$ What does this tell us about $5a-3b$?
Suppose that Riemann reaches $(1,0)$ after $p$ steps of $(+3,+5)$ and $q$ steps of $(+a,+b)$. Then $(3p + aq, 5p + bq) = (1,0)$, which means $$5 = 5(1) - 3(0) = 5(5p+bq) - 3(3p+aq) = (5a-3b)(q).$$ What does this tell us about $5a-3b$?
tluo5458
2018-05-14 19:51:21
isn't (+1, +1) and (+3, +5) enough?
isn't (+1, +1) and (+3, +5) enough?
pretzel
2018-05-14 19:51:21
divides 5
divides 5
crocodile_40
2018-05-14 19:51:21
5a - 3b must be a multiple of 5
5a - 3b must be a multiple of 5
Misha
2018-05-14 19:51:36
whoops that was me being slightly bad at passing on things
whoops that was me being slightly bad at passing on things
Misha
2018-05-14 19:51:46
but it tells us that $5a-3b$ divides $5$.
but it tells us that $5a-3b$ divides $5$.
Misha
2018-05-14 19:51:48
Suppose that Riemann reaches $(0,1)$ after $p$ steps of $(+3,+5)$ and $q$ steps of $(+a,+b)$. Then $(3p + aq, 5p + bq) = (0,1)$, which means $$3 = 3(1) - 5(0) = 3(5p+bq) - 5(3p+aq) = (5a-3b)(-q).$$ What does this tell us about $5a-3b$?
Suppose that Riemann reaches $(0,1)$ after $p$ steps of $(+3,+5)$ and $q$ steps of $(+a,+b)$. Then $(3p + aq, 5p + bq) = (0,1)$, which means $$3 = 3(1) - 5(0) = 3(5p+bq) - 5(3p+aq) = (5a-3b)(-q).$$ What does this tell us about $5a-3b$?
StyrofoamCup
2018-05-14 19:52:06
It divides 3
It divides 3
pretzel
2018-05-14 19:52:06
divides 3
divides 3
Misha
2018-05-14 19:52:34
So now we know that if $5a-3b$ divides both $3$ and $5...
So now we know that if $5a-3b$ divides both $3$ and $5...
dihydrogen
2018-05-14 19:52:40
it must be $1$
it must be $1$
Kreps
2018-05-14 19:52:40
gcf(5,3) = 1
gcf(5,3) = 1
Misha
2018-05-14 19:52:46
Conversely, if $5a-3b = \pm 1$, then Riemann can get to both $(0,1)$ and $(1,0)$. (And so Riemann can get anywhere.) For example, if $5a-3b = 1$, then Riemann can get to $(1,0)$ by 5 steps of $(+a,+b)$ and $b$ steps of $(-3,-5)$.
Conversely, if $5a-3b = \pm 1$, then Riemann can get to both $(0,1)$ and $(1,0)$. (And so Riemann can get anywhere.) For example, if $5a-3b = 1$, then Riemann can get to $(1,0)$ by 5 steps of $(+a,+b)$ and $b$ steps of $(-3,-5)$.
AtlasO
2018-05-14 19:53:16
Cool proof
Cool proof
Misha
2018-05-14 19:53:19
thanks
thanks
Misha
2018-05-14 19:53:20
Problem 2(c) solution.
Problem 2(c) solution.
Misha
2018-05-14 19:53:26
When our sails were $(+3,+5)$ and $(+a,+b)$ and their opposites, we needed $5a-3b = \pm 1$. So if our sails are $(+a,+b)$ and $(+c,+d)$ and their opposites, what's a natural condition to guess?
When our sails were $(+3,+5)$ and $(+a,+b)$ and their opposites, we needed $5a-3b = \pm 1$. So if our sails are $(+a,+b)$ and $(+c,+d)$ and their opposites, what's a natural condition to guess?
StyrofoamCup
2018-05-14 19:54:03
Just slap in 5 = b, 3 = a, and use the formula from last time?
Just slap in 5 = b, 3 = a, and use the formula from last time?
mrbox
2018-05-14 19:54:03
ad - bc = +- 1
ad - bc = +- 1
shroomley
2018-05-14 19:54:03
ad-bc=+ or - 1
ad-bc=+ or - 1
Misha
2018-05-14 19:54:11
It turns out that $ad-bc = \pm1$ is the condition we want. If it holds, then Riemann can get from $(0,0)$ to $(0,1)$ and to $(1,0)$, so he can get anywhere. For example, how would you go from $(0,0)$ to $(1,0)$ if $ad-bc = 1$?
It turns out that $ad-bc = \pm1$ is the condition we want. If it holds, then Riemann can get from $(0,0)$ to $(0,1)$ and to $(1,0)$, so he can get anywhere. For example, how would you go from $(0,0)$ to $(1,0)$ if $ad-bc = 1$?
Misha
2018-05-14 19:54:31
(by the way, people that are saying the word "determinant": hold on a couple of minutes
(by the way, people that are saying the word "determinant": hold on a couple of minutes
Misha
2018-05-14 19:55:05
Almost as before, we can take $d$ steps of $(+a,+b)$ and $b$ steps of $(-c,-d)$. Something similar works for going to $(0,1)$, and this proves that having $ad-bc = \pm1$ is sufficient. We also need to prove that it's necessary.
Almost as before, we can take $d$ steps of $(+a,+b)$ and $b$ steps of $(-c,-d)$. Something similar works for going to $(0,1)$, and this proves that having $ad-bc = \pm1$ is sufficient. We also need to prove that it's necessary.
mathfarmer
2018-05-14 19:55:17
a steps of sail 2 and d of sail 1?
a steps of sail 2 and d of sail 1?
Misha
2018-05-14 19:55:20
yep!
yep!
Misha
2018-05-14 19:55:26
We can copy the algebra in part (b) to prove that $ad-bc$ must be a divisor of both $a$ and $b$: just replace 3 and 5 by $c$ and $d$. Actually, we can also prove that $ad-bc$ is a divisor of both $c$ and $d$, by switching the roles of the two sails. Why does this prove that we need $ad-bc = \pm 1$?
We can copy the algebra in part (b) to prove that $ad-bc$ must be a divisor of both $a$ and $b$: just replace 3 and 5 by $c$ and $d$. Actually, we can also prove that $ad-bc$ is a divisor of both $c$ and $d$, by switching the roles of the two sails. Why does this prove that we need $ad-bc = \pm 1$?
reedmj
2018-05-14 19:56:39
All the distances we travel will always be multiples of the numbers' gcd's, so their gcd's have to be 1 since we can go anywhere
All the distances we travel will always be multiples of the numbers' gcd's, so their gcd's have to be 1 since we can go anywhere
Misha
2018-05-14 19:56:45
If $ad-bc$ is not $\pm 1$, then $a,b,c,d$ have a nontrivial divisor. In that case, we can only get to islands whose coordinates are multiples of that divisor.
If $ad-bc$ is not $\pm 1$, then $a,b,c,d$ have a nontrivial divisor. In that case, we can only get to islands whose coordinates are multiples of that divisor.
Misha
2018-05-14 19:57:10
And finally, for people who know linear algebra...
And finally, for people who know linear algebra...
Misha
2018-05-14 19:57:11
Note: $ad-bc$ is the determinant of the $2\times 2$ matrix $\begin{bmatrix}a&b \\ c&d\end{bmatrix}$. This problem is actually equivalent to showing that this matrix has an integer inverse exactly when its determinant is $\pm 1$, which is a very useful result from linear algebra!
Note: $ad-bc$ is the determinant of the $2\times 2$ matrix $\begin{bmatrix}a&b \\ c&d\end{bmatrix}$. This problem is actually equivalent to showing that this matrix has an integer inverse exactly when its determinant is $\pm 1$, which is a very useful result from linear algebra!
Misha
2018-05-14 19:57:29
but as we just saw, we can also solve this problem with just basic number theory.
but as we just saw, we can also solve this problem with just basic number theory.
Misha
2018-05-14 19:57:35
on to #3!
on to #3!
Misha
2018-05-14 19:57:38
Problem 3.
Problem 3.
Misha
2018-05-14 19:57:40
For any positive integer $n$, its list of divisors contains all integers between 1 and $n$, including 1 and $n$ itself, that divide $n$ with no remainder; they are always listed in increasing order. For example, if $n = 20$, its list of divisors is $1, 2, 4, 5, 10, 20$.
For any positive integer $n$, its list of divisors contains all integers between 1 and $n$, including 1 and $n$ itself, that divide $n$ with no remainder; they are always listed in increasing order. For example, if $n = 20$, its list of divisors is $1, 2, 4, 5, 10, 20$.
Misha
2018-05-14 19:57:43
In a fill-in-the-blank puzzle, we take the list of divisors, erase some of them and replace them with blanks, and ask what the original number was.
In a fill-in-the-blank puzzle, we take the list of divisors, erase some of them and replace them with blanks, and ask what the original number was.
Misha
2018-05-14 19:57:48
(a) Solve the puzzle 1, 2, _, _, _, 8, _, _.
(a) Solve the puzzle 1, 2, _, _, _, 8, _, _.
Misha
2018-05-14 19:57:49
(b) Does there exist a fill-in-the-blank puzzle that has exactly 2018 solutions?
(b) Does there exist a fill-in-the-blank puzzle that has exactly 2018 solutions?
Misha
2018-05-14 19:57:50
(c) For each value of $n$, the very hard puzzle for $n$ is the one that leaves only the next-to-last divisor, replacing all the others with blanks. For example, the very hard puzzle for 10 is _, _, 5, _. It has two solutions: 10 and 15. For which values of $n$ does the very hard puzzle for $n$ have no solutions other than $n$?
(c) For each value of $n$, the very hard puzzle for $n$ is the one that leaves only the next-to-last divisor, replacing all the others with blanks. For example, the very hard puzzle for 10 is _, _, 5, _. It has two solutions: 10 and 15. For which values of $n$ does the very hard puzzle for $n$ have no solutions other than $n$?
Misha
2018-05-14 19:57:57
Let's warm up by solving part (a). What's the only value that $n$ can have?
Let's warm up by solving part (a). What's the only value that $n$ can have?
pretzel
2018-05-14 19:58:27
24
24
dihydrogen
2018-05-14 19:58:27
$24$
$24$
mathlogician
2018-05-14 19:58:27
24.
24.
Axolotl
2018-05-14 19:58:27
24
24
StyrofoamCup
2018-05-14 19:58:27
24
24
AtlasO
2018-05-14 19:58:27
1, 2, 3, 4, 6, 8, 12, 24
1, 2, 3, 4, 6, 8, 12, 24
hwl0304
2018-05-14 19:58:27
24
24
AtlasO
2018-05-14 19:58:27
24
24
ccx09
2018-05-14 19:58:27
24
24
PSC
2018-05-14 19:58:27
24
24
porkemon2
2018-05-14 19:58:27
24
24
shroomley
2018-05-14 19:58:27
24
24
Misha
2018-05-14 19:58:33
The logic is this: the blanks before 8 include 1, 2, 4, and two other numbers. So the original number has at least one more prime divisor other than 2, and that prime divisor appears before 8 on the list: it can be 3, 5, or 7.
The logic is this: the blanks before 8 include 1, 2, 4, and two other numbers. So the original number has at least one more prime divisor other than 2, and that prime divisor appears before 8 on the list: it can be 3, 5, or 7.
Misha
2018-05-14 19:58:42
If it's 3, we get 1, 2, 3, 4, 6, 8, 12, 24. If it's 5 or 7, we don't get a solution: 10 and 14 are both bigger than 8, so they need the blanks to be in a different order.
If it's 3, we get 1, 2, 3, 4, 6, 8, 12, 24. If it's 5 or 7, we don't get a solution: 10 and 14 are both bigger than 8, so they need the blanks to be in a different order.
Misha
2018-05-14 19:58:55
this is a good practice for the later parts
this is a good practice for the later parts
Misha
2018-05-14 19:58:58
Problem 3(b) solution.
Problem 3(b) solution.
Misha
2018-05-14 19:59:02
The warm-up problem gives us a pretty good hint for part (b). The extra blanks before 8 gave us 3 cases. (Not all of the solutions worked out, but that's a minor detail.) So how do we get 2018 cases?
The warm-up problem gives us a pretty good hint for part (b). The extra blanks before 8 gave us 3 cases. (Not all of the solutions worked out, but that's a minor detail.) So how do we get 2018 cases?
ccx09
2018-05-14 19:59:31
1, _ , p_2019, _
1, _ , p_2019, _
reedmj
2018-05-14 19:59:31
2018 primes less than n
2018 primes less than n
shroomley
2018-05-14 19:59:31
1, blank, 2019th prime, blank
1, blank, 2019th prime, blank
Axolotl
2018-05-14 19:59:31
2019th prime
2019th prime
Misha
2018-05-14 19:59:40
(more blanks doesn't help us - it's more primes that does)
(more blanks doesn't help us - it's more primes that does)
Misha
2018-05-14 19:59:43
We want to go up to a number with 2018 primes below it. The simplest puzzle would be 1, _, 17569, _, where 17569 is the 2019-th prime. (For any prime p below 17659, we get a solution 1, p, 17569, 17569p.) There are other solutions along the same lines.
We want to go up to a number with 2018 primes below it. The simplest puzzle would be 1, _, 17569, _, where 17569 is the 2019-th prime. (For any prime p below 17659, we get a solution 1, p, 17569, 17569p.) There are other solutions along the same lines.
Misha
2018-05-14 19:59:59
Problem 3(c) solution.
Problem 3(c) solution.
Misha
2018-05-14 20:00:03
Here's two examples of "very hard" puzzles. One is "_, _, _, 35, _". Another is "_, _, _, _, _, _, 35, _". Which has a unique solution, and which one doesn't?
Here's two examples of "very hard" puzzles. One is "_, _, _, 35, _". Another is "_, _, _, _, _, _, 35, _". Which has a unique solution, and which one doesn't?
mrbox
2018-05-14 20:00:47
the first one is the unique solution, second one isnt
the first one is the unique solution, second one isnt
Kreps
2018-05-14 20:00:47
the first one has a unique solution
the first one has a unique solution
Burrito
2018-05-14 20:00:47
the first one has a unique solution and the second one does not
the first one has a unique solution and the second one does not
PCampbell
2018-05-14 20:00:47
First one has a unique solution
First one has a unique solution
Misha
2018-05-14 20:00:53
By counting the divisors of the number we see, and comparing it to the number of blanks there are, we can see that the first puzzle doesn't introduce any new prime factors, and the second puzzle does. (This can be done in general.) So the first puzzle must begin "1, 5, ..." and the answer is $5\cdot 35 = 175$. The second puzzle can begin "1, 2, ..." or "1, 3, ..." and has multiple solutions.
By counting the divisors of the number we see, and comparing it to the number of blanks there are, we can see that the first puzzle doesn't introduce any new prime factors, and the second puzzle does. (This can be done in general.) So the first puzzle must begin "1, 5, ..." and the answer is $5\cdot 35 = 175$. The second puzzle can begin "1, 2, ..." or "1, 3, ..." and has multiple solutions.
Misha
2018-05-14 20:01:13
(I'm skipping some of the arithmetic here, but you can count how many divisors $175$ has, and that helps.)
(I'm skipping some of the arithmetic here, but you can count how many divisors $175$ has, and that helps.)
Misha
2018-05-14 20:01:23
When does the next-to-last divisor of $n$ already contain all its prime factors?
When does the next-to-last divisor of $n$ already contain all its prime factors?
shroomley
2018-05-14 20:01:58
when the smallest prime that divides n is taken to a power greater than 1
when the smallest prime that divides n is taken to a power greater than 1
StyrofoamCup
2018-05-14 20:01:58
When n is divisible by the square of its smallest prime factor
When n is divisible by the square of its smallest prime factor
Misha
2018-05-14 20:02:06
This happens when $n$'s smallest prime factor is repeated. (For example, $175 = 5 \cdot 5 \cdot 7$.) In such cases, the very hard puzzle for $n$ always has a unique solution.
This happens when $n$'s smallest prime factor is repeated. (For example, $175 = 5 \cdot 5 \cdot 7$.) In such cases, the very hard puzzle for $n$ always has a unique solution.
Misha
2018-05-14 20:02:21
this is because the next-to-last divisor tells us what all the prime factors are, here
this is because the next-to-last divisor tells us what all the prime factors are, here
Misha
2018-05-14 20:02:31
so we can just fill the smallest one
so we can just fill the smallest one
Misha
2018-05-14 20:02:36
but there's another case...
but there's another case...
Misha
2018-05-14 20:02:39
Now suppose that $n$ has a prime factor missing from its next-to-last divisor. Are there any cases when we can deduce what that prime factor must be?
Now suppose that $n$ has a prime factor missing from its next-to-last divisor. Are there any cases when we can deduce what that prime factor must be?
StyrofoamCup
2018-05-14 20:03:16
if we know it's divisible by 3 from the second to last entry
if we know it's divisible by 3 from the second to last entry
shroomley
2018-05-14 20:03:16
when the first prime factor is 2 and the second one is 3
when the first prime factor is 2 and the second one is 3
Misha
2018-05-14 20:03:22
The missing prime factor must be the smallest. So we can figure out what it is if it's 2, and the prime factor 3 is already present. (For example, "_, _, _, _, 9, _" only has one solution.)
The missing prime factor must be the smallest. So we can figure out what it is if it's 2, and the prime factor 3 is already present. (For example, "_, _, _, _, 9, _" only has one solution.)
Misha
2018-05-14 20:03:28
So there are two cases answering this question: the very hard puzzle for $n$ has only one solution if $n$'s smallest prime factor is repeated, or if $n$ is divisible by both 2 and 3.
So there are two cases answering this question: the very hard puzzle for $n$ has only one solution if $n$'s smallest prime factor is repeated, or if $n$ is divisible by both 2 and 3.
Misha
2018-05-14 20:03:49
Alright. On to...
Alright. On to...
Misha
2018-05-14 20:03:50
Problem 4.
Problem 4.
Misha
2018-05-14 20:03:52
A flock of $3^k$ crows hold a speed-flying competition. All crows have different speeds, and each crow's speed remains the same throughout the competition. Because crows love secrecy, they don't want to be distinctive and recognizable, so instead of trying to find the fastest or slowest crow, they want to be as medium as possible.
A flock of $3^k$ crows hold a speed-flying competition. All crows have different speeds, and each crow's speed remains the same throughout the competition. Because crows love secrecy, they don't want to be distinctive and recognizable, so instead of trying to find the fastest or slowest crow, they want to be as medium as possible.
Misha
2018-05-14 20:03:54
The crows split into groups of 3 at random and then race. In each group of 3, the crow that finishes second wins, so there are $3^{k-1}$ winners, who repeat this process. In each round, a third of the crows win, and move on to the next round. The crow left after $k$ rounds is declared the most medium crow.
The crows split into groups of 3 at random and then race. In each group of 3, the crow that finishes second wins, so there are $3^{k-1}$ winners, who repeat this process. In each round, a third of the crows win, and move on to the next round. The crow left after $k$ rounds is declared the most medium crow.
Misha
2018-05-14 20:03:57
(a) How many of the crows have a chance (depending on which groups of 3 compete together) of being declared the most medium?
(a) How many of the crows have a chance (depending on which groups of 3 compete together) of being declared the most medium?
Misha
2018-05-14 20:03:59
(b) If there are $n$ crows, where $n$ is not a power of 3, this process has to be modified. In a round where the crows cannot be evenly divided into groups of 3, one or two crows are randomly chosen to sit out: they automatically move on to the next round. At the end, there is either a single crow declared the most medium, or a tie between two crows.
(b) If there are $n$ crows, where $n$ is not a power of 3, this process has to be modified. In a round where the crows cannot be evenly divided into groups of 3, one or two crows are randomly chosen to sit out: they automatically move on to the next round. At the end, there is either a single crow declared the most medium, or a tie between two crows.
Misha
2018-05-14 20:04:01
For which values of $n$ will a single crow be declared the most medium? When this happens, which of the crows can it be?
For which values of $n$ will a single crow be declared the most medium? When this happens, which of the crows can it be?
Misha
2018-05-14 20:04:12
(I'll give you a moment to remind yourself of the problem.)
(I'll give you a moment to remind yourself of the problem.)
einsteinium612
2018-05-14 20:04:30
induction!
induction!
Misha
2018-05-14 20:04:36
things are certainly looking induction-y
things are certainly looking induction-y
Misha
2018-05-14 20:04:42
Problem 4(a) solution.
Problem 4(a) solution.
Misha
2018-05-14 20:04:46
There's a quick way to see that the $k$ fastest and the $k$ slowest crows can't win the race. The most medium crow has won $k$ rounds, so it's finished second $k$ times. This gives us $k$ crows that were faster (the ones that finished first) and $k$ crows that were slower (the ones that finished third).
There's a quick way to see that the $k$ fastest and the $k$ slowest crows can't win the race. The most medium crow has won $k$ rounds, so it's finished second $k$ times. This gives us $k$ crows that were faster (the ones that finished first) and $k$ crows that were slower (the ones that finished third).
Misha
2018-05-14 20:05:01
But actually, there are lots of other crows that must be faster than the most medium crow. Why?
But actually, there are lots of other crows that must be faster than the most medium crow. Why?
StyrofoamCup
2018-05-14 20:05:50
Because we need at least one buffer crow to take one to the next round
Because we need at least one buffer crow to take one to the next round
shroomley
2018-05-14 20:05:50
because each of the winners from the first round was slower than a crow
because each of the winners from the first round was slower than a crow
dihydrogen
2018-05-14 20:05:50
Each of the crows that the most medium crow faces in later rounds had to win their previous rounds
Each of the crows that the most medium crow faces in later rounds had to win their previous rounds
Misha
2018-05-14 20:05:54
The crows that the most medium crow wins against in later rounds must, themselves, have been fairly medium to make it that far. They have their own crows that they won against. A race with two rounds gives us the following picture:
The crows that the most medium crow wins against in later rounds must, themselves, have been fairly medium to make it that far. They have their own crows that they won against. A race with two rounds gives us the following picture:
Misha
2018-05-14 20:05:57
Misha
2018-05-14 20:06:04
Here, all red crows must be faster than the black (most-medium) crow, and all blue crows must be slower. (Each rectangle is a race, with first through third place drawn from left to right.)
Here, all red crows must be faster than the black (most-medium) crow, and all blue crows must be slower. (Each rectangle is a race, with first through third place drawn from left to right.)
Misha
2018-05-14 20:06:25
Here's another picture for a race with three rounds:
Here's another picture for a race with three rounds:
Misha
2018-05-14 20:06:26
Misha
2018-05-14 20:06:35
Here, all the crows previously marked red were slower than other crows that lost to them in the very first round. Again, all red crows in this picture are faster than the black crow, and all blue crows are slower.
Here, all the crows previously marked red were slower than other crows that lost to them in the very first round. Again, all red crows in this picture are faster than the black crow, and all blue crows are slower.
Misha
2018-05-14 20:07:05
So here, when we started out with $27$ crows, there are $7$ red crows and $7$ blue crows that can't win.
So here, when we started out with $27$ crows, there are $7$ red crows and $7$ blue crows that can't win.
Misha
2018-05-14 20:07:08
If we draw this picture for the $k$-round race, how many red crows must there be at the start? (And how many blue crows?)
If we draw this picture for the $k$-round race, how many red crows must there be at the start? (And how many blue crows?)
Collatz__conjecture
2018-05-14 20:07:39
$2^k$ crows would be kicked out
$2^k$ crows would be kicked out
StyrofoamCup
2018-05-14 20:07:39
2^k-1
2^k-1
reedmj
2018-05-14 20:07:39
$2^k - 1$
$2^k - 1$
einsteinatguelph
2018-05-14 20:07:39
2^k
2^k
404nfound
2018-05-14 20:07:39
2^k?
2^k?
Axolotl
2018-05-14 20:07:39
f(k-1)*2+1
f(k-1)*2+1
Misha
2018-05-14 20:07:44
Together with the black, most-medium crow, the number of red crows doubles with each round back we go. So in a $k$-round race, there are $2^k$ red-or-black crows: $2^k-1$ crows faster than the most medium crow.
Together with the black, most-medium crow, the number of red crows doubles with each round back we go. So in a $k$-round race, there are $2^k$ red-or-black crows: $2^k-1$ crows faster than the most medium crow.
crocodile_40
2018-05-14 20:07:50
2^k-1
2^k-1
Misha
2018-05-14 20:07:57
(be careful about the $-1$ here!)
(be careful about the $-1$ here!)
Misha
2018-05-14 20:08:04
This proves that the fastest $2^k-1$ crows, and the slowest $2^k-1$ crows, cannot win.
This proves that the fastest $2^k-1$ crows, and the slowest $2^k-1$ crows, cannot win.
Misha
2018-05-14 20:08:16
In fact, this picture also shows how any other crow can win. If the blue crows are the $2^k-1$ slowest crows, and the red crows are the $2^k-1$ fastest crows, then the black crow can be any of the other crows and win.
In fact, this picture also shows how any other crow can win. If the blue crows are the $2^k-1$ slowest crows, and the red crows are the $2^k-1$ fastest crows, then the black crow can be any of the other crows and win.
Misha
2018-05-14 20:08:30
So that tells us the complete answer to (a)
So that tells us the complete answer to (a)
Misha
2018-05-14 20:08:41
Problem 4(b) solution.
Problem 4(b) solution.
Misha
2018-05-14 20:08:46
First, the easier of the two questions. What determines whether there are one or two crows left at the end?
First, the easier of the two questions. What determines whether there are one or two crows left at the end?
shroomley
2018-05-14 20:09:17
whether the original number was even or odd
whether the original number was even or odd
StyrofoamCup
2018-05-14 20:09:17
The parity of n
The parity of n
404nfound
2018-05-14 20:09:17
odd=1, even=2
odd=1, even=2
TheBigOne
2018-05-14 20:09:17
odd number of crows to start means one crow left
odd number of crows to start means one crow left
ccx09
2018-05-14 20:09:17
parity
parity
hliu70
2018-05-14 20:09:17
starting number of crows is even or odd
starting number of crows is even or odd
Misha
2018-05-14 20:09:20
Every time three crows race and one crow wins, the number of crows still in the race goes down by 2. So if we start with an odd number of crows, the number of crows always stays odd, and we end with 1 crow; if we start with an even number of crows, the number stays even, and we end with 2 crows.
Every time three crows race and one crow wins, the number of crows still in the race goes down by 2. So if we start with an odd number of crows, the number of crows always stays odd, and we end with 1 crow; if we start with an even number of crows, the number stays even, and we end with 2 crows.
Misha
2018-05-14 20:09:35
Now we can think about how the answer to "which crows can win?" changes when we don't have a perfect power of 3. Here's one possible picture of the result:
Now we can think about how the answer to "which crows can win?" changes when we don't have a perfect power of 3. Here's one possible picture of the result:
Misha
2018-05-14 20:09:38
Misha
2018-05-14 20:09:45
Just as before, if we want to say "the $x$ many slowest crows can't be the most medium", we should count the number of blue crows at the bottom layer. (They are the crows that the most medium crow must beat.) What changes about that number?
Just as before, if we want to say "the $x$ many slowest crows can't be the most medium", we should count the number of blue crows at the bottom layer. (They are the crows that the most medium crow must beat.) What changes about that number?
AtlasO
2018-05-14 20:11:01
decreases every round by 1
decreases every round by 1
AtlasO
2018-05-14 20:11:01
by 2*
by 2*
Burrito
2018-05-14 20:11:01
there are remainders
there are remainders
Misha
2018-05-14 20:11:06
people are on the right track
people are on the right track
Misha
2018-05-14 20:11:16
but keep in mind that the number of byes depends on the number of crows
but keep in mind that the number of byes depends on the number of crows
Misha
2018-05-14 20:11:25
Before, each blue-or-black crow must have beaten another crow in a race, so their number doubled. Now, in every layer, one or two of them can get a "bye" and not beat anyone.
Before, each blue-or-black crow must have beaten another crow in a race, so their number doubled. Now, in every layer, one or two of them can get a "bye" and not beat anyone.
Burrito
2018-05-14 20:11:30
the byes are either 1 or 2
the byes are either 1 or 2
Misha
2018-05-14 20:11:41
Just from that, we can write down a recurrence for $a_n$, the least rank of the most medium crow, if all crows are ranked by speed. (So the slowest $a_n-1$ and the fastest $a_n-1$ crows cannot win.) We have: $$\begin{cases}a_{3n} &= 2a_n \\ a_{3n-2} &= 2a_n - 1 \\ a_{3n-4} &= 2a_n - 2.\end{cases}$$
Just from that, we can write down a recurrence for $a_n$, the least rank of the most medium crow, if all crows are ranked by speed. (So the slowest $a_n-1$ and the fastest $a_n-1$ crows cannot win.) We have: $$\begin{cases}a_{3n} &= 2a_n \\ a_{3n-2} &= 2a_n - 1 \\ a_{3n-4} &= 2a_n - 2.\end{cases}$$
Misha
2018-05-14 20:11:49
This just says: if the bottom layer contains no byes, the number of black-or-blue crows doubles from the previous layer. If there's a bye, the number of black-or-blue crows might grow by one less; if there's two byes, it grows by two less.
This just says: if the bottom layer contains no byes, the number of black-or-blue crows doubles from the previous layer. If there's a bye, the number of black-or-blue crows might grow by one less; if there's two byes, it grows by two less.
StyrofoamCup
2018-05-14 20:12:22
Then is there a closed form for which crows can win?
Then is there a closed form for which crows can win?
Misha
2018-05-14 20:12:31
We didn't expect everyone to come up with one, but...
We didn't expect everyone to come up with one, but...
Misha
2018-05-14 20:12:33
There is also a more interesting formula, which I don't have the time to talk about, so I leave it as homework It can be found on http://oeis.org/A065365 and gives us the number of crows too slow to win in a race with $2n+1$ crows.
There is also a more interesting formula, which I don't have the time to talk about, so I leave it as homework
It can be found on http://oeis.org/A065365 and gives us the number of crows too slow to win in a race with $2n+1$ crows.
Misha
2018-05-14 20:13:00
I'd have to first explain what "balanced ternary" is!
I'd have to first explain what "balanced ternary" is!
Misha
2018-05-14 20:13:08
Finally, one consequence of all this is that with $3^k+2$ crows, every single crow except the fastest and the slowest can win.
Finally, one consequence of all this is that with $3^k+2$ crows, every single crow except the fastest and the slowest can win.
Misha
2018-05-14 20:13:12
Do you see why?
Do you see why?
hliu70
2018-05-14 20:13:57
crows can get byes all the way up to the top
crows can get byes all the way up to the top
StyrofoamCup
2018-05-14 20:13:57
Save the slowest and second slowest with byes till the end
Save the slowest and second slowest with byes till the end
reedmj
2018-05-14 20:13:57
The "+2" crows always get byes
The "+2" crows always get byes
Collatz__conjecture
2018-05-14 20:13:57
two crows are safe until the last round
two crows are safe until the last round
shroomley
2018-05-14 20:13:57
the fastest and slowest crows could get byes until the final round?
the fastest and slowest crows could get byes until the final round?
Misha
2018-05-14 20:14:11
I thought this was a particularly neat way for two crows to "rig" the race.
I thought this was a particularly neat way for two crows to "rig" the race.
Misha
2018-05-14 20:14:26
Problem 5.
Problem 5.
Misha
2018-05-14 20:14:31
Take a unit tetrahedron: a 3-dimensional solid with four vertices $A, B, C, D$ all at distance one from each other. We can cut the tetrahedron along a plane that's equidistant from and parallel to edge $AB$ and edge $CD$. If we do, the cross-section is a square with side length 1/2, as shown in the diagram below.
Take a unit tetrahedron: a 3-dimensional solid with four vertices $A, B, C, D$ all at distance one from each other. We can cut the tetrahedron along a plane that's equidistant from and parallel to edge $AB$ and edge $CD$. If we do, the cross-section is a square with side length 1/2, as shown in the diagram below.
Misha
2018-05-14 20:14:33
Misha
2018-05-14 20:14:45
Now take a unit 5-cell, which is the 4-dimensional analog of the tetrahedron: a 4-dimensional solid with five vertices $A, B, C, D, E$ all at distance one from each other. We can cut the 5-cell along a 3-dimensional surface (a hyperplane) that's equidistant from and parallel to edge $AB$ and plane $CDE$. If we do, what (3-dimensional) cross-section do we get?
Now take a unit 5-cell, which is the 4-dimensional analog of the tetrahedron: a 4-dimensional solid with five vertices $A, B, C, D, E$ all at distance one from each other. We can cut the 5-cell along a 3-dimensional surface (a hyperplane) that's equidistant from and parallel to edge $AB$ and plane $CDE$. If we do, what (3-dimensional) cross-section do we get?
Misha
2018-05-14 20:15:15
Problem 5 solution.
Problem 5 solution.
Misha
2018-05-14 20:15:19
For lots of people, their first instinct when looking at this problem is to give everything coordinates. This is great for 4-dimensional problems, because it lets you avoid thinking about what anything looks like. But we're not looking for easy answers, so let's not do coordinates.
For lots of people, their first instinct when looking at this problem is to give everything coordinates. This is great for 4-dimensional problems, because it lets you avoid thinking about what anything looks like. But we're not looking for easy answers, so let's not do coordinates.
Misha
2018-05-14 20:15:48
One way to figure out the shape of our 3-dimensional cross-section is to understand all of its 2-dimensional faces. This would be like figuring out that the cross-section of the tetrahedron is a square by understanding all of its 1-dimensional sides.
One way to figure out the shape of our 3-dimensional cross-section is to understand all of its 2-dimensional faces. This would be like figuring out that the cross-section of the tetrahedron is a square by understanding all of its 1-dimensional sides.
Misha
2018-05-14 20:16:03
So to get an intuition for how to do this: in the diagram above, where did the sides of the squares come from?
So to get an intuition for how to do this: in the diagram above, where did the sides of the squares come from?
reedmj
2018-05-14 20:16:35
From the triangular faces
From the triangular faces
cTurek2
2018-05-14 20:16:35
faces of the tetrahedron
faces of the tetrahedron
AtlasO
2018-05-14 20:16:35
the smaller triangles that make up the side
the smaller triangles that make up the side
Misha
2018-05-14 20:16:42
The key two points here are this:
1. The sides of the square come from its intersections with a face of the tetrahedron (such as $ABC$).
2. The thing we get inside face $ABC$ is a solution to the 2-dimensional problem: a cut halfway between edge $AB$ and point $C$.
The key two points here are this:
1. The sides of the square come from its intersections with a face of the tetrahedron (such as $ABC$).
2. The thing we get inside face $ABC$ is a solution to the 2-dimensional problem: a cut halfway between edge $AB$ and point $C$.
Misha
2018-05-14 20:17:07
(Look back at the 3D picture and make sure this makes sense.)
(Look back at the 3D picture and make sure this makes sense.)
Misha
2018-05-14 20:17:32
The same thing should happen in 4 dimensions. So how many sides is our 3-dimensional cross-section going to have? Which shapes have that many sides?
The same thing should happen in 4 dimensions. So how many sides is our 3-dimensional cross-section going to have? Which shapes have that many sides?
StyrofoamCup
2018-05-14 20:18:35
5, triangular prism
5, triangular prism
dihydrogen
2018-05-14 20:18:35
it should have 5 choose 4 sides, so five sides
it should have 5 choose 4 sides, so five sides
Misha
2018-05-14 20:18:46
(some other people have this answer too, but are a bit ahead of the game)
(some other people have this answer too, but are a bit ahead of the game)
Misha
2018-05-14 20:18:56
There are actually two 5-sided polyhedra this could be
There are actually two 5-sided polyhedra this could be
Misha
2018-05-14 20:19:01
A triangular prism, and a square pyramid
A triangular prism, and a square pyramid
Misha
2018-05-14 20:19:09
So we'll have to do a bit more work to figure out which one it is.
So we'll have to do a bit more work to figure out which one it is.
Misha
2018-05-14 20:19:19
Our next step is to think about each of these sides more carefully. For example, suppose we are looking at side $ABCD$: a 3-dimensional facet of the 5-cell $ABCDE$, which is shaped like a tetrahedron. When we make our cut through the 5-cell, how does it intersect side $ABCD$?
Our next step is to think about each of these sides more carefully. For example, suppose we are looking at side $ABCD$: a 3-dimensional facet of the 5-cell $ABCDE$, which is shaped like a tetrahedron. When we make our cut through the 5-cell, how does it intersect side $ABCD$?
Misha
2018-05-14 20:20:01
(This will tell us what all the sides are: each of $ABCD$, $ABCE$, $ABDE$, $ACDE$, $BCDE$ will give us a side.)
(This will tell us what all the sides are: each of $ABCD$, $ABCE$, $ABDE$, $ACDE$, $BCDE$ will give us a side.)
AtlasO
2018-05-14 20:20:42
through the square triangle thingy section
through the square triangle thingy section
StyrofoamCup
2018-05-14 20:20:42
As a square, similarly for all including A and B
As a square, similarly for all including A and B
Misha
2018-05-14 20:20:49
This is just the example problem in 3 dimensions! The intersection with $ABCD$ is a 2-dimensional cut halfway between $AB$ and $CD$, so it's a square whose side length is $\frac12$. The same thing happens with sides $ABCE$ and $ABDE$.
This is just the example problem in 3 dimensions! The intersection with $ABCD$ is a 2-dimensional cut halfway between $AB$ and $CD$, so it's a square whose side length is $\frac12$. The same thing happens with sides $ABCE$ and $ABDE$.
Misha
2018-05-14 20:20:55
What about the intersection with $ACDE$, or $BCDE$?
What about the intersection with $ACDE$, or $BCDE$?
AtlasO
2018-05-14 20:21:44
triangle!!
triangle!!
StyrofoamCup
2018-05-14 20:21:44
It's a triangle with side lengths 1/2
It's a triangle with side lengths 1/2
Axolotl
2018-05-14 20:21:44
triangle?
triangle?
dihydrogen
2018-05-14 20:21:49
those are a plane that's equidistant from a point and a face on the tetrahedron, so it makes a triangle
those are a plane that's equidistant from a point and a face on the tetrahedron, so it makes a triangle
Burrito
2018-05-14 20:21:54
triangle
triangle
Misha
2018-05-14 20:21:59
Here, the intersection is also a 2-dimensional cut of a tetrahedron, but a different one. For $ACDE$, it's a cut halfway between point $A$ and plane $CDE$. This cut is shaped like a triangle. The same thing happens with $BCDE$: the cut is halfway between point $B$ and plane $BCDE$.
Here, the intersection is also a 2-dimensional cut of a tetrahedron, but a different one. For $ACDE$, it's a cut halfway between point $A$ and plane $CDE$. This cut is shaped like a triangle. The same thing happens with $BCDE$: the cut is halfway between point $B$ and plane $BCDE$.
symmbowl
2018-05-14 20:22:11
Why isn’t it not a cube when the 2d cross section is a square (leading to a 3D square,cube)
Why isn’t it not a cube when the 2d cross section is a square (leading to a 3D square,cube)
Misha
2018-05-14 20:22:23
It's not a cube so that you wouldn't be able to just guess the answer!
It's not a cube so that you wouldn't be able to just guess the answer!
Misha
2018-05-14 20:22:35
So if we have three sides that are squares, and two that are triangles, the cross-section must look like a triangular prism. Here is my best attempt at a diagram:
So if we have three sides that are squares, and two that are triangles, the cross-section must look like a triangular prism. Here is my best attempt at a diagram:
Misha
2018-05-14 20:22:37
AtlasO
2018-05-14 20:23:13
Thats a little...
Thats a little...
AtlasO
2018-05-14 20:23:13
Umm...
Umm...
AtlasO
2018-05-14 20:23:13
No.
No.
Misha
2018-05-14 20:23:20
That's what 4D geometry is like
That's what 4D geometry is like
Misha
2018-05-14 20:23:37
And on that note, it's over to Yasha for Problem 6.
And on that note, it's over to Yasha for Problem 6.
Yasha
2018-05-14 20:23:49
Hi everyone!
Hi everyone!
Yasha
2018-05-14 20:23:51
Problem 6.
Problem 6.
Yasha
2018-05-14 20:23:53
Max finds a large sphere with 2018 rubber bands wrapped around it. Each rubber band is stretched in the shape of a circle. Max notices that any two rubber bands cross each other in two points, and that no three rubber bands cross at the same point.
Max finds a large sphere with 2018 rubber bands wrapped around it. Each rubber band is stretched in the shape of a circle. Max notices that any two rubber bands cross each other in two points, and that no three rubber bands cross at the same point.
Yasha
2018-05-14 20:23:56
By the nature of rubber bands, whenever two cross, one is on top of the other. Max has a magic wand that, when tapped on a crossing, switches which rubber band is on top at that crossing. He may use the magic wand any number of times.
By the nature of rubber bands, whenever two cross, one is on top of the other. Max has a magic wand that, when tapped on a crossing, switches which rubber band is on top at that crossing. He may use the magic wand any number of times.
Yasha
2018-05-14 20:24:00
Prove that Max can make it so that if he follows each rubber band around the sphere, no rubber band is ever the top band at two consecutive crossings.
Prove that Max can make it so that if he follows each rubber band around the sphere, no rubber band is ever the top band at two consecutive crossings.
Yasha
2018-05-14 20:24:17
Problem 5 solution.
Problem 5 solution.
ccx09
2018-05-14 20:24:26
For this problem I got an orange and placed a bunch of rubber bands around it
For this problem I got an orange and placed a bunch of rubber bands around it
Yasha
2018-05-14 20:24:31
An excellent plan!
An excellent plan!
Yasha
2018-05-14 20:24:58
It's always a good idea to try some small cases. Two rubber bands is easy, and you can work out that Max can make things work with three rubber bands.
It's always a good idea to try some small cases. Two rubber bands is easy, and you can work out that Max can make things work with three rubber bands.
Yasha
2018-05-14 20:25:09
With an orange, you might be able to go up to four or five.
With an orange, you might be able to go up to four or five.
ccx09
2018-05-14 20:25:28
( I got 7 and then gave up)
( I got 7 and then gave up)
Yasha
2018-05-14 20:25:38
impressive
impressive
BobsonJoe
2018-05-14 20:25:41
problem 5 solution :o
problem 5 solution :o
Yasha
2018-05-14 20:25:46
oops, I meant problem 6.
oops, I meant problem 6.
hwl0304
2018-05-14 20:26:03
i think using a watermelon would have been more effective
i think using a watermelon would have been more effective
sooper
2018-05-14 20:26:03
watermelon challenge!
watermelon challenge!
Yasha
2018-05-14 20:26:12
you'd need some pretty stretchy rubber bands
you'd need some pretty stretchy rubber bands
Yasha
2018-05-14 20:26:27
Does the number 2018 seem relevant to the problem?
Does the number 2018 seem relevant to the problem?
Axolotl
2018-05-14 20:26:44
no
no
Kreps
2018-05-14 20:26:44
no
no
sjosyula72
2018-05-14 20:26:44
nope
nope
hliu70
2018-05-14 20:26:44
no
no
ccx09
2018-05-14 20:26:44
no
no
AtlasO
2018-05-14 20:26:44
not really
not really
PCampbell
2018-05-14 20:26:44
No
No
StyrofoamCup
2018-05-14 20:26:44
Not really, besides being the year
Not really, besides being the year
dihydrogen
2018-05-14 20:26:44
...no
...no
Th3Numb3rThr33
2018-05-14 20:26:44
no
no
Yasha
2018-05-14 20:27:08
After trying small cases, we might guess that Max can succeed regardless of the number of rubber bands, so the specific number of rubber bands is not relevant to the problem.
After trying small cases, we might guess that Max can succeed regardless of the number of rubber bands, so the specific number of rubber bands is not relevant to the problem.
Yasha
2018-05-14 20:27:28
Hopefully.
Hopefully.
Yasha
2018-05-14 20:27:36
One good solution method is to work backwards. If each rubber band alternates between being above and below, we can try to understand what conditions have to hold. Then we can try to use that understanding to prove that we can always arrange it so that each rubber band alternates.
One good solution method is to work backwards. If each rubber band alternates between being above and below, we can try to understand what conditions have to hold. Then we can try to use that understanding to prove that we can always arrange it so that each rubber band alternates.
Yasha
2018-05-14 20:27:51
There's a lot of ways to explore the situation, making lots of pretty pictures in the process. Here's one thing you might eventually try:
There's a lot of ways to explore the situation, making lots of pretty pictures in the process. Here's one thing you might eventually try:
deadwindow
2018-05-14 20:27:56
Like weaving?
Like weaving?
Yasha
2018-05-14 20:28:05
Yup, that's the goal, to get each rubber band to weave up and down
Yup, that's the goal, to get each rubber band to weave up and down
Yasha
2018-05-14 20:28:18
Let's say we're walking along a red rubber band. We eventually hit an intersection, where we meet a blue rubber band. We find that, at this intersection, the blue rubber band is above our red one. At this point, rather than keep going, we turn left onto the blue rubber band. What can we say about the next intersection we meet?
Let's say we're walking along a red rubber band. We eventually hit an intersection, where we meet a blue rubber band. We find that, at this intersection, the blue rubber band is above our red one. At this point, rather than keep going, we turn left onto the blue rubber band. What can we say about the next intersection we meet?
Yasha
2018-05-14 20:28:25
StyrofoamCup
2018-05-14 20:29:03
Blue is on bottom
Blue is on bottom
Th3Numb3rThr33
2018-05-14 20:29:03
should be under
should be under
shroomley
2018-05-14 20:29:03
it is also under
it is also under
AtlasO
2018-05-14 20:29:03
blue will go under
blue will go under
PCampbell
2018-05-14 20:29:03
The next rubber band will be on top of the blue one
The next rubber band will be on top of the blue one
Th3Numb3rThr33
2018-05-14 20:29:03
blue will be underneath
blue will be underneath
Kreps
2018-05-14 20:29:03
we will switch to another band's path
we will switch to another band's path
dihydrogen
2018-05-14 20:29:03
it'll be under
it'll be under
Tapeman
2018-05-14 20:29:03
blue has to be below
blue has to be below
Yasha
2018-05-14 20:29:07
At the next intersection, our rubber band will once again be below the one we meet.
At the next intersection, our rubber band will once again be below the one we meet.
Yasha
2018-05-14 20:29:10
Yasha
2018-05-14 20:29:21
After all, if blue was above red, then it has to be below green.
After all, if blue was above red, then it has to be below green.
nmego12345
2018-05-14 20:29:39
so basically each rubber band is under the previous one and they form a circle?
so basically each rubber band is under the previous one and they form a circle?
Kreps
2018-05-14 20:29:39
this continues
this continues
Yasha
2018-05-14 20:29:46
If we keep turning left, our rubber band will always be below the one we meet, and eventually we'll get back to where we started.
If we keep turning left, our rubber band will always be below the one we meet, and eventually we'll get back to where we started.
Yasha
2018-05-14 20:29:50
Yasha
2018-05-14 20:30:19
It might take more steps, or fewer steps, depending on what the rubber bands decided to be like.
It might take more steps, or fewer steps, depending on what the rubber bands decided to be like.
deadwindow
2018-05-14 20:30:29
2018 colors
2018 colors
Yasha
2018-05-14 20:30:32
:-/
:-/
Yasha
2018-05-14 20:30:40
When we get back to where we started, we see that we've enclosed a region. What we found is that if we go around the region counter-clockwise, every time we get to an intersection, our rubber band is below the one we meet.
When we get back to where we started, we see that we've enclosed a region. What we found is that if we go around the region counter-clockwise, every time we get to an intersection, our rubber band is below the one we meet.
AtlasO
2018-05-14 20:31:11
are the rubber bands always straight?
are the rubber bands always straight?
Yasha
2018-05-14 20:31:31
They bend around the sphere, and the problem doesn't require them to go straight.
They bend around the sphere, and the problem doesn't require them to go straight.
Yasha
2018-05-14 20:31:46
But it does require that any two rubber bands cross each other in two points.
But it does require that any two rubber bands cross each other in two points.
porkemon2
2018-05-14 20:32:01
but it won't matter if they're straight or not right?
but it won't matter if they're straight or not right?
AtlasO
2018-05-14 20:32:01
it said circle
it said circle
AtlasO
2018-05-14 20:32:01
perfect circle?
perfect circle?
Yasha
2018-05-14 20:32:23
yeah it doesn't have to be a great circle necessarily, but it should probably be pretty close for it to cross the other rubber bands in two points
yeah it doesn't have to be a great circle necessarily, but it should probably be pretty close for it to cross the other rubber bands in two points
Yasha
2018-05-14 20:32:37
but experimenting with an orange or watermelon or whatever would suggest that it doesn't matter all that much
but experimenting with an orange or watermelon or whatever would suggest that it doesn't matter all that much
Yasha
2018-05-14 20:33:27
Anyways, in our region, we found that if we keep turning left, our rubber band will always be below the one we meet, and eventually we'll get back to where we started. Will that be true of every region?
Anyways, in our region, we found that if we keep turning left, our rubber band will always be below the one we meet, and eventually we'll get back to where we started. Will that be true of every region?
PCampbell
2018-05-14 20:34:33
No! Start the same way we started, but turn right instead, and you'll get the same result.
No! Start the same way we started, but turn right instead, and you'll get the same result.
Yasha
2018-05-14 20:34:58
We might also have the reverse situation: If we go around a region counter-clockwise, we might find that every time we get to an intersection, our rubber band is above the one we meet.
We might also have the reverse situation: If we go around a region counter-clockwise, we might find that every time we get to an intersection, our rubber band is above the one we meet.
Yasha
2018-05-14 20:35:16
In fact, we can see that happening in the above diagram if we zoom out a bit.
In fact, we can see that happening in the above diagram if we zoom out a bit.
Yasha
2018-05-14 20:35:17
Yasha
2018-05-14 20:35:24
Look at the region bounded by the blue, orange, and green rubber bands. As we move counter-clockwise around this region, our rubber band is always above.
Look at the region bounded by the blue, orange, and green rubber bands. As we move counter-clockwise around this region, our rubber band is always above.
Yasha
2018-05-14 20:35:58
So it looks like we have two types of regions. Going counter-clockwise around regions of the first type, our rubber band is always below the one we meet. Going counter-clockwise around regions of the second type, our rubber band is always above the one we meet.
So it looks like we have two types of regions. Going counter-clockwise around regions of the first type, our rubber band is always below the one we meet. Going counter-clockwise around regions of the second type, our rubber band is always above the one we meet.
Yasha
2018-05-14 20:36:02
Are there any other types of regions?
Are there any other types of regions?
PCampbell
2018-05-14 20:36:39
No.
No.
reedmj
2018-05-14 20:36:39
no
no
nmego12345
2018-05-14 20:36:39
nope
nope
Yasha
2018-05-14 20:36:44
No, our reasoning from before applies. If, at the first intersection we encounter, our rubber band is below, then that will continue to be the case at all other intersections as we go around the region. Likewise, if, at the first intersection we encounter, our rubber band is above, then that will continue to be the case at all other intersections as we go around the region.
No, our reasoning from before applies. If, at the first intersection we encounter, our rubber band is below, then that will continue to be the case at all other intersections as we go around the region. Likewise, if, at the first intersection we encounter, our rubber band is above, then that will continue to be the case at all other intersections as we go around the region.
Burrito
2018-05-14 20:37:14
multiple lines intersecting at one point
multiple lines intersecting at one point
Yasha
2018-05-14 20:37:20
the problem bans that, so we're good.
the problem bans that, so we're good.
Yasha
2018-05-14 20:37:24
Now that we've identified two types of regions, what should we add to our picture?
Now that we've identified two types of regions, what should we add to our picture?
PCampbell
2018-05-14 20:37:45
color-code the regions
color-code the regions
Yasha
2018-05-14 20:37:53
We should add colors! We'll leave the regions where we have to "hop up" when going around white, and color the regions where we have to "hop down" black.
We should add colors! We'll leave the regions where we have to "hop up" when going around white, and color the regions where we have to "hop down" black.
Yasha
2018-05-14 20:37:58
Yasha
2018-05-14 20:38:08
Here's another picture showing this region coloring idea.
Here's another picture showing this region coloring idea.
Yasha
2018-05-14 20:38:10
Yasha
2018-05-14 20:39:17
As we move around the region counterclockwise, we either keep hopping up at each intersection or hopping down
As we move around the region counterclockwise, we either keep hopping up at each intersection or hopping down
Yasha
2018-05-14 20:39:30
Yasha
2018-05-14 20:39:49
so, here, we hop up from red to blue, then up from blue to green, then up from green to orange, then up from orange to cyan, and finally up from cyan to red.
so, here, we hop up from red to blue, then up from blue to green, then up from green to orange, then up from orange to cyan, and finally up from cyan to red.
Yasha
2018-05-14 20:40:12
But in the triangular region on the right, we hop down from blue to orange, then from orange to green, and then from green to blue.
But in the triangular region on the right, we hop down from blue to orange, then from orange to green, and then from green to blue.
einsteinatguelph
2018-05-14 20:40:21
Would it be true at this point that no two regions next to each other will have the same color?
Would it be true at this point that no two regions next to each other will have the same color?
Axolotl
2018-05-14 20:40:21
is the ball gonna look like a checkerboard soccer ball thing
is the ball gonna look like a checkerboard soccer ball thing
ccx09
2018-05-14 20:40:21
so just partitioning the surface into black and white portions
so just partitioning the surface into black and white portions
Yasha
2018-05-14 20:40:36
The coloring seems to alternate. All neighbors of white regions are black, and all neighbors of black regions are white.
The coloring seems to alternate. All neighbors of white regions are black, and all neighbors of black regions are white.
Yasha
2018-05-14 20:40:51
Why do you think that's true?
Why do you think that's true?
StyrofoamCup
2018-05-14 20:41:26
Because going counterclockwise on two adjacent regions requires going opposite directions on the shared edge
Because going counterclockwise on two adjacent regions requires going opposite directions on the shared edge
Yasha
2018-05-14 20:41:33
If, in one region, we're hopping up from green to orange, then in a neighboring region, we'd be hopping down from orange to green.
If, in one region, we're hopping up from green to orange, then in a neighboring region, we'd be hopping down from orange to green.
Yasha
2018-05-14 20:41:51
OK. We've gotten a sense of what's going on. Now it's time to write down a solution.
OK. We've gotten a sense of what's going on. Now it's time to write down a solution.
Yasha
2018-05-14 20:42:21
We've worked backwards. But now it's time to consider a random arrangement of rubber bands and tell Max how to use his magic wand to make each rubber band alternate between above and below.
We've worked backwards. But now it's time to consider a random arrangement of rubber bands and tell Max how to use his magic wand to make each rubber band alternate between above and below.
Yasha
2018-05-14 20:42:31
What's the first thing we should do upon seeing this mess of rubber bands?
What's the first thing we should do upon seeing this mess of rubber bands?
AtlasO
2018-05-14 20:42:51
color in regions!
color in regions!
hexated
2018-05-14 20:42:51
designate regions?
designate regions?
AtlasO
2018-05-14 20:42:54
alternating regions
alternating regions
Yasha
2018-05-14 20:43:01
We should look at the regions and try to color them black and white so that adjacent regions are opposite colors.
We should look at the regions and try to color them black and white so that adjacent regions are opposite colors.
Yasha
2018-05-14 20:43:07
Our first step will be showing that we can color the regions in this manner. What should our step after that be?
Our first step will be showing that we can color the regions in this manner. What should our step after that be?
hliu70
2018-05-14 20:43:48
start off with solving one region
start off with solving one region
nmego12345
2018-05-14 20:43:48
make it so that each region alternates?
make it so that each region alternates?
AtlasO
2018-05-14 20:43:48
then either move counterclockwise or clockwise
then either move counterclockwise or clockwise
Yasha
2018-05-14 20:43:55
Our second step will be to use the coloring of the regions to tell Max which rubber band should be on top at each intersection. We'll need to make sure that the result is what Max wants, namely that each rubber band alternates between being above and below.
Our second step will be to use the coloring of the regions to tell Max which rubber band should be on top at each intersection. We'll need to make sure that the result is what Max wants, namely that each rubber band alternates between being above and below.
StyrofoamCup
2018-05-14 20:44:02
How do we know it doesn't loop around and require a different color upon rereaching the same region?
How do we know it doesn't loop around and require a different color upon rereaching the same region?
Yasha
2018-05-14 20:44:09
Yes, exactly. Step 1 isn't so simple.
Yes, exactly. Step 1 isn't so simple.
Yasha
2018-05-14 20:44:40
Now we have a two-step outline that will solve the problem for us, let's focus on step 1.
Now we have a two-step outline that will solve the problem for us, let's focus on step 1.
PCampbell
2018-05-14 20:45:04
Think about adding 1 rubber band at a time
Think about adding 1 rubber band at a time
Yasha
2018-05-14 20:45:19
Yup, induction is one good proof technique here. I'll cover induction first, and then a direct proof.
Yup, induction is one good proof technique here. I'll cover induction first, and then a direct proof.
Yasha
2018-05-14 20:45:32
If we have just one rubber band, there are two regions. We color one of them black and the other one white, and we're done.
If we have just one rubber band, there are two regions. We color one of them black and the other one white, and we're done.
Yasha
2018-05-14 20:45:38
So now we assume that we've got some rubber bands and we've successfully colored the regions black and white so that adjacent regions are different colors. But now a magenta rubber band gets added, making lots of new regions and ruining everything. What do we do? How do we fix the situation?
So now we assume that we've got some rubber bands and we've successfully colored the regions black and white so that adjacent regions are different colors. But now a magenta rubber band gets added, making lots of new regions and ruining everything. What do we do? How do we fix the situation?
reedmj
2018-05-14 20:46:06
Use induction: Add a band and alternate the colors of the regions it cuts
Use induction: Add a band and alternate the colors of the regions it cuts
MathAwesome123
2018-05-14 20:46:06
reverse all regions on one side of the new band
reverse all regions on one side of the new band
PCampbell
2018-05-14 20:46:06
Reverse all of the colors on one side of the magenta, and keep all the colors on the other side
Reverse all of the colors on one side of the magenta, and keep all the colors on the other side
StyrofoamCup
2018-05-14 20:46:06
Leave the colors the same on one side, swap on the other
Leave the colors the same on one side, swap on the other
Yasha
2018-05-14 20:46:12
We can keep all the regions on one side of the magenta rubber band the same color, and flip the colors of the regions on the other side.
We can keep all the regions on one side of the magenta rubber band the same color, and flip the colors of the regions on the other side.
Yasha
2018-05-14 20:46:22
Why does this procedure result in an acceptable black and white coloring of the regions?
Why does this procedure result in an acceptable black and white coloring of the regions?
StyrofoamCup
2018-05-14 20:46:53
Because the only problems are along the band, and we're making them alternate along the band
Because the only problems are along the band, and we're making them alternate along the band
Axolotl
2018-05-14 20:46:59
regions that got cut now are different colors, other regions not changed wrt neighbors
regions that got cut now are different colors, other regions not changed wrt neighbors
nmego12345
2018-05-14 20:47:05
because all the colors on one side are still adjacent and different, just different colors white instead of black. but we've fixed the magenta problem
because all the colors on one side are still adjacent and different, just different colors white instead of black. but we've fixed the magenta problem
Yasha
2018-05-14 20:47:08
If the magenta rubber band cut a white region into two halves, then, as a result of this procedure, one half will be white and the other half will be black, which is acceptable.
If the magenta rubber band cut a white region into two halves, then, as a result of this procedure, one half will be white and the other half will be black, which is acceptable.
Yasha
2018-05-14 20:47:14
Here's a before and after picture.
Here's a before and after picture.
Yasha
2018-05-14 20:47:15
Yasha
2018-05-14 20:47:23
Meanwhile, if two regions share a border that's not the magenta rubber band, they'll either both stay the same or both get flipped, depending on which side of the magenta rubber band they're on.
Meanwhile, if two regions share a border that's not the magenta rubber band, they'll either both stay the same or both get flipped, depending on which side of the magenta rubber band they're on.
Yasha
2018-05-14 20:47:27
Here are pictures of the two possible outcomes.
Here are pictures of the two possible outcomes.
Yasha
2018-05-14 20:47:29
Yasha
2018-05-14 20:47:31
or
or
Yasha
2018-05-14 20:47:32
Yasha
2018-05-14 20:47:38
Either way works.
Either way works.
Yasha
2018-05-14 20:47:45
So, because we can always make the region coloring work after adding a rubber band, we can get all the way up to 2018 rubber bands.
So, because we can always make the region coloring work after adding a rubber band, we can get all the way up to 2018 rubber bands.
Yasha
2018-05-14 20:48:33
OK, so let's do another proof, starting directly from a mess of rubber bands, and hopefully answering some questions people had.
OK, so let's do another proof, starting directly from a mess of rubber bands, and hopefully answering some questions people had.
Yasha
2018-05-14 20:48:37
We can also directly prove that we can color the regions black and white so that adjacent regions are different colors.
We can also directly prove that we can color the regions black and white so that adjacent regions are different colors.
Yasha
2018-05-14 20:48:40
Here's a naive thing to try. Start with a region $R_0$ colored black. To determine the color of another region $R$, walk from $R_0$ to $R$, avoiding intersections because crossing two rubber bands at once is too complex a task for our simple walker. If you cross an odd number of rubber bands, color $R$ white. If you cross an even number of rubber bands, color $R$ black.
Here's a naive thing to try. Start with a region $R_0$ colored black. To determine the color of another region $R$, walk from $R_0$ to $R$, avoiding intersections because crossing two rubber bands at once is too complex a task for our simple walker. If you cross an odd number of rubber bands, color $R$ white. If you cross an even number of rubber bands, color $R$ black.
Yasha
2018-05-14 20:48:58
This procedure ensures that neighboring regions have different colors. If $R$ and $S$ are neighbors, then if it took an odd number of steps to get to $R$, it'll take one more (or one fewer) step to get to $S$, resulting in an even number of steps, and vice versa. Or will it?
This procedure ensures that neighboring regions have different colors. If $R$ and $S$ are neighbors, then if it took an odd number of steps to get to $R$, it'll take one more (or one fewer) step to get to $S$, resulting in an even number of steps, and vice versa. Or will it?
Yasha
2018-05-14 20:49:34
This procedure is also similar to declaring one region black, declaring its neighbors white, declaring the neighbors of those regions black, etc.
This procedure is also similar to declaring one region black, declaring its neighbors white, declaring the neighbors of those regions black, etc.
Yasha
2018-05-14 20:49:39
What might go wrong?
What might go wrong?
shroomley
2018-05-14 20:49:53
you could reach the same region in 1 step or 2 steps right?
you could reach the same region in 1 step or 2 steps right?
yrnsmurf
2018-05-14 20:49:55
odd cycle
odd cycle
dihydrogen
2018-05-14 20:49:59
a region might already have a black and a white neighbor that give conflicting messages
a region might already have a black and a white neighbor that give conflicting messages
Yasha
2018-05-14 20:50:06
Maybe one way of walking from $R_0$ to $R$ takes an odd number of steps, but a different way of walking from $R_0$ to $R$ takes an even number of steps.
Maybe one way of walking from $R_0$ to $R$ takes an odd number of steps, but a different way of walking from $R_0$ to $R$ takes an even number of steps.
Yasha
2018-05-14 20:50:14
One red flag you should notice is that our reasoning didn't use the fact that our regions come from rubber bands. With arbitrary regions, you could have something like this:
One red flag you should notice is that our reasoning didn't use the fact that our regions come from rubber bands. With arbitrary regions, you could have something like this:
Yasha
2018-05-14 20:50:18
Yasha
2018-05-14 20:50:22
It's not possible to color these regions black and white so that adjacent regions are different colors. You can also see that if you walk between two different regions, you might end up taking an odd number of steps or an even number steps, depending on the path you take.
It's not possible to color these regions black and white so that adjacent regions are different colors. You can also see that if you walk between two different regions, you might end up taking an odd number of steps or an even number steps, depending on the path you take.
Yasha
2018-05-14 20:50:31
But we've got rubber bands, not just random regions. Can we salvage this line of reasoning?
But we've got rubber bands, not just random regions. Can we salvage this line of reasoning?
StyrofoamCup
2018-05-14 20:51:02
Probably
Probably
Yasha
2018-05-14 20:51:50
Our goal is to show that the parity of the number of steps it takes to get from $R_0$ to $R$ doesn't depend on the path we take. We either need an even number of steps or an odd number of steps.
Our goal is to show that the parity of the number of steps it takes to get from $R_0$ to $R$ doesn't depend on the path we take. We either need an even number of steps or an odd number of steps.
Yasha
2018-05-14 20:52:19
Let's just consider one rubber band $B_1$. If $R_0$ and $R$ are on different sides of $B_!$, we can get from $R_0$ to $R$ crossing $B_!$ once. If we take a silly path, we might cross $B_1$ three times or five times or seventeen times, but, no matter what, we'll cross $B_1$ an odd number of times.
Let's just consider one rubber band $B_1$. If $R_0$ and $R$ are on different sides of $B_!$, we can get from $R_0$ to $R$ crossing $B_!$ once. If we take a silly path, we might cross $B_1$ three times or five times or seventeen times, but, no matter what, we'll cross $B_1$ an odd number of times.
Yasha
2018-05-14 20:52:26
fixed it slightly
fixed it slightly
Yasha
2018-05-14 20:52:38
well almost there's still an exclamation point instead of a 1
well almost there's still an exclamation point instead of a 1
Yasha
2018-05-14 20:53:03
Likewise, if $R_0$ and $R$ are on the same side of $B_1$, then, no matter how silly our path is, we'll cross $B_1$ an even number of times.
Likewise, if $R_0$ and $R$ are on the same side of $B_1$, then, no matter how silly our path is, we'll cross $B_1$ an even number of times.
PCampbell
2018-05-14 20:53:35
And that works for all of the rubber bands
And that works for all of the rubber bands
Yasha
2018-05-14 20:53:50
We have the same reasoning for rubber bands $B_2$, $B_3$, and so forth, all the way to $B_{2018}$. The number of times we cross each rubber band depends on the path we take, but the parity (odd or even) does not.
We have the same reasoning for rubber bands $B_2$, $B_3$, and so forth, all the way to $B_{2018}$. The number of times we cross each rubber band depends on the path we take, but the parity (odd or even) does not.
Yasha
2018-05-14 20:53:54
How does that help?
How does that help?
StyrofoamCup
2018-05-14 20:54:14
The parity is all that determines the color
The parity is all that determines the color
Yasha
2018-05-14 20:54:35
Adding all of these numbers up, we get the total number of times we cross a rubber band. Again, that number depends on our path, but its parity does not.
Adding all of these numbers up, we get the total number of times we cross a rubber band. Again, that number depends on our path, but its parity does not.
Yasha
2018-05-14 20:54:47
So, we'll make a consistent choice of color for the region $R$, regardless of which path we take from $R_0$.
So, we'll make a consistent choice of color for the region $R$, regardless of which path we take from $R_0$.
Yasha
2018-05-14 20:54:57
So, indeed, if $R$ and $S$ are neighbors, they must be different colors, since we can take a path to $R$ and then take one more step to get to $S$. The number of steps to get to $R$ thus has a different parity from the number of steps to get to $S$. Importantly, this path to get to $S$ is as valid as any other in determining the color of $S$, so we conclude that $R$ and $S$ are different colors.
So, indeed, if $R$ and $S$ are neighbors, they must be different colors, since we can take a path to $R$ and then take one more step to get to $S$. The number of steps to get to $R$ thus has a different parity from the number of steps to get to $S$. Importantly, this path to get to $S$ is as valid as any other in determining the color of $S$, so we conclude that $R$ and $S$ are different colors.
Yasha
2018-05-14 20:55:11
So, we've finished the first step of our proof, coloring the regions. Now we need to do the second step. We've colored the regions. How do we use that coloring to tell Max which rubber band to put on top?
So, we've finished the first step of our proof, coloring the regions. Now we need to do the second step. We've colored the regions. How do we use that coloring to tell Max which rubber band to put on top?
AtlasO
2018-05-14 20:55:45
he starts from any point and makes his way around
he starts from any point and makes his way around
Yasha
2018-05-14 20:55:51
Yeah, let's focus on a single point.
Yeah, let's focus on a single point.
Yasha
2018-05-14 20:55:52
Near each intersection, we've got two rubber bands meeting, splitting the neighborhood into four regions, two black and two white.
Near each intersection, we've got two rubber bands meeting, splitting the neighborhood into four regions, two black and two white.
Yasha
2018-05-14 20:55:54
Yasha
2018-05-14 20:56:01
Moving counter-clockwise around the intersection, we see that we move from white to black as we cross the green rubber band, and we move from black to white as we cross the orange rubber band.
Moving counter-clockwise around the intersection, we see that we move from white to black as we cross the green rubber band, and we move from black to white as we cross the orange rubber band.
Yasha
2018-05-14 20:56:11
So what we tell Max to do is to go counter-clockwise around the intersection. We tell him to look at the rubber band he crosses as he moves from a white region to a black region, and to use his magic wand to put that rubber band below.
So what we tell Max to do is to go counter-clockwise around the intersection. We tell him to look at the rubber band he crosses as he moves from a white region to a black region, and to use his magic wand to put that rubber band below.
Yasha
2018-05-14 20:56:28
Now we need to make sure that this procedure answers the question. We need to consider a rubber band $B$, and consider two adjacent intersections with rubber bands $B_1$ and $B_2$. Must it be true that $B$ is either above $B_1$ and below $B_2$ or below $B_1$ and then above $B_2$? If so, why?
Now we need to make sure that this procedure answers the question. We need to consider a rubber band $B$, and consider two adjacent intersections with rubber bands $B_1$ and $B_2$. Must it be true that $B$ is either above $B_1$ and below $B_2$ or below $B_1$ and then above $B_2$? If so, why?
Yasha
2018-05-14 20:56:38
Here is a picture of the situation at hand.
Here is a picture of the situation at hand.
Yasha
2018-05-14 20:56:39
AtlasO
2018-05-14 20:57:09
add the coloring
add the coloring
Yasha
2018-05-14 20:57:21
What might the coloring be?
What might the coloring be?
mathfarmer
2018-05-14 20:57:53
WB BW WB, with space-separated columns.
WB BW WB, with space-separated columns.
Yasha
2018-05-14 20:58:03
That's one option. Is that the only possibility?
That's one option. Is that the only possibility?
RiverDog47
2018-05-14 20:58:14
no
no
dihydrogen
2018-05-14 20:58:14
invert black and white
invert black and white
Yasha
2018-05-14 20:58:36
We could also have the reverse of that option. Are those two the only possibilities?
We could also have the reverse of that option. Are those two the only possibilities?
AtlasO
2018-05-14 20:58:46
yes
yes
mathfarmer
2018-05-14 20:58:46
Yes.
Yes.
Yasha
2018-05-14 20:58:56
There are only two ways of coloring the regions of this picture black and white so that adjacent regions are different colors. Using the rule above to decide which rubber band goes on top, our resulting picture looks like:
There are only two ways of coloring the regions of this picture black and white so that adjacent regions are different colors. Using the rule above to decide which rubber band goes on top, our resulting picture looks like:
Yasha
2018-05-14 20:59:00
Yasha
2018-05-14 20:59:01
or
or
Yasha
2018-05-14 20:59:03
Yasha
2018-05-14 20:59:06
Either way, these two intersections satisfy Max's requirements.
Either way, these two intersections satisfy Max's requirements.
Yasha
2018-05-14 20:59:14
Are we done?
Are we done?
StyrofoamCup
2018-05-14 20:59:46
Just about
Just about
Vfire
2018-05-14 20:59:46
yes
yes
AtlasO
2018-05-14 20:59:46
almost
almost
crocodile_40
2018-05-14 20:59:46
no
no
Yasha
2018-05-14 20:59:50
seems people disagree.
seems people disagree.
Yasha
2018-05-14 20:59:55
We've instructed Max how to color the regions and how to use those regions to decide which rubber band is on top at each intersection, and then we proved that this procedure results in a configuration that satisfies Max's requirements.
We've instructed Max how to color the regions and how to use those regions to decide which rubber band is on top at each intersection, and then we proved that this procedure results in a configuration that satisfies Max's requirements.
Yasha
2018-05-14 21:00:05
So we are, in fact, done.
So we are, in fact, done.
Yasha
2018-05-14 21:00:14
This problem illustrates that we can often understand a complex situation just by looking at local pieces: a region and its neighbors, the immediate vicinity of an intersection, and the immediate vicinity of two adjacent intersections. We solved most of the problem without needing to consider the "big picture" of the entire sphere.
This problem illustrates that we can often understand a complex situation just by looking at local pieces: a region and its neighbors, the immediate vicinity of an intersection, and the immediate vicinity of two adjacent intersections. We solved most of the problem without needing to consider the "big picture" of the entire sphere.
Yasha
2018-05-14 21:00:29
And now, back to Misha for the final problem.
And now, back to Misha for the final problem.
Misha
2018-05-14 21:00:38
Hi again everyone!
Hi again everyone!
Vfire
2018-05-14 21:00:40
yay
yay
AtlasO
2018-05-14 21:00:40
that was way easier than it looked
that was way easier than it looked
Misha
2018-05-14 21:00:46
Problem 7.
Problem 7.
Misha
2018-05-14 21:00:52
A tribble is a creature with unusual powers of reproduction. Tribbles come in positive integer sizes. Every night, a tribble grows in size by 1, and every day, any tribble of even size can split into two tribbles of half its size (possibly multiple times), if it wants to.
A tribble is a creature with unusual powers of reproduction. Tribbles come in positive integer sizes. Every night, a tribble grows in size by 1, and every day, any tribble of even size can split into two tribbles of half its size (possibly multiple times), if it wants to.
Misha
2018-05-14 21:00:55
(a) Suppose that we start with a single tribble of size $n$. (We start in the morning, so if $n$ is even, the tribble has a chance to split before it grows.) What is the fastest way in which it could split fully into tribbles of size $1$? How many tribbles of size $1$ would there be?
(a) Suppose that we start with a single tribble of size $n$. (We start in the morning, so if $n$ is even, the tribble has a chance to split before it grows.) What is the fastest way in which it could split fully into tribbles of size $1$? How many tribbles of size $1$ would there be?
Misha
2018-05-14 21:00:59
(b) Suppose that we start with a single tribble of size $1$. Let $T(k)$ be the number of different possibilities for what we could see after $k$ days (in the evening, after the tribbles have had a chance to split). What are the best upper and lower bounds you can give on $T(k)$, in terms of $k$?
(b) Suppose that we start with a single tribble of size $1$. Let $T(k)$ be the number of different possibilities for what we could see after $k$ days (in the evening, after the tribbles have had a chance to split). What are the best upper and lower bounds you can give on $T(k)$, in terms of $k$?
Misha
2018-05-14 21:01:01
(c) Given a tribble population such as "Ten tribbles of size 3", it can be difficult to tell whether it can ever be reached, if we start from a single tribble of size 1. Can you come up with any simple conditions that tell us that a population can definitely be reached, or that it definitely cannot be reached?
(c) Given a tribble population such as "Ten tribbles of size 3", it can be difficult to tell whether it can ever be reached, if we start from a single tribble of size 1. Can you come up with any simple conditions that tell us that a population can definitely be reached, or that it definitely cannot be reached?
Misha
2018-05-14 21:01:25
Okay, let's go.
Okay, let's go.
Misha
2018-05-14 21:01:33
Problem 7(a) solution.
Problem 7(a) solution.
Misha
2018-05-14 21:01:38
To begin with, there's a strategy for the tribbles to follow that's a natural one to guess. (And which works for small tribble sizes.) What is it?
To begin with, there's a strategy for the tribbles to follow that's a natural one to guess. (And which works for small tribble sizes.) What is it?
shroomley
2018-05-14 21:01:54
divide whenever you can
divide whenever you can
Generic_Username
2018-05-14 21:01:54
split whenever you can
split whenever you can
porkemon2
2018-05-14 21:01:57
split whenever possible
split whenever possible
Misha
2018-05-14 21:02:12
It's: all tribbles split as often as possible, as much as possible. This is called a "greedy" strategy, because it doesn't look ahead: it just does what's best in the moment.
It's: all tribbles split as often as possible, as much as possible. This is called a "greedy" strategy, because it doesn't look ahead: it just does what's best in the moment.
Misha
2018-05-14 21:02:18
In this case, the greedy strategy turns out to be best, but that's important to prove. (For some other rules for tribble growth, it isn't best!)
In this case, the greedy strategy turns out to be best, but that's important to prove. (For some other rules for tribble growth, it isn't best!)
Misha
2018-05-14 21:02:31
So suppose that at some point, we have a tribble of an even size $2a$. It decides not to split right then, and waits until it's size $2b$ to split into two tribbles of size $b$. How do we know that's a bad idea?
So suppose that at some point, we have a tribble of an even size $2a$. It decides not to split right then, and waits until it's size $2b$ to split into two tribbles of size $b$. How do we know that's a bad idea?
cTurek2
2018-05-14 21:03:22
because it takes more days to wait until 2b and then split than to split and then grow into b
because it takes more days to wait until 2b and then split than to split and then grow into b
Vfire
2018-05-14 21:03:22
because 2a-- > 2b --> b is slower than 2a --> a --> b
because 2a-- > 2b --> b is slower than 2a --> a --> b
einsteinatguelph
2018-05-14 21:03:25
We had waited 2b-2a days. If we split, b-a days is needed to achieve b
We had waited 2b-2a days. If we split, b-a days is needed to achieve b
Misha
2018-05-14 21:03:29
It takes $2b-2a$ days for it to grow before it splits. But if the tribble split right away, then both tribbles can grow to size $b$ in just $b-a$ more days.
It takes $2b-2a$ days for it to grow before it splits. But if the tribble split right away, then both tribbles can grow to size $b$ in just $b-a$ more days.
Misha
2018-05-14 21:03:55
(Note that this argument doesn't care what else is going on or what we're doing. It just says: if we wait to split, then whatever we're doing, we could be doing it faster.)
(Note that this argument doesn't care what else is going on or what we're doing. It just says: if we wait to split, then whatever we're doing, we could be doing it faster.)
Misha
2018-05-14 21:04:03
So now we know that any strategy that's not greedy can be improved. In other words, the greedy strategy is the best! So if we follow this strategy, how many size-1 tribbles do we have at the end? (If you like, try out what happens with 19 tribbles.)
So now we know that any strategy that's not greedy can be improved. In other words, the greedy strategy is the best! So if we follow this strategy, how many size-1 tribbles do we have at the end? (If you like, try out what happens with 19 tribbles.)
shroomley
2018-05-14 21:05:00
2^ceiling(log base 2 of n) i think
2^ceiling(log base 2 of n) i think
dihydrogen
2018-05-14 21:05:00
the least power of $2$ greater than $n$
the least power of $2$ greater than $n$
hliu70
2018-05-14 21:05:00
the next highest power of two
the next highest power of two
Misha
2018-05-14 21:05:25
This seems like a good guess. For 19, you go to 20, which becomes 5,5,5,5. Then 6,6,6,6 becomes 3,3,3,3,3,3.
This seems like a good guess. For 19, you go to 20, which becomes 5,5,5,5. Then 6,6,6,6 becomes 3,3,3,3,3,3.
Misha
2018-05-14 21:05:34
Then 4,4,4,4,4,4 becomes 32 tribbles of size 1.
Then 4,4,4,4,4,4 becomes 32 tribbles of size 1.
Misha
2018-05-14 21:05:40
It sure looks like we just round up to the next power of 2. (That is, if we start with a size-$n$ tribble, and $2^{k-1} < n \le 2^k$, then we end with $2^k$ size-1 tribbles.) There's a lot of ways to prove this, but my favorite approach that I saw in solutions is induction on $k$.
It sure looks like we just round up to the next power of 2. (That is, if we start with a size-$n$ tribble, and $2^{k-1} < n \le 2^k$, then we end with $2^k$ size-1 tribbles.) There's a lot of ways to prove this, but my favorite approach that I saw in solutions is induction on $k$.
Misha
2018-05-14 21:05:57
Base case: it's not hard to prove that this observation holds when $k=1$.
Base case: it's not hard to prove that this observation holds when $k=1$.
Misha
2018-05-14 21:06:06
(We just check $n=1$ and $n=2$.)
(We just check $n=1$ and $n=2$.)
Misha
2018-05-14 21:06:21
Suppose it's true in the range $(2^{k-1}, 2^k]$.
Suppose it's true in the range $(2^{k-1}, 2^k]$.
Misha
2018-05-14 21:06:29
If $2^k < n \le 2^{k+1}$ and $n$ is even, we split into two tribbles of size $\frac n2$, which eventually end up as $2^k$ size-1 tribbles each by the induction hypothesis.
If $2^k < n \le 2^{k+1}$ and $n$ is even, we split into two tribbles of size $\frac n2$, which eventually end up as $2^k$ size-1 tribbles each by the induction hypothesis.
Misha
2018-05-14 21:06:42
If $2^k < n \le 2^{k+1}$ and $n$ is odd, then we grow to $n+1$ (still in the same range!) and then split into two tribbles of size $\frac{n+1}2$ and then the same thing happens.
If $2^k < n \le 2^{k+1}$ and $n$ is odd, then we grow to $n+1$ (still in the same range!) and then split into two tribbles of size $\frac{n+1}2$ and then the same thing happens.
Misha
2018-05-14 21:07:08
So by induction, we round up to the next power of $2$ in the range $(2^k, 2^{k+1}]$, too.
So by induction, we round up to the next power of $2$ in the range $(2^k, 2^{k+1}]$, too.
Misha
2018-05-14 21:07:20
This solves (a).
This solves (a).
dihydrogen
2018-05-14 21:07:30
efficient proof!
efficient proof!
Misha
2018-05-14 21:07:33
It's not mine!
It's not mine!
Misha
2018-05-14 21:07:41
I was reading all of y'all's solutions for the quiz
I was reading all of y'all's solutions for the quiz
Misha
2018-05-14 21:07:43
and took the best one
and took the best one
Misha
2018-05-14 21:07:54
(I don't know whose because I was reading them anonymously)
(I don't know whose because I was reading them anonymously)
Misha
2018-05-14 21:07:59
Anyway.
Anyway.
Misha
2018-05-14 21:08:01
Problem 7(b) solution.
Problem 7(b) solution.
Misha
2018-05-14 21:08:06
First, some philosophy. How can we prove a lower bound on $T(k)$? One way is to limit how the tribbles split, and only consider those cases in which the tribbles follow those limits. To prove an upper bound, we might consider a larger set of cases that includes all real possibilities, as well as some impossible outcomes.
First, some philosophy. How can we prove a lower bound on $T(k)$? One way is to limit how the tribbles split, and only consider those cases in which the tribbles follow those limits. To prove an upper bound, we might consider a larger set of cases that includes all real possibilities, as well as some impossible outcomes.
Misha
2018-05-14 21:08:16
In both cases, our goal with adding either limits or impossible cases is to get a number that's easier to count.
In both cases, our goal with adding either limits or impossible cases is to get a number that's easier to count.
Misha
2018-05-14 21:08:27
So as a warm-up, let's get some not-very-good lower and upper bounds. Suppose I add a limit: for the first $k-1$ days, all tribbles of size 2 must split. On the last day, they can do anything. How many outcomes are there now?
So as a warm-up, let's get some not-very-good lower and upper bounds. Suppose I add a limit: for the first $k-1$ days, all tribbles of size 2 must split. On the last day, they can do anything. How many outcomes are there now?
StyrofoamCup
2018-05-14 21:09:10
2^k
2^k
Vfire
2018-05-14 21:09:10
2^k
2^k
Misha
2018-05-14 21:09:15
Not quite.
Not quite.
Misha
2018-05-14 21:09:17
But mostly.
But mostly.
Misha
2018-05-14 21:09:39
There's $2^{k-1}+1$ outcomes. (More or less $2^k$.) After $k-1$ days, there are $2^{k-1}$ size-1 tribbles. On the last day, they all grow to size 2, and between 0 and $2^{k-1}$ of them split. All those cases are different.
There's $2^{k-1}+1$ outcomes. (More or less $2^k$.) After $k-1$ days, there are $2^{k-1}$ size-1 tribbles. On the last day, they all grow to size 2, and between 0 and $2^{k-1}$ of them split. All those cases are different.
Misha
2018-05-14 21:10:07
Really, just seeing "it's kind of like $2^k$" is good enough.
Really, just seeing "it's kind of like $2^k$" is good enough.
Misha
2018-05-14 21:10:15
Okay, so now let's get a terrible upper bound.
Okay, so now let's get a terrible upper bound.
Misha
2018-05-14 21:10:53
After $k$ days, there are going to be at most $2^k$ tribbles, which have total volume at most $2^k$ or less.
After $k$ days, there are going to be at most $2^k$ tribbles, which have total volume at most $2^k$ or less.
Misha
2018-05-14 21:11:31
If we also line up the tribbles in order, then there are $2^{2^k}-1$ ways to "split up" the tribble volume into individual tribbles.
If we also line up the tribbles in order, then there are $2^{2^k}-1$ ways to "split up" the tribble volume into individual tribbles.
Misha
2018-05-14 21:11:42
(Some of you are already giving better bounds than this!)
(Some of you are already giving better bounds than this!)
Misha
2018-05-14 21:12:22
So $2^k$ and $2^{2^k}$ are very far apart. Let's get better bounds. First, let's improve our bad lower bound to a good lower bound.
So $2^k$ and $2^{2^k}$ are very far apart. Let's get better bounds. First, let's improve our bad lower bound to a good lower bound.
Misha
2018-05-14 21:12:34
We can get a better lower bound by modifying our first strategy strategy a bit. Let's say that:
* All tribbles split for the first $k/2$ days.
* Then we split the $2^{k/2}$ tribbles we have into groups numbered $1$ through $k/2$.
* The tribbles in group $i$ will keep splitting for the next $i$ days, and grow without splitting for the remainder.
We can get a better lower bound by modifying our first strategy strategy a bit. Let's say that:
* All tribbles split for the first $k/2$ days.
* Then we split the $2^{k/2}$ tribbles we have into groups numbered $1$ through $k/2$.
* The tribbles in group $i$ will keep splitting for the next $i$ days, and grow without splitting for the remainder.
Misha
2018-05-14 21:12:39
How many ways can we split the $2^{k/2}$ tribbles into $k/2$ groups?
How many ways can we split the $2^{k/2}$ tribbles into $k/2$ groups?
Misha
2018-05-14 21:13:44
(maybe "split" is a bad word to use here. How many ways can we divide the tribbles into groups?)
(maybe "split" is a bad word to use here. How many ways can we divide the tribbles into groups?)
Misha
2018-05-14 21:14:53
This can be counted by stars and bars. (See https://artofproblemsolving.com/wiki/index.php?title=Ball-and-urn if you haven't seen these before.) The total is $\binom{2^{k/2} + k/2 -1}{k/2-1}$, which is very approximately $2^{k^2/4}$. And all the different splits produce different outcomes at the end, so this is a lower bound for $T(k)$.
This can be counted by stars and bars. (See https://artofproblemsolving.com/wiki/index.php?title=Ball-and-urn if you haven't seen these before.) The total is $\binom{2^{k/2} + k/2 -1}{k/2-1}$, which is very approximately $2^{k^2/4}$. And all the different splits produce different outcomes at the end, so this is a lower bound for $T(k)$.
Misha
2018-05-14 21:15:51
Does everyone see the stars and bars connection? We have $2^{k/2}$ identical tribbles, and we just put in $k/2-1$ dividers between them to separate them into groups.
Does everyone see the stars and bars connection? We have $2^{k/2}$ identical tribbles, and we just put in $k/2-1$ dividers between them to separate them into groups.
AtlasO
2018-05-14 21:16:00
how do we find the higher bound?
how do we find the higher bound?
Misha
2018-05-14 21:16:08
Our higher bound will actually look very similar!
Our higher bound will actually look very similar!
Misha
2018-05-14 21:16:31
But for this, remember the philosophy: to get an upper bound, we need to allow extra, impossible combinations, and we do this to get something easier to count.
But for this, remember the philosophy: to get an upper bound, we need to allow extra, impossible combinations, and we do this to get something easier to count.
Misha
2018-05-14 21:16:36
So now let's get an upper bound. Here, we notice that there's at most $2^k$ tribbles after $k$ days, and all tribbles have size $k+1$ or less (since they've had at most $k$ days to grow). How can we use these two facts?
So now let's get an upper bound. Here, we notice that there's at most $2^k$ tribbles after $k$ days, and all tribbles have size $k+1$ or less (since they've had at most $k$ days to grow). How can we use these two facts?
reedmj
2018-05-14 21:18:30
partitions of $2^k(k+1)$
partitions of $2^k(k+1)$
Misha
2018-05-14 21:18:35
Almost this.
Almost this.
Misha
2018-05-14 21:18:39
We can count all ways to split $2^k$ tribbles into $k+2$ groups (size 1, size 2, all the way up to size $k+1$, and size "does not exist".) A bunch of these are impossible to achieve in $k$ days, but we don't care: we just want an upper bound. How many such ways are there?
We can count all ways to split $2^k$ tribbles into $k+2$ groups (size 1, size 2, all the way up to size $k+1$, and size "does not exist".) A bunch of these are impossible to achieve in $k$ days, but we don't care: we just want an upper bound. How many such ways are there?
einsteinatguelph
2018-05-14 21:20:13
Do we user the stars and bars method again?
Do we user the stars and bars method again?
dihydrogen
2018-05-14 21:20:13
$(2^k+k+1)$ choose $(k+1)$
$(2^k+k+1)$ choose $(k+1)$
Misha
2018-05-14 21:20:28
This is just stars and bars again. But now the answer is $\binom{2^k+k+1}{k+1}$, which is very approximately $2^{k^2}$.
This is just stars and bars again. But now the answer is $\binom{2^k+k+1}{k+1}$, which is very approximately $2^{k^2}$.
dihydrogen
2018-05-14 21:20:48
How do you get to that approximation?
How do you get to that approximation?
Misha
2018-05-14 21:21:05
Great question! I am saying that $\binom nk$ is approximately $n^k$.
Great question! I am saying that $\binom nk$ is approximately $n^k$.
Misha
2018-05-14 21:21:12
This is kind of a bad approximation.
This is kind of a bad approximation.
Misha
2018-05-14 21:21:20
Actually, $\frac{n^k}{k!}$ would be better.
Actually, $\frac{n^k}{k!}$ would be better.
Misha
2018-05-14 21:21:35
(Since $\binom nk$ is $\frac{n(n-1)(n-2)(\dots)(n-k+1)}{k!}$.)
(Since $\binom nk$ is $\frac{n(n-1)(n-2)(\dots)(n-k+1)}{k!}$.)
Misha
2018-05-14 21:21:58
But in our case, the bottom part of the $\binom nk$ is much smaller than the top part, so $\frac[n^k}{k!}$ is about the same as $n^k$.
But in our case, the bottom part of the $\binom nk$ is much smaller than the top part, so $\frac[n^k}{k!}$ is about the same as $n^k$.
Misha
2018-05-14 21:22:07
Sorry, that was a $\frac[n^k}{k!}$.
Sorry, that was a $\frac[n^k}{k!}$.
AtlasO
2018-05-14 21:22:10
that approximation only works for relativly small values of k, right?
that approximation only works for relativly small values of k, right?
Misha
2018-05-14 21:22:12
Right.
Right.
Misha
2018-05-14 21:22:29
So now we have lower and upper bounds for $T(k)$ that look about the same; let's call that good enough!
So now we have lower and upper bounds for $T(k)$ that look about the same; let's call that good enough!
Misha
2018-05-14 21:22:47
(We have about $2^{k^2/4}$ on one side and $2^{k^2}$ on the other.)
(We have about $2^{k^2/4}$ on one side and $2^{k^2}$ on the other.)
Misha
2018-05-14 21:22:56
Problem 7(c) solution.
Problem 7(c) solution.
Misha
2018-05-14 21:23:03
Lots of people wrote in conjectures for this one. It was popular to guess that you can only reach $n$ tribbles of the same size if $n$ is a power of 2.
Lots of people wrote in conjectures for this one. It was popular to guess that you can only reach $n$ tribbles of the same size if $n$ is a power of 2.
Misha
2018-05-14 21:23:15
So let me surprise everyone. You can reach ten tribbles of size 3. All you have to do is go 1 to 2 to 11 to 22 to 1111 to 2222 to 11222 to 22333 to 1111333 to 2222444 to 2222222222 to 3333333333.
So let me surprise everyone. You can reach ten tribbles of size 3. All you have to do is go 1 to 2 to 11 to 22 to 1111 to 2222 to 11222 to 22333 to 1111333 to 2222444 to 2222222222 to 3333333333.
AtlasO
2018-05-14 21:23:45
howd u get that?
howd u get that?
Misha
2018-05-14 21:23:57
This is part of a general strategy that proves that you can reach any even number of tribbles of size 2 (and any higher size). Of all the partial results that people proved, I think this was the most exciting.
This is part of a general strategy that proves that you can reach any even number of tribbles of size 2 (and any higher size). Of all the partial results that people proved, I think this was the most exciting.
hliu70
2018-05-14 21:24:06
wow
wow
Misha
2018-05-14 21:24:08
wow is right!
wow is right!
Misha
2018-05-14 21:24:23
reading all of these solutions was really fun for me, because I got to see all the cool things everyone did
reading all of these solutions was really fun for me, because I got to see all the cool things everyone did
Misha
2018-05-14 21:24:54
So here's how we can get $2n$ tribbles of size $2$ for any $n$.
So here's how we can get $2n$ tribbles of size $2$ for any $n$.
Misha
2018-05-14 21:24:57
First of all, we know how to reach $2^k$ tribbles of size 2, for any $k$. These can be split into $n$ tribbles in a mix of sizes 1 and 2, for any $n$ such that $2^k \le n \le 2^{k+1}$.
First of all, we know how to reach $2^k$ tribbles of size 2, for any $k$. These can be split into $n$ tribbles in a mix of sizes 1 and 2, for any $n$ such that $2^k \le n \le 2^{k+1}$.
Misha
2018-05-14 21:25:22
Those $n$ tribbles can turn into $2n$ tribbles of size 2 in just two more days. The size-1 tribbles grow, split, and grow again. The size-2 tribbles grow, grow, and then split.
Those $n$ tribbles can turn into $2n$ tribbles of size 2 in just two more days. The size-1 tribbles grow, split, and grow again. The size-2 tribbles grow, grow, and then split.
Misha
2018-05-14 21:26:11
And since any $n$ is between some two powers of $2$, we can get any even number this way.
And since any $n$ is between some two powers of $2$, we can get any even number this way.
Misha
2018-05-14 21:26:19
(This is how I got the solution for ten tribbles, above.)
(This is how I got the solution for ten tribbles, above.)
Misha
2018-05-14 21:26:33
So I think that wraps up all the problems!
So I think that wraps up all the problems!
MarisaD
2018-05-14 21:26:45
And right on time, too!
And right on time, too!
MarisaD
2018-05-14 21:26:49
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
MarisaD
2018-05-14 21:26:57
If we didn't get to your question, you can also post questions in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too!
If we didn't get to your question, you can also post questions in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too!
MarisaD
2018-05-14 21:27:19
I'll stick around for another five minutes and answer non-Quiz questions (e.g. about the program and the application process).
I'll stick around for another five minutes and answer non-Quiz questions (e.g. about the program and the application process).
AtlasO
2018-05-14 21:27:34
find an expression using the variables
find an expression using the variables
AtlasO
2018-05-14 21:27:34
Thank you to all the moderators who are working on this and all the AOPS staff who worked on this, it really means a lot to me and to us so I hope you know we appreciate all your work and kindness.
Thank you to all the moderators who are working on this and all the AOPS staff who worked on this, it really means a lot to me and to us so I hope you know we appreciate all your work and kindness.
reedmj
2018-05-14 21:27:34
Thank you very much for working through the problems with us! See you all at Mines this summer!
Thank you very much for working through the problems with us! See you all at Mines this summer!
MarisaD
2018-05-14 21:27:39
Thank YOU for joining us here!
Thank YOU for joining us here!
MarisaD
2018-05-14 21:27:58
We love getting to actually *talk* about the QQ problems.
We love getting to actually *talk* about the QQ problems.
404nfound
2018-05-14 21:28:03
How many problems do people who are admitted generally solved?
How many problems do people who are admitted generally solved?
MarisaD
2018-05-14 21:28:18
It varies widely. Most successful applicants have at least a few complete solutions.
It varies widely. Most successful applicants have at least a few complete solutions.
MarisaD
2018-05-14 21:28:35
(Very few have full solutions to every problem!)
(Very few have full solutions to every problem!)
sooper
2018-05-14 21:29:42
how do we get the summer camp?
how do we get the summer camp?
MarisaD
2018-05-14 21:29:51
Well, first, you apply! See http://www.mathcamp.org/prospectiveapplicants/index.php for details.
Well, first, you apply! See http://www.mathcamp.org/prospectiveapplicants/index.php for details.
MarisaD
2018-05-14 21:30:02
And then most students fly.
And then most students fly.
MarisaD
2018-05-14 21:31:02
Alrighty – we've hit our two hour mark. Time to wrap up. Thanks again, everybody - good night!
Alrighty – we've hit our two hour mark. Time to wrap up. Thanks again, everybody - good night!
5space
2018-05-14 21:31:35
Thanks again, everybody - good night!
Thanks again, everybody - good night!
5space
2018-05-14 21:31:43
If you have further questions for Mathcamp, you can contact them at http://www.mathcamp.org/contact.php
If you have further questions for Mathcamp, you can contact them at http://www.mathcamp.org/contact.php
5space
2018-05-14 21:31:49
Or ask on the Mathcamps forum
Or ask on the Mathcamps forum
5space
2018-05-14 21:31:52
Finally, a transcript of this Math Jam will be posted soon here: http://www.aops.com/school/mathjams-transcripts
Finally, a transcript of this Math Jam will be posted soon here: http://www.aops.com/school/mathjams-transcripts
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
