Canada/USA Mathcamp Qualifying Quiz
Go back to the Math Jam ArchiveMathcamp instructors discuss the problems from the 2014 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: Marisa Debowsky
rrusczyk
2014-06-16 19:54:44
Greetings and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Greetings and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
rrusczyk
2014-06-16 19:54:50
We'll get started in a little under 10 minutes.
We'll get started in a little under 10 minutes.
rrusczyk
2014-06-16 19:55:06
Please note that the classroom is moderated, meaning that students can type into the classroom, but these comments will not go directly into the room. These comments go to the instructors, who may choose to share your comments with the room.
Please note that the classroom is moderated, meaning that students can type into the classroom, but these comments will not go directly into the room. These comments go to the instructors, who may choose to share your comments with the room.
rrusczyk
2014-06-16 20:02:23
Are you ready for some interesting math?
Are you ready for some interesting math?
ninjataco
2014-06-16 20:02:40
YEAH!
YEAH!
jhuang967
2014-06-16 20:02:40
Yes.
Yes.
tiko1004
2014-06-16 20:02:40
yez
yez
64138luc
2014-06-16 20:02:40
yes
yes
distortedwalrus
2014-06-16 20:02:40
yes
yes
rrusczyk
2014-06-16 20:02:45
You're in the right place.
You're in the right place.
rrusczyk
2014-06-16 20:02:49
Greetings and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Greetings and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
rrusczyk
2014-06-16 20:02:57
Canada/USA Mathcamp is an intensive 5-week-long summer program for mathematically talented high school students, designed to expose these students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about the program at www.mathcamp.org .
Canada/USA Mathcamp is an intensive 5-week-long summer program for mathematically talented high school students, designed to expose these students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about the program at www.mathcamp.org .
rrusczyk
2014-06-16 20:03:09
Mira Bernstein, Executive Director of Mathcamp, will host the discussion of the Qualifying Quiz. Joining her tonight is Marisa Debowsky, Mathcamp Program Director.
Mira Bernstein, Executive Director of Mathcamp, will host the discussion of the Qualifying Quiz. Joining her tonight is Marisa Debowsky, Mathcamp Program Director.
rrusczyk
2014-06-16 20:03:17
Before we get started tonight, I'd like to quickly go through some classroom procedures.
Before we get started tonight, I'd like to quickly go through some classroom procedures.
rrusczyk
2014-06-16 20:03:27
The classroom is moderated, meaning that students can type into the classroom, but these comments will not go directly into the room. These comments go to the instructors, who may choose to share your comments with the room.
The classroom is moderated, meaning that students can type into the classroom, but these comments will not go directly into the room. These comments go to the instructors, who may choose to share your comments with the room.
rrusczyk
2014-06-16 20:03:38
This classroom supports LaTeX, so you can use LaTeX in your posts.
This classroom supports LaTeX, so you can use LaTeX in your posts.
rrusczyk
2014-06-16 20:03:46
You can also resize the classroom, and change the font size with the "A"s in the top bar.
You can also resize the classroom, and change the font size with the "A"s in the top bar.
rrusczyk
2014-06-16 20:03:57
Enough instructions, I'll turn the room over to Mira and Marisa now!
Enough instructions, I'll turn the room over to Mira and Marisa now!
MiraBernstein
2014-06-16 20:04:07
Thanks Richard!
$\qquad$
Hi everyone! Welcome to the Math Jam for the 2014 Mathcamp Qualifying Quiz.
Thanks Richard!
$\qquad$
Hi everyone! Welcome to the Math Jam for the 2014 Mathcamp Qualifying Quiz.
MiraBernstein
2014-06-16 20:04:16
My name is Mira. I have been teaching at Mathcamp since 1997 (almost since the beginning), and have been the Executive Director (aka "Ze Top Banana Of Ze Mathcamp Power Structure") since 2002. I was also the one in charge of putting together this year's qualifying quiz (though I got help from lots of other people too).
My name is Mira. I have been teaching at Mathcamp since 1997 (almost since the beginning), and have been the Executive Director (aka "Ze Top Banana Of Ze Mathcamp Power Structure") since 2002. I was also the one in charge of putting together this year's qualifying quiz (though I got help from lots of other people too).
MiraBernstein
2014-06-16 20:04:28
Full disclosure before we start: I have never taught an AoPS class before. I watched my friend and Mathcamp colleague Ari Nieh do it on Friday, and was a little intimidated by the speed of the multitasking that was involved! So please bear with me as I learn the ropes. (Also, if I know you, but wouldn't recognize you from your username, please introduce yourself!)
Full disclosure before we start: I have never taught an AoPS class before. I watched my friend and Mathcamp colleague Ari Nieh do it on Friday, and was a little intimidated by the speed of the multitasking that was involved! So please bear with me as I learn the ropes. (Also, if I know you, but wouldn't recognize you from your username, please introduce yourself!)
MiraBernstein
2014-06-16 20:04:41
My "TA" today is Marisa Debowsky, Mathcamp's program director. Marisa did an AOPS MathJam about Mathcamp earlier this year, and if you applied to Mathcamp, it's likely that you've been in communication with her.
My "TA" today is Marisa Debowsky, Mathcamp's program director. Marisa did an AOPS MathJam about Mathcamp earlier this year, and if you applied to Mathcamp, it's likely that you've been in communication with her.
MarisaD
2014-06-16 20:05:00
Hi, all, I'm Marisa. I've been teaching at Mathcamp since 2006, and have been running the program since 2009.
Hi, all, I'm Marisa. I've been teaching at Mathcamp since 2006, and have been running the program since 2009.
minimario
2014-06-16 20:05:13
Will Mathcamp be discussed or only the QQ
Will Mathcamp be discussed or only the QQ
MarisaD
2014-06-16 20:05:19
Tonight, we're just talking about the Quiz. (If you have questions about Mathcamp, you'll find lots of info on our website, or check out the AoPS Jam about the program and the application process from a few weeks ago: http://www.artofproblemsolving.com/School/mathjams.php?mj_id=358.
Tonight, we're just talking about the Quiz. (If you have questions about Mathcamp, you'll find lots of info on our website, or check out the AoPS Jam about the program and the application process from a few weeks ago: http://www.artofproblemsolving.com/School/mathjams.php?mj_id=358.
MarisaD
2014-06-16 20:05:25
I read lots of your great solutions to Quiz problems during admissions this spring, and I'm glad we all get a chance to chat about the Quiz this evening! Thanks, everybody, for joining us.
I read lots of your great solutions to Quiz problems during admissions this spring, and I'm glad we all get a chance to chat about the Quiz this evening! Thanks, everybody, for joining us.
MiraBernstein
2014-06-16 20:05:25
I'll be going over the solutions to the Mathcamp Qualifying Quiz, an untimed set of (hard) problems that all applicants to Canada/USA Mathcamp must solve for admission. You don't need to solve all of the problems, but you need to make good progress. The Quiz is not the only factor that affects your admission to Mathcamp, but it is the most important one.
I'll be going over the solutions to the Mathcamp Qualifying Quiz, an untimed set of (hard) problems that all applicants to Canada/USA Mathcamp must solve for admission. You don't need to solve all of the problems, but you need to make good progress. The Quiz is not the only factor that affects your admission to Mathcamp, but it is the most important one.
MiraBernstein
2014-06-16 20:05:47
This chat room is moderated. That means your messages go only to me, and I will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time.
$\qquad$
But if you have questions about how we select problems or how we grade solutions, please save them and I'll try to leave time for them at the end of the Math Jam. If I don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS at http://www.artofproblemsolving.com/Forum/viewforum.php?f=314
This chat room is moderated. That means your messages go only to me, and I will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time.
$\qquad$
But if you have questions about how we select problems or how we grade solutions, please save them and I'll try to leave time for them at the end of the Math Jam. If I don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS at http://www.artofproblemsolving.com/Forum/viewforum.php?f=314
MiraBernstein
2014-06-16 20:06:17
My goal is to get through the first six problems on the quiz, in about two hours. (I'm really sorry, I ran out of time and didn't have a chance to prepare a script for #7.)
$\qquad$
I'll try to show you not just the correct answers, but how you might come up with those answers, and how to write them in a way that really communicates the mathematics you're doing. We're going to start relatively slowly, but accelerate as we go along. The idea is for everyone to be able to follow at first, but be warned that things will get more and more difficult as we go on. (This is how a lot of actual math talks work too.)
My goal is to get through the first six problems on the quiz, in about two hours. (I'm really sorry, I ran out of time and didn't have a chance to prepare a script for #7.)
$\qquad$
I'll try to show you not just the correct answers, but how you might come up with those answers, and how to write them in a way that really communicates the mathematics you're doing. We're going to start relatively slowly, but accelerate as we go along. The idea is for everyone to be able to follow at first, but be warned that things will get more and more difficult as we go on. (This is how a lot of actual math talks work too.)
MiraBernstein
2014-06-16 20:06:42
To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/prospectiveapplicants/quiz/index.php
$\qquad$
And if you applied this year, I recommend having your solutions open too. That way, you can reply more quickly to the questions I ask of the room. I like to teach interactively, so I'm expecting you all to pitch in to the solutions!
To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/prospectiveapplicants/quiz/index.php
$\qquad$
And if you applied this year, I recommend having your solutions open too. That way, you can reply more quickly to the questions I ask of the room. I like to teach interactively, so I'm expecting you all to pitch in to the solutions!
NeilOnnsu
2014-06-16 20:06:54
Will a solution for #7 be posted somewhere?
Will a solution for #7 be posted somewhere?
MiraBernstein
2014-06-16 20:07:23
Yes, I'll post it on the Mathcamp webpage. Really sorry -- this took a lot longer to prepare than I expected.
Yes, I'll post it on the Mathcamp webpage. Really sorry -- this took a lot longer to prepare than I expected.
MiraBernstein
2014-06-16 20:07:31
That's what comes form being a newbie
That's what comes form being a newbie
MiraBernstein
2014-06-16 20:07:44
We've got a lot to cover, so let's get started.
We've got a lot to cover, so let's get started.
MiraBernstein
2014-06-16 20:07:54
PROBLEM 1: Imagine a chessboard that extends infinitely far in all directions. In the center of every square is a grasshopper.
$\qquad$(a)Show that it is possible for all the grasshoppers to jump simultaneously, so that after the jump there are exactly two grasshoppers in the center of every square. (A grasshopper can jump arbitrarily far; it can also jump straight up and land on the same spot it started on.)
$\qquad$(a) Now suppose the squares are 1 inch $\times$ 1 inch, and a grasshopper can jump at most 100 inches. Is it still possible to end up with two grasshoppers in the center of every square after one jump? If yes, show how it can be done. If no, prove your answer.
PROBLEM 1: Imagine a chessboard that extends infinitely far in all directions. In the center of every square is a grasshopper.
$\qquad$(a)Show that it is possible for all the grasshoppers to jump simultaneously, so that after the jump there are exactly two grasshoppers in the center of every square. (A grasshopper can jump arbitrarily far; it can also jump straight up and land on the same spot it started on.)
$\qquad$(a) Now suppose the squares are 1 inch $\times$ 1 inch, and a grasshopper can jump at most 100 inches. Is it still possible to end up with two grasshoppers in the center of every square after one jump? If yes, show how it can be done. If no, prove your answer.
MiraBernstein
2014-06-16 20:08:13
Let's start with part (a). Is it possible?
Let's start with part (a). Is it possible?
ChilledLemonade
2014-06-16 20:08:28
yes
yes
danusv
2014-06-16 20:08:28
Yes
Yes
chessderek
2014-06-16 20:08:28
yes
yes
MiraBernstein
2014-06-16 20:08:39
Yes, it IS possible! You might think that it can't be done, since you'd need twice as many grasshoppers as you started with. But there are infinitely many of them to start with, and infinities are funny that way. (There is no pigeonhole principle for infinitely many objects!)
Yes, it IS possible! You might think that it can't be done, since you'd need twice as many grasshoppers as you started with. But there are infinitely many of them to start with, and infinities are funny that way. (There is no pigeonhole principle for infinitely many objects!)
MiraBernstein
2014-06-16 20:08:51
There are many different ways in which you can tell the grasshoppers to jump. I personally found it easiest to deal with each row of the chessboard separately. Whatever you can do in one row, you can do in the others.
$\;$
So let's pick any row. Pick one square in that row and call it 0. Number the squares to its right 1,2,3,... and the squares to its left -1,-2,-3. .... Now, how can we get all the grasshoppers in this row to jump so that afterwards there are two per square?
There are many different ways in which you can tell the grasshoppers to jump. I personally found it easiest to deal with each row of the chessboard separately. Whatever you can do in one row, you can do in the others.
$\;$
So let's pick any row. Pick one square in that row and call it 0. Number the squares to its right 1,2,3,... and the squares to its left -1,-2,-3. .... Now, how can we get all the grasshoppers in this row to jump so that afterwards there are two per square?
loconate
2014-06-16 20:09:31
Yes
Yes
ChilledLemonade
2014-06-16 20:09:31
use the floor or ceiling function
use the floor or ceiling function
Akababa
2014-06-16 20:09:31
2n and 2n+1 jump to n!
2n and 2n+1 jump to n!
amwmath
2014-06-16 20:09:31
Halve it and round up. (Or down.)
Halve it and round up. (Or down.)
distortedwalrus
2014-06-16 20:09:31
n --> floor(n/2)
n --> floor(n/2)
MiraBernstein
2014-06-16 20:09:50
As I said, there are many ways to do this. For example, for each $n$, make the grasshoppers from squares $2n$ and $2n+1$ jump to $n$. So,
$\qquad$ 0 and 1 jump to 0 $\qquad$ -1 and -2 jump to -1
$\qquad$ 2 and 3 jump to 1 $\qquad$ -3 and -4 jump to -2
$\qquad$ 4 and 5 jump to 2 $\qquad$ -5 and -6 jump to -3
$\qquad$ etc.
$\qquad$
In mathematical terms, what we have here is a 2-to-1 function from the integers to the integers. And since we can replicate it in every row, we have a 2-to-1 function from the chessboard to the chessboard, as required.
$\qquad$
Questions?
As I said, there are many ways to do this. For example, for each $n$, make the grasshoppers from squares $2n$ and $2n+1$ jump to $n$. So,
$\qquad$ 0 and 1 jump to 0 $\qquad$ -1 and -2 jump to -1
$\qquad$ 2 and 3 jump to 1 $\qquad$ -3 and -4 jump to -2
$\qquad$ 4 and 5 jump to 2 $\qquad$ -5 and -6 jump to -3
$\qquad$ etc.
$\qquad$
In mathematical terms, what we have here is a 2-to-1 function from the integers to the integers. And since we can replicate it in every row, we have a 2-to-1 function from the chessboard to the chessboard, as required.
$\qquad$
Questions?
murfel
2014-06-16 20:10:14
it's like Hilbert's hotel ;)
it's like Hilbert's hotel ;)
MiraBernstein
2014-06-16 20:10:30
Yes! those of you who have't seen this kind of weird stuff with infinities before may want to google "Hilbert's Hotel". You can learn even more at http://www.math.hmc.edu/funfacts/ffiles/30001.3-4.shtml
Yes! those of you who have't seen this kind of weird stuff with infinities before may want to google "Hilbert's Hotel". You can learn even more at http://www.math.hmc.edu/funfacts/ffiles/30001.3-4.shtml
MiraBernstein
2014-06-16 20:10:38
OK, on to part (b), where the grasshoppers can only jump 100 inches. This turns out to be impossible. What's the general idea of the proof?
OK, on to part (b), where the grasshoppers can only jump 100 inches. This turns out to be impossible. What's the general idea of the proof?
64138luc
2014-06-16 20:11:44
Proove it cannot be done in a bounded area
Proove it cannot be done in a bounded area
Moonlight243
2014-06-16 20:11:44
use contradiction after assuming it is possible
use contradiction after assuming it is possible
jhuang967
2014-06-16 20:11:44
Basically, consider the grasshoppers jumping in to fill a particular square.
Basically, consider the grasshoppers jumping in to fill a particular square.
distortedwalrus
2014-06-16 20:11:44
consider a very large area, for which it's impossible for a sufficient number of grasshoppers to enter
consider a very large area, for which it's impossible for a sufficient number of grasshoppers to enter
jhuang967
2014-06-16 20:11:44
Then consider the grasshoppers having to fill those squares.
Then consider the grasshoppers having to fill those squares.
MiraBernstein
2014-06-16 20:12:02
Right! Any finite region of the board can now collect grasshoppers only from a finite radius around it. We need to find an example of a region where the total number of grasshoppers that can jump into it is insufficient. What's an example?
Right! Any finite region of the board can now collect grasshoppers only from a finite radius around it. We need to find an example of a region where the total number of grasshoppers that can jump into it is insufficient. What's an example?
mathlover3737
2014-06-16 20:12:38
a very large square
a very large square
distortedwalrus
2014-06-16 20:12:38
a 500 x 500 square
a 500 x 500 square
amwmath
2014-06-16 20:12:38
I did 1,000,000 by 1,000,000 (because I can).
I did 1,000,000 by 1,000,000 (because I can).
MiraBernstein
2014-06-16 20:12:58
There are many examples you can choose from, but for some reason a lot of applicants chose a $1000 \times 1000$ square, so let's go with that. This region has a million little squares in it, so we need to provide two million grasshoppers. Can we describe some simple set of boundaries that all these grasshoppers must come from?
There are many examples you can choose from, but for some reason a lot of applicants chose a $1000 \times 1000$ square, so let's go with that. This region has a million little squares in it, so we need to provide two million grasshoppers. Can we describe some simple set of boundaries that all these grasshoppers must come from?
amwmath
2014-06-16 20:13:50
They all came from a 1200 x 1200 square.
They all came from a 1200 x 1200 square.
mathlover3737
2014-06-16 20:13:50
a 1200 by 1200 square (without the corners)
a 1200 by 1200 square (without the corners)
ninjataco
2014-06-16 20:13:50
all points 100 inches from the boundary of the square
all points 100 inches from the boundary of the square
rohana
2014-06-16 20:13:50
1200*1200
1200*1200
shipeiyang1708
2014-06-16 20:13:50
within the 1000 by 1000 and a 100 inch radius around the square
within the 1000 by 1000 and a 100 inch radius around the square
gedt11
2014-06-16 20:13:50
a 1200*1200square
a 1200*1200square
happiface
2014-06-16 20:14:05
the 1200 by 1200 square with the same center
the 1200 by 1200 square with the same center
MiraBernstein
2014-06-16 20:14:07
The easiest way to do this is to take a $1200 \times 1200$ square, with our original $1000\times 1000$ square in the center.
The easiest way to do this is to take a $1200 \times 1200$ square, with our original $1000\times 1000$ square in the center.
MiraBernstein
2014-06-16 20:14:32
The grasshoppers in the corners of the $1200 \times 1200$ square are too far to get to the $1000 \times 1000$ square, but that doesn't matter. We don't need to know that ALL the grasshoppers in the large square can reach the small square. We just need to know that ONLY the grasshoppers in the large square can reach the small square. You could try to make a smaller region (like a square with rounded edges), and there's nothing wrong with that. But as you'll see soon, that just creates unnecessary work.
The grasshoppers in the corners of the $1200 \times 1200$ square are too far to get to the $1000 \times 1000$ square, but that doesn't matter. We don't need to know that ALL the grasshoppers in the large square can reach the small square. We just need to know that ONLY the grasshoppers in the large square can reach the small square. You could try to make a smaller region (like a square with rounded edges), and there's nothing wrong with that. But as you'll see soon, that just creates unnecessary work.
MiraBernstein
2014-06-16 20:14:58
We're almost done. How do we finish the argument?
We're almost done. How do we finish the argument?
Sesquipedalian
2014-06-16 20:15:12
It actually works with a significantly smaller square; for instance, a $483\times483$!
It actually works with a significantly smaller square; for instance, a $483\times483$!
MiraBernstein
2014-06-16 20:15:22
True -- but no reason economize!
True -- but no reason economize!
NeilOnnsu
2014-06-16 20:16:00
1200*1200 < 2*1000*1000
1200*1200 < 2*1000*1000
loconate
2014-06-16 20:16:00
show that there arent enough grasshoppers to fit in the 1000 * 1000 square
show that there arent enough grasshoppers to fit in the 1000 * 1000 square
joshualee2000
2014-06-16 20:16:00
we need 2,000,000 grasshoppers, but we only have 1,440,000
we need 2,000,000 grasshoppers, but we only have 1,440,000
ChilledLemonade
2014-06-16 20:16:00
calculate the area of both squares and see that the area of the bigger square is more than two times the area of the small square
calculate the area of both squares and see that the area of the bigger square is more than two times the area of the small square
MiraBernstein
2014-06-16 20:16:16
The number of grasshoppers that can reach the $1000 \times 1000$ square is less than $1200^2 = 1,440,000$, which is less than the 2 million that we needed. Thus part (b) is impossible.
The number of grasshoppers that can reach the $1000 \times 1000$ square is less than $1200^2 = 1,440,000$, which is less than the 2 million that we needed. Thus part (b) is impossible.
MiraBernstein
2014-06-16 20:16:26
General note: you can see in this problem how the techniques required to prove POSSIBILITY are very different from the techniques for proving IMPOSSIBILITY.
General note: you can see in this problem how the techniques required to prove POSSIBILITY are very different from the techniques for proving IMPOSSIBILITY.
MiraBernstein
2014-06-16 20:16:45
Possibility proofs are generally proofs by construction: the easiest way to prove that something can be done is to find a specific algorithm or procedure that gets it done. That's what we did in (a).
Possibility proofs are generally proofs by construction: the easiest way to prove that something can be done is to find a specific algorithm or procedure that gets it done. That's what we did in (a).
MiraBernstein
2014-06-16 20:17:01
Impossibility proofs don't deal with any specific algorithms. Rather, they look for some aspect of the problem that is going to create an insurmountable obstacle for ANY algorithm. For us, in part (b), the obstacle was getting enough grasshoppers to fill a region. We didn't have to think about which way the grasshoppers might jump; we just counted.
Impossibility proofs don't deal with any specific algorithms. Rather, they look for some aspect of the problem that is going to create an insurmountable obstacle for ANY algorithm. For us, in part (b), the obstacle was getting enough grasshoppers to fill a region. We didn't have to think about which way the grasshoppers might jump; we just counted.
MiraBernstein
2014-06-16 20:17:23
Often it takes a lot of thought and creativity (and practice) to find the little thread that you need to pull on, to get everything to unravel. But it's good at least to know that this is what you're looking for!
Often it takes a lot of thought and creativity (and practice) to find the little thread that you need to pull on, to get everything to unravel. But it's good at least to know that this is what you're looking for!
ukulifeguard
2014-06-16 20:17:29
How do we know this works for an arbitrarily large square?
How do we know this works for an arbitrarily large square?
MiraBernstein
2014-06-16 20:17:42
We don't need to know it works for an arbitrarily large square
We don't need to know it works for an arbitrarily large square
MiraBernstein
2014-06-16 20:18:07
Once we know that a 1000 x 1000 square already poses a problem, then we know it's impossible
Once we know that a 1000 x 1000 square already poses a problem, then we know it's impossible
MiraBernstein
2014-06-16 20:18:18
You only need one problem for the whole thing to fail
You only need one problem for the whole thing to fail
happiface
2014-06-16 20:18:23
as long as we have one counterexample, we're done
as long as we have one counterexample, we're done
MiraBernstein
2014-06-16 20:18:27
Exactly
Exactly
loconate
2014-06-16 20:18:37
Its like jenga
Its like jenga
MiraBernstein
2014-06-16 20:18:42
Hmm
Hmm
MiraBernstein
2014-06-16 20:18:53
OK, ready for Problem 2?
OK, ready for Problem 2?
MiraBernstein
2014-06-16 20:19:10
PROBLEM #2: Stephanie is an evil genius; she is building an army of robots and cyborgs. Every day, each of Stephanie's robots builds a copy of itself, while each of her cyborgs builds three new cyborgs and a robot. Once built, the cyborgs and robots never break or die.
$\qquad$ (a) If Stephanie wants to double her army each successive day (i.e. to have exactly twice as many robots and twice as many cyborgs as the day before), what ratio of robots and cyborgs should she start with? What if she wants to quadruple her army each day?
$\qquad$ (b) More generally, if Stephanie starts with $R$ robots and $C$ cyborgs on day 0, what will be the composition of her army after $n$ days? Prove your answer. (One way to approach this problem is to use part (a), but you're welcome to do it any way you like.)
PROBLEM #2: Stephanie is an evil genius; she is building an army of robots and cyborgs. Every day, each of Stephanie's robots builds a copy of itself, while each of her cyborgs builds three new cyborgs and a robot. Once built, the cyborgs and robots never break or die.
$\qquad$ (a) If Stephanie wants to double her army each successive day (i.e. to have exactly twice as many robots and twice as many cyborgs as the day before), what ratio of robots and cyborgs should she start with? What if she wants to quadruple her army each day?
$\qquad$ (b) More generally, if Stephanie starts with $R$ robots and $C$ cyborgs on day 0, what will be the composition of her army after $n$ days? Prove your answer. (One way to approach this problem is to use part (a), but you're welcome to do it any way you like.)
MiraBernstein
2014-06-16 20:19:35
This is a fairly standard recurrence problem, but I'm going to go through the solution for those who have never seen recurrences. (You can certainly solve this problem from scratch -- many people did.)
$\qquad$
First, let's define some variables. Let $R_t$ and $C_t$ be the number of robots and cyborgs in Stephanie's army on day $t$.
This is a fairly standard recurrence problem, but I'm going to go through the solution for those who have never seen recurrences. (You can certainly solve this problem from scratch -- many people did.)
$\qquad$
First, let's define some variables. Let $R_t$ and $C_t$ be the number of robots and cyborgs in Stephanie's army on day $t$.
MiraBernstein
2014-06-16 20:19:49
According to the statement of the problem, what is $R_{t+1}$ in terms of $R_t$ and $C_t$?
According to the statement of the problem, what is $R_{t+1}$ in terms of $R_t$ and $C_t$?
MiraBernstein
2014-06-16 20:20:30
(By the way, all people in the Mathcamp Qualifying Quiz are named for actual Mathcampers. I named this one for Stephanie because she was the least evil-genius-type person imaginable )
(By the way, all people in the Mathcamp Qualifying Quiz are named for actual Mathcampers. I named this one for Stephanie because she was the least evil-genius-type person imaginable
)
jhuang967
2014-06-16 20:20:55
$R_{t+1}=2R_t+C_t$
$R_{t+1}=2R_t+C_t$
NeilOnnsu
2014-06-16 20:20:55
R_t+1 = 2R_t + C_t
R_t+1 = 2R_t + C_t
distortedwalrus
2014-06-16 20:20:55
2R_t + C_t
2R_t + C_t
MiraBernstein
2014-06-16 20:21:10
The problem tells us that $R_{t+1} = 2R_t+C_t$. We have the $R_t$ robots that we had on day $t$, plus the $R_t$ copies they created, plus the $C_t$ new robots created by the cyborgs.
$\qquad$
And what's $C_{t+1}$?
The problem tells us that $R_{t+1} = 2R_t+C_t$. We have the $R_t$ robots that we had on day $t$, plus the $R_t$ copies they created, plus the $C_t$ new robots created by the cyborgs.
$\qquad$
And what's $C_{t+1}$?
64138luc
2014-06-16 20:21:40
4C_t
4C_t
ninjataco
2014-06-16 20:21:40
$4C_t$
$4C_t$
Sesquipedalian
2014-06-16 20:21:40
$C_{t+1} = 4C_t$
$C_{t+1} = 4C_t$
mjuvekar
2014-06-16 20:21:40
4C_t
4C_t
mathwizard888
2014-06-16 20:21:40
$C_{t+1}=4C_t$
$C_{t+1}=4C_t$
MiraBernstein
2014-06-16 20:21:52
$C_{t+1} = 4C_t$. There's no $R_t$ here, because the robots from day $t$ don't build any cyborgs.
$C_{t+1} = 4C_t$. There's no $R_t$ here, because the robots from day $t$ don't build any cyborgs.
MiraBernstein
2014-06-16 20:22:06
So, in part (a), let's say first that Stephanie wants her army to double each day. In other words, she wants
$R_{t+1} = 2R_t$ and $C_{t+1} = 2C_t$, for all $t$.
$\qquad$
But wait, we just saw that $R_{t+1} = 2R_t+C_t$ and $C_{t+1} = 4C_t$. What do we need to make this work?
So, in part (a), let's say first that Stephanie wants her army to double each day. In other words, she wants
$R_{t+1} = 2R_t$ and $C_{t+1} = 2C_t$, for all $t$.
$\qquad$
But wait, we just saw that $R_{t+1} = 2R_t+C_t$ and $C_{t+1} = 4C_t$. What do we need to make this work?
nisrus
2014-06-16 20:22:44
No cyborgs
No cyborgs
NeilOnnsu
2014-06-16 20:22:44
No cyborgs
No cyborgs
nebulagirl
2014-06-16 20:22:44
We can't have any cyborgs.
We can't have any cyborgs.
Philip7086
2014-06-16 20:22:44
C_t = 0
C_t = 0
johnnyc1729
2014-06-16 20:22:44
0 cyclops
0 cyclops
MiraBernstein
2014-06-16 20:22:52
Wait, where did the cyclops come from?
Wait, where did the cyclops come from?
MiraBernstein
2014-06-16 20:22:55
Anyway...
Anyway...
MiraBernstein
2014-06-16 20:23:05
If we have $C_t = 0$ for all $t$, then it works out perfectly. And it's easy to check that if Stephanie starts with no cyborgs on day $0$ ($C_0 = 0$), she will have $C_t = 0$ for all $t$.
$\qquad$
What about robots?
If we have $C_t = 0$ for all $t$, then it works out perfectly. And it's easy to check that if Stephanie starts with no cyborgs on day $0$ ($C_0 = 0$), she will have $C_t = 0$ for all $t$.
$\qquad$
What about robots?
MiraBernstein
2014-06-16 20:23:17
Any restriction on those?
Any restriction on those?
Pythonprogrammer
2014-06-16 20:23:28
Any number
Any number
genesis2
2014-06-16 20:23:28
doesn't matter
doesn't matter
imath34
2014-06-16 20:23:28
any #
any #
amwmath
2014-06-16 20:23:28
Any number.
Any number.
MiraBernstein
2014-06-16 20:23:37
Any value of $R_0$ works, since without cyborgs, the number of robots simply doubles each day. So Stephanie's army will double if and only if it has all robots and no cyborgs.
Any value of $R_0$ works, since without cyborgs, the number of robots simply doubles each day. So Stephanie's army will double if and only if it has all robots and no cyborgs.
MiraBernstein
2014-06-16 20:23:46
Now what if Stephanie wants to quadruple her army? In other words, now she wants
$R_{t+1} = 4R_t$ and $C_{t+1} = 4C_t$, for all $t$.
$\qquad$
Conveniently, the equation $C_{t+1} = 4C_t$ is already automatically satisfied. What other equation do we need to solve?
Now what if Stephanie wants to quadruple her army? In other words, now she wants
$R_{t+1} = 4R_t$ and $C_{t+1} = 4C_t$, for all $t$.
$\qquad$
Conveniently, the equation $C_{t+1} = 4C_t$ is already automatically satisfied. What other equation do we need to solve?
jhuang967
2014-06-16 20:24:38
$4R_t=2R_t+C_t$
$4R_t=2R_t+C_t$
ukulifeguard
2014-06-16 20:24:38
2R+C=4R
2R+C=4R
atmchallenge
2014-06-16 20:24:38
4R_t=2R_t+C_t
4R_t=2R_t+C_t
MiraBernstein
2014-06-16 20:24:51
Stephanie needs to have $2R_t+C_t = 4R_t$ for all $t$, which means that she needs $C_t = 2R_t$. In particular, she needs $C_0 = 2R_0$, i.e. she needs to start with twice as many cyborgs as robots.
Stephanie needs to have $2R_t+C_t = 4R_t$ for all $t$, which means that she needs $C_t = 2R_t$. In particular, she needs $C_0 = 2R_0$, i.e. she needs to start with twice as many cyborgs as robots.
MiraBernstein
2014-06-16 20:25:02
Technically, you also have to check that if she does start with $C_0 = 2R_0$, then she will always keep getting $C_t = 2R_t$ on each successive day. You can prove this by induction, but it's so obvious that we didn't mark you down if you didn't do it. :)
Technically, you also have to check that if she does start with $C_0 = 2R_0$, then she will always keep getting $C_t = 2R_t$ on each successive day. You can prove this by induction, but it's so obvious that we didn't mark you down if you didn't do it. :)
MiraBernstein
2014-06-16 20:25:30
That's it for (a), now for part (b). We want to find a formula for $C_t$ and $R_t$ in terms of $C_0$ and $R_0$. One of those is easy! Which one?
That's it for (a), now for part (b). We want to find a formula for $C_t$ and $R_t$ in terms of $C_0$ and $R_0$. One of those is easy! Which one?
happiface
2014-06-16 20:26:09
$C_t$
$C_t$
clarencechenct
2014-06-16 20:26:09
C_t
C_t
jhuang967
2014-06-16 20:26:09
$C_t=4^t \cdot C_0$
$C_t=4^t \cdot C_0$
happiface
2014-06-16 20:26:09
$C_t$ since only cyborgs make cyborgs
$C_t$ since only cyborgs make cyborgs
shipeiyang1708
2014-06-16 20:26:13
Ct=4tC0
Ct=4tC0
MiraBernstein
2014-06-16 20:26:24
The number of cyborgs simply quadruples each day, so we get $C_t = 4^t \cdot C_0$.
$\qquad$
The formula for $R_t$ looks more complicated. What should your first reaction be when you're asked to find a formula for a sequence and you're not sure how?
The number of cyborgs simply quadruples each day, so we get $C_t = 4^t \cdot C_0$.
$\qquad$
The formula for $R_t$ looks more complicated. What should your first reaction be when you're asked to find a formula for a sequence and you're not sure how?
ninjataco
2014-06-16 20:27:07
experiment with some terms
experiment with some terms
magital15
2014-06-16 20:27:07
write out the terms and look for a pattern
write out the terms and look for a pattern
mathwizard888
2014-06-16 20:27:07
find the first few and look for a pattern
find the first few and look for a pattern
MiraBernstein
2014-06-16 20:27:18
Yes -- compute the first few terms to get some idea of what's going on. This is always a good first step! In our case, you get:
$\qquad$
$t \qquad \;\;C_t \;\;\;\qquad R_t$
-----------------------------
$1 \qquad 4C_0 \; \qquad 2R_0 + C_0 $
$2 \qquad 16C_0 \qquad 4R_0 + 6C_0 $
$3 \qquad 32C_0 \qquad 8R_0 + 28C_0 $
$4 \qquad 64C_0 \qquad 16R_0 + 120 C_0 $
etc.
Yes -- compute the first few terms to get some idea of what's going on. This is always a good first step! In our case, you get:
$\qquad$
$t \qquad \;\;C_t \;\;\;\qquad R_t$
-----------------------------
$1 \qquad 4C_0 \; \qquad 2R_0 + C_0 $
$2 \qquad 16C_0 \qquad 4R_0 + 6C_0 $
$3 \qquad 32C_0 \qquad 8R_0 + 28C_0 $
$4 \qquad 64C_0 \qquad 16R_0 + 120 C_0 $
etc.
MiraBernstein
2014-06-16 20:27:50
It's pretty clear (and not surprising) that the coefficient of $R_0$ is doubling every time, so our formula for $R_t$ will be
$\qquad$
$\qquad R_t = 2^t R_0 + [?] C_0$.
$\qquad$
But what is $[?]$ -- can we find a pattern?
It's pretty clear (and not surprising) that the coefficient of $R_0$ is doubling every time, so our formula for $R_t$ will be
$\qquad$
$\qquad R_t = 2^t R_0 + [?] C_0$.
$\qquad$
But what is $[?]$ -- can we find a pattern?
NeilOnnsu
2014-06-16 20:28:56
1*1, 2*3, 4*7, 8*15... ==> 1*(2-1), 2*(4-1), 4*(8-1), 8*(16-1)
1*1, 2*3, 4*7, 8*15... ==> 1*(2-1), 2*(4-1), 4*(8-1), 8*(16-1)
chezbgone2
2014-06-16 20:28:56
we can divide R_t by 2^t, to get 2^(t+1)-1
we can divide R_t by 2^t, to get 2^(t+1)-1
MiraBernstein
2014-06-16 20:29:09
Here's what I did. The coefficients of $C_0$ look kind of like odd powers of 2 (i.e. $2^1, 2^3, 2^5,$ etc.) but a little smaller.
$\qquad$
If you check to see how much smaller, the pattern is easy to see. You end up with
$\qquad$
$\qquad R_t = 2^t R_0 + (2^{2t-1} - 2^{t-1}) C_0$.
$\qquad$
(This is equivalent to all your answers above.)
Here's what I did. The coefficients of $C_0$ look kind of like odd powers of 2 (i.e. $2^1, 2^3, 2^5,$ etc.) but a little smaller.
$\qquad$
If you check to see how much smaller, the pattern is easy to see. You end up with
$\qquad$
$\qquad R_t = 2^t R_0 + (2^{2t-1} - 2^{t-1}) C_0$.
$\qquad$
(This is equivalent to all your answers above.)
MiraBernstein
2014-06-16 20:29:30
(At least I think it's equivalent)
(At least I think it's equivalent)
64138luc
2014-06-16 20:29:47
Don't we need induction to prove it?
Don't we need induction to prove it?
MiraBernstein
2014-06-16 20:29:53
Yes!
Yes!
MiraBernstein
2014-06-16 20:30:05
In many math problems, the first step is seeing the pattern -- like solving a puzzle. But once you've figured it out, you still have to prove that this pattern extends forever! After all, your guess was only based on the first few terms of the sequence.
In many math problems, the first step is seeing the pattern -- like solving a puzzle. But once you've figured it out, you still have to prove that this pattern extends forever! After all, your guess was only based on the first few terms of the sequence.
ukulifeguard
2014-06-16 20:30:19
What's induction?
What's induction?
MiraBernstein
2014-06-16 20:30:41
I'm sorry, I don't have time to explain it right now, but you might be able to figure it out from watching what's about to happen
I'm sorry, I don't have time to explain it right now, but you might be able to figure it out from watching what's about to happen
MiraBernstein
2014-06-16 20:30:53
And I highly recommend that if you don't know what induction is, you look it up!
And I highly recommend that if you don't know what induction is, you look it up!
MiraBernstein
2014-06-16 20:31:05
This kind of problem is perfect for induction, because it gives you the formula for going from one term of the sequence to the next: $R_{t+1} = 2R_t + C_t$. That's the inductive step handed to you on a silver platter!
$\qquad$
But first, what's the base case?
This kind of problem is perfect for induction, because it gives you the formula for going from one term of the sequence to the next: $R_{t+1} = 2R_t + C_t$. That's the inductive step handed to you on a silver platter!
$\qquad$
But first, what's the base case?
MiraBernstein
2014-06-16 20:31:45
People are saying t=0, but the formula actually doesn't work for that one!
People are saying t=0, but the formula actually doesn't work for that one!
swamih
2014-06-16 20:31:57
$C_t=1$
$C_t=1$
Moonlight243
2014-06-16 20:31:57
t=1?
t=1?
chessderek
2014-06-16 20:31:57
t=1
t=1
justindong
2014-06-16 20:31:57
t=1
t=1
MiraBernstein
2014-06-16 20:32:08
For the base case, we need to check that
$\qquad$
$\qquad R_1 = 2^1 R_0 + (2^1 - 2^0) C_0$.
$\qquad$
Indeed, according to our table, $R_1 = 2R_0 + C_0$, so it works.
$\qquad$
(Of course, it was bound to work, since $R_1$ was one of the cases that we used to guess the pattern in the first place. But you should still spell it out in your proof.)
For the base case, we need to check that
$\qquad$
$\qquad R_1 = 2^1 R_0 + (2^1 - 2^0) C_0$.
$\qquad$
Indeed, according to our table, $R_1 = 2R_0 + C_0$, so it works.
$\qquad$
(Of course, it was bound to work, since $R_1$ was one of the cases that we used to guess the pattern in the first place. But you should still spell it out in your proof.)
MiraBernstein
2014-06-16 20:32:29
Now for the inductive step, we assume that we have already proved that
$\qquad$
$\qquad R_t = 2^t R_0 + (2^{2t-1} - 2^{t-1}) C_0$
$\qquad$
for some specific $t$. What do we need to show?
Now for the inductive step, we assume that we have already proved that
$\qquad$
$\qquad R_t = 2^t R_0 + (2^{2t-1} - 2^{t-1}) C_0$
$\qquad$
for some specific $t$. What do we need to show?
ninjataco
2014-06-16 20:33:21
that it's true for $t+1$
that it's true for $t+1$
joshualee2000
2014-06-16 20:33:21
that it works for t+1
that it works for t+1
Philip7086
2014-06-16 20:33:21
that it is right for t+ 1
that it is right for t+ 1
6stars
2014-06-16 20:33:21
This works for k = t + 1
This works for k = t + 1
MiraBernstein
2014-06-16 20:33:30
We need to show that
$\qquad$
$\qquad R_{t+1} = 2^{t+1} R_0 + (2^{2(t+1)-1} - 2^{(t+1)-1}) C_0$.
$\qquad$
What do we know about $R_{t+1}$ from the problem statement?
We need to show that
$\qquad$
$\qquad R_{t+1} = 2^{t+1} R_0 + (2^{2(t+1)-1} - 2^{(t+1)-1}) C_0$.
$\qquad$
What do we know about $R_{t+1}$ from the problem statement?
Pythonprogrammer
2014-06-16 20:34:29
R_T+1=2*R_T+C_T
R_T+1=2*R_T+C_T
swamih
2014-06-16 20:34:29
$R_{t+1}=2R_t+C_t$
$R_{t+1}=2R_t+C_t$
mjuvekar
2014-06-16 20:34:29
R_t+1 = 2R_t + C_t
R_t+1 = 2R_t + C_t
MiraBernstein
2014-06-16 20:34:44
We are given that $R_{t+1} = 2R_t + C_t$. So we just plug in $R_t$ (which the inductive assumption lets us pretend we already know) and $C_t$ (which we actually already know) and do some algebra:
$\qquad$
$R_{t+1} = 2R_t + C_t$ (given)
We are given that $R_{t+1} = 2R_t + C_t$. So we just plug in $R_t$ (which the inductive assumption lets us pretend we already know) and $C_t$ (which we actually already know) and do some algebra:
$\qquad$
$R_{t+1} = 2R_t + C_t$ (given)
MiraBernstein
2014-06-16 20:34:52
$\qquad$
$\qquad\; = 2(2^t R_0 + (2^{2t-1} - 2^{t-1}) C_0) + 4^t C_0$ (plugging in $R_t$)
$\qquad$
$\qquad\; = 2(2^t R_0 + (2^{2t-1} - 2^{t-1}) C_0) + 4^t C_0$ (plugging in $R_t$)
MiraBernstein
2014-06-16 20:35:01
$\qquad\; = \left[ 2^{t+1} R_0 + (2^{2t} - 2^t)C_0\right] + 2^{2t}C_0$ (simplifying)
$\qquad\; = \left[ 2^{t+1} R_0 + (2^{2t} - 2^t)C_0\right] + 2^{2t}C_0$ (simplifying)
MiraBernstein
2014-06-16 20:35:11
$\qquad\; = 2^{t+1} R_0 + (2^{2t+1} - 2^t) C_0 \qquad$ (grouping terms)
$\qquad\; = 2^{t+1} R_0 + (2^{2t+1} - 2^t) C_0 \qquad$ (grouping terms)
MiraBernstein
2014-06-16 20:35:45
That's probably too much algebra to digest on the spot, but trust me, it works
That's probably too much algebra to digest on the spot, but trust me, it works
MiraBernstein
2014-06-16 20:36:03
And it is exactly what our formula for $R_{t+1}$ tells us. Thus the formula works for $t=1$, and if it works for $t$ then it works for $t+1$. By the magic of induction, we're done.
$\qquad$
Questions?
And it is exactly what our formula for $R_{t+1}$ tells us. Thus the formula works for $t=1$, and if it works for $t$ then it works for $t+1$. By the magic of induction, we're done.
$\qquad$
Questions?
amwmath
2014-06-16 20:36:21
"People are saying t=0, but the formula actually doesn't work for that one!" Double check that?
"People are saying t=0, but the formula actually doesn't work for that one!" Double check that?
MiraBernstein
2014-06-16 20:36:39
Yeah, a bunch of people objected to this. I thyink you're right, it does work. Sorry.
Yeah, a bunch of people objected to this. I thyink you're right, it does work. Sorry.
happiface
2014-06-16 20:36:46
next problem!
next problem!
MiraBernstein
2014-06-16 20:36:55
Oh wait, not yet!
Oh wait, not yet!
MiraBernstein
2014-06-16 20:37:01
Now, you might say: "I don't like problem-solving methods that depend on me just figuring out a pattern. What if I can't spot the pattern? And what if I'm interested in WHY the pattern is what it is?" So here is a better way to solve this problem, which hints at something deeper that's going on.
Now, you might say: "I don't like problem-solving methods that depend on me just figuring out a pattern. What if I can't spot the pattern? And what if I'm interested in WHY the pattern is what it is?" So here is a better way to solve this problem, which hints at something deeper that's going on.
MiraBernstein
2014-06-16 20:37:16
Think back to part (a): we know that an army composed only of robots always doubles, and an army with twice as many cyborgs as robots always quadruples. Now neither of these might be true of Stephanie's army, but can we split it into two sub-armies -- a doubling one and a quadrupling one? How big would these armies be?
Think back to part (a): we know that an army composed only of robots always doubles, and an army with twice as many cyborgs as robots always quadruples. Now neither of these might be true of Stephanie's army, but can we split it into two sub-armies -- a doubling one and a quadrupling one? How big would these armies be?
MiraBernstein
2014-06-16 20:38:08
I mean, how big would they be to start with?
I mean, how big would they be to start with?
MiraBernstein
2014-06-16 20:38:51
If she starts with $R_O$ robots and $C_0$ cyborgs, how should she split them up into the two armies?
If she starts with $R_O$ robots and $C_0$ cyborgs, how should she split them up into the two armies?
MiraBernstein
2014-06-16 20:39:23
(Sorry didn't mean to pass those yet)
(Sorry didn't mean to pass those yet)
Technik
2014-06-16 20:40:19
for the doubling one have robots
for the doubling one have robots
Technik
2014-06-16 20:40:19
for quadrupling, have twice as many cyborgs as robots
for quadrupling, have twice as many cyborgs as robots
Philip7086
2014-06-16 20:40:19
no. of cyborgs + 1/2 as many robots and the other remaining robots
no. of cyborgs + 1/2 as many robots and the other remaining robots
nebulagirl
2014-06-16 20:40:22
The quadrupling one would take all the cyborgs and C0/2 robots. The extra robots are in the doubling army.
The quadrupling one would take all the cyborgs and C0/2 robots. The extra robots are in the doubling army.
NeilOnnsu
2014-06-16 20:40:29
C cyborgs and C/2 robots, then the left over robots in the other army. Of course, you'll have to account for odd numbers of cyborgs and not enough robots
C cyborgs and C/2 robots, then the left over robots in the other army. Of course, you'll have to account for odd numbers of cyborgs and not enough robots
MiraBernstein
2014-06-16 20:40:36
All the cyborgs have to be in the quadrupling army, so it must have $C_0$ cyborgs and thus $\frac{C_0}2$ robots. The doubling army will have the remaining $R_0 - \frac{C_0}2$ robots and no cyborgs.
All the cyborgs have to be in the quadrupling army, so it must have $C_0$ cyborgs and thus $\frac{C_0}2$ robots. The doubling army will have the remaining $R_0 - \frac{C_0}2$ robots and no cyborgs.
MiraBernstein
2014-06-16 20:41:07
Good point about off numbers of cyborgs, but it turns out not to matter. You can do this with frcational cyborgs and robots!
Good point about off numbers of cyborgs, but it turns out not to matter. You can do this with frcational cyborgs and robots!
MiraBernstein
2014-06-16 20:41:27
Now once again, the number of cyborgs on day $t$ is easy: they're all in the quadrupling army, so $C_t = 4^t C_0$. But what about $R_t$?
Now once again, the number of cyborgs on day $t$ is easy: they're all in the quadrupling army, so $C_t = 4^t C_0$. But what about $R_t$?
NeilOnnsu
2014-06-16 20:41:46
And negative robots?
And negative robots?
MiraBernstein
2014-06-16 20:42:21
Yes, that too! The math works anyway.
Yes, that too! The math works anyway.
shipeiyang1708
2014-06-16 20:42:28
you cant have a negative of a physical object
you cant have a negative of a physical object
MiraBernstein
2014-06-16 20:42:57
But this is a math problem, so it's OK. In the end, all the answers will turn out to be whole positive numbers!
But this is a math problem, so it's OK. In the end, all the answers will turn out to be whole positive numbers!
MiraBernstein
2014-06-16 20:43:17
We asked about $R_t$
We asked about $R_t$
MiraBernstein
2014-06-16 20:43:34
$R^t = 2^t \times$ [original # of robots in the doubling army]
$\qquad$
$\qquad +\;\; 4^t\times$[original # of robots in the quadrupling army].
$\qquad$
$R^t = 2^t \times$ [original # of robots in the doubling army]
$\qquad$
$\qquad +\;\; 4^t\times$[original # of robots in the quadrupling army].
$\qquad$
NeilOnnsu
2014-06-16 20:43:55
R_t = 4^t * C_0 /2 + 2^t *(R_0 - C_0 /2)
R_t = 4^t * C_0 /2 + 2^t *(R_0 - C_0 /2)
MiraBernstein
2014-06-16 20:44:13
From here, if you do the algebra, you get the same formula we got before, but you don't need the induction proof: we didn't just guess this formula, we derived it rigorously. Cool, huh?
From here, if you do the algebra, you get the same formula we got before, but you don't need the induction proof: we didn't just guess this formula, we derived it rigorously. Cool, huh?
distortedwalrus
2014-06-16 20:44:18
did anyone submit a solution like this?
did anyone submit a solution like this?
MiraBernstein
2014-06-16 20:44:28
yes, because...
yes, because...
MiraBernstein
2014-06-16 20:44:35
Those of you who have seen some linear algebra, what does this remind you of?
Those of you who have seen some linear algebra, what does this remind you of?
clarencechenct
2014-06-16 20:45:09
oh yeah you notice how the closed form of these formulas is based on sums/differences, aren't all linear recursions like that?
oh yeah you notice how the closed form of these formulas is based on sums/differences, aren't all linear recursions like that?
MiraBernstein
2014-06-16 20:45:23
Yes, it should remind you of recursion (because that's what this is)
Yes, it should remind you of recursion (because that's what this is)
MiraBernstein
2014-06-16 20:45:29
but that's not from linear algebra
but that's not from linear algebra
MiraBernstein
2014-06-16 20:45:43
Looks like not a lot of people have had linear algebra, which is fine
Looks like not a lot of people have had linear algebra, which is fine
MiraBernstein
2014-06-16 20:46:02
This is very closely related to eigenvalues and eigenvectors in linear algebra
This is very closely related to eigenvalues and eigenvectors in linear algebra
MiraBernstein
2014-06-16 20:46:17
OK, if you're totally confused, don't worry about it
OK, if you're totally confused, don't worry about it
MiraBernstein
2014-06-16 20:46:54
I just wanted to show you this cool trick; if you're still bothered by negative fractional robots, look over it later and convince yourself that it's OK
I just wanted to show you this cool trick; if you're still bothered by negative fractional robots, look over it later and convince yourself that it's OK
MiraBernstein
2014-06-16 20:47:08
And you don't have to have taken linear algebra to solve the problem
And you don't have to have taken linear algebra to solve the problem
MiraBernstein
2014-06-16 20:47:35
We saw an elementary solution at the beginning that required no background
We saw an elementary solution at the beginning that required no background
isanimath
2014-06-16 20:47:42
question, what level of math are we doing in this math jam?
question, what level of math are we doing in this math jam?
MiraBernstein
2014-06-16 20:47:53
Many different levels, for different levels of audience
Many different levels, for different levels of audience
MiraBernstein
2014-06-16 20:48:01
OK, going on to #3...
OK, going on to #3...
MiraBernstein
2014-06-16 20:48:22
PROBLEM #3: Let $P_n$ be a regular $n$-sided polygon inscribed in a circle of radius 1. What is the minimum number of circles of radius $1/2$ required to cover $P_n$ completely? (Both $P_n$ and the circles in this problem include the boundary as well as the interior.)
PROBLEM #3: Let $P_n$ be a regular $n$-sided polygon inscribed in a circle of radius 1. What is the minimum number of circles of radius $1/2$ required to cover $P_n$ completely? (Both $P_n$ and the circles in this problem include the boundary as well as the interior.)
MiraBernstein
2014-06-16 20:48:53
So, presumably, when you see a problem like this, you start by looking for nice geometric constructions that show how to cover a regular $n$-gon with circles. People who worked on this problem: in the first geometric construction that you found, how many circles did you use to cover $P_n$?
So, presumably, when you see a problem like this, you start by looking for nice geometric constructions that show how to cover a regular $n$-gon with circles. People who worked on this problem: in the first geometric construction that you found, how many circles did you use to cover $P_n$?
niraekjs
2014-06-16 20:49:45
7
7
jhuang967
2014-06-16 20:49:45
$n$ circles. :P
$n$ circles. :P
loconate
2014-06-16 20:49:45
n circles
n circles
dylanxu1213
2014-06-16 20:49:45
n
n
gedt11
2014-06-16 20:49:45
7
7
MiraBernstein
2014-06-16 20:50:01
There are two geometric constructions relevant to this problem, both of which work for all $n$: the first shows how to cover $P_n$ with 7 circles and the second shows how to cover $P_n$ with $n$ circles. Let's look at each of these in turn.
There are two geometric constructions relevant to this problem, both of which work for all $n$: the first shows how to cover $P_n$ with 7 circles and the second shows how to cover $P_n$ with $n$ circles. Let's look at each of these in turn.
MiraBernstein
2014-06-16 20:51:01
How do you prove that you can cover $P_n$ with 7 circles of radius $1/2$ for all $n$?
How do you prove that you can cover $P_n$ with 7 circles of radius $1/2$ for all $n$?
gedt11
2014-06-16 20:51:37
7circles can cover a big circle
7circles can cover a big circle
RavenclawPrefect
2014-06-16 20:51:37
Because you can cover an entire circle with it
Because you can cover an entire circle with it
Obyeag
2014-06-16 20:51:37
it covers one with an infinite number of faces, aka a circle
it covers one with an infinite number of faces, aka a circle
amwmath
2014-06-16 20:51:42
MiraBernstein
2014-06-16 20:51:51
Wow, someone did my job for me!!
Wow, someone did my job for me!!
MiraBernstein
2014-06-16 20:52:05
If we can show how to cover the entire unit circle with 7 circles of radius 1/2, then surely any polygon inscribed in the unit circle will also be covered.
$\qquad$
Here is a diagram that shows how you can cover the unit circle (black) with 7 circles of radius 1/2 (blue):
http://www.mathcamp.org/2014/quiz/seven_circles.jpg
If we can show how to cover the entire unit circle with 7 circles of radius 1/2, then surely any polygon inscribed in the unit circle will also be covered.
$\qquad$
Here is a diagram that shows how you can cover the unit circle (black) with 7 circles of radius 1/2 (blue):
http://www.mathcamp.org/2014/quiz/seven_circles.jpg
MiraBernstein
2014-06-16 20:52:26
Technically, you need to prove that the diagram is accurate and the whole unit circle is really covered. This involves some very easy elementary geometry -- lots of equilateral triangles and $60^\circ$ angles -- so I won't go through it. We basically gave full credit to people who drew this picture and labeled it clearly, even if they didn't say anything more.
Technically, you need to prove that the diagram is accurate and the whole unit circle is really covered. This involves some very easy elementary geometry -- lots of equilateral triangles and $60^\circ$ angles -- so I won't go through it. We basically gave full credit to people who drew this picture and labeled it clearly, even if they didn't say anything more.
MiraBernstein
2014-06-16 20:53:06
Are we OK that 7 circles cover any $P_n$?
Are we OK that 7 circles cover any $P_n$?
MiraBernstein
2014-06-16 20:53:24
Now here is a diagram showing that you can cover $P_n$ with $n$ circles of radius $1/2$:
http://www.mathcamp.org/2014/quiz/n_circles.jpg
Now here is a diagram showing that you can cover $P_n$ with $n$ circles of radius $1/2$:
http://www.mathcamp.org/2014/quiz/n_circles.jpg
MiraBernstein
2014-06-16 20:53:45
Here the picture is not quite as self-explanatory: it's not immediately obvious that the point $D$ where circle $Q$ intersects segment $AB$ really is the midpoint of $AB$(and same for all the other circles). Any suggestions for how to prove this?
Here the picture is not quite as self-explanatory: it's not immediately obvious that the point $D$ where circle $Q$ intersects segment $AB$ really is the midpoint of $AB$(and same for all the other circles). Any suggestions for how to prove this?
Sesquipedalian
2014-06-16 20:54:47
Let $p$ be the circle with radius 1 in which the polygons are described, and $P$ be its center. Construct radius $PR$ of $p$ with midpoint $Q$, and define circle $q$ as the one with midpoint $Q$ and diameter $PR$. Clearly, $q$ has a radius of $\frac{1}{2}$. Let $S$ be another point on the circumference of $p$ and $T$ be the midpoint of chord $RS$. Since chords are perpendicular to radii, $RS \perp
Let $p$ be the circle with radius 1 in which the polygons are described, and $P$ be its center. Construct radius $PR$ of $p$ with midpoint $Q$, and define circle $q$ as the one with midpoint $Q$ and diameter $PR$. Clearly, $q$ has a radius of $\frac{1}{2}$. Let $S$ be another point on the circumference of $p$ and $T$ be the midpoint of chord $RS$. Since chords are perpendicular to radii, $RS \perp
MiraBernstein
2014-06-16 20:55:32
I'm getting lots of good suggestions -- let me summarize two ways
I'm getting lots of good suggestions -- let me summarize two ways
MiraBernstein
2014-06-16 20:55:44
One way to prove it: Since $AC$ is the diameter of circle $Q$, $\angle ADC$ must be a right angle, so $AD$ is the perpendicular bisector of $AB$.
One way to prove it: Since $AC$ is the diameter of circle $Q$, $\angle ADC$ must be a right angle, so $AD$ is the perpendicular bisector of $AB$.
MiraBernstein
2014-06-16 20:56:27
Another way to prove it: let $R_n$ be a copy of $P_n$ scaled by a factor of $1/2$ and inscribed in circle $Q$. Then $AD$ is a side of $R_n$, so it must be half the length of $AB$. Thus $D$ is the midpoint of $AB$.
$\qquad$
Either way, it's clear from this that we have a valid covering of $P_n$ with $n$ circles of radius $1/2$.
Another way to prove it: let $R_n$ be a copy of $P_n$ scaled by a factor of $1/2$ and inscribed in circle $Q$. Then $AD$ is a side of $R_n$, so it must be half the length of $AB$. Thus $D$ is the midpoint of $AB$.
$\qquad$
Either way, it's clear from this that we have a valid covering of $P_n$ with $n$ circles of radius $1/2$.
MiraBernstein
2014-06-16 20:57:46
OK, let's take stock of where we are in solving the problem.
Let $f(n)$ to be the minimal number of circles of radius $1/2$ required to cover $P_n$. This is the quantity we are trying to find. What have we proved about $f(n)$ so far?
OK, let's take stock of where we are in solving the problem.
Let $f(n)$ to be the minimal number of circles of radius $1/2$ required to cover $P_n$. This is the quantity we are trying to find. What have we proved about $f(n)$ so far?
amwmath
2014-06-16 20:59:24
We have an upper bound.
We have an upper bound.
gedt11
2014-06-16 20:59:24
f(n)<=min(7,n)
f(n)<=min(7,n)
codyj
2014-06-16 20:59:24
$f(n)\le n$
$f(n)\le n$
clarencechenct
2014-06-16 20:59:24
upper bound is 7
upper bound is 7
MiraBernstein
2014-06-16 20:59:42
Just because we can show how to cover $P_n$ with $n$ circles, we cannot conclude that $f(n) = n$. We don't know that $n$ is the MINIMAL number that works. (In fact, for $n>7$, we know that it isn't!)
$\qquad$
All we can conclude from our construction is that the true minimum, $f(n)$, is either $n$ or smaller. In other words, what we have proved so far are two inequalities: $f(n)\leq n$ and $f(n) \leq 7$, for all $n$.
Just because we can show how to cover $P_n$ with $n$ circles, we cannot conclude that $f(n) = n$. We don't know that $n$ is the MINIMAL number that works. (In fact, for $n>7$, we know that it isn't!)
$\qquad$
All we can conclude from our construction is that the true minimum, $f(n)$, is either $n$ or smaller. In other words, what we have proved so far are two inequalities: $f(n)\leq n$ and $f(n) \leq 7$, for all $n$.
MiraBernstein
2014-06-16 21:00:13
Based on this, what is a reasonable CONJECTURE for the final answer to the problem?
Based on this, what is a reasonable CONJECTURE for the final answer to the problem?
NeilOnnsu
2014-06-16 21:00:55
f(n) = n if n <= 7 and 7 otherwise
f(n) = n if n <= 7 and 7 otherwise
jhuang967
2014-06-16 21:00:55
$f(n) = min(n,7)$
$f(n) = min(n,7)$
mjuvekar
2014-06-16 21:00:55
f(n) = min(7, n)
f(n) = min(7, n)
gedt11
2014-06-16 21:00:55
f(n)=min(7,n)
f(n)=min(7,n)
RavenclawPrefect
2014-06-16 21:00:55
That f(n) is n for n<7, and 7 for n>7.
That f(n) is n for n<7, and 7 for n>7.
MiraBernstein
2014-06-16 21:01:07
It is reasonable to conjecture that $f(n)$ is either $n$ or $7$, whichever is smaller. In other words, we conjecture that
$\qquad$
$\qquad f(n)=n$ for $n \leq 6$ and $f(n)=7$ for $n\geq 7$.
It is reasonable to conjecture that $f(n)$ is either $n$ or $7$, whichever is smaller. In other words, we conjecture that
$\qquad$
$\qquad f(n)=n$ for $n \leq 6$ and $f(n)=7$ for $n\geq 7$.
MiraBernstein
2014-06-16 21:01:23
To prove this, we need to show that it is IMPOSSIBLE to cover $P_n$ with fewer than $n$ circles if $n\leq 6$ and with fewer than $7$ circles if $n\geq 7$. So the overall logical structure of our proof will have four parts:
$\qquad$ (a) Proving that $f(n)\leq n$ for all $n$;
$\qquad$ (b) Proving that $f(n)\leq 7$ for all $n$;
$\qquad$ (c) Proving that $f(n)\geq n$ for $n\leq 6$;
$\qquad$ (d) Proving that $f(n)\geq 7$ for $n\geq 7$
To prove this, we need to show that it is IMPOSSIBLE to cover $P_n$ with fewer than $n$ circles if $n\leq 6$ and with fewer than $7$ circles if $n\geq 7$. So the overall logical structure of our proof will have four parts:
$\qquad$ (a) Proving that $f(n)\leq n$ for all $n$;
$\qquad$ (b) Proving that $f(n)\leq 7$ for all $n$;
$\qquad$ (c) Proving that $f(n)\geq n$ for $n\leq 6$;
$\qquad$ (d) Proving that $f(n)\geq 7$ for $n\geq 7$
MiraBernstein
2014-06-16 21:01:42
We have already proved (a) and (b) using the two geometric constructions. The proofs of (c) and (d) are impossibility proofs, and we haven't done them yet. Remember, impossibility proofs work totally differently from possibility proofs, so we'll need a whole new approach!
$\qquad$
Before we start, any questions on the structure of the argument and why we need four separate proofs?
We have already proved (a) and (b) using the two geometric constructions. The proofs of (c) and (d) are impossibility proofs, and we haven't done them yet. Remember, impossibility proofs work totally differently from possibility proofs, so we'll need a whole new approach!
$\qquad$
Before we start, any questions on the structure of the argument and why we need four separate proofs?
MiraBernstein
2014-06-16 21:02:20
OK, let's prove (c). For $n=3,4,5$, it's pretty straightforward. What can we say about the vertices of $P_n$?
OK, let's prove (c). For $n=3,4,5$, it's pretty straightforward. What can we say about the vertices of $P_n$?
MiraBernstein
2014-06-16 21:02:52
(in c, we're proving that you can't cover $P_n$ with fewer than $n$ circles when $n\leq 6$
(in c, we're proving that you can't cover $P_n$ with fewer than $n$ circles when $n\leq 6$
amwmath
2014-06-16 21:03:27
For pentagons and smaller, no circle can cover two vertices.
For pentagons and smaller, no circle can cover two vertices.
jhuang967
2014-06-16 21:03:27
More than 1 unit apart.
More than 1 unit apart.
numbersandnumbers
2014-06-16 21:03:27
more than 1 apart
more than 1 apart
NeilOnnsu
2014-06-16 21:03:27
You can't cover two of them with one circle
You can't cover two of them with one circle
distortedwalrus
2014-06-16 21:03:27
you can't cover more than one vertex of P_n with one circle for n=3, 4, 5
you can't cover more than one vertex of P_n with one circle for n=3, 4, 5
MiraBernstein
2014-06-16 21:03:49
For $n\leq 5$, the distance between any two vertices of $P_n$ is greater than 1, so each circle of radius $1/2$ can contain at most one vertex. Thus we need at least $n$ circles to cover $P_n$, i.e. $f(n)\geq n$ for $n\leq 5$.
For $n\leq 5$, the distance between any two vertices of $P_n$ is greater than 1, so each circle of radius $1/2$ can contain at most one vertex. Thus we need at least $n$ circles to cover $P_n$, i.e. $f(n)\geq n$ for $n\leq 5$.
MiraBernstein
2014-06-16 21:04:02
Why doesn't this argument work for $n=6$?
Why doesn't this argument work for $n=6$?
niraekjs
2014-06-16 21:04:40
for n =6, they are exactly 1 unit apart.
for n =6, they are exactly 1 unit apart.
amwmath
2014-06-16 21:04:40
They are exactly a distance of 1 apart.
They are exactly a distance of 1 apart.
happiface
2014-06-16 21:04:40
because the side length is $1$
because the side length is $1$
danusv
2014-06-16 21:04:40
Because then the side length is 1 and it can exactly cover two vertices
Because then the side length is 1 and it can exactly cover two vertices
jhuang967
2014-06-16 21:04:40
Since the vertices are 1 unit apart, 1 circle can cover two vertices.
Since the vertices are 1 unit apart, 1 circle can cover two vertices.
MiraBernstein
2014-06-16 21:04:44
The sides of $P_6$ have length exactly 1, so it IS possible to cover two vertices of $P_6$ with one circle. We need to look at something other than vertices. Let's try edges.
The sides of $P_6$ have length exactly 1, so it IS possible to cover two vertices of $P_6$ with one circle. We need to look at something other than vertices. Let's try edges.
MiraBernstein
2014-06-16 21:04:59
We will argue by contradiction. Suppose we were able to cover all the edges of $P_6$ with 5 circles of radius 1/2. Let's say we position $k$ of these circles so that each of them covers one whole edge (and two vertices). Now we have $5-k$ circles to cover the other $6-k$ edges.
$\qquad$
Let's call the intersection of one of these edges with one of these circles an "edge-circle segment". What is the minimum number of edge-circle segments required to cover our $6-k$ edges?
We will argue by contradiction. Suppose we were able to cover all the edges of $P_6$ with 5 circles of radius 1/2. Let's say we position $k$ of these circles so that each of them covers one whole edge (and two vertices). Now we have $5-k$ circles to cover the other $6-k$ edges.
$\qquad$
Let's call the intersection of one of these edges with one of these circles an "edge-circle segment". What is the minimum number of edge-circle segments required to cover our $6-k$ edges?
MiraBernstein
2014-06-16 21:06:38
I think I've managed to confuse you guys
I think I've managed to confuse you guys
MiraBernstein
2014-06-16 21:07:16
If two circles are covering an edge, then that's two edg-circle segments on that edge
If two circles are covering an edge, then that's two edg-circle segments on that edge
MiraBernstein
2014-06-16 21:07:45
Each of the $6-k$ edges requires at least 2 circles to cover it (since we've already excluded all the edges entirely contained in one circle). Thus each edge contains at least two edge-circle segments of non-zero length, and the total number of such segments is at least $2(6-k)$.
Each of the $6-k$ edges requires at least 2 circles to cover it (since we've already excluded all the edges entirely contained in one circle). Thus each edge contains at least two edge-circle segments of non-zero length, and the total number of such segments is at least $2(6-k)$.
jhuang967
2014-06-16 21:08:11
Diagram, please?
Diagram, please?
MiraBernstein
2014-06-16 21:08:21
Sorry, didn't make one
Sorry, didn't make one
MiraBernstein
2014-06-16 21:09:18
the total number of edge-circle segments is at least $2(6-k)$. Why is this a problem?
the total number of edge-circle segments is at least $2(6-k)$. Why is this a problem?
happiface
2014-06-16 21:09:30
hence why i said 12-2k
hence why i said 12-2k
jhuang967
2014-06-16 21:09:30
Oh - edge-circle segments are LINE segments (silly me).
Oh - edge-circle segments are LINE segments (silly me).
MiraBernstein
2014-06-16 21:09:52
Yes, they are line segments.
Yes, they are line segments.
MiraBernstein
2014-06-16 21:10:18
So we've got 2(6-k) of them... and 5-k circles... why is that bad?
So we've got 2(6-k) of them... and 5-k circles... why is that bad?
happiface
2014-06-16 21:10:58
each of the 5-k circles can only gives us two edge circle segments
each of the 5-k circles can only gives us two edge circle segments
RavenclawPrefect
2014-06-16 21:10:58
A circle can only create 2 edge-cricle segments, and 10-2k is smaller than 12-2k
A circle can only create 2 edge-cricle segments, and 10-2k is smaller than 12-2k
distortedwalrus
2014-06-16 21:11:03
5-k circles gives at most 10-2k segments
5-k circles gives at most 10-2k segments
MiraBernstein
2014-06-16 21:11:18
Each of the $5-k$ circles can contain at most two edge segments. (A circle of radius $1/2$ cannot contain segments on three different edges of $P_n$, since points on non-adjacent edges are more than $1$ apart.)
$\qquad$
Thus we can have at most $2(5-k)$ edge segments, which is too few. This proves that $P_6$ cannot be covered with 5 circles of radius 1/2.
Each of the $5-k$ circles can contain at most two edge segments. (A circle of radius $1/2$ cannot contain segments on three different edges of $P_n$, since points on non-adjacent edges are more than $1$ apart.)
$\qquad$
Thus we can have at most $2(5-k)$ edge segments, which is too few. This proves that $P_6$ cannot be covered with 5 circles of radius 1/2.
MiraBernstein
2014-06-16 21:11:30
This concludes the proof of part (c): $f(n)\geq n$ for $n\leq 6$.
This concludes the proof of part (c): $f(n)\geq n$ for $n\leq 6$.
MiraBernstein
2014-06-16 21:11:47
And now I have an embarrassing confession to make. When we decided to put this problem on the Qualifying Quiz, we somehow neglected to check that part (d) was actually doable. Only later did we realize that the proof of (d) for $n\geq 10$ was quite tricky, and for $n=7, 8, 9$ it was completely ridiculous! (In fact, none of us could figure out how to do it -- and neither could any of you.)
And now I have an embarrassing confession to make. When we decided to put this problem on the Qualifying Quiz, we somehow neglected to check that part (d) was actually doable. Only later did we realize that the proof of (d) for $n\geq 10$ was quite tricky, and for $n=7, 8, 9$ it was completely ridiculous! (In fact, none of us could figure out how to do it -- and neither could any of you.)
MiraBernstein
2014-06-16 21:12:02
So how do we know that (d) is actually true? Wait a bit and see.
So how do we know that (d) is actually true? Wait a bit and see.
MiraBernstein
2014-06-16 21:12:17
But first let's deal with the case $n\geq 10$, which we (and a few of the applicants) did figure out how to prove. We need to show that $P_n$ cannot be covered with 6 circles for $n\geq 10$? Any suggestions for how to start?
But first let's deal with the case $n\geq 10$, which we (and a few of the applicants) did figure out how to prove. We need to show that $P_n$ cannot be covered with 6 circles for $n\geq 10$? Any suggestions for how to start?
amwmath
2014-06-16 21:13:19
WHAT! ARE YOU KIDDING ME!
WHAT! ARE YOU KIDDING ME!
distortedwalrus
2014-06-16 21:13:19
are you kidding me.
are you kidding me.
MiraBernstein
2014-06-16 21:13:58
Sorry
Sorry
MiraBernstein
2014-06-16 21:14:16
Let's inscribe a circle $C_n$ in $P_n$ and try to show that we cannot cover all of $C_n$ with 6 circles of radius $1/2$. Of course, if we can't even cover $C_n$, then certainly we cannot cover all of $P_n$.
$\qquad$
First, what is the radius of $C_n$?
Let's inscribe a circle $C_n$ in $P_n$ and try to show that we cannot cover all of $C_n$ with 6 circles of radius $1/2$. Of course, if we can't even cover $C_n$, then certainly we cannot cover all of $P_n$.
$\qquad$
First, what is the radius of $C_n$?
numbersandnumbers
2014-06-16 21:15:26
$\cos \dfrac{\pi}{n}$
$\cos \dfrac{\pi}{n}$
jhuang967
2014-06-16 21:15:26
$\cos \pi/n$
$\cos \pi/n$
MiraBernstein
2014-06-16 21:15:35
The radius of $C_n$ is $r = \cos(\pi/n)$. Here is a diagram to help you see it:
http://www.mathcamp.org/2014/quiz/Cn_radius.jpg
The radius of $C_n$ is $r = \cos(\pi/n)$. Here is a diagram to help you see it:
http://www.mathcamp.org/2014/quiz/Cn_radius.jpg
MiraBernstein
2014-06-16 21:16:07
Now, how much of the BOUNDARY of $C_n$ can one circle $Q$ of radius 1/2 cover?
$\qquad$
Well, if $Q$ and $C_n$ intersect in points $A$ and $B$, then $Q$ covers the entire arc of $C_n$ between $A$ and $B$. The longer the chord $AB$, the longer the arc and the larger the angle it subtends in $C_n$.
$\qquad$
Here's a picture:
http://www.mathcamp.org/2014/quiz/generic_arc.jpg
Now, how much of the BOUNDARY of $C_n$ can one circle $Q$ of radius 1/2 cover?
$\qquad$
Well, if $Q$ and $C_n$ intersect in points $A$ and $B$, then $Q$ covers the entire arc of $C_n$ between $A$ and $B$. The longer the chord $AB$, the longer the arc and the larger the angle it subtends in $C_n$.
$\qquad$
Here's a picture:
http://www.mathcamp.org/2014/quiz/generic_arc.jpg
MiraBernstein
2014-06-16 21:16:23
So what is the maximal angle $\theta$ that $AB$ can subtend in $C_n$?
So what is the maximal angle $\theta$ that $AB$ can subtend in $C_n$?
distortedwalrus
2014-06-16 21:18:12
arccos((2r^2+1)/2r^2)
arccos((2r^2+1)/2r^2)
jhuang967
2014-06-16 21:18:12
$2 \arcsin \left(\frac{1}{2}\frac{1}{\cos \pi/n} \right)$
$2 \arcsin \left(\frac{1}{2}\frac{1}{\cos \pi/n} \right)$
NeilOnnsu
2014-06-16 21:18:12
2arcsin(1/(2cos pi/n))
2arcsin(1/(2cos pi/n))
MiraBernstein
2014-06-16 21:18:25
Those are actually the same (and correct).
Those are actually the same (and correct).
MiraBernstein
2014-06-16 21:18:39
$AB$ is a chord of $Q$ as well as of $C_n$, so its maximal length is 1. Thus the maximal angle that it can subtend is
$\qquad$
$\qquad \arccos(\frac{2r^2-1}{r^2})$.
$\qquad$
(Use the Law of Cosines on a triangle with sidelengths $r$, $r$, and $1$.)
$AB$ is a chord of $Q$ as well as of $C_n$, so its maximal length is 1. Thus the maximal angle that it can subtend is
$\qquad$
$\qquad \arccos(\frac{2r^2-1}{r^2})$.
$\qquad$
(Use the Law of Cosines on a triangle with sidelengths $r$, $r$, and $1$.)
MiraBernstein
2014-06-16 21:18:46
Here's a picture:
http://www.mathcamp.org/2014/quiz/optimal_arc.jpg
Here's a picture:
http://www.mathcamp.org/2014/quiz/optimal_arc.jpg
MiraBernstein
2014-06-16 21:19:04
If you did it a different way and got $2\arcsin(1/2r)$, that's the same thing.
If you did it a different way and got $2\arcsin(1/2r)$, that's the same thing.
MiraBernstein
2014-06-16 21:19:52
OK, so this tells us the MAXIMAL possible arc that each circle of radius 1/2 can cover on $C_n$. However, we can't just place all 6 of our circles to maximize the arc. We also need to make sure one of the small circles covers the center $O$ of $C_n$, which may force this circle to cover a smaller arc in $C_n$:
http://www.mathcamp.org/2014/quiz/center_arc.jpg
OK, so this tells us the MAXIMAL possible arc that each circle of radius 1/2 can cover on $C_n$. However, we can't just place all 6 of our circles to maximize the arc. We also need to make sure one of the small circles covers the center $O$ of $C_n$, which may force this circle to cover a smaller arc in $C_n$:
http://www.mathcamp.org/2014/quiz/center_arc.jpg
MiraBernstein
2014-06-16 21:20:34
What is the maximal angle $\alpha$ that this arc can subtend in $C_n$?
What is the maximal angle $\alpha$ that this arc can subtend in $C_n$?
jhuang967
2014-06-16 21:24:41
$2\arccos r$
$2\arccos r$
jhuang967
2014-06-16 21:24:41
$2 \arccos r = 2 \pi/n$
$2 \arccos r = 2 \pi/n$
numbersandnumbers
2014-06-16 21:24:41
$2 \arccos r = \dfrac{2\pi}{n}$?
$2 \arccos r = \dfrac{2\pi}{n}$?
forthegreatergood
2014-06-16 21:24:54
is it 2pi/n?
is it 2pi/n?
gedt11
2014-06-16 21:24:54
2pi/n
2pi/n
MiraBernstein
2014-06-16 21:26:52
The arc is maximized when the small circle has $O$ on its boundary. The maximal angle that this arc subtends is $2\pi/n$, as you can see from the next picture
The arc is maximized when the small circle has $O$ on its boundary. The maximal angle that this arc subtends is $2\pi/n$, as you can see from the next picture
MiraBernstein
2014-06-16 21:27:50
If each of the remaining 5 circles covers the maximal possible arc, then the total angle subtended by the arc of $C_n$ contained inside the 6 small circles is at most
$\qquad$
$\qquad \frac{2\pi}{n} + 5\cdot 2\arccos\left(\frac{2r^2-1}{r^2}\right)$
$\qquad$
If you plug this into your calculator, you'll see that this is less than $2\pi$ for $n\geq 10$, but greater than $2\pi$ for $n \leq 9$. Thus we have proved that for $n\geq 10$, $C_n$ (and hence $P_n$) cannot be covered with just 6 circles.
If each of the remaining 5 circles covers the maximal possible arc, then the total angle subtended by the arc of $C_n$ contained inside the 6 small circles is at most
$\qquad$
$\qquad \frac{2\pi}{n} + 5\cdot 2\arccos\left(\frac{2r^2-1}{r^2}\right)$
$\qquad$
If you plug this into your calculator, you'll see that this is less than $2\pi$ for $n\geq 10$, but greater than $2\pi$ for $n \leq 9$. Thus we have proved that for $n\geq 10$, $C_n$ (and hence $P_n$) cannot be covered with just 6 circles.
MiraBernstein
2014-06-16 21:28:11
You can try to improve this argument to work for $n \leq 9$ by placing additional constraints on the positions of the 6 circles, but it gets very nasty. (As if it isn't nasty enough already!) As I said before, we couldn't figure out how to prove this result for $7 \leq n \leq 9$.
You can try to improve this argument to work for $n \leq 9$ by placing additional constraints on the positions of the 6 circles, but it gets very nasty. (As if it isn't nasty enough already!) As I said before, we couldn't figure out how to prove this result for $7 \leq n \leq 9$.
MiraBernstein
2014-06-16 21:28:54
However, what we did find is a web page that cites a theorem from 1979:
$\qquad$
$\qquad$ http://www2.stetson.edu/~efriedma/circovcir/
However, what we did find is a web page that cites a theorem from 1979:
$\qquad$
$\qquad$ http://www2.stetson.edu/~efriedma/circovcir/
MiraBernstein
2014-06-16 21:29:05
The theorem says that if you want to cover a circle of radius R with 6 circles of radius 1, then the maximal R that will work is $\approx 1.798 < 1.8$. Our 6 small circles have radius 1/2, so the largest circle that can be covered with six of them has radius less than $1.8/2 = 0.9$. How does this help us?
The theorem says that if you want to cover a circle of radius R with 6 circles of radius 1, then the maximal R that will work is $\approx 1.798 < 1.8$. Our 6 small circles have radius 1/2, so the largest circle that can be covered with six of them has radius less than $1.8/2 = 0.9$. How does this help us?
distortedwalrus
2014-06-16 21:29:51
so who did figure it out?
so who did figure it out?
MiraBernstein
2014-06-16 21:30:42
If you use the theorem it's not that hard. We found the theorem online and so did exactly one applicant.
If you use the theorem it's not that hard. We found the theorem online and so did exactly one applicant.
MiraBernstein
2014-06-16 21:31:17
A few people got the $n\geq 10$ argument
A few people got the $n\geq 10$ argument
amwmath
2014-06-16 21:31:25
But there was a rule about no looking up... I didn't dare Google anything problem-related!
But there was a rule about no looking up... I didn't dare Google anything problem-related!
MiraBernstein
2014-06-16 21:31:46
You are allowed to use the Web if you cite the source and if you don't look for the answer to the problem directly
You are allowed to use the Web if you cite the source and if you don't look for the answer to the problem directly
MiraBernstein
2014-06-16 21:32:03
We still haven't quite finished saying how the theorem helped us.
We still haven't quite finished saying how the theorem helped us.
MiraBernstein
2014-06-16 21:32:14
As we computed earlier, the radius of $C_7$ is $\cos(\pi/7) \approx 0.90097$. So $C_7$ is too big to be covered with 6 circles of radius 1/2. Hence neither can $C_8$ or $C_9$ can be covered (since they are even larger), and neither can $P_7$, $P_8$, or $P_9$.
As we computed earlier, the radius of $C_7$ is $\cos(\pi/7) \approx 0.90097$. So $C_7$ is too big to be covered with 6 circles of radius 1/2. Hence neither can $C_8$ or $C_9$ can be covered (since they are even larger), and neither can $P_7$, $P_8$, or $P_9$.
nebulagirl
2014-06-16 21:32:27
This bothers me. Is there a proof for the theorem?
This bothers me. Is there a proof for the theorem?
MiraBernstein
2014-06-16 21:32:50
Yes, there is (that's why it's a theorem). It was published *somewhere* in 1979 -- but I haven't been able to track down the article
Yes, there is (that's why it's a theorem). It was published *somewhere* in 1979 -- but I haven't been able to track down the article
MiraBernstein
2014-06-16 21:33:13
Probably published in Hungarian, so wouldn't be much help even if I found it...
Probably published in Hungarian, so wouldn't be much help even if I found it...
amwmath
2014-06-16 21:33:43
I'm assuming that everyone who proved everything but the n>6 case got full credit.
I'm assuming that everyone who proved everything but the n>6 case got full credit.
MiraBernstein
2014-06-16 21:34:04
Yes, and people who proved the $n\geq 10$ case got extra credit.
Yes, and people who proved the $n\geq 10$ case got extra credit.
MiraBernstein
2014-06-16 21:34:25
we're done with problem #3. Whew!!
$\qquad$
we're done with problem #3. Whew!!
$\qquad$
MiraBernstein
2014-06-16 21:34:54
I'm not sure we'll have time for all of 4, 5, and 6. Want to vote on which one to do first?
I'm not sure we'll have time for all of 4, 5, and 6. Want to vote on which one to do first?
MiraBernstein
2014-06-16 21:35:17
(We're supposed to go until 10 EDT, I'm OK with staying a little later, but you might have to go)
(We're supposed to go until 10 EDT, I'm OK with staying a little later, but you might have to go)
MiraBernstein
2014-06-16 21:36:38
So far, 6 beats 4 beats 5, so let's do them in that roder
So far, 6 beats 4 beats 5, so let's do them in that roder
MiraBernstein
2014-06-16 21:36:56
Problem 6 is by Bill Kuszmaul, a Mathcamp alum who has just graduated from high school. It is based on his own research in combinatorics. It starts with a bunch of definitions:
Problem 6 is by Bill Kuszmaul, a Mathcamp alum who has just graduated from high school. It is based on his own research in combinatorics. It starts with a bunch of definitions:
MiraBernstein
2014-06-16 21:37:11
A path from the bottom left to the upper right corner of an $m \times n$ grid is called "monotonic" if on each step it goes either up (U) or to the right (R).
$\qquad$
Such a path has $m+n$ steps, of which $m$ are U's and $n$ are R's. Thus the total number of monotonic paths is ${m+n \choose m} = {m+n \choose n}$.
$\qquad$
We define the "area" of a monotonic path to be the number of squares underneath it. The area can be anywhere between 0 and $mn$.
$\qquad$
The "forward shift" of a monotonic path $P$ is the path that results when we take the first step of $P$ (either U or R) and move it to the end. For instance, the forward shift of URRURU would be RRURUU. Of course, once we perform $m+n$ forward shifts, we get our original path back.
A path from the bottom left to the upper right corner of an $m \times n$ grid is called "monotonic" if on each step it goes either up (U) or to the right (R).
$\qquad$
Such a path has $m+n$ steps, of which $m$ are U's and $n$ are R's. Thus the total number of monotonic paths is ${m+n \choose m} = {m+n \choose n}$.
$\qquad$
We define the "area" of a monotonic path to be the number of squares underneath it. The area can be anywhere between 0 and $mn$.
$\qquad$
The "forward shift" of a monotonic path $P$ is the path that results when we take the first step of $P$ (either U or R) and move it to the end. For instance, the forward shift of URRURU would be RRURUU. Of course, once we perform $m+n$ forward shifts, we get our original path back.
nebulagirl
2014-06-16 21:37:23
What happens if we don't cover all the problems?
What happens if we don't cover all the problems?
MiraBernstein
2014-06-16 21:37:36
I'll post solutions to the ones we didn't do
I'll post solutions to the ones we didn't do
MiraBernstein
2014-06-16 21:37:47
Here are some examples of forward shifts of monotonic paths and their different areas. I'll let you stare at them for a little bit, so you can get used to the terminology.
http://www.mathcamp.org/2014/quiz/forward_shifts_example.jpg
Here are some examples of forward shifts of monotonic paths and their different areas. I'll let you stare at them for a little bit, so you can get used to the terminology.
http://www.mathcamp.org/2014/quiz/forward_shifts_example.jpg
MiraBernstein
2014-06-16 21:38:30
I hope the definitions make sense to everyone. Now here is the first part of the problem:
I hope the definitions make sense to everyone. Now here is the first part of the problem:
MiraBernstein
2014-06-16 21:38:37
PROBLEM #6(a):
Suppose $m+n= q$, where $q$ is prime. Let $P_0$ be a monotonic path on an $m\times n$ grid, and let $P_1, P_2, \dots, P_{q-1}$ be successive forward shifts of $P_0$. Show that for each integer $k = 0, 1,\dots , q-1$, exactly one of $P_0, P_1,\dots, P_{q-1}$ has area congruent to $k$ modulo $q$.
PROBLEM #6(a):
Suppose $m+n= q$, where $q$ is prime. Let $P_0$ be a monotonic path on an $m\times n$ grid, and let $P_1, P_2, \dots, P_{q-1}$ be successive forward shifts of $P_0$. Show that for each integer $k = 0, 1,\dots , q-1$, exactly one of $P_0, P_1,\dots, P_{q-1}$ has area congruent to $k$ modulo $q$.
MiraBernstein
2014-06-16 21:38:51
Clearly, for this problem, we need to figure out what happens to the area of a path on an $m \times n$ grid when you perform a forward shift. Any ideas?
Clearly, for this problem, we need to figure out what happens to the area of a path on an $m \times n$ grid when you perform a forward shift. Any ideas?
distortedwalrus
2014-06-16 21:40:43
you either add m or subtract n from the area
you either add m or subtract n from the area
NeilOnnsu
2014-06-16 21:40:43
When the forward shift moves a U to the back, the area decreases by n. When it moves an R to the back, the area increases by m.
When the forward shift moves a U to the back, the area decreases by n. When it moves an R to the back, the area increases by m.
Sesquipedalian
2014-06-16 21:40:43
Sometimes it increases by $m$, and sometimes it decreases by $n$.
Sometimes it increases by $m$, and sometimes it decreases by $n$.
MiraBernstein
2014-06-16 21:41:20
Let's look at our previous examples more closely:
http://www.mathcamp.org/2014/quiz/Ufirst.jpg
Let's look at our previous examples more closely:
http://www.mathcamp.org/2014/quiz/Ufirst.jpg
MiraBernstein
2014-06-16 21:41:32
Here you can see that when a path begins with a "U", the forward shift causes its area to DECREASE by $n$.
$\qquad$
Similarly, when a path begins with a "R", the forward shift causes its area to INCREASE by $m$.
http://www.mathcamp.org/2014/quiz/Rfirst.jpg
Here you can see that when a path begins with a "U", the forward shift causes its area to DECREASE by $n$.
$\qquad$
Similarly, when a path begins with a "R", the forward shift causes its area to INCREASE by $m$.
http://www.mathcamp.org/2014/quiz/Rfirst.jpg
MiraBernstein
2014-06-16 21:42:26
Since $q=m+n$, we have $m=-n$ (mod $q$)! This means that all forward shifts have the SAME effect on the area mod $q$: they always increase it by $m$ (which is the same as decreasing by $n$).
Since $q=m+n$, we have $m=-n$ (mod $q$)! This means that all forward shifts have the SAME effect on the area mod $q$: they always increase it by $m$ (which is the same as decreasing by $n$).
distortedwalrus
2014-06-16 21:42:45
since m == -n (mod m+n), we see that this is equivalent to adding m each time. Since m is relatively prime to m+n, we cycle through all the residues
since m == -n (mod m+n), we see that this is equivalent to adding m each time. Since m is relatively prime to m+n, we cycle through all the residues
MiraBernstein
2014-06-16 21:42:59
So if $P_0$ has area $A$ mod $q$, then what is the area of $P_j$ mod $q$?
So if $P_0$ has area $A$ mod $q$, then what is the area of $P_j$ mod $q$?
mathwizard888
2014-06-16 21:43:43
A+jm
A+jm
lucylai
2014-06-16 21:43:43
distortedwalrus
2014-06-16 21:43:43
A+mj
A+mj
NeilOnnsu
2014-06-16 21:43:43
A+mj (mod q)
A+mj (mod q)
MiraBernstein
2014-06-16 21:43:53
The area of $P_j$ is $A+jm$ mod $q$.
$\qquad$
Is it possible for $P_j$ and $P_k$ to have the same area mod $q$?
The area of $P_j$ is $A+jm$ mod $q$.
$\qquad$
Is it possible for $P_j$ and $P_k$ to have the same area mod $q$?
justindong
2014-06-16 21:44:32
no
no
NeilOnnsu
2014-06-16 21:44:32
Nope, since gcd(m, q) = gcd(m, n) = 1
Nope, since gcd(m, q) = gcd(m, n) = 1
distortedwalrus
2014-06-16 21:44:32
no because that would imply that mj == mk (mod q) iff j==k (mod q)
no because that would imply that mj == mk (mod q) iff j==k (mod q)
MiraBernstein
2014-06-16 21:44:41
If $P_j$ and $P_k$ have the same area, then $A+jm = A+km$ mod $q$, so $km=jm$ mod $q$.
$\qquad$
Since $q$ is prime, we are allowed to divide mod $q$, so we can cancel the $m$ and conclude that $j=k$.
$\qquad$
Thus two different forward shifts always have different areas mod $q$.
If $P_j$ and $P_k$ have the same area, then $A+jm = A+km$ mod $q$, so $km=jm$ mod $q$.
$\qquad$
Since $q$ is prime, we are allowed to divide mod $q$, so we can cancel the $m$ and conclude that $j=k$.
$\qquad$
Thus two different forward shifts always have different areas mod $q$.
amwmath
2014-06-16 21:45:14
Quote from my solution: "m and q are relatively prime, because q is prime and m is nonzero. It is a well known theorem that, if m and q are relatively prime, each of p, p + m, p + 2m, . . . , p + (q − 1)m are unique modulo q. Therefore, each of P_0, P_1, . . . , P_(q−1) have unique areas modulo q."
Quote from my solution: "m and q are relatively prime, because q is prime and m is nonzero. It is a well known theorem that, if m and q are relatively prime, each of p, p + m, p + 2m, . . . , p + (q − 1)m are unique modulo q. Therefore, each of P_0, P_1, . . . , P_(q−1) have unique areas modulo q."
MiraBernstein
2014-06-16 21:45:21
The areas of $P_0, P_1,\dots, P_{q-1}$ mod $q$ are all integers between 0 and $q-1$, and they are all different. Thus, by pigeonhole principle, each integer appears exactly once, which is what we needed to prove.
The areas of $P_0, P_1,\dots, P_{q-1}$ mod $q$ are all integers between 0 and $q-1$, and they are all different. Thus, by pigeonhole principle, each integer appears exactly once, which is what we needed to prove.
MiraBernstein
2014-06-16 21:45:33
Now let's use part (a) to solve parts (b) and (c):
Now let's use part (a) to solve parts (b) and (c):
MiraBernstein
2014-06-16 21:45:43
PROBLEM 6b:
Consider all monotonic paths on a $q\times q$ grid, where $q$ is prime. For each integer $k = 0, 1,\dots , q-1$, how many of these ${2q \choose q}$ paths have area congruent to $k$ modulo $q$?
PROBLEM 6b:
Consider all monotonic paths on a $q\times q$ grid, where $q$ is prime. For each integer $k = 0, 1,\dots , q-1$, how many of these ${2q \choose q}$ paths have area congruent to $k$ modulo $q$?
MiraBernstein
2014-06-16 21:46:15
Notice that now we are on a $q\times q$ grid, not an $m\times n$ grid.
$\qquad$
Let's consider two special paths:
$\qquad UUU...URRR...R$ and $RRRR...RUUUU....U$
These are the paths that go all the way up and then across, or all the way across and then up.
$\qquad$
What are their areas mod $q$?
Notice that now we are on a $q\times q$ grid, not an $m\times n$ grid.
$\qquad$
Let's consider two special paths:
$\qquad UUU...URRR...R$ and $RRRR...RUUUU....U$
These are the paths that go all the way up and then across, or all the way across and then up.
$\qquad$
What are their areas mod $q$?
64138luc
2014-06-16 21:46:54
0
0
clarencechenct
2014-06-16 21:46:54
0
0
64138luc
2014-06-16 21:46:54
0
0
MiraBernstein
2014-06-16 21:47:06
$UUU...URRR...R$ has area $q^2$ and $RRRR...RUUUU....U$ has area 0, both of which are $0$ mod $q$.
$UUU...URRR...R$ has area $q^2$ and $RRRR...RUUUU....U$ has area 0, both of which are $0$ mod $q$.
MiraBernstein
2014-06-16 21:47:30
Sound familiar? That's the setup of part (a), so let's try to use the result we proved there.
Sound familiar? That's the setup of part (a), so let's try to use the result we proved there.
MiraBernstein
2014-06-16 21:47:46
Let's call two paths $P$ and $P'$ "equivalent" if
$\qquad$* the first $q$ steps of $P'$ can be obtained from the first $q$ steps of $P$ via forward shifts;
$\qquad$* the last $q$ steps are the same.
Let's call two paths $P$ and $P'$ "equivalent" if
$\qquad$* the first $q$ steps of $P'$ can be obtained from the first $q$ steps of $P$ via forward shifts;
$\qquad$* the last $q$ steps are the same.
MiraBernstein
2014-06-16 21:48:32
How many different paths are equivalent to a generic path $P$, and what can you about their areas mod $q$.
How many different paths are equivalent to a generic path $P$, and what can you about their areas mod $q$.
jhuang967
2014-06-16 21:49:37
q. And all of their areas have different areas $\bmod q$.
q. And all of their areas have different areas $\bmod q$.
MiraBernstein
2014-06-16 21:49:48
There are $q-1$ other paths equivalent to $P$, since the $q-1$ successive forward shifts of the first $q$ steps are all distinct. By part (a), all these paths have different areas mod $q$.
There are $q-1$ other paths equivalent to $P$, since the $q-1$ successive forward shifts of the first $q$ steps are all distinct. By part (a), all these paths have different areas mod $q$.
MiraBernstein
2014-06-16 21:50:02
What does this tell us about the areas of generic paths mod $q$?
What does this tell us about the areas of generic paths mod $q$?
lucylai
2014-06-16 21:51:29
outside of the "exceptional paths" the areas are regularly distributed mod q
outside of the "exceptional paths" the areas are regularly distributed mod q
jhuang967
2014-06-16 21:51:29
For any modular residue $k$ other than 0, $1/q$ of the generic paths have areas congruent to $k$.
For any modular residue $k$ other than 0, $1/q$ of the generic paths have areas congruent to $k$.
clarencechenct
2014-06-16 21:51:29
that there is an equal distribution from 0 to q-1
that there is an equal distribution from 0 to q-1
amwmath
2014-06-16 21:51:29
For every two numbers k and j, there are the same number of generic paths with areas mod k as there are mod j.
For every two numbers k and j, there are the same number of generic paths with areas mod k as there are mod j.
MiraBernstein
2014-06-16 21:51:41
Since the generic paths split up into equivalence classes, and each equivalence class contains one path of each possible area mod $q$, the total number of generic paths of area $k$ mod $q$ must the same for all $k$.
How many are there?
Since the generic paths split up into equivalence classes, and each equivalence class contains one path of each possible area mod $q$, the total number of generic paths of area $k$ mod $q$ must the same for all $k$.
How many are there?
lucylai
2014-06-16 21:53:07
ncr(2q,q)-2
ncr(2q,q)-2
Jettywang828
2014-06-16 21:53:07
I just joined, so I'm gonna say 42
I just joined, so I'm gonna say 42
MiraBernstein
2014-06-16 21:53:15
jhuang967
2014-06-16 21:53:33
There are $\left( \binom{2q}{q} - 2 \right)$ generic paths and $\frac{1}{q} \left( \binom{2q}{q} - 2 \right)$ for each of ${0,1,\dots,q-1}$
There are $\left( \binom{2q}{q} - 2 \right)$ generic paths and $\frac{1}{q} \left( \binom{2q}{q} - 2 \right)$ for each of ${0,1,\dots,q-1}$
MiraBernstein
2014-06-16 21:53:50
There are ${2q \choose q}$ different monotonic paths through our grid, of which all but 2 are generic. There are $q$ possible areas mod $q$.
$\qquad$
Thus there are
$\qquad$
$\qquad \frac{{2q \choose q} - 2}{q}$
$\qquad$
generic paths of area $k$ for each $k = 0, 1, \dots, q-1$.
There are ${2q \choose q}$ different monotonic paths through our grid, of which all but 2 are generic. There are $q$ possible areas mod $q$.
$\qquad$
Thus there are
$\qquad$
$\qquad \frac{{2q \choose q} - 2}{q}$
$\qquad$
generic paths of area $k$ for each $k = 0, 1, \dots, q-1$.
MiraBernstein
2014-06-16 21:54:11
We add the two exceptional paths back in, and conclude that there are a total of
$\qquad$
$\qquad \frac{{2q \choose q} - 2}{q} + 2$
$\qquad$
paths of area 0 mod $q$.
We add the two exceptional paths back in, and conclude that there are a total of
$\qquad$
$\qquad \frac{{2q \choose q} - 2}{q} + 2$
$\qquad$
paths of area 0 mod $q$.
MiraBernstein
2014-06-16 21:55:17
$\qquad$
and $\qquad \frac{{2q \choose q} - 2}{q}$
$\qquad$
paths of area $k$ for each $k = 0, 1, \dots, q-1$.
$\qquad$
and $\qquad \frac{{2q \choose q} - 2}{q}$
$\qquad$
paths of area $k$ for each $k = 0, 1, \dots, q-1$.
MiraBernstein
2014-06-16 21:55:34
OK, on to part (c)
OK, on to part (c)
MiraBernstein
2014-06-16 21:55:55
Oh wait, one comment
Oh wait, one comment
clarencechenct
2014-06-16 21:56:01
and you can prove that both are integers through wilson's theorem and manuipulation (i think)
and you can prove that both are integers through wilson's theorem and manuipulation (i think)
MiraBernstein
2014-06-16 21:56:13
You don't need to prove they;re integers! We just proved it.
You don't need to prove they;re integers! We just proved it.
MiraBernstein
2014-06-16 21:56:22
Anything that counts paths is an integer!
Anything that counts paths is an integer!
MiraBernstein
2014-06-16 21:56:39
PROBLEM 6c:
More generally, consider all monotonic paths on an $mq \times nq$ grid, where $q$ is prime and $m$ and $n$ are arbitrary positive integers. For each integer $k = 0, 1,\dots , q-1$, how many of these paths have area congruent to $k$ modulo $q$?
PROBLEM 6c:
More generally, consider all monotonic paths on an $mq \times nq$ grid, where $q$ is prime and $m$ and $n$ are arbitrary positive integers. For each integer $k = 0, 1,\dots , q-1$, how many of these paths have area congruent to $k$ modulo $q$?
MiraBernstein
2014-06-16 21:57:34
I actually didn't have time to write out a very interactive script for this, but let me give you Bill's own solution and hopefully it wlil make sense
I actually didn't have time to write out a very interactive script for this, but let me give you Bill's own solution and hopefully it wlil make sense
MiraBernstein
2014-06-16 21:57:42
Let $j$ and $k$ be positive integers and let $p$ be prime. Consider a path $w$ containing $jp$ vertical steps and $kp$ side steps.
Let $j$ and $k$ be positive integers and let $p$ be prime. Consider a path $w$ containing $jp$ vertical steps and $kp$ side steps.
MiraBernstein
2014-06-16 21:58:09
Suppose there exists a $r$ such that the steps $w_{pr+1}, \dots, w_{p(r+1)}$ are not all either just ones or just zeros. Let $r$ be the smallest such $r$. Then, we can "cancel out" the area of $w$ with the area of the paths reached by taking $w$ and cyclicly shifting the steps $w_{pr+1}, \dots, w_{p(r+1)}$ within $w$. The paths we have "cancelled out" with each other have areas equidistributed modulo $p$.
Suppose there exists a $r$ such that the steps $w_{pr+1}, \dots, w_{p(r+1)}$ are not all either just ones or just zeros. Let $r$ be the smallest such $r$. Then, we can "cancel out" the area of $w$ with the area of the paths reached by taking $w$ and cyclicly shifting the steps $w_{pr+1}, \dots, w_{p(r+1)}$ within $w$. The paths we have "cancelled out" with each other have areas equidistributed modulo $p$.
MiraBernstein
2014-06-16 21:58:31
Oh no, just noticed that he uses p insetad of our $q$
Oh no, just noticed that he uses p insetad of our $q$
MiraBernstein
2014-06-16 21:58:55
Anyway, the point is that you look at the first q steps, then the next q steps, then the next q steps
Anyway, the point is that you look at the first q steps, then the next q steps, then the next q steps
MiraBernstein
2014-06-16 21:59:25
If any one of them is not all U's or all R's, then we take forward shifts of that piece of the path
If any one of them is not all U's or all R's, then we take forward shifts of that piece of the path
MiraBernstein
2014-06-16 21:59:48
We call all those $q$ paths equivalent, and each has a different area mod $q$
We call all those $q$ paths equivalent, and each has a different area mod $q$
MiraBernstein
2014-06-16 22:00:04
POnes and zeroes = U's and R's
POnes and zeroes = U's and R's
MiraBernstein
2014-06-16 22:00:22
Here's more from Bill:
Here's more from Bill:
MiraBernstein
2014-06-16 22:00:44
Now let us consider the remaining paths. Each such path consists of chunks of $p$ side steps and $p$ vertical steps appended together. Each such path, as a consequence, has area $0$ mod $p$, and there are exactly $j+k \choose j$ such paths.
Now let us consider the remaining paths. Each such path consists of chunks of $p$ side steps and $p$ vertical steps appended together. Each such path, as a consequence, has area $0$ mod $p$, and there are exactly $j+k \choose j$ such paths.
MiraBernstein
2014-06-16 22:01:09
Hence, the number of paths on a $jp \times kp$ grid with area $0$ mod $p$ is
$$
\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}+{j+k \choose j}.
$$
And the number of paths with area $i$ mod $p$ for $i$ not congruent to zero is
$$
\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}.
Hence, the number of paths on a $jp \times kp$ grid with area $0$ mod $p$ is
$$
\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}+{j+k \choose j}.
$$
And the number of paths with area $i$ mod $p$ for $i$ not congruent to zero is
$$
\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}.
MiraBernstein
2014-06-16 22:01:33
$\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}.$
$\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}.$
MiraBernstein
2014-06-16 22:02:06
So basically, part (c) is a generalization of part (b)
So basically, part (c) is a generalization of part (b)
amwmath
2014-06-16 22:02:22
Split the path into m+n parts. If each part is either all U's or all R's, call it "exceptional".
Split the path into m+n parts. If each part is either all U's or all R's, call it "exceptional".
MiraBernstein
2014-06-16 22:02:41
Once we generalize "exceptional" it proceeds as before.
Once we generalize "exceptional" it proceeds as before.
MiraBernstein
2014-06-16 22:02:46
OK, guys, it's 10 pm
OK, guys, it's 10 pm
MiraBernstein
2014-06-16 22:03:04
I'm happy to stay and do #4
I'm happy to stay and do #4
MiraBernstein
2014-06-16 22:03:21
But you should feel free to go, since 2 hours is a long time to absorb hard math
But you should feel free to go, since 2 hours is a long time to absorb hard math
MiraBernstein
2014-06-16 22:04:18
PROBLEM #4: Hannah is about to get into a swimming pool in which every lane already has one swimmer in it. Hannah wants to choose a lane in which she would have to encounter the other swimmer as infrequently as possible. All swimmers, including Hannah, swim back and forth at constant speeds, never pausing at the ends of the pool. Hannah swims at speed 1 (one pool length per minute).
$\qquad$
$\qquad$(a) Say Hannah chooses a lane with a swimmer who swims at speed $s < 1$. Prove that, if they keep swimming long enough, eventually Hannah and the other swimmer will settle into a pattern where they pass each other (either in the same or in opposite directions) exactly $N$ times every $M$ minutes, where $M$ and $N$ are relatively prime integers. Find $M$ and $N$. Do they depend on the other swimmer's speed and/or initial position when Hannah enters the pool?
$\qquad$ (b) What if Hannah chooses a lane with a swimmer whose speed is $s>1$?
$\qquad$ (c) From Hannah's point of view, what is the ideal speed that another swimmer can have? (Assume Hannah can time her entry into the pool with perfect precision, so she can make the other swimmer's initial position be whatever she wants.)
PROBLEM #4: Hannah is about to get into a swimming pool in which every lane already has one swimmer in it. Hannah wants to choose a lane in which she would have to encounter the other swimmer as infrequently as possible. All swimmers, including Hannah, swim back and forth at constant speeds, never pausing at the ends of the pool. Hannah swims at speed 1 (one pool length per minute).
$\qquad$
$\qquad$(a) Say Hannah chooses a lane with a swimmer who swims at speed $s < 1$. Prove that, if they keep swimming long enough, eventually Hannah and the other swimmer will settle into a pattern where they pass each other (either in the same or in opposite directions) exactly $N$ times every $M$ minutes, where $M$ and $N$ are relatively prime integers. Find $M$ and $N$. Do they depend on the other swimmer's speed and/or initial position when Hannah enters the pool?
$\qquad$ (b) What if Hannah chooses a lane with a swimmer whose speed is $s>1$?
$\qquad$ (c) From Hannah's point of view, what is the ideal speed that another swimmer can have? (Assume Hannah can time her entry into the pool with perfect precision, so she can make the other swimmer's initial position be whatever she wants.)
ukulifeguard
2014-06-16 22:05:26
As a lifeguard, I will take this to heart and use it to stop lap-swimmer-fights (more common than you may think)...
As a lifeguard, I will take this to heart and use it to stop lap-swimmer-fights (more common than you may think)...
MiraBernstein
2014-06-16 22:05:44
Actually, a bunch of people pointed out that this problem is a terrible model for actual swimming
Actually, a bunch of people pointed out that this problem is a terrible model for actual swimming
MiraBernstein
2014-06-16 22:06:22
First let's agree on some terminology: in this problem, we'll use "one lane" to mean "one pool-length". So "swimming a lane" means swimming once across the pool. If something happens "once per lane", it means it happens once each time you swim across the pool. (What swimmers usually call "swimming a lap" -- there and back -- would count as swimming two lanes.)
$\qquad$
Also, for ease of reference, we might as well give the second swimmer a name. Let's call him Sam.
First let's agree on some terminology: in this problem, we'll use "one lane" to mean "one pool-length". So "swimming a lane" means swimming once across the pool. If something happens "once per lane", it means it happens once each time you swim across the pool. (What swimmers usually call "swimming a lap" -- there and back -- would count as swimming two lanes.)
$\qquad$
Also, for ease of reference, we might as well give the second swimmer a name. Let's call him Sam.
MiraBernstein
2014-06-16 22:06:41
In part (a), Sam's speed $s$ is less than 1. At the heart of the solution is a very simple observation: each time Hannah swims one lane (1 minute), how many times does she encounter Sam?
In part (a), Sam's speed $s$ is less than 1. At the heart of the solution is a very simple observation: each time Hannah swims one lane (1 minute), how many times does she encounter Sam?
distortedwalrus
2014-06-16 22:07:13
the main observation for part a is that Hannah passes the swimmer at least once per minute. So we'd like it to be exactly once
the main observation for part a is that Hannah passes the swimmer at least once per minute. So we'd like it to be exactly once
danusv
2014-06-16 22:07:13
once
once
va2010
2014-06-16 22:07:13
once
once
ukulifeguard
2014-06-16 22:07:13
Only once.
Only once.
MiraBernstein
2014-06-16 22:07:26
First of all, each time Hannah swims a lane, she encounters Sam at least once. If, when Hannah enters the water, Sam is swimming toward her, then clearly they'll meet. If he's swimming away from her, then either Hannah will pass him before he reaches the edge, or he'll reach the edge, turn around, and start swimming toward her; either way, they'll meet.
First of all, each time Hannah swims a lane, she encounters Sam at least once. If, when Hannah enters the water, Sam is swimming toward her, then clearly they'll meet. If he's swimming away from her, then either Hannah will pass him before he reaches the edge, or he'll reach the edge, turn around, and start swimming toward her; either way, they'll meet.
MiraBernstein
2014-06-16 22:07:39
(Some people used the Intermediate Value Theorem from calculus to prove this, which certainly works. However, since we know exactly how the swimmers are moving, we don't need anything that complicated.)
(Some people used the Intermediate Value Theorem from calculus to prove this, which certainly works. However, since we know exactly how the swimmers are moving, we don't need anything that complicated.)
MiraBernstein
2014-06-16 22:08:13
Once Hannah meets Sam some time during her lane, how do we know she cannot meet him again during the same lane?
Once Hannah meets Sam some time during her lane, how do we know she cannot meet him again during the same lane?
niraekjs
2014-06-16 22:08:52
Because she is travelling faster than him
Because she is travelling faster than him
nebulagirl
2014-06-16 22:08:52
Sam's not fast enough
Sam's not fast enough
MiraBernstein
2014-06-16 22:08:58
The first meeting can happen in one of two ways: either Hannah passes Sam (going in the same direction), or she meets him face-to-face (going in opposite directions).
$\qquad$ * If Hannah passes Sam, then to meet her again in the same lane, Sam would have to catch up to her. But he swims slower than her ($s<1$) so this is impossible.
$\qquad$ * If Hannah meets Sam face-to-face, then to meet her again in the same lane, Sam would have to reverse direction and THEN catch up to her. That's even more impossible.
$\qquad$
So we conclude that Hannah meets Sam exactly once per lane, i.e. once per minute.
The first meeting can happen in one of two ways: either Hannah passes Sam (going in the same direction), or she meets him face-to-face (going in opposite directions).
$\qquad$ * If Hannah passes Sam, then to meet her again in the same lane, Sam would have to catch up to her. But he swims slower than her ($s<1$) so this is impossible.
$\qquad$ * If Hannah meets Sam face-to-face, then to meet her again in the same lane, Sam would have to reverse direction and THEN catch up to her. That's even more impossible.
$\qquad$
So we conclude that Hannah meets Sam exactly once per lane, i.e. once per minute.
danusv
2014-06-16 22:09:24
She either passed him or they crossed paths and so by the time they encounter again she will be in another lane
She either passed him or they crossed paths and so by the time they encounter again she will be in another lane
MiraBernstein
2014-06-16 22:09:33
Does that mean we can say that $M = N = 1$ and be done with part (a)?
Does that mean we can say that $M = N = 1$ and be done with part (a)?
danusv
2014-06-16 22:10:14
No because sometimes they meet at the end of a pool and so that is one encounter per two laps
No because sometimes they meet at the end of a pool and so that is one encounter per two laps
leekkww
2014-06-16 22:10:14
noooo
noooo
nebulagirl
2014-06-16 22:10:14
No, because they can meet at the end of the pool
No, because they can meet at the end of the pool
clarencechenct
2014-06-16 22:10:14
I calculated that one meet would be conflated in that case
I calculated that one meet would be conflated in that case
RavenclawPrefect
2014-06-16 22:10:14
No, it does not. We've left out the effects of endpoints
No, it does not. We've left out the effects of endpoints
MiraBernstein
2014-06-16 22:10:28
When Hannah and Sam meet at the EDGE of the pool, this counts as their meeting both for the previous lane and for the next lane! This complicates things -- so let's look at edge meetings more closely.
$\qquad$
If Hannah and Sam swim meet at the edge exactly once during their (infinite) swimming session, do we need to worry about this?
When Hannah and Sam meet at the EDGE of the pool, this counts as their meeting both for the previous lane and for the next lane! This complicates things -- so let's look at edge meetings more closely.
$\qquad$
If Hannah and Sam swim meet at the edge exactly once during their (infinite) swimming session, do we need to worry about this?
lucylai
2014-06-16 22:11:17
no because "infinite"
no because "infinite"
clarencechenct
2014-06-16 22:11:17
no, "eventually settles" is the key phrase
no, "eventually settles" is the key phrase
MiraBernstein
2014-06-16 22:11:28
The problem asks for what happens "eventually", so we just wait until after their edge-meeting. After this, we'll have $M=N=1$ forever more, and we're done.
The problem asks for what happens "eventually", so we just wait until after their edge-meeting. After this, we'll have $M=N=1$ forever more, and we're done.
MiraBernstein
2014-06-16 22:11:37
What if they meet at the edge more than once?
What if they meet at the edge more than once?
64138luc
2014-06-16 22:12:25
That means it is a pattern
That means it is a pattern
Akababa
2014-06-16 22:12:25
repeat the pattern!
repeat the pattern!
shipeiyang1708
2014-06-16 22:12:25
it will just happen again
it will just happen again
danusv
2014-06-16 22:12:25
Then they will meet there at regular occurences
Then they will meet there at regular occurences
RavenclawPrefect
2014-06-16 22:12:25
Then we have to find the frequency
Then we have to find the frequency
lucylai
2014-06-16 22:12:25
they need to do so periodically so s must be rational
they need to do so periodically so s must be rational
MiraBernstein
2014-06-16 22:12:36
Between their first and second meeting, both Hannah and Sam swim an integer number of lanes (since they both start and end at an edge). Suppose Sam swims $a$ lanes while Hannah swims $b$ lanes. Then Sam swims $a$ lanes in $b$ minutes, so his speed is $s=a/b$, a rational number. After this, the cycle will repeat again, and Sam and Hannah will keep meeting at the edge every $b$ minutes forever.
Between their first and second meeting, both Hannah and Sam swim an integer number of lanes (since they both start and end at an edge). Suppose Sam swims $a$ lanes while Hannah swims $b$ lanes. Then Sam swims $a$ lanes in $b$ minutes, so his speed is $s=a/b$, a rational number. After this, the cycle will repeat again, and Sam and Hannah will keep meeting at the edge every $b$ minutes forever.
MiraBernstein
2014-06-16 22:12:58
Let's recap what we know so far. For $s<1$, the generic case is $M=N=1$. The only exception is if $s$ is rational and the two swimmers meet at the edge of the pool at least once. In that case, they will keep meeting at the edge of the pool infinitely many times at regular intervals.
Let's recap what we know so far. For $s<1$, the generic case is $M=N=1$. The only exception is if $s$ is rational and the two swimmers meet at the edge of the pool at least once. In that case, they will keep meeting at the edge of the pool infinitely many times at regular intervals.
MiraBernstein
2014-06-16 22:13:13
Since the interesting case is when $s$ is rational, let's now assume $s = p/q$ in lowest terms. (I don't want to use $a$ and $b$, because, as you'll see in a minute, $a/b$ is not necessarily in lowest terms.) Let's call the two ends of the pool A and Z. If Sam and Hannah first meet at edge A, how can we tell which edge they'll meet at next?
Since the interesting case is when $s$ is rational, let's now assume $s = p/q$ in lowest terms. (I don't want to use $a$ and $b$, because, as you'll see in a minute, $a/b$ is not necessarily in lowest terms.) Let's call the two ends of the pool A and Z. If Sam and Hannah first meet at edge A, how can we tell which edge they'll meet at next?
MiraBernstein
2014-06-16 22:14:54
How can we tell in terms of $p$ and $q$?
How can we tell in terms of $p$ and $q$?
numbersandnumbers
2014-06-16 22:15:49
parity: If both are odd, then Z. Otherwise, A
parity: If both are odd, then Z. Otherwise, A
MiraBernstein
2014-06-16 22:16:01
If $p$ and $q$ are both odd, then after $q$ minutes, both swimmers will be at edge Z, and that will be their next meeting. But if one of $p$ or $q$ is even (they can't both be even, since $p/q$ is in lowest terms), then after $q$ minutes one swimmer will be at A and the other at Z. They'll have to swim another $q$ minutes until they both get back to $A$.
$\qquad$
So what are $M$ and $N$ in these two cases?
If $p$ and $q$ are both odd, then after $q$ minutes, both swimmers will be at edge Z, and that will be their next meeting. But if one of $p$ or $q$ is even (they can't both be even, since $p/q$ is in lowest terms), then after $q$ minutes one swimmer will be at A and the other at Z. They'll have to swim another $q$ minutes until they both get back to $A$.
$\qquad$
So what are $M$ and $N$ in these two cases?
niraekjs
2014-06-16 22:17:55
sorry confused ugh
sorry confused ugh
lucylai
2014-06-16 22:17:55
(q-1,q) and (2q-1,2q) respectively
(q-1,q) and (2q-1,2q) respectively
MiraBernstein
2014-06-16 22:18:32
If $p$ and $q$ are both odd, then Hannah meets Sam at the edge every $q$ minutes. During each such cycle, she meets him once per lane (i.e. once per minute), but one of those meetings -- the edge meeting -- counts for both the lane before and the lane after. Hannah will meet Sam $q-1$ times every $q$ minutes, so $N=q-1$, $M=q$.
If $p$ and $q$ are both odd, then Hannah meets Sam at the edge every $q$ minutes. During each such cycle, she meets him once per lane (i.e. once per minute), but one of those meetings -- the edge meeting -- counts for both the lane before and the lane after. Hannah will meet Sam $q-1$ times every $q$ minutes, so $N=q-1$, $M=q$.
MiraBernstein
2014-06-16 22:18:42
If one of $p$ and $q$ is even, then Hannah meets Sam at the edge every $2q$ minutes, so, by the same reasoning, $N=2q-1$ and $M=2q$.
If one of $p$ and $q$ is even, then Hannah meets Sam at the edge every $2q$ minutes, so, by the same reasoning, $N=2q-1$ and $M=2q$.
amwmath
2014-06-16 22:19:08
I agree with lucylai (except that I didn't realize that a and b had to be replaced by p and q).
I agree with lucylai (except that I didn't realize that a and b had to be replaced by p and q).
MiraBernstein
2014-06-16 22:19:35
Yes, this is important, because if one of p and q is even, then a=2p and b=2q
Yes, this is important, because if one of p and q is even, then a=2p and b=2q
MiraBernstein
2014-06-16 22:20:15
So it seems that our answer to part (a) is:
$\qquad$ * If $s$ is irrational then $M=N=1$;
$\qquad$ * If $s=p/q$, with $p$ and $q$ both odd, then $N=q-1$, $M=q$.
$\qquad$ * If $s=p/q$, with either $p$ or $q$ even, then $N=2q-1$, $M=2q$.
Does everyone agree?
So it seems that our answer to part (a) is:
$\qquad$ * If $s$ is irrational then $M=N=1$;
$\qquad$ * If $s=p/q$, with $p$ and $q$ both odd, then $N=q-1$, $M=q$.
$\qquad$ * If $s=p/q$, with either $p$ or $q$ even, then $N=2q-1$, $M=2q$.
Does everyone agree?
niraekjs
2014-06-16 22:20:55
amwmath
2014-06-16 22:20:55
Wait. Doesn't it depend on where Sam was when she started swimming?
Wait. Doesn't it depend on where Sam was when she started swimming?
MiraBernstein
2014-06-16 22:21:16
Yes! When $s$ is rational, our analysis up to now ASSUMED that Sam and Hannah met at the edge at least once (and therefore infinitely many times). But if they never meet at the edge at all, then we're back to $M=N=1$. So now we need to figure out under what conditions they do and don't meet at an edge.
$\qquad$
Yes! When $s$ is rational, our analysis up to now ASSUMED that Sam and Hannah met at the edge at least once (and therefore infinitely many times). But if they never meet at the edge at all, then we're back to $M=N=1$. So now we need to figure out under what conditions they do and don't meet at an edge.
$\qquad$
MiraBernstein
2014-06-16 22:21:24
So you're right to disagree!
So you're right to disagree!
MiraBernstein
2014-06-16 22:21:58
(This part gets a little technical, so bear with me.)
(This part gets a little technical, so bear with me.)
MiraBernstein
2014-06-16 22:22:07
Suppose Hannah first enters the pool when Sam is at a distance $x$ from that edge. For them to meet at an edge, Hannah would have to swim $b$ lanes while Sam swims $a \pm x$ lanes, where $a$ and $b$ are integers.
$\qquad$
Just to make sure we're all on the same page: where did the $\pm$ come from?
Suppose Hannah first enters the pool when Sam is at a distance $x$ from that edge. For them to meet at an edge, Hannah would have to swim $b$ lanes while Sam swims $a \pm x$ lanes, where $a$ and $b$ are integers.
$\qquad$
Just to make sure we're all on the same page: where did the $\pm$ come from?
amwmath
2014-06-16 22:23:36
What direction he is swimming at the start.
What direction he is swimming at the start.
numbersandnumbers
2014-06-16 22:23:36
It depends on in which direction Sam was swimming.
It depends on in which direction Sam was swimming.
daovuquang
2014-06-16 22:23:36
depending on the direction Sam was swimming
depending on the direction Sam was swimming
MiraBernstein
2014-06-16 22:23:46
It's $a+x$ if Sam is initially swimming toward Hannah and $a-x$ if he is initially swimming away from her.
$\qquad$
Are there any further restrictions on $a$ and $b$?
It's $a+x$ if Sam is initially swimming toward Hannah and $a-x$ if he is initially swimming away from her.
$\qquad$
Are there any further restrictions on $a$ and $b$?
MiraBernstein
2014-06-16 22:25:52
No one is giving me an answer....
No one is giving me an answer....
MiraBernstein
2014-06-16 22:26:22
$a$ and $b$ have to be of the same parity; otherwise, Sam and Hannah will get to an edge of the pool at the same time, but it won't be the SAME edge.
$a$ and $b$ have to be of the same parity; otherwise, Sam and Hannah will get to an edge of the pool at the same time, but it won't be the SAME edge.
MiraBernstein
2014-06-16 22:26:36
For what values of $x$ is this possible? Well, we need
$\qquad$
$\qquad s = \frac{p}{q} = \frac{a\pm x}{b}.$
$\qquad$
For what values of $x$ is this possible? Well, we need
$\qquad$
$\qquad s = \frac{p}{q} = \frac{a\pm x}{b}.$
$\qquad$
MiraBernstein
2014-06-16 22:26:47
Solving for $x$, we get
$\qquad$
$\qquad x = \pm\frac{bp-aq}{q}$.
$\qquad$
So clearly $x$ has to be of the form $\frac k q$, for some integer $k$.
Solving for $x$, we get
$\qquad$
$\qquad x = \pm\frac{bp-aq}{q}$.
$\qquad$
So clearly $x$ has to be of the form $\frac k q$, for some integer $k$.
MiraBernstein
2014-06-16 22:27:01
The question now is: which integers $k$ between 0 and $q$ can be expressed in the form $bp-aq$, where $a$ and $b$ are either both even or both odd?
The question now is: which integers $k$ between 0 and $q$ can be expressed in the form $bp-aq$, where $a$ and $b$ are either both even or both odd?
MiraBernstein
2014-06-16 22:27:12
Before we go on, here is a famous theorem from elementary number theory: If $p$ and $q$ are relatively prime (which in our case they are), then there exist positive integers $c$ and $d$ such that $cp-dq=1$.
$\qquad$
I'm not going to prove this theorem here. (It's a pretty easy consequence of the Euclidean algorithm.) But let's use it to answer our question about $k$.
Before we go on, here is a famous theorem from elementary number theory: If $p$ and $q$ are relatively prime (which in our case they are), then there exist positive integers $c$ and $d$ such that $cp-dq=1$.
$\qquad$
I'm not going to prove this theorem here. (It's a pretty easy consequence of the Euclidean algorithm.) But let's use it to answer our question about $k$.
MiraBernstein
2014-06-16 22:27:39
The easier case is when $p$ and $q$ are both odd. What's the restriction on $k$ that results from $a$ and $b$ both having to be the same parity?
The easier case is when $p$ and $q$ are both odd. What's the restriction on $k$ that results from $a$ and $b$ both having to be the same parity?
distortedwalrus
2014-06-16 22:28:02
even
even
niraekjs
2014-06-16 22:28:02
Even
Even
MiraBernstein
2014-06-16 22:28:28
If $p$ and $q$ are both odd, then $k=bp-aq$ has to be even, since $a$ and $b$ are of the same parity. Conversely, can we write any even integer $k$ in this form?
If $p$ and $q$ are both odd, then $k=bp-aq$ has to be even, since $a$ and $b$ are of the same parity. Conversely, can we write any even integer $k$ in this form?
distortedwalrus
2014-06-16 22:29:01
yes by that lemma
yes by that lemma
MiraBernstein
2014-06-16 22:29:25
Using $c$ and $d$ from the theorem I just quoted, let $b=kc$ and $a=kd$. Then $bp-aq = k(cp-dq)=k$. Since $k$ is even, both $a$ and $b$ are even as well. Thus, when $p$ and $q$ are both odd, Hannah and Sam will meet at an edge if and only if Sam's initial position $x$ is an EVEN multiple of $1/q$.
Using $c$ and $d$ from the theorem I just quoted, let $b=kc$ and $a=kd$. Then $bp-aq = k(cp-dq)=k$. Since $k$ is even, both $a$ and $b$ are even as well. Thus, when $p$ and $q$ are both odd, Hannah and Sam will meet at an edge if and only if Sam's initial position $x$ is an EVEN multiple of $1/q$.
MiraBernstein
2014-06-16 22:29:37
The case when one of $p$ or $q$ is even requires a similar, but slightly trickier, argument. I'm going to skip it here in the interest of time, but the upshot is that Hannah and Sam will meet at an edge if and only Sam's initial position $x$ is any multiple of $1/q$ (even or odd).
The case when one of $p$ or $q$ is even requires a similar, but slightly trickier, argument. I'm going to skip it here in the interest of time, but the upshot is that Hannah and Sam will meet at an edge if and only Sam's initial position $x$ is any multiple of $1/q$ (even or odd).
MiraBernstein
2014-06-16 22:29:52
So here is our final solution to part (a):
$\qquad$ * If $s=p/q$ in lowest terms, with both $p$ and $q$ odd, and Sam's initial position is $2k/q$ for some $k$, then $M=q$ and $N=q-1$.
$\qquad$ * If $s=p/q$ in lowest terms, with either $p$ or $q$ even, and Sam's initial position is $k/q$ for some $k$, then $M=2q$ and $N=2q-1$.
$\qquad$ * Otherwise, $M=N=1$.
$\qquad$
Any questions on part (a)?
So here is our final solution to part (a):
$\qquad$ * If $s=p/q$ in lowest terms, with both $p$ and $q$ odd, and Sam's initial position is $2k/q$ for some $k$, then $M=q$ and $N=q-1$.
$\qquad$ * If $s=p/q$ in lowest terms, with either $p$ or $q$ even, and Sam's initial position is $k/q$ for some $k$, then $M=2q$ and $N=2q-1$.
$\qquad$ * Otherwise, $M=N=1$.
$\qquad$
Any questions on part (a)?
nebulagirl
2014-06-16 22:30:25
How would Bob and Hannah meet just once?
How would Bob and Hannah meet just once?
MiraBernstein
2014-06-16 22:30:34
(Bob = Sam)
(Bob = Sam)
MiraBernstein
2014-06-16 22:31:39
For example, if Bob swims at speed $1/\pi$ and Hannah enters the pool when he is $1/\pi$ away form the opposite edge of the pool.
For example, if Bob swims at speed $1/\pi$ and Hannah enters the pool when he is $1/\pi$ away form the opposite edge of the pool.
MiraBernstein
2014-06-16 22:31:54
Then they'll meet once at the opposite edge, and never again, since his speed is irrational
Then they'll meet once at the opposite edge, and never again, since his speed is irrational
MiraBernstein
2014-06-16 22:32:25
OK, Part (b) deals with the case $s>1$. Fortunately, we don't have to redo everything we did for part (a). Why not?
OK, Part (b) deals with the case $s>1$. Fortunately, we don't have to redo everything we did for part (a). Why not?
nebulagirl
2014-06-16 22:33:15
Just do it from Bob's perspective.
Just do it from Bob's perspective.
Akababa
2014-06-16 22:33:15
scale their speeds
scale their speeds
64138luc
2014-06-16 22:33:15
Just scale the case, view Hanna as the slow swimmer
Just scale the case, view Hanna as the slow swimmer
lucylai
2014-06-16 22:33:15
Sam and Hannah switch roles
Sam and Hannah switch roles
MiraBernstein
2014-06-16 22:33:25
We can simply interchange the roles of Hannah and Sam by rescaling time. Let a "Sam-minute" be a length of time equal to $1/s$ regular minutes. Then Sam's speed is one lane per "Sam-minute" and Hannah's speed is $1/s< 1$ lanes per "Sam-minute", so everything we said in part (a) applies, with the roles reversed.
We can simply interchange the roles of Hannah and Sam by rescaling time. Let a "Sam-minute" be a length of time equal to $1/s$ regular minutes. Then Sam's speed is one lane per "Sam-minute" and Hannah's speed is $1/s< 1$ lanes per "Sam-minute", so everything we said in part (a) applies, with the roles reversed.
MiraBernstein
2014-06-16 22:33:41
In the generic case, Hannah and Sam will meet once every "Sam-minute" (which is more often than once per minute).
In the generic case, Hannah and Sam will meet once every "Sam-minute" (which is more often than once per minute).
MiraBernstein
2014-06-16 22:33:51
If $s=p/q$ in lowest terms, then Hannah's speed in "Sam-minutes" is $1/s=q/p$. So, under the right initial condition, Hannah and Sam will meet $p-1$ times every $p$ "Sam-minutes" (which is $p/s =q$ minutes) or $2p-1$ times every $2p$ "Sam-minutes" (which is $2p/s = 2q$ minutes), depending on the parity of $p$ and $q$.
$\qquad$
Note that this is still at least once per minute on average.
If $s=p/q$ in lowest terms, then Hannah's speed in "Sam-minutes" is $1/s=q/p$. So, under the right initial condition, Hannah and Sam will meet $p-1$ times every $p$ "Sam-minutes" (which is $p/s =q$ minutes) or $2p-1$ times every $2p$ "Sam-minutes" (which is $2p/s = 2q$ minutes), depending on the parity of $p$ and $q$.
$\qquad$
Note that this is still at least once per minute on average.
MiraBernstein
2014-06-16 22:34:34
We basically gave credit here to anyone who said "switch the swimmers", even if they didn't go into details
We basically gave credit here to anyone who said "switch the swimmers", even if they didn't go into details
MiraBernstein
2014-06-16 22:34:42
Finally, we come to part (c). We want to know what value of $s>0$ minimizes $N/M$, the average frequency of encounters in the long run. First of all, should we take $s$ to be greater or less than 1? Rational or irrational?
Finally, we come to part (c). We want to know what value of $s>0$ minimizes $N/M$, the average frequency of encounters in the long run. First of all, should we take $s$ to be greater or less than 1? Rational or irrational?
6stars
2014-06-16 22:35:55
So are they swimming through lanes or in them (parallel to them?) I'm having trouble visualizing this
So are they swimming through lanes or in them (parallel to them?) I'm having trouble visualizing this
clarencechenct
2014-06-16 22:35:55
rational
rational
clarencechenct
2014-06-16 22:35:55
less than 1
less than 1
numbersandnumbers
2014-06-16 22:35:55
less, rational
less, rational
lucylai
2014-06-16 22:36:13
less than 1 because greater than 1 always results in more than one meeting per minute
less than 1 because greater than 1 always results in more than one meeting per minute
MiraBernstein
2014-06-16 22:36:18
We saw in part (b) that if $s>1$, we always have $N/M \geq 1$. It's also clear that for $s=1$, we always have $N=M=1$ (or else a continuous non-stop encounter, which is surely bad).
$\qquad$
On the other hand, in part (a) we saw that for rational $s<1$, we can get $N/M < 1$. Thus we only need to consider rational $s<1$.
We saw in part (b) that if $s>1$, we always have $N/M \geq 1$. It's also clear that for $s=1$, we always have $N=M=1$ (or else a continuous non-stop encounter, which is surely bad).
$\qquad$
On the other hand, in part (a) we saw that for rational $s<1$, we can get $N/M < 1$. Thus we only need to consider rational $s<1$.
MiraBernstein
2014-06-16 22:36:29
How do we find the particular $s=p/q$ that minimizes $N/M$?
How do we find the particular $s=p/q$ that minimizes $N/M$?
numbersandnumbers
2014-06-16 22:37:32
minimize q and make it odd
minimize q and make it odd
amwmath
2014-06-16 22:37:32
Use the result from part (a).
Use the result from part (a).
MiraBernstein
2014-06-16 22:37:47
We always have $N=M-1$, so we want to minimize $M$. If $q = 2$, then $M = 4$. If $q=3$, then $M=3$ or $M=6$, depending on $p$. If $q>3$, then $M>3$. Thus we want $q=3$, with $p$ odd; so $p=1$.
We always have $N=M-1$, so we want to minimize $M$. If $q = 2$, then $M = 4$. If $q=3$, then $M=3$ or $M=6$, depending on $p$. If $q>3$, then $M>3$. Thus we want $q=3$, with $p$ odd; so $p=1$.
MiraBernstein
2014-06-16 22:38:03
We conclude that from Hannah's point of view, the optimal speed for Sam is $1/3$. In this case, she'll meet him only 2 times every 2 minutes. She'll still need to time her entry correctly, but the problem explicitly tells us not to worry about this.
We conclude that from Hannah's point of view, the optimal speed for Sam is $1/3$. In this case, she'll meet him only 2 times every 2 minutes. She'll still need to time her entry correctly, but the problem explicitly tells us not to worry about this.
MiraBernstein
2014-06-16 22:38:28
That's it for #4, and I think we should call it a day!
That's it for #4, and I think we should call it a day!
MiraBernstein
2014-06-16 22:38:43
Thanks to everyone who stayed so late and kept answering questions
Thanks to everyone who stayed so late and kept answering questions
lucylai
2014-06-16 22:39:08
was there a solution for 7c?
was there a solution for 7c?
MiraBernstein
2014-06-16 22:39:26
For 7c, no one found anything better than what we had found
For 7c, no one found anything better than what we had found
MiraBernstein
2014-06-16 22:39:48
which was a number of voters that increased linearly in the number of candidates
which was a number of voters that increased linearly in the number of candidates
amwmath
2014-06-16 22:39:56
Where would we find the solutions to the rest?
Where would we find the solutions to the rest?
MiraBernstein
2014-06-16 22:40:16
I will type them up and we'll post them on the Mathcamp webpage.
I will type them up and we'll post them on the Mathcamp webpage.
MiraBernstein
2014-06-16 22:40:51
Thanks, Marisa!
Thanks, Marisa!
amwmath
2014-06-16 22:40:59
When will they be out?
When will they be out?
MiraBernstein
2014-06-16 22:41:03
A few days?
A few days?
MiraBernstein
2014-06-16 22:41:34
OK, guys, thanks again! I'm off. Hope to see some of you at MC this summer (or a future summer)!
OK, guys, thanks again! I'm off. Hope to see some of you at MC this summer (or a future summer)!
MarisaD
2014-06-16 22:41:51
Thanks for coming, everybody!
Thanks for coming, everybody!
Akababa
2014-06-16 22:42:26
bye!
bye!
happiface
2014-06-16 22:42:26
thanks!!!
thanks!!!
tiko1004
2014-06-16 22:42:26
Thank You!
Thank You!
64138luc
2014-06-16 22:42:32
Thank you very much!
Thank you very much!
ProfessorPi
2014-06-16 22:43:03
Have a nice summer!
Have a nice summer!
bengals
2014-06-16 22:43:03
thanks
thanks
Mualpha7
2014-06-16 22:43:03
Thanks!!!
Thanks!!!
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.
