Canada/USA Mathcamp Qualifying Quiz

Go back to the Math Jam Archive

Copyright © 2017 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!
rrusczyk 2014-06-16 19:54:50
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.
rrusczyk 2014-06-16 20:02:23
Are you ready for some interesting math?
ninjataco 2014-06-16 20:02:40
YEAH!
jhuang967 2014-06-16 20:02:40
Yes.
tiko1004 2014-06-16 20:02:40
yez
64138luc 2014-06-16 20:02:40
yes
distortedwalrus 2014-06-16 20:02:40
yes
rrusczyk 2014-06-16 20:02:45
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!
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 .
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.
rrusczyk 2014-06-16 20:03:17
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.
rrusczyk 2014-06-16 20:03:38
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.
rrusczyk 2014-06-16 20:03:57
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.
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).
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!)
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.
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.
minimario 2014-06-16 20:05:13
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.
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.
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.
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
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.)
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!
NeilOnnsu 2014-06-16 20:06:54
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.
MiraBernstein 2014-06-16 20:07:31
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.
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.
MiraBernstein 2014-06-16 20:08:13
Let's start with part (a). Is it possible?
ChilledLemonade 2014-06-16 20:08:28
yes
danusv 2014-06-16 20:08:28
Yes
chessderek 2014-06-16 20:08:28
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!)
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?
loconate 2014-06-16 20:09:31
Yes
ChilledLemonade 2014-06-16 20:09:31
use the floor or ceiling function
Akababa 2014-06-16 20:09:31
2n and 2n+1 jump to n!
amwmath 2014-06-16 20:09:31
Halve it and round up. (Or down.)
distortedwalrus 2014-06-16 20:09:31
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?
murfel 2014-06-16 20:10:14
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
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?
64138luc 2014-06-16 20:11:44
Proove it cannot be done in a bounded area
Moonlight243 2014-06-16 20:11:44
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.
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
jhuang967 2014-06-16 20:11:44
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?
mathlover3737 2014-06-16 20:12:38
a very large square
distortedwalrus 2014-06-16 20:12:38
a 500 x 500 square
amwmath 2014-06-16 20:12:38
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?
amwmath 2014-06-16 20:13:50
They all came from a 1200 x 1200 square.
mathlover3737 2014-06-16 20:13:50
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
rohana 2014-06-16 20:13:50
1200*1200
shipeiyang1708 2014-06-16 20:13:50
within the 1000 by 1000 and a 100 inch radius around the square
gedt11 2014-06-16 20:13:50
a 1200*1200square
happiface 2014-06-16 20:14:05
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.
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.
MiraBernstein 2014-06-16 20:14:58
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$!
MiraBernstein 2014-06-16 20:15:22
True -- but no reason economize!
NeilOnnsu 2014-06-16 20:16:00
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
joshualee2000 2014-06-16 20:16:00
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
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.
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.
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).
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.
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!
ukulifeguard 2014-06-16 20:17:29
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
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
MiraBernstein 2014-06-16 20:18:18
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
MiraBernstein 2014-06-16 20:18:27
Exactly
loconate 2014-06-16 20:18:37
Its like jenga
MiraBernstein 2014-06-16 20:18:42
Hmm
MiraBernstein 2014-06-16 20:18:53
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.)
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$.
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$?
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 )
jhuang967 2014-06-16 20:20:55
$R_{t+1}=2R_t+C_t$
NeilOnnsu 2014-06-16 20:20:55
R_t+1 = 2R_t + C_t
distortedwalrus 2014-06-16 20:20:55
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}$?
64138luc 2014-06-16 20:21:40
4C_t
ninjataco 2014-06-16 20:21:40
$4C_t$
Sesquipedalian 2014-06-16 20:21:40
$C_{t+1} = 4C_t$
mjuvekar 2014-06-16 20:21:40
4C_t
mathwizard888 2014-06-16 20:21:40
$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.
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?
nisrus 2014-06-16 20:22:44
No cyborgs
NeilOnnsu 2014-06-16 20:22:44
No cyborgs
nebulagirl 2014-06-16 20:22:44
We can't have any cyborgs.
Philip7086 2014-06-16 20:22:44
C_t = 0
johnnyc1729 2014-06-16 20:22:44
0 cyclops
MiraBernstein 2014-06-16 20:22:52
Wait, where did the cyclops come from?
MiraBernstein 2014-06-16 20:22:55
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?
MiraBernstein 2014-06-16 20:23:17
Any restriction on those?
Pythonprogrammer 2014-06-16 20:23:28
Any number
genesis2 2014-06-16 20:23:28
doesn't matter
imath34 2014-06-16 20:23:28
any #
amwmath 2014-06-16 20:23:28
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.
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?
jhuang967 2014-06-16 20:24:38
$4R_t=2R_t+C_t$
ukulifeguard 2014-06-16 20:24:38
2R+C=4R
atmchallenge 2014-06-16 20:24:38
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.
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. :)
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?
happiface 2014-06-16 20:26:09
$C_t$
clarencechenct 2014-06-16 20:26:09
C_t
jhuang967 2014-06-16 20:26:09
$C_t=4^t \cdot C_0$
happiface 2014-06-16 20:26:09
$C_t$ since only cyborgs make cyborgs
shipeiyang1708 2014-06-16 20:26:13
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?
ninjataco 2014-06-16 20:27:07
experiment with some terms
magital15 2014-06-16 20:27:07
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
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.
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?
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)
chezbgone2 2014-06-16 20:28:56
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.)
MiraBernstein 2014-06-16 20:29:30
(At least I think it's equivalent)
64138luc 2014-06-16 20:29:47
Don't we need induction to prove it?
MiraBernstein 2014-06-16 20:29:53
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.
ukulifeguard 2014-06-16 20:30:19
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
MiraBernstein 2014-06-16 20:30:53
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?
MiraBernstein 2014-06-16 20:31:45
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$
Moonlight243 2014-06-16 20:31:57
t=1?
chessderek 2014-06-16 20:31:57
t=1
justindong 2014-06-16 20:31:57
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.)
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?
ninjataco 2014-06-16 20:33:21
that it's true for $t+1$
joshualee2000 2014-06-16 20:33:21
that it works for t+1
Philip7086 2014-06-16 20:33:21
that it is right for t+ 1
6stars 2014-06-16 20:33:21
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?
Pythonprogrammer 2014-06-16 20:34:29
R_T+1=2*R_T+C_T
swamih 2014-06-16 20:34:29
$R_{t+1}=2R_t+C_t$
mjuvekar 2014-06-16 20:34:29
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)
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$)
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)
MiraBernstein 2014-06-16 20:35:11
$\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
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?
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?
MiraBernstein 2014-06-16 20:36:39
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!
MiraBernstein 2014-06-16 20:36:55
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.
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?
MiraBernstein 2014-06-16 20:38:08
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?
MiraBernstein 2014-06-16 20:39:23
(Sorry didn't mean to pass those yet)
Technik 2014-06-16 20:40:19
for the doubling one have robots
Technik 2014-06-16 20:40:19
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
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.
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
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.
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!
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$?
NeilOnnsu 2014-06-16 20:41:46
And negative robots?
MiraBernstein 2014-06-16 20:42:21
Yes, that too! The math works anyway.
shipeiyang1708 2014-06-16 20:42:28
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!
MiraBernstein 2014-06-16 20:43:17
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$
NeilOnnsu 2014-06-16 20:43:55
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?
distortedwalrus 2014-06-16 20:44:18
did anyone submit a solution like this?
MiraBernstein 2014-06-16 20:44:28
yes, because...
MiraBernstein 2014-06-16 20:44:35
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?
MiraBernstein 2014-06-16 20:45:23
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
MiraBernstein 2014-06-16 20:45:43
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
MiraBernstein 2014-06-16 20:46:17
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
MiraBernstein 2014-06-16 20:47:08
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
isanimath 2014-06-16 20:47:42
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
MiraBernstein 2014-06-16 20:48:01
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.)
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$?
niraekjs 2014-06-16 20:49:45
7
jhuang967 2014-06-16 20:49:45
$n$ circles. :P
loconate 2014-06-16 20:49:45
n circles
dylanxu1213 2014-06-16 20:49:45
n
gedt11 2014-06-16 20:49:45
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.
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$?
gedt11 2014-06-16 20:51:37
7circles can cover a big circle
RavenclawPrefect 2014-06-16 20:51:37
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
amwmath 2014-06-16 20:51:42
MiraBernstein 2014-06-16 20:51:51
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
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.
MiraBernstein 2014-06-16 20:53:06
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
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?
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
MiraBernstein 2014-06-16 20:55:32
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$.
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$.
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?
amwmath 2014-06-16 20:59:24
We have an upper bound.
gedt11 2014-06-16 20:59:24
f(n)<=min(7,n)
codyj 2014-06-16 20:59:24
$f(n)\le n$
clarencechenct 2014-06-16 20:59:24
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$.
MiraBernstein 2014-06-16 21:00:13

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
jhuang967 2014-06-16 21:00:55
$f(n) = min(n,7)$
mjuvekar 2014-06-16 21:00:55
f(n) = min(7, n)
gedt11 2014-06-16 21:00:55
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.
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$.
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$
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?
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$?
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$
amwmath 2014-06-16 21:03:27
For pentagons and smaller, no circle can cover two vertices.
jhuang967 2014-06-16 21:03:27
More than 1 unit apart.
numbersandnumbers 2014-06-16 21:03:27
more than 1 apart
NeilOnnsu 2014-06-16 21:03:27
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
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$.
MiraBernstein 2014-06-16 21:04:02
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.
amwmath 2014-06-16 21:04:40
They are exactly a distance of 1 apart.
happiface 2014-06-16 21:04:40
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
jhuang967 2014-06-16 21:04:40
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.
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?
MiraBernstein 2014-06-16 21:06:38

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
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)$.
jhuang967 2014-06-16 21:08:11
Diagram, please?
MiraBernstein 2014-06-16 21:08:21
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?
happiface 2014-06-16 21:09:30
hence why i said 12-2k
jhuang967 2014-06-16 21:09:30
Oh - edge-circle segments are LINE segments (silly me).
MiraBernstein 2014-06-16 21:09:52
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?
happiface 2014-06-16 21:10:58
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
distortedwalrus 2014-06-16 21:11:03
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.
MiraBernstein 2014-06-16 21:11:30
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.)
MiraBernstein 2014-06-16 21:12:02
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?
amwmath 2014-06-16 21:13:19
WHAT! ARE YOU KIDDING ME!
distortedwalrus 2014-06-16 21:13:19
are you kidding me.
MiraBernstein 2014-06-16 21:13:58
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$?
numbersandnumbers 2014-06-16 21:15:26
$\cos \dfrac{\pi}{n}$
jhuang967 2014-06-16 21:15:26
$\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
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
MiraBernstein 2014-06-16 21:16:23
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)
jhuang967 2014-06-16 21:18:12
$2 \arcsin \left(\frac{1}{2}\frac{1}{\cos \pi/n} \right)$
NeilOnnsu 2014-06-16 21:18:12
2arcsin(1/(2cos pi/n))
MiraBernstein 2014-06-16 21:18:25
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$.)
MiraBernstein 2014-06-16 21:18:46
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.
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
MiraBernstein 2014-06-16 21:20:34
What is the maximal angle $\alpha$ that this arc can subtend in $C_n$?
jhuang967 2014-06-16 21:24:41
$2\arccos r$
jhuang967 2014-06-16 21:24:41
$2 \arccos r = 2 \pi/n$
numbersandnumbers 2014-06-16 21:24:41
$2 \arccos r = \dfrac{2\pi}{n}$?
forthegreatergood 2014-06-16 21:24:54
is it 2pi/n?
gedt11 2014-06-16 21:24:54
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
MiraBernstein 2014-06-16 21:27:05
http://www.mathcamp.org/2014/quiz/center_arc_angle.jpg
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.
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$.
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/
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?
distortedwalrus 2014-06-16 21:29:51
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.
MiraBernstein 2014-06-16 21:31:17
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!
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
MiraBernstein 2014-06-16 21:32:03
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$.
nebulagirl 2014-06-16 21:32:27
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
MiraBernstein 2014-06-16 21:33:13
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.
MiraBernstein 2014-06-16 21:34:04
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$
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?
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)
MiraBernstein 2014-06-16 21:36:38
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:
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.
nebulagirl 2014-06-16 21:37:23
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
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
MiraBernstein 2014-06-16 21:38:30
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$.
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?
distortedwalrus 2014-06-16 21:40:43
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.
Sesquipedalian 2014-06-16 21:40:43
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
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
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$).
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
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$?
mathwizard888 2014-06-16 21:43:43
A+jm
lucylai 2014-06-16 21:43:43
distortedwalrus 2014-06-16 21:43:43
A+mj
NeilOnnsu 2014-06-16 21:43:43
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$?
justindong 2014-06-16 21:44:32
no
NeilOnnsu 2014-06-16 21:44:32
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)
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$.
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."
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.
MiraBernstein 2014-06-16 21:45:33
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$?
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$?
64138luc 2014-06-16 21:46:54
0
clarencechenct 2014-06-16 21:46:54
0
64138luc 2014-06-16 21:46:54
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$.
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.
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.
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$.
jhuang967 2014-06-16 21:49:37
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$.
MiraBernstein 2014-06-16 21:50:02
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
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$.
clarencechenct 2014-06-16 21:51:29
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.
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?
lucylai 2014-06-16 21:53:07
ncr(2q,q)-2
Jettywang828 2014-06-16 21:53:07
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}$
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$.
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$.
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$.
MiraBernstein 2014-06-16 21:55:34
OK, on to part (c)
MiraBernstein 2014-06-16 21:55:55

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)
MiraBernstein 2014-06-16 21:56:13
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!
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$?
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
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.
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$.
MiraBernstein 2014-06-16 21:58:31
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
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
MiraBernstein 2014-06-16 21:59:48
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
MiraBernstein 2014-06-16 22:00:22
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.
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}.
MiraBernstein 2014-06-16 22:01:33
$\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)
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".
MiraBernstein 2014-06-16 22:02:41
Once we generalize "exceptional" it proceeds as before.
MiraBernstein 2014-06-16 22:02:46
OK, guys, it's 10 pm
MiraBernstein 2014-06-16 22:03:04
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
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.)
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)...
MiraBernstein 2014-06-16 22:05:44
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.
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?
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
danusv 2014-06-16 22:07:13
once
va2010 2014-06-16 22:07:13
once
ukulifeguard 2014-06-16 22:07:13
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.
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.)
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?
niraekjs 2014-06-16 22:08:52
Because she is travelling faster than him
nebulagirl 2014-06-16 22:08:52
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.
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
MiraBernstein 2014-06-16 22:09:33
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
leekkww 2014-06-16 22:10:14
noooo
nebulagirl 2014-06-16 22:10:14
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
RavenclawPrefect 2014-06-16 22:10:14
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?
lucylai 2014-06-16 22:11:17
no because "infinite"
clarencechenct 2014-06-16 22:11:17
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.
MiraBernstein 2014-06-16 22:11:37
What if they meet at the edge more than once?
64138luc 2014-06-16 22:12:25
That means it is a pattern
Akababa 2014-06-16 22:12:25
repeat the pattern!
shipeiyang1708 2014-06-16 22:12:25
it will just happen again
danusv 2014-06-16 22:12:25
Then they will meet there at regular occurences
RavenclawPrefect 2014-06-16 22:12:25
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
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.
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.
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?
MiraBernstein 2014-06-16 22:14:54
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
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?
niraekjs 2014-06-16 22:17:55
sorry confused ugh
lucylai 2014-06-16 22:17:55
(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$.
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$.
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).
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
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?
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?
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$
MiraBernstein 2014-06-16 22:21:24
So you're right to disagree!
MiraBernstein 2014-06-16 22:21:58
(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?
amwmath 2014-06-16 22:23:36
What direction he is swimming at the start.
numbersandnumbers 2014-06-16 22:23:36
It depends on in which direction Sam was swimming.
daovuquang 2014-06-16 22:23:36
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$?
MiraBernstein 2014-06-16 22:25:52
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.
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$
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$.
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?
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$.
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?
distortedwalrus 2014-06-16 22:28:02
even
niraekjs 2014-06-16 22:28:02
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?
distortedwalrus 2014-06-16 22:29:01
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$.
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).
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)?    
nebulagirl 2014-06-16 22:30:25
How would Bob and Hannah meet just once?
MiraBernstein 2014-06-16 22:30:34
(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.
MiraBernstein 2014-06-16 22:31:54
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?
nebulagirl 2014-06-16 22:33:15
Just do it from Bob's perspective.
Akababa 2014-06-16 22:33:15
scale their speeds
64138luc 2014-06-16 22:33:15
Just scale the case, view Hanna as the slow swimmer
lucylai 2014-06-16 22:33:15
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.
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).
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.
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
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?
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
clarencechenct 2014-06-16 22:35:55
rational
clarencechenct 2014-06-16 22:35:55
less than 1
numbersandnumbers 2014-06-16 22:35:55
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
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$.
MiraBernstein 2014-06-16 22:36:29

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
amwmath 2014-06-16 22:37:32
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$.
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.
MiraBernstein 2014-06-16 22:38:28
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
lucylai 2014-06-16 22:39:08
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
MiraBernstein 2014-06-16 22:39:48
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?
MiraBernstein 2014-06-16 22:40:16
I will type them up and we'll post them on the Mathcamp webpage.
MiraBernstein 2014-06-16 22:40:51
Thanks, Marisa!
amwmath 2014-06-16 22:40:59
When will they be out?
MiraBernstein 2014-06-16 22:41:03
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)!
MarisaD 2014-06-16 22:41:51
Thanks for coming, everybody!
Akababa 2014-06-16 22:42:26
bye!
happiface 2014-06-16 22:42:26
thanks!!!
tiko1004 2014-06-16 22:42:26
Thank You!
64138luc 2014-06-16 22:42:32
Thank you very much!
ProfessorPi 2014-06-16 22:43:03
Have a nice summer!
bengals 2014-06-16 22:43:03
thanks
Mualpha7 2014-06-16 22:43:03
Thanks!!!

Copyright © 2017 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.

ACS WASC
ACCREDITED
SCHOOL

Stay Connected

Subscribe to get news and
updates from AoPS, or Contact Us.
© 2017
AoPS Incorporated
Invalid username
Login to AoPS