Canada/USA Mathcamp Qualifying Quiz Math Jam

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


LauraZed 2016-05-18 19:30:11
Hello and welcome to the Canada/USA Qualifying Quiz Math Jam!
Zer0waltz 2016-05-18 19:30:25
hello
skipiano 2016-05-18 19:30:25
Hi!
lcalvert99 2016-05-18 19:30:25
Awesome!!
claserken 2016-05-18 19:30:25
Hi!
reLAXer12 2016-05-18 19:30:27
Hi! Thanks for having us!
LauraZed 2016-05-18 19:30:29
Before I introduce our guests, let me briefly explain how our online classroom works.
LauraZed 2016-05-18 19:30:33
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose.
LauraZed 2016-05-18 19:30:38
Also, you'll find that you can adjust the classroom windows in a variety of ways, and can adjust the font size by clicking the A icons atop the main window.
LauraZed 2016-05-18 19:30:51
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. Many AoPS instructors, assistants, and students are alumni of this outstanding problem, including me! You can learn more about Canada/USA Mathcamp at www.mathcamp.org.
LauraZed 2016-05-18 19:30:59
In this Math Jam, Canada/USA Mathcamp admission committee members will discuss the problems from the 2016 Qualifying Quiz:
LauraZed 2016-05-18 19:31:05
Marisa Debowsky (MarisaD) started teaching at Mathcamp in ?06 and has been the director of the program since 2009. If you have been writing emails to Mathcamp, she's probably been answering them.
LauraZed 2016-05-18 19:31:12
Kevin Carde (KevinCarde) has been teaching at Mathcamp since 2011. He received his PhD in Mathematics from the University of Michigan in 2014 and is now a Software Developer for Mathcamp.
LauraZed 2016-05-18 19:31:19
I'll turn the room over to Marisa now!
MarisaD 2016-05-18 19:31:38
Hi, everybody, and welcome to the (now annual) Mathcamp Qualifying Quiz Jam!
MarisaD 2016-05-18 19:31:51
A big thanks as always to @LauraZed, @rrusczyk, and the AoPS team for hosting us.
MarisaD 2016-05-18 19:32:02
I’ll take a moment to answer a few non-QQ questions that have already come up, and if we have time at the end, I’ll answer more.
BobaFett101 2016-05-18 19:32:05
What was the median score for those accepted?
MarisaD 2016-05-18 19:32:08
The scores aren’t quite linear, so it’s hard to say.
aq1048576 2016-05-18 19:32:14
I know that it isn't May 20th yet, but do you guys have any statistics regarding age/gender at camp yet? Thanks
MarisaD 2016-05-18 19:32:18
Not yet.
Minimons 2016-05-18 19:32:22
do you know where it will be next year?
MarisaD 2016-05-18 19:32:26
Not yet.
pandadude 2016-05-18 19:32:34
what is the acceptance ratio to mathcamp
MarisaD 2016-05-18 19:32:38
We haven’t finished the process yet for this year (there are still students on the waitlist), so it’s too soon to tell, but it’s looking like the admit rate will be just under 15%
MarisaD 2016-05-18 19:32:47
Okay, onto problems!
GeneralCobra19 2016-05-18 19:32:50
Yay problems!
MarisaD 2016-05-18 19:32:56
Kevin and I are here to talk about the Mathcamp 2016 QQ. To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/2016/qquiz.php
MarisaD 2016-05-18 19:33:06
The Quiz problems are written by Mathcamp alumni and staff each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
MarisaD 2016-05-18 19:33:12
If you applied this year, I recommend having your solutions open. That way, you can reply more quickly to the questions I ask of the room. And we're expecting you all to pitch in to the solutions!
MarisaD 2016-05-18 19:33:17
Students can use LaTeX in this classroom, just like on the message board. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We know that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We know that $\frac{1}{2} +\frac{1}{3} = \frac{5}{6}$.
MarisaD 2016-05-18 19:33:27
Also, as @LauraZed pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
MarisaD 2016-05-18 19:33:42
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, you'll find lots of info on our website (e.g., at http://mathcamp.org/gettoknowmathcamp/ ), or check out the AoPS Jam about the program and the application process from a few weeks ago: http://www.artofproblemsolving.com/school/mathjams-transcripts?id=402.
MarisaD 2016-05-18 19:33:50
If we don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS at http://www.artofproblemsolving.com/community/c135 .
MarisaD 2016-05-18 19:33:55
We've got a lot to cover, so let's get started! We've set an ambitious goal of keeping this Jam to 90 minutes (but I'm putting the over/under at 2 hours…).
MarisaD 2016-05-18 19:34:01
Ready?
MarisaD 2016-05-18 19:34:02
PROBLEM 1: Alchemy
MarisaD 2016-05-18 19:34:08
It is the future, and you are working as an alchemist in the depths of the Earth's core. You work in the business of turning silver into gold and back. Each silver piece is worth 1 dollar; each gold piece is worth $\phi = \frac{1 + \sqrt{5}}{2}$ dollars.
MarisaD 2016-05-18 19:34:13
You start with a single piece of silver. On your first day of the job, you turn the silver piece into a gold piece. On each successive day, you turn each silver piece from the previous day into a gold piece, and each gold piece from the previous day into two pieces, one silver and one gold. So at the end of day 1, you have 1 gold piece; at the end of day 2, you have 1 gold piece and 1 silver piece; at the end of day 3, you have 2 gold pieces and 1 silver piece. Prove that at the end of day $n$, your treasure is worth $\phi^n$ dollars for all positive integers $n$.
MarisaD 2016-05-18 19:34:27
PROBLEM 1 SOLUTION
MarisaD 2016-05-18 19:34:35
Let me start by walking you through one way of coming up with (and rigorously proving!) a solution, and then I'll briefly point out some other approaches people took.
MarisaD 2016-05-18 19:34:44
We want to prove that at the end of day $n$, our treasure is worth $\phi^n$ dollars.
MarisaD 2016-05-18 19:34:50
When I started approaching this problem, I thought: we want to know that at the end of day 6, we have $\phi^6$ dollars of treasure... at the end of day 7, we have $\phi^7$ dollars of treasure... so we're hoping that every day, the value of our treasure gets multiplied by $\phi$. That sounds like something we can prove.
MarisaD 2016-05-18 19:35:07
There's probably something special about $\phi$; if gold pieces were worth, say, 5 dollars, we might not get this elegant "value of $5^n$ on day $n$" behavior. So: let's take a detour into properties of $\phi$.
MarisaD 2016-05-18 19:35:13
If you read about $\phi$ on Wikipedia, you'll find that it satisfies the equation $\phi^2=\phi+1$.
MarisaD 2016-05-18 19:35:18
Let's verify that fact with some quick algebra:
MarisaD 2016-05-18 19:35:22
\begin{align*}
\phi&=\tfrac{1+\sqrt5}2,\\
2\phi&=1+\sqrt5,\\
2\phi-1&=\sqrt5,\\
4\phi^2-4\phi+1&=5,\\
4\phi^2&=4\phi+4,\\
\phi^2&=\phi+1.
\end{align*}
MarisaD 2016-05-18 19:35:41
Okay, now, armed with this nice fact about $\phi$, we can get back to our alchemy question: we want to know about the value of our treasure.
MarisaD 2016-05-18 19:36:02
Everybody with me on the statement and the goal?
MarisaD 2016-05-18 19:36:16
Great! Okay, so: Let's say that, at some point, you start the day with $x$ silver pieces and $y$ gold pieces. How many dollars is your treasure worth at the beginning of that day?
claserken 2016-05-18 19:36:56
$x+\phi y$
hliu70 2016-05-18 19:36:56
x+y(phi)
CATAPHRAT 2016-05-18 19:36:56
x+phi*y
Shri333 2016-05-18 19:36:56
x + phi*y
speck 2016-05-18 19:36:56
$x + \phi y$
lcalvert99 2016-05-18 19:36:56
y*phi+x
MarisaD 2016-05-18 19:36:58
Yep: the value of your precious metal is $x+\phi y$ dollars at the beginning of the day.
MarisaD 2016-05-18 19:37:04
Okay, so what happens at the end of the day? The $x$ silver pieces turn into $x$ gold pieces, and the $y$ gold pieces turn into $y$ silver pieces and $y$ gold pieces, for a total of $y$ silver pieces and $x+y$ gold pieces. How much is your treasure worth now?
hliu70 2016-05-18 19:37:43
y+(x+y)phi
aopssolver2 2016-05-18 19:37:43
This is like fibonacci!!
aq1048576 2016-05-18 19:37:43
$\phi x+y+\phi y$
Mario2357 2016-05-18 19:37:43
y+(x+y)phi
sunny2000 2016-05-18 19:37:43
y+(x+y)phi
speck 2016-05-18 19:37:43
$y + \phi (x+y)$
CATAPHRAT 2016-05-18 19:37:43
y+(x+y)phi
GeneralCobra19 2016-05-18 19:37:43
y+phi(x+y)
Shri333 2016-05-18 19:37:43
x*phi + y + y*phi
rb100 2016-05-18 19:37:43
$\phi y + \phi x$
claserken 2016-05-18 19:37:43
$y+\phi\cdot(x+y)$
MarisaD 2016-05-18 19:37:50
Yes: at the end of the day, your treasure is worth $y+\phi(x+y)=\phi x+(\phi+1)y$ dollars.
MarisaD 2016-05-18 19:37:58
Can we show that the value at the end of the day is $\phi$ times the value at the beginning of the day?
Shri333 2016-05-18 19:38:31
yes
CATAPHRAT 2016-05-18 19:38:31
yes
hliu70 2016-05-18 19:38:31
phi+1=phi^2
CATAPHRAT 2016-05-18 19:38:31
phi+1=phi^2
speck 2016-05-18 19:38:34
$\phi + 1 = \phi^2$, so we substitute that and factor to $\phi \left( x + \phi y \right)$
MarisaD 2016-05-18 19:38:45
Right: $$ \phi x+(\phi+1)y=\phi x+\phi^2 y=\phi(x+\phi y) $$
(That's where we get to use our fact about $\phi$.)
MarisaD 2016-05-18 19:39:02
Now, to formally finish this argument, let's use induction to prove that at the end of day $n$, our treasure is worth $\phi^n$ dollars for all positive integers $n$.
MarisaD 2016-05-18 19:39:07
(If you aren't familiar with induction, check out: http://artofproblemsolving.com/wiki/index.php?title=Induction and https://en.wikipedia.org/wiki/Mathematical_induction ).
MarisaD 2016-05-18 19:39:17
What's our base case?
Shri333 2016-05-18 19:39:22
day 1?
GeneralCobra19 2016-05-18 19:39:22
1
claserken 2016-05-18 19:39:36
$n=1$
ephshal 2016-05-18 19:39:36
day 1?
MarisaD 2016-05-18 19:39:39
Right, our base case is day 1. At the end of day $1$, we have $1$ gold piece, worth $\phi=\phi^1$.
MarisaD 2016-05-18 19:39:44
What's our inductive hypothesis?
hliu70 2016-05-18 19:40:50
each day after, it will be worth phi^n
awesomeclaw 2016-05-18 19:40:50
If the value of the treasure is $\phi^n$ on day $n$, then the value of the treasure on day $n+1$ is $\phi^{n+1}$.
speck 2016-05-18 19:40:50
If day $n$ is worth $\phi^n$, then day $n+1$ is worth $\phi \cdot \phi^n = \phi^{n+1}$
pandadude 2016-05-18 19:40:50
D(n+1)/Dn=phi
MarisaD 2016-05-18 19:41:06
Great, you guys are on top of this.
MarisaD 2016-05-18 19:41:07
Assume for induction that at the end of day $k$, our treasure is worth $\phi^k$. We want to show that at the end of day $k+1$, our treasure is worth $\phi^{k+1}$.
claserken 2016-05-18 19:41:28
It must be because we just showed it above
MarisaD 2016-05-18 19:41:30
Exactly!
MarisaD 2016-05-18 19:41:31
We have already shown that, each day, the value of the treasure gets multiplied by $\phi$, so at the end of day $k+1$, our treasure is worth $\phi\cdot\phi^k=\phi^{k+1}$, as desired.
MarisaD 2016-05-18 19:41:39
Therefore, for any positive integer $n$, our treasure at the end of day $n$ is worth $\phi^n$. QED.
Shri333 2016-05-18 19:41:52
how did we show it above?
MarisaD 2016-05-18 19:42:04
Well, the key observation was above: the relationship between day $n$ and day $n+1$.
MarisaD 2016-05-18 19:42:12
Now, there are lots of other ways to approach this problem. (We saw complete and correct proofs using Taylor Series, eigenvalues of matrices... all sorts of great stuff!)
MarisaD 2016-05-18 19:42:20
The most common alternative was to notice a Fibonacci pattern among the quantities of silver and gold, and then use a closed form for $F_n$ to calculate the value of treasure on day $n$. This is great as long as you fully justify the pattern that you see (just like we fully justified here that every day, the value of our treasure gets multiplied by $\phi$).
MarisaD 2016-05-18 19:42:32
Ready? Over to KevinCarde for problem 2.
KevinCarde 2016-05-18 19:42:49
Thanks, MarisaD, and hello everyone!
KevinCarde 2016-05-18 19:43:03
PROBLEM 2: Francisco and Savannah's Game
KevinCarde 2016-05-18 19:43:17
Francisco and Savannah are playing a game with two tokens, which are placed on the squares of a rectangular grid of arbitrary size, as shown in the two figures below. The two tokens must be in different rows and columns. The players take turns moving a token of their choice to any different square (not necessarily just an adjacent one) satisfying the following constraints:
KevinCarde 2016-05-18 19:43:27
* Tokens can never be moved upward or to the right.
* The row ordering must be preserved: if one token is above the other, it must stay above the other.
* The column ordering must be preserved: if one token is to the right of the other, it must stay to the right of the other.
KevinCarde 2016-05-18 19:43:35
Francisco goes first. Whichever player has no legal moves (with either token) loses.
KevinCarde 2016-05-18 19:43:41
a) Suppose one token begins above and to the right of the other, as in the figure on the left below. (The constraints require that the two tokens stay in that order.) For which starting positions does Francisco win and for which does Savannah win? What is the winning strategy in each case?
KevinCarde 2016-05-18 19:43:48
b) Do the same analysis assuming one token begins below and to the right of the other, as the figure on the right below. (The constraints require that the two tokens stay in that order.)
KevinCarde 2016-05-18 19:43:56
http://www.mathcamp.org/2016/math_jam/problem-2-a.png http://www.mathcamp.org/2016/math_jam/problem-2-b.png
KevinCarde 2016-05-18 19:44:27
I'll give you all a moment to read through the problem, and then we'll talk about some tricky interpretation issues with this one
KevinCarde 2016-05-18 19:45:01
NOTES ON PROBLEM 2
KevinCarde 2016-05-18 19:45:07
This problem requires very careful reading! There were many incorrect assumptions made that were not actually part of the rules of the game. Here are some important things to note:
KevinCarde 2016-05-18 19:45:25
* The board can be any rectangular size, not just the 3 rows and 4 columns shown in the examples.
* The tokens can start anywhere, subject to the constraints mentioned in each part (a) and (b).
* Tokens can move down and left simultaneously -- they don't just have to move like a castle in chess. For example, in the example image on the right, Francisco could move the top token left 2 and down 1 as a single move.
* Each player can move either token -- there's no assignment of players to token. Moreover, they can change which token they use from turn to turn, so just because Fernando starts with one token doesn't mean he has to use it again later.
ProGameXD 2016-05-18 19:45:31
How many tokens can be moved per turn?
KevinCarde 2016-05-18 19:45:38
Each player moves a single token each turn.
KevinCarde 2016-05-18 19:46:17
I'm seeing a lot of messages about winning on these particular boards, but keep in mind that we want a strategy that works for larger boards and different starting positions as well!
KevinCarde 2016-05-18 19:46:45
PROBLEM 2a SOLUTION
KevinCarde 2016-05-18 19:46:56
Let's now start talking about Part (a), where one token is above and to the right of the other. Where are the tokens when the game ends? (I'm already seeing some answers before I've asked!)
awesomeclaw 2016-05-18 19:47:58
The bottom left token has to end up in the bottom left square
hliu70 2016-05-18 19:47:58
(0,0) (1,1)
fishy15 2016-05-18 19:47:58
in a corner?
Yaksher 2016-05-18 19:47:58
Bottom Left corner and 1 to the right and up from there.
WeiXu27617 2016-05-18 19:47:58
lower left corner
KevinCarde 2016-05-18 19:48:05
The tokens must both be in the bottom left, like this:
http://www.mathcamp.org/2016/math_jam/solution-2-a.png
KevinCarde 2016-05-18 19:48:18
If the tokens are in these positions, then the next player loses, as he or she has no valid moves.
KevinCarde 2016-05-18 19:48:29
(I've seen some questions about how to win -- you win if the other player can't make a move!)
KevinCarde 2016-05-18 19:48:47
Now, suppose one token is all the way in the bottom left like above, but the other is somewhere else. Who wins?
fishy15 2016-05-18 19:49:10
the first person (if good strategy)
ioanandrei 2016-05-18 19:49:10
next player
Mario2357 2016-05-18 19:49:10
the person whose turn it is
alismith01 2016-05-18 19:49:10
Francisco
awesomeclaw 2016-05-18 19:49:10
the person making the move, since they can just put it in the final position
KevinCarde 2016-05-18 19:49:30
Right -- the player moving next (the first player, Francisco, whatever word you want to use!) can move into the ending position we just talked about.
KevinCarde 2016-05-18 19:49:38
We can summarize this in the following diagram:
http://www.mathcamp.org/2016/math_jam/solution-2-b.png
(with the F labels continuing off upwards and rightwards)
KevinCarde 2016-05-18 19:49:43
If the other token is in an F position, the first player wins; if it's in an S position, the second player wins.
KevinCarde 2016-05-18 19:50:01
Now let's consider a general starting position, where the only requirement is that one token is above and to the right of the other. We make the following claim:
Savannah wins if one token is immediately above and to the right of the other, and Francisco wins otherwise.
KevinCarde 2016-05-18 19:50:12
(Several of you have already reached that conclusion!)
KevinCarde 2016-05-18 19:50:23
(And recall that Francisco plays First, Savannah Second)
KevinCarde 2016-05-18 19:50:37
If one token is immediately above and to the right of the other, Francisco must (by the rules of the game) move the lower left token somewhere further down and left. Where should Savannah move?
hliu70 2016-05-18 19:51:21
one up and one over
fishy15 2016-05-18 19:51:21
right next to it diagonally
aopssolver2 2016-05-18 19:51:21
copy
turnip123 2016-05-18 19:51:21
The other piece immediately above and to the right
Shri333 2016-05-18 19:51:21
right up
KevinCarde 2016-05-18 19:51:23
Right -- Savannah matches Francisco's move by placing the upper right token immediately above and to the right of the other again. They continue this way until finally Francisco moves a token into the lower left corner, Savannah matches him by moving the other token into the S position above, and Francisco has no moves -- Savannah wins!
KevinCarde 2016-05-18 19:51:52
What if we're not in this case?
KevinCarde 2016-05-18 19:52:09
What should Francisco do if the other token does not begin immediately above and to the right of the other?
Yaksher 2016-05-18 19:52:29
Player one wins by always moving (if the coords of the lower left token are (x,y) the upper right token to (x+1,y+1)
Shri333 2016-05-18 19:52:29
Francisco could win
ephshal 2016-05-18 19:52:29
Then fransisco makes it this case
hliu70 2016-05-18 19:52:29
move it to the spot one up and one over
Zer0waltz 2016-05-18 19:52:29
move it there
Mario2357 2016-05-18 19:52:39
well then the person going first makes it go in that position
KevinCarde 2016-05-18 19:52:45
Right -- Francisco moves into that position.
KevinCarde 2016-05-18 19:52:50
Now Savannah is forced to move the lower left token, and Francisco can match her moves the same way she matched his in the other case. The end result is that Francisco wins!
Shri333 2016-05-18 19:53:06
cool
aopssolver2 2016-05-18 19:53:06
KevinCarde 2016-05-18 19:53:13
So we've shown what we wanted: Savannah wins if one token is immediately above and to the right of the other, and Francisco wins otherwise.
ephshal 2016-05-18 19:53:25
Wait, can fransisco lose in this case?
KevinCarde 2016-05-18 19:53:37
Francisco could lose by playing badly, but he does have a winning strategy that we described!
claserken 2016-05-18 19:54:06
Are we assuming that they are always making the smartest moves?
KevinCarde 2016-05-18 19:54:18
Yes -- we're trying to figure out what the smartest moves are for them!
KevinCarde 2016-05-18 19:54:53
I'm seeing a few questions about "Francisco's token" or "where Francisco is"
KevinCarde 2016-05-18 19:55:06
Remember that Francisco can move either token -- the tokens aren't assigned to players
KevinCarde 2016-05-18 19:55:15
Let's move on to Part (b), which is a little trickier.
KevinCarde 2016-05-18 19:55:23
PROBLEM 2b SOLUTION
KevinCarde 2016-05-18 19:55:37
Same overall rules, now one token starts above and to the left of the other. Where are the tokens when the game ends?
Yaksher 2016-05-18 19:56:16
(0,1) and (1,0)
skipiano 2016-05-18 19:56:16
top left, bottom right?
hliu70 2016-05-18 19:56:16
(0,1) (1,0)
aopssolver2 2016-05-18 19:56:16
0,1 and 1,0?
ioanandrei 2016-05-18 19:56:16
(1, 0) and (0, 1)
KevinCarde 2016-05-18 19:56:19
The tokens are once again as far in the bottom left as they can be, but due to the rules of the game, they now look like this:
http://www.mathcamp.org/2016/math_jam/solution-2-c.png
KevinCarde 2016-05-18 19:56:38
(Remember that since one started above and to the left, it must stay above and to the left!)
KevinCarde 2016-05-18 19:56:53
We claim that in general (with ideal play), Savannah wins if the two tokens begin on the same diagonal, and Francisco wins otherwise.
KevinCarde 2016-05-18 19:57:08
(Note that this is certainly true of the ending position -- if the tokens start this way, they're on the same diagonal, Francisco has no moves, and Savannah wins.)
KevinCarde 2016-05-18 19:57:23
We can summarize this claim in the following picture:
http://www.mathcamp.org/2016/math_jam/solution-2-d.png
KevinCarde 2016-05-18 19:57:42
(Francisco wins if the other token starts on an F, which continue off to the right; Savannah wins if the other token starts on an S)
KevinCarde 2016-05-18 19:57:52
To prove our claim, we make the following important observation: If the two tokens are not on the same diagonal, there is always at least one move that places them on the same diagonal. To see this, consider two cases:
KevinCarde 2016-05-18 19:58:28
* If the lower right token is on the upper right side of the other token's diagonal (e.g., in one of the three F positions right of the red diagonal, in the image above), we can move it down and left onto the diagonal.
KevinCarde 2016-05-18 19:58:40
* If the lower right token is on the lower left side of the other token's diagonal (e.g., in the one F position left of the red diagonal, in the image above), we can move the other token down and left until its diagonal intersects the lower right token.
KevinCarde 2016-05-18 19:58:46
(These cases might sound confusing when written out, but they're easier to understand if you play with them a bit on your own!)
KevinCarde 2016-05-18 19:59:21
Now: what's the winning strategy?
fishy15 2016-05-18 20:00:24
stay on the diagonal
ephshal 2016-05-18 20:00:24
Fransisco's winning strategy is to put the tokens in the position where one is to the direct upper left of the other, and then, when Savannah has to move the other one down, repeat by moving the upper one down as well. He will then, once the lower one hits the bottom, move his token to the left.
b7de 2016-05-18 20:00:24
move the further up piece onto the diagonal of the other token
Mario2357 2016-05-18 20:00:24
if ur on the smae diagonal, match the other person till they are at the end position
awesomeclaw 2016-05-18 20:00:24
Move the tokens onto the same diagonal, then mirror the other token. Eventually, the tokens will end up in the position to win.
hliu70 2016-05-18 20:00:24
keep on the same diagonal
b7de 2016-05-18 20:00:24
move the further up-right token onto the diagonal of the other piece!
KevinCarde 2016-05-18 20:00:32
Right -- we want to keep the tokens on the same diagonal!
KevinCarde 2016-05-18 20:00:51
Whenever possible, Francisco and Savannah should make moves that place the two tokens on the same diagonal.
KevinCarde 2016-05-18 20:01:21
So: If the two tokens begin on the same diagonal, Francisco must make a move that disrupts this. According to the observation, Savannah can move them back onto the same diagonal, and this process continues until we reach the ending position. Since the tokens are on the same diagonal only after Savannah's turns, it must be Francisco up next, and since he has no valid moves, Savannah wins!
KevinCarde 2016-05-18 20:01:43
If the two tokens do not begin on the same diagonal, Francisco immediately makes a move to put them on the same diagonal. Savannah is forced to to disrupt this, and they continue as before, but with the roles reversed. Now, when we reach the ending position, Savannah is up next with no valid moves, and Francisco wins!
KevinCarde 2016-05-18 20:02:06
So as we claimed, Savannah wins if the two tokens begin on the same diagonal, and Francisco wins otherwise.
KevinCarde 2016-05-18 20:02:31
That wraps up the strategies for Problem 2! The game can seem pretty confusing if you haven't had a chance to play around with it, so I encourage you to do so!
KevinCarde 2016-05-18 20:03:16
Onwards to Problem 3!
KevinCarde 2016-05-18 20:03:29
PROBLEM 3: Folding Triangles
KevinCarde 2016-05-18 20:03:41
Given an arbitrary triangle cut out from paper, we can fold one of its sides in half, so that one corner overlaps with another. This makes a crease through the midpoint of that side, as in the following figure:
http://www.mathcamp.org/2016/math_jam/problem-3-1.png
KevinCarde 2016-05-18 20:04:11
Unfolding and repeating with the other two sides, we get two more creases, as in the following figure:
http://www.mathcamp.org/2016/math_jam/problem-3-2.png
KevinCarde 2016-05-18 20:04:20
a) If two of the three creases have the same length, must the triangle be isosceles?
KevinCarde 2016-05-18 20:04:27
b) If all three creases have the same length, must the triangle be equilateral?
fishy15 2016-05-18 20:04:46
do the points touch
KevinCarde 2016-05-18 20:04:53
Yes -- we fold the triangle so that the two vertices touch
KevinCarde 2016-05-18 20:05:14
NOTES ON PROBLEM 3
KevinCarde 2016-05-18 20:05:20
Before we discuss solutions to the individual parts, I want to make a few comments about the situation, and about some common pitfalls.
KevinCarde 2016-05-18 20:05:37
I'm already seeing a lot from you all about what these creases are!
bluek 2016-05-18 20:05:51
perpendicular Bisector
cimatecest01 2016-05-18 20:05:51
the creases are perpendicular to the sides?
Ancy 2016-05-18 20:05:51
The folds are perpendicular bisectors of the line the two points are on that touch
Mario2357 2016-05-18 20:05:51
so its the perpendicular bisector right?
aopssolver2 2016-05-18 20:05:51
they are perpendicular bisectors
awesomeclaw 2016-05-18 20:05:51
the creases are the perpendicular bisectors of the triangles
fishy15 2016-05-18 20:05:51
perpendicular bisectors
KevinCarde 2016-05-18 20:06:13
The creases form segments of perpendicular bisectors of the sides!
KevinCarde 2016-05-18 20:06:27
But there's another observation we can make
KevinCarde 2016-05-18 20:06:51
How can we tell which of the other two sides a crease intersects?
pandadude 2016-05-18 20:07:20
the longer one
awesomeclaw 2016-05-18 20:07:20
the longer of the other sides
turnip123 2016-05-18 20:07:20
It intersects the longer of the two sides
aq1048576 2016-05-18 20:07:20
Whichever side is longer, hence is across from the larger angle measure
bluek 2016-05-18 20:07:20
the longer side
b7de 2016-05-18 20:07:20
the longer side!
KevinCarde 2016-05-18 20:07:23
Exactly!
KevinCarde 2016-05-18 20:07:36
One nice way to justify this is to observe that the perpendicular of a line segment $AB$ separates the plane into points closer to $A$ on one side, and points closer to $B$ on the other. Now consider any third point $C$. If $AC < BC$, then $C$ is closer to $A$ than to $B$, so $A$ and $C$ lie on the same side of the perpendicular bisector and $B$ and $C$ lie on opposite sides. Thus the perpendicular bisector intersects $BC$, which was the longer of the two sides, as desired.
KevinCarde 2016-05-18 20:08:25
(And note that if $AC = BC$, the perpendicular bisector must actually pass through $C$ -- think about this for a bit if you need to!)
KevinCarde 2016-05-18 20:08:34
So: Creases are segments of the perpendicular bisector, and they intersect the longer of the two remaining sides. This will be very important throughout.
KevinCarde 2016-05-18 20:08:50
Now let's talk about the most common pitfall in trying to solve this problem -- casework!
KevinCarde 2016-05-18 20:08:57
Casework itself isn't the problem, but the choice of cases often led students astray. It's very tempting, given a problem about triangles, to divide it into acute, right, and obtuse cases, but that turns out not to be very relevant here. Instead, in Part (a), we have three different creases, and we're declaring two of them to be equal. If we want to divide into cases, we should instead have cases based on which two of those three creases are equal!
KevinCarde 2016-05-18 20:09:26
This is a perfectly valid way to solve this problem -- two out of the three cases force two sides of the triangle to be equal, but the third doesn't, and that can indeed lead to a counterexample. In fact, there are several ways to solve this problem -- we'll present one way, but other possible solutions involve pure Euclidean geometry, algebra on coordinates, and trigonometry.
KevinCarde 2016-05-18 20:09:40
But I've been talking too long about geometry without a picture -- let's dive into Part (a)!
KevinCarde 2016-05-18 20:09:50
PROBLEM 3a SOLUTION
KevinCarde 2016-05-18 20:10:05
If two out of three creases have the same length, the triangle is not necessarily isosceles. Here's a diagram of one counterexample:
http://www.mathcamp.org/2016/math_jam/solution-3-a.png
KevinCarde 2016-05-18 20:10:12
Now, this diagram itself is not a proof -- the triangle looks non-isosceles, and the two creases (the dashed lines) look equal in length, but that's not rigorous. So let's prove a counterexample like this exists.
KevinCarde 2016-05-18 20:10:40
Let $\triangle ABC$ be a triangle with $AB \le BC \le AC$ with the measure of $\angle BAC$ equal to $45^\circ$. Scale the triangle so that $AB = 1$. Let $H$ be the base point of the altitude from vertex $B$. Notice that the crease along $AB$ passes through $H$. What's the length of this crease, and what's the length of the altitude $BH$?
fishy15 2016-05-18 20:11:53
$\frac{\sqrt{2}}{2}$
BobaFett101 2016-05-18 20:11:53
$\frac{\sqrt{2}}{2}$
ProGameXD 2016-05-18 20:11:53
sqrt2/2
aopssolver2 2016-05-18 20:11:53
1/2
ioanandrei 2016-05-18 20:11:53
AB sin A
Shri333 2016-05-18 20:11:53
sqrt(2)/2
derpli 2016-05-18 20:11:53
$\frac{1}{2}$ and $\frac{\sqrt2}{2}$
KevinCarde 2016-05-18 20:12:12
(Note that AB is length 1, and A is 45 degrees, so AB sin A is indeed $\sqrt2/2$)
KevinCarde 2016-05-18 20:12:23
The length of the crease is $\frac{1}{2}$, as it divides $\triangle ABH$ into two smaller isosceles triangles, and the length of the altitude $BH$ is $\frac{1}{\sqrt 2}\approx 0.707$, as it's a leg in a 45-45-90 triangle with hypotenuse of length 1.
KevinCarde 2016-05-18 20:12:47
Now let's start thinking about the crease along side $AC$, which we'll call $PQ$ as in the diagram. We'd like it to have length $\frac{1}{2}$ so that it has the same length as the other crease we just talked about.
KevinCarde 2016-05-18 20:13:04
Consider varying the position of point $C$. Since we declared $AB \le BC$, the furthest left we can put point $C$ makes $ABC$ into an isosceles triangle with $AB = BC$. In this case, the crease $PQ$ coincides with the altitude $BH$, which we know has length approximately $0.707$.
KevinCarde 2016-05-18 20:13:47
If we instead let $C$ go off far, far to the right, what happens to the length of the crease $PQ$?
Superwiz 2016-05-18 20:14:13
it becomes smaller and smaller
pandadude 2016-05-18 20:14:13
smaller
KevinCarde 2016-05-18 20:14:18
What's the smallest it can get?
KevinCarde 2016-05-18 20:14:31
(This is tricky!)
BobaFett101 2016-05-18 20:15:18
$BH/2$
Mario2357 2016-05-18 20:15:18
sqrt(2)/4
pandadude 2016-05-18 20:15:18
Sqrt(2)/4
KevinCarde 2016-05-18 20:15:51
Excellent! As $C$ moves to the right, the perpendicular bisector of $AC$ will hit side $BC$ almost in the middle, so its length will be half of the altitude $BH$.
Ancy 2016-05-18 20:15:57
but wait, values stretch from sqrt2 /4 to sqrt2 over 2, so 1/2 is in the range
KevinCarde 2016-05-18 20:16:16
Aha!
KevinCarde 2016-05-18 20:16:40
Since the crease approaches $\frac{1}{2}BH \approx 0.354$ in length, we can use the Intermediate Value Theorem
KevinCarde 2016-05-18 20:16:50
We can continuously vary the length of $PQ$ from $0.707$ to $0.354$, so somewhere in between it must be exactly $0.5$, the length of the other crease, exactly what we want.
fishy15 2016-05-18 20:16:58
but how do we know that that isn't isoceles
KevinCarde 2016-05-18 20:17:32
The leftmost position we considered for $C$ made $\triangle ABC$ isosceles, but as long as we move $C$ to the right at all, we won't have an isosceles triangle
KevinCarde 2016-05-18 20:18:03
This is a somewhat tricky argument, so I encourage you to think through it more and play with it!
KevinCarde 2016-05-18 20:18:14
But let's move on to Part (b).
KevinCarde 2016-05-18 20:18:20
PROBLEM 3b SOLUTION
KevinCarde 2016-05-18 20:18:28
If all three creases have the same length, we claim that the triangle must be equilateral.
KevinCarde 2016-05-18 20:18:36
Let's consider a triangle $\triangle ABC$. Without loss of generality, let the shortest side be $BC$. Since $BC$ is the shortest side, neither of the other two creases intersect it (remember that claim we made at the very beginning?). Call those two creases $PQ$ and $MN$, as in the the following picture:
http://www.mathcamp.org/2016/math_jam/solution-3-b.png
KevinCarde 2016-05-18 20:18:59
All three creases are equal in length, so in particular, $PQ = MN$. We can thus conclude that $\triangle AMN \cong \triangle APQ$ -- why?
Ancy 2016-05-18 20:19:38
AAA, and they share the same side length
claserken 2016-05-18 20:19:38
SAA
aopssolver2 2016-05-18 20:19:38
by AAS
KevinCarde 2016-05-18 20:19:41
By Angle-Angle-Side -- they share $\angle A$, $\angle AMN$ and $\angle APQ$ are both $90^\circ$, and $PQ = MN$. We conclude that $AM = AP$. Then, since the creases bisect the sides, we have $AB = 2AM = 2AP = AC$, and the triangle is isosceles with $AB = AC$.
KevinCarde 2016-05-18 20:20:09
Now that we know the triangle is isosceles, let's consider the third crease $RA$ (which must pass through $A$ since the triangle is isosceles):
http://www.mathcamp.org/2016/math_jam/solution-3-c.png
KevinCarde 2016-05-18 20:20:30
There are many different ways to proceed, but here's my favorite -- it's the most elementary of the solutions I know. Consider the areas of $\triangle ABC$ and $\triangle ABN$:
$\triangle ABC$ has area $\frac{1}{2} BC\cdot RA$.
$\triangle ABN$ has area $\frac{1}{2} AB\cdot MN$.
KevinCarde 2016-05-18 20:20:47
Which of these areas is bigger?
aopssolver2 2016-05-18 20:21:08
ABC
claserken 2016-05-18 20:21:08
$\bigtriangleup ABC$
awesomeclaw 2016-05-18 20:21:08
$\triangle ABC$
hliu70 2016-05-18 20:21:08
ABC
manick 2016-05-18 20:21:08
ABC
insero1 2016-05-18 20:21:08
ABC
KevinCarde 2016-05-18 20:21:10
But since $\triangle ABN$ is contained inside $\triangle ABC$, we certainly have
$\frac{1}{2} AB\cdot MN \le \frac{1}{2} BC\cdot RA$.
KevinCarde 2016-05-18 20:21:26
What can we cancel from both sides?
BobaFett101 2016-05-18 20:21:39
1/2
bluek 2016-05-18 20:21:39
1/2
insero1 2016-05-18 20:21:39
1/2
KevinCarde 2016-05-18 20:21:44
What else?
KevinCarde 2016-05-18 20:22:00
(Think about the creases!)
hliu70 2016-05-18 20:22:19
RA and MN
ioanandrei 2016-05-18 20:22:19
MN and RA
awesomeclaw 2016-05-18 20:22:19
$MN=RA$
Mario2357 2016-05-18 20:22:19
mn and ra
BobaFett101 2016-05-18 20:22:22
$MN = RA$ from assumption
bluek 2016-05-18 20:22:22
RA and MN because they are equal
KevinCarde 2016-05-18 20:22:36
Right -- those are both creases, and we assumed all three creases had the same length!
KevinCarde 2016-05-18 20:22:46
After canceling, then
KevinCarde 2016-05-18 20:22:47
We just have $AB \le BC$!
KevinCarde 2016-05-18 20:22:55
But we started by assuming $BC$ was the shortest side, and hence $BC \le AB$. We conclude, then, that $BC = AB$. Since we also have $AB = AC$, all three sides are equal, and the triangle is equilateral, as desired.
KevinCarde 2016-05-18 20:23:32
As I said, there are many ways to do this problem, so I encourage you to keep thinking about other methods if you found it interesting!
KevinCarde 2016-05-18 20:23:36
But now, back to MarisaD for Problem 4!
MarisaD 2016-05-18 20:23:44
Half way there -- everybody take a minute to jump up and down for a sec, shake it off, grab a new piece of scratch paper.
MarisaD 2016-05-18 20:24:05
Ready? Here we go.
fishy15 2016-05-18 20:24:11
1/2 done yay
MarisaD 2016-05-18 20:24:13
MarisaD 2016-05-18 20:24:17
PROBLEM 4a: Misha and Ivy's conversation
MarisaD 2016-05-18 20:24:22
Drake is thinking of a positive integer $x$. He tells Misha the number of digits $x$ has in base 2. He tells Ivy the number of digits $x$ has in base 3. For example, if Drake thinks of $x = 11 = 1011_2 = 102_3$, he'll tell Misha "$x$ has 4 digits in base 2" and he'll tell Ivy "$x$ has 3 digits in base 3".
MarisaD 2016-05-18 20:24:27
Drake alternates asking Misha and Ivy if they know $x$. They have the following conversation:
MarisaD 2016-05-18 20:24:33
Misha: No, I don't know $x$.
Ivy: No, I don't know $x$.
Misha: Yes, now I know $x$.
Ivy: Yes, now I know $x$.
MarisaD 2016-05-18 20:24:37
What was $x$?
MarisaD 2016-05-18 20:24:47
PROBLEM 4a SOLUTION
MarisaD 2016-05-18 20:25:21
I'm already seeing correct answers (great!). Let's start with the thought process: how to approach such a problem.
awesomeguy720 2016-05-18 20:25:24
HERE WE GO!!!
MarisaD 2016-05-18 20:25:26
One way to get a handle on this problem is to start imagining (on your scratch paper) what Misha and Ivy's conversations would be for specific values of $x$. For example, if $x = 1$, what do Misha and Ivy know, and what do they say in their conversation?
fishy15 2016-05-18 20:26:03
misha knows, so ivy knows
MarisaD 2016-05-18 20:26:24
Exactly. So, the at the outset: If $x=1$, then Misha hears from Drake that $x$ has 1 digit in base 2, and Ivy hears from Drake that $x$ has 1 digit in base 3.
MarisaD 2016-05-18 20:26:31
Before the conversation starts, Misha already knows the answer: 1 is the only positive one-digit number in base 2. On the other side of the table, before the conversation starts, Ivy knows that $x$ is either 1 or 2.
MarisaD 2016-05-18 20:26:46
So at the outset, Misha will say "Yes, I know $x$", at which point Ivy will think to herself a little argument by contradiction to decide between 1 and 2. Suppose $x=2$: then Misha would have heard that the number of digits in base $2$ is 2, but he wouldn't be able to distinguish between $2_{10}=10_2$ and $3_{10}=11_2$, so he wouldn't be able to confidently assert what he knows. Contradiction! So $x$ must be 1. Now Ivy, too, can say "Yes, now I know $x$."
ephshal 2016-05-18 20:26:54
If X = 1, then for both of them it will be 1 digit. Misha says she knows, and since Ivy knows that the only way she could know is that it's one digit in base 2, he says he knows as well
Superwiz 2016-05-18 20:27:26
so does Ivy know how many digits x has in base 2?
MarisaD 2016-05-18 20:27:50
Ivy hears from Drake only about $x$ in base 3, but she can deduce the same thing an outsider can.
ProGameXD 2016-05-18 20:28:05
Are we assuming that these guys are mathmeticians and can do this in their head in like 1 sec?
MarisaD 2016-05-18 20:28:11
It can be a slow conversation.
MarisaD 2016-05-18 20:28:15
Even this little example gave us the basic structure of what's going on here: each player is making a list of possibilities for the value of $x$, and using a process of elimination to figure out which one it is.
MarisaD 2016-05-18 20:28:25
Let's review that conversation again from the outsider's perspective:
MarisaD 2016-05-18 20:28:31
Before the conversation:
Drake knows $x$.
Misha knows $x$ must be 1.
Ivy knows $x$ is either 1 or 2.
The observer, let's call him Kevin, knows nothing.
MarisaD 2016-05-18 20:28:39
Then there's a conversation:
Misha: Yes, I know $x$.
MarisaD 2016-05-18 20:28:45
At this point, everybody knows $x$ (including Kevin), and just for completeness, we get:
Ivy: Yes, now I know $x$.
CATAPHRAT 2016-05-18 20:28:50
I am confused. So Ivy hears what drake says to Misha?
MarisaD 2016-05-18 20:29:11
Before the conversation, Ivy only hears her own info (about base 3), and Misha only hears his own info (about base 2).
Mario2357 2016-05-18 20:29:39
this is for x=1
MarisaD 2016-05-18 20:29:43
Yep, just as a warm-up.
ephshal 2016-05-18 20:29:48
With X=2 however, it should be harder for Ivy, since Misha knows that x= either 2 or 3, it could be 11 or 10, so she says she doesn't know
MarisaD 2016-05-18 20:30:14
Indeed. So let's talk about the bigger question: the four-sentence conversation that we actually got in this problem, viewed from Kevin's outside perspective.
MarisaD 2016-05-18 20:30:30
Misha starts by saying "I don't know $x$."
MarisaD 2016-05-18 20:30:33
After Misha's first statement, Kevin knows that $x$ wasn't 1, because that's the only one-digit number in base 2, but for any other number of digits, there are multiple possible values of $x$.
skipiano 2016-05-18 20:30:46
So $x \neq 1$
sp1729 2016-05-18 20:30:58
But how does the answer change. Does Drake give them more clues?
MarisaD 2016-05-18 20:31:07
Drake doesn't give more clues, but they start doing some deductions.
MarisaD 2016-05-18 20:31:13
Let's see what happens at the next step:
MarisaD 2016-05-18 20:31:28
Ivy says "I don't know $x$".
MarisaD 2016-05-18 20:31:30
After Ivy's first statement, Kevin knows that $x$ wasn't 2, because that's the only one-digit number in base 3 (other than 1, which is ruled out), but for any other number of digits, there are multiple possible values of $x$.
lcalvert99 2016-05-18 20:31:38
And 2 is eliminated
aopssolver2 2016-05-18 20:32:23
can you keep on going up like that?
MarisaD 2016-05-18 20:32:27
Let's see!
MarisaD 2016-05-18 20:32:37
What happens after Misha's next statement?
sumeetk 2016-05-18 20:32:55
This is a very interesting logic problem
MarisaD 2016-05-18 20:32:57
I agree!
lcalvert99 2016-05-18 20:33:09
Then Masha known it's three
aopsmathabc 2016-05-18 20:33:09
3!
skipiano 2016-05-18 20:33:09
x=3?
checkmatetang 2016-05-18 20:33:09
Misha has ruled out 1 and 2, so it must be 3, as that is the other two digit binary $x$
MarisaD 2016-05-18 20:33:23
Indeed: after Misha's second statement, Kevin knows that $x$ is 3, because that's the only two-digit number in base 2 (other than 1 and 2, which are ruled out), but (and this is important!) for any other number of digits, there are multiple possible values of $x$.
MarisaD 2016-05-18 20:33:33
(Specifically: if $x\geq 4$, Misha would not have been able to say he knew $x$ at this stage.)
MarisaD 2016-05-18 20:33:51
Finally: after Ivy's second statement, we all still know that $x$ is 3.
MarisaD 2016-05-18 20:34:12
Notice that the pieces that had to go into our argument:
* Checking that $x=1$ and $x=2$ do not work.
* Checking that $x=3$ *does* work.
* Checking that $x>3$ does not work.
MarisaD 2016-05-18 20:34:20
You can see that $x>3$ does not work either with an argument about numbers of digits of numbers above 4 (as we did here), or with a proof that Misha and Ivy gain no more information than we do. That was a point that a lot of people glossed over.
turnip123 2016-05-18 20:34:33
I love these logic problems!
MarisaD 2016-05-18 20:34:38
Me, too!
MarisaD 2016-05-18 20:34:39
On to part b:
MarisaD 2016-05-18 20:34:45
PROBLEM 4b: Drake's functions
MarisaD 2016-05-18 20:34:50
Suppose Drake instead chooses some other functions $f$ and $g$, tells Misha $f(x)$, and tells Ivy $g(x)$. Drake then alternates asking them if they know $x$ until they both say "Yes". The functions $f$ and $g$ are common knowledge: you, Misha, and Ivy all know what they are. But of course, you don't know the particular numbers $f(x)$ and $g(x)$ that Drake tells Misha and Ivy.
MarisaD 2016-05-18 20:34:54
Can Drake choose functions $f$ and $g$ such that you can always deduce $x$ just by listening to Misha and Ivy's conversation?
MarisaD 2016-05-18 20:35:13
PROBLEM 4b SOLUTION
MarisaD 2016-05-18 20:35:17
Let's start with: yes or no? Can he do it?
awesomeclaw 2016-05-18 20:35:30
yes
ProGameXD 2016-05-18 20:35:30
yes
inavda 2016-05-18 20:35:30
YES
orangekelp 2016-05-18 20:35:30
yes
ephshal 2016-05-18 20:35:30
yes
CATAPHRAT 2016-05-18 20:35:30
I think so.....
b7de 2016-05-18 20:35:30
he can!
MarisaD 2016-05-18 20:35:40
Yes! What's a pair of functions that works?
inavda 2016-05-18 20:36:05
f(x)=floor(x/2), g(x)=ceil(x/2)
lcalvert99 2016-05-18 20:36:05
We need for one number to be eliminated at every step
inavda 2016-05-18 20:36:05
f(x)=floor(x/2), g(x)=ceil(x/2)
mil246 2016-05-18 20:36:05
floor x/2, ceiling x/2
Yaksher 2016-05-18 20:36:11
f(x) = floor of log base 2 of x and g(x) = floor of log base 3 of x.
ioanandrei 2016-05-18 20:36:11
floor(x/2), floor((x+1)/2)
MarisaD 2016-05-18 20:36:15
Yep: the most common example was a floor/ceiling combination. Let's say $f(x)$ is $x/2$ rounded down and $g(x)$ is $x/2$ rounded up. We need to check that these two functions will do what we need.
MarisaD 2016-05-18 20:36:26
(Grab your scratch paper so you can follow along: I'll use "$f$" and "$g$", but floor and ceiling notation might be easier for you to see.)
MarisaD 2016-05-18 20:36:40
Specifically, we need to check that if the first $n-1$ answers are "No", then $x \geq n$, and that all values of $x$ at least $n$ are still possible.
MarisaD 2016-05-18 20:36:58
Now, starting small: what can $x$ be if Misha's first statement is "I know $x$."?
pandadude 2016-05-18 20:37:35
1
BobaFett101 2016-05-18 20:37:35
1
ephshal 2016-05-18 20:37:35
1
manick 2016-05-18 20:37:35
1
ioanandrei 2016-05-18 20:37:35
1
MarisaD 2016-05-18 20:37:38
Right. In fact, Misha knows $x$ immediately iff $x = 1$.
MarisaD 2016-05-18 20:37:54
That's the base case of the following statement: iff the $n$th thing said is "No", $x > n$.
MarisaD 2016-05-18 20:38:05
(Think about that for a sec!)
ProGameXD 2016-05-18 20:38:23
Wait, do the players(Misha and Ivy) know the function, or the output
MarisaD 2016-05-18 20:38:39
Everybody knows the functions: that's public knowledge.
MarisaD 2016-05-18 20:38:53
Misha knows the output of f(x), and Ivy knows the output of g(x).
MarisaD 2016-05-18 20:39:22
(So f plays the role of "# of digits in base 2", and g plays the role of "# of digits in base 3", to make an analogy to the previous part.)
MarisaD 2016-05-18 20:39:34
(But now $f$ and $g$ are these floor and ceiling functions.)
sp1729 2016-05-18 20:39:45
For problem 4B, are we assuming functions f and g are inversable?
MarisaD 2016-05-18 20:39:53
Not necessarily, no.
Superwiz 2016-05-18 20:40:13
because f(x) = 0, so x = 0 or 1
MarisaD 2016-05-18 20:40:18
Exactly.
MarisaD 2016-05-18 20:40:23
That's our base case right there.
MarisaD 2016-05-18 20:40:30
Let's prove the inductive step by splitting into two cases, depending on whose turn it is to talk.
MarisaD 2016-05-18 20:40:58
The players have been going back and forth, and they say "no, I don't know $x$" over and over again...
MarisaD 2016-05-18 20:41:17
...and at each stage, we are crossing off possibilities for $x$.
MarisaD 2016-05-18 20:41:19
If the $(2n-1)$st thing said was "No", then $x > 2n-1$, and it's Ivy's turn to say something.
MarisaD 2016-05-18 20:41:35
If $g(x) > n$, then Ivy can't distinguish $2g(x)$ from $2g(x)-1$, so if Ivy says yes, then $g(x) \leq n$. Which means $x$ itself was less than or equal to $2n$, so in fact $x = 2n$. Great!
MarisaD 2016-05-18 20:41:50
But if Ivy says "No", then $g(x) > 2n$.
MarisaD 2016-05-18 20:42:07
(Pausing for scratch paper work.)
MarisaD 2016-05-18 20:42:26
Now, if the $(2n)$th thing said was "No", then $x > 2n$, and it's Misha's turn to say something.
MarisaD 2016-05-18 20:42:45
This case is almost the same: if $f(x) > n$, then Misha can't distinguish $2f(x)$ from $2f(x)+1$, so if Misha says yes, then $f(x) \leq n$, which is to say $x \leq 2n+1$, and so $x = 2n+1$. (Great again!)
MarisaD 2016-05-18 20:43:08
But if Misha says "No", then $f(x) > 2n+1$.
MarisaD 2016-05-18 20:43:18
This tells us exactly how to deduce $x$ from Misha and Ivy's conversation, as desired.
MarisaD 2016-05-18 20:43:55
This is a little bit tricky, so I encourage you to think about why it suffices!
MarisaD 2016-05-18 20:44:03
If you want to double-check whether your pair of functions did the right thing: the pairs (in either order) of functions that work are exactly $h(f(s(n)))$ and $i(g(s(n)))$ for some bijective function $s$ and injective functions $h$ and $i$.
MarisaD 2016-05-18 20:44:24
(And if you're curious, prove that statement!)
skipiano 2016-05-18 20:44:59
Is that f(x) and g(x) the only functions?
MarisaD 2016-05-18 20:45:05
Nope, there are lots of choices.
awesomeclaw 2016-05-18 20:45:12
When you say $g(x)>2n$ and $f(x)>2n+1$, shouldn't it be $x>2n$ and $x>2n+1$?
ProGameXD 2016-05-18 20:45:44
What would happen if another person would be added, one more function would be added
MarisaD 2016-05-18 20:45:49
Ooh, great question.
MarisaD 2016-05-18 20:45:56
PROBLEM 5: Oddly Nice Numbers
MarisaD 2016-05-18 20:46:02
We call some positive integers oddly nice according to the following rules:
MarisaD 2016-05-18 20:46:08
* 1 is oddly nice.
* An integer $n>1$ is oddly nice if and only if an odd number of its proper divisors are oddly nice.
MarisaD 2016-05-18 20:46:14
Which numbers are oddly nice? If $s(n)$ is the number of oddly nice proper divisors of an integer $n$, what are all the possible values of $s(n)$? Prove your answer.
MarisaD 2016-05-18 20:46:23
PROBLEM 5 SOLUTION
MarisaD 2016-05-18 20:46:50
I love this problem, and a lot of people sent us very nice solutions to #5.
MarisaD 2016-05-18 20:46:56
A lot of people started this problem by testing out small values of $n$ and checking which were oddly nice, and noticed a pattern. What's the pattern?
awesomeclaw 2016-05-18 20:47:35
squarefree
BobaFett101 2016-05-18 20:47:35
square free numbers
Mario2357 2016-05-18 20:47:35
proper divisors dont include the number itself right
math1012 2016-05-18 20:47:35
product of primes to the first power
ioanandrei 2016-05-18 20:47:35
sqare-free numbers
MarisaD 2016-05-18 20:47:48
Yes! When the prime factorization of $n$ looked like $n=p_1 \cdot p_2 \cdot p_3 \cdots p_k$ where the $p_i$s are all distinct primes, our number $n$ was oddly nice, and when the prime factorization of $n$ had a repeated factor (i.e. $p_i^2$ divides $n$ for some $p_i$) then $n$ was not oddly nice.
pandadude 2016-05-18 20:47:58
what is a proper divisor
MarisaD 2016-05-18 20:48:11
A number $a$ which divides $b$, but is strictly less than $b$.
manick 2016-05-18 20:48:20
no squares
awesomeguy720 2016-05-18 20:48:20
none of them can be squared!
MarisaD 2016-05-18 20:48:31
Yeah! That's a good starting place! Now we can state our conjecture:
Conjecture: $n$ is oddly nice iff its prime decomposition has no repeated factors.
MarisaD 2016-05-18 20:48:43
A linguistic note: there is another word for an integer whose prime decomposition has no repeated factors, and that is "square-free". I'll use that interchangeably (and it's shorter to type).
MarisaD 2016-05-18 20:48:52
Now, in the solutions we read, a lot of people moved on to start building this up piece by piece. Let's look at that strategy for a moment, just to develop the motivation and intuition for how this problem works.
MarisaD 2016-05-18 20:49:01
We're already given the starting point: 1 is oddly nice. (That's like a product of zero primes.) What if $k=1$, and $n$ is prime? Is it oddly nice?
pandadude 2016-05-18 20:49:22
all primes are oddly nice
awesomeclaw 2016-05-18 20:49:22
yes
awesomeguy720 2016-05-18 20:49:22
yup
math1012 2016-05-18 20:49:22
yes
ProGameXD 2016-05-18 20:49:22
yes
manick 2016-05-18 20:49:22
yes
MarisaD 2016-05-18 20:49:24
Yep. Its only proper factor is 1, which is oddly nice, so it has an odd number of oddly nice divisors. Great.
MarisaD 2016-05-18 20:49:28
Moving up: let's say $k=2$, so $n=p_1 \cdot p_2$, where $p_1$ and $p_2$ are different primes. What are the proper divisors? Are they oddly nice?
awesomeclaw 2016-05-18 20:50:14
1, $p_1$ and $p_2$
math1012 2016-05-18 20:50:14
1, p_1, p_2 yes
Mario2357 2016-05-18 20:50:14
1, p1 and p2, so yes it is oddly nice
turnip123 2016-05-18 20:50:14
$1,p_1,p_2$ yes
b7de 2016-05-18 20:50:14
the proper divisors are 1, $p_1$, $p_2$, which are an odd number of oddly nice numbers, so $n$ is oddly nice
MarisaD 2016-05-18 20:50:18
Right: the three proper divisors are 1, $p_1$, and $p_2$, and we just checked that each of those will be oddly nice. So $n$ has three oddly nice divisors -- which makes it oddly nice.
MarisaD 2016-05-18 20:50:29
Let's look at one more example case, just to make it really clear. What if $n=p_1^2 \cdot p_2$?
math1012 2016-05-18 20:51:14
no
insero1 2016-05-18 20:51:14
no
manick 2016-05-18 20:51:14
no
skipiano 2016-05-18 20:51:14
then $1, p_1, p_2,$ and $p_1*p_2$
CATAPHRAT 2016-05-18 20:51:14
p1,p2, p1p2,
awesomeguy720 2016-05-18 20:51:14
p2
Mario2357 2016-05-18 20:51:14
1, p2, p1, p2p1
ProGameXD 2016-05-18 20:51:14
Then it is not oddly nice?
MarisaD 2016-05-18 20:51:20
Right. There are 5 proper divisors (1, $p_1$, $p_2$, $p_1 p_2$, and $p_1^2$), and the first four are oddly nice. (You can check that $p_1^2$ is not.) An even number of oddly-nice divisors! So $p_1^2 p_2$ is not oddly nice.
awesomeguy720 2016-05-18 20:51:27
wat is the dot in the middle?
MarisaD 2016-05-18 20:51:31
Sorry, multiplication.
MarisaD 2016-05-18 20:51:47
Now, all that was just prep work to support our conjecture. It's possible to keep building up from here combinatorially (and a lot of people did, to my chagrin), but it's messy, so let's walk through a cleaner approach.
MarisaD 2016-05-18 20:51:55
Starting from our conjecture: what tool shall we use to prove it?
awesomeclaw 2016-05-18 20:52:30
induction
CATAPHRAT 2016-05-18 20:52:30
induction?
ephshal 2016-05-18 20:52:30
Induction?
eisirrational 2016-05-18 20:52:30
induction
turnip123 2016-05-18 20:52:30
Induction
ioanandrei 2016-05-18 20:52:30
induction on n
Mario2357 2016-05-18 20:52:30
induction
MarisaD 2016-05-18 20:52:33
Induction it is! In fact, let's use strong induction.
MarisaD 2016-05-18 20:52:44
Just as a reminder, strong induction means that not only will we assume that the claim is true for $n-1$, but in fact for all of $1,2,\ldots,n-1$.
MarisaD 2016-05-18 20:52:54
So: we claim that oddly nice numbers are precisely those which are square-free, and we prove this by (strong) induction on $n$.
MarisaD 2016-05-18 20:52:59
(We saw some inductions on other quantities, like the number of prime factors, but this is the cleanest approach.)
MarisaD 2016-05-18 20:53:03
What's the base case?
ephshal 2016-05-18 20:53:41
n=1
math1012 2016-05-18 20:53:41
1
Satori99 2016-05-18 20:53:41
$n=1$
ioanandrei 2016-05-18 20:53:41
n=1
MarisaD 2016-05-18 20:53:44
Yes: $n=1$ is the base case, and it is true as $1$ is oddly nice.
MarisaD 2016-05-18 20:53:49
Now, it's possible to wrap the "if" and "only if" directions into one argument, but let's break it up for clarity.
MarisaD 2016-05-18 20:53:54
For $n>1$, let's suppose $n$ is square-free, and use our inductive hypothesis to show that $n$ is oddly nice.
MarisaD 2016-05-18 20:54:01
Let's write out its prime factorization as $n=p_1p_2\dotsm p_k$ for some $k\ge1$ (where the $p_i$ are distinct primes). How many proper factors does it have?
awesomeclaw 2016-05-18 20:54:31
$2^k-1$, and all the proper factors are oddly nice
BobaFett101 2016-05-18 20:54:31
2^k - 1
Satori99 2016-05-18 20:54:31
$2^k-1$
bluek 2016-05-18 20:54:31
2^k - 1
MarisaD 2016-05-18 20:54:36
Right: it has $2^{k}-1$ proper factors. How many of them are square-free?
amwmath 2016-05-18 20:54:59
All
Satori99 2016-05-18 20:54:59
All
math1012 2016-05-18 20:54:59
all of them
bluek 2016-05-18 20:54:59
none have square factors
MarisaD 2016-05-18 20:55:02
Of course! If $a|b$ and $b$ is square-free, then $a$ certainly can't have any squares. So, all the proper divisors of $n$ are square-free. Now what?
fishy15 2016-05-18 20:55:52
they are all squarefree, so they are oddly nice
Mario2357 2016-05-18 20:55:52
so by strong induction, there is an odd number of oddly nice factors
MarisaD 2016-05-18 20:55:58
Exactly. Now we get to apply our inductive hypothesis. All of those $2^{k}-1$ proper divisors are square-free and less than $n$, and hence oddly nice by the induction hypothesis.
amwmath 2016-05-18 20:56:05
It's slightly weird how 1 is considered squarefree and yet is also a square. (I guess we can put it on the list of "weird properties of $\varnothing$ and related")
MarisaD 2016-05-18 20:56:09
I agree!
MarisaD 2016-05-18 20:56:22
So: we conclude that $n$ is oddly nice.
awesomeclaw 2016-05-18 20:56:30
thus $n$ is oddly nice
aopssolver2 2016-05-18 20:56:30
wow!
MarisaD 2016-05-18 20:56:34
Let's look at the other direction: suppose $n$ is not square-free.
MarisaD 2016-05-18 20:56:43
Again, let's write down its prime decomposition: $n=p_1^{a_1}\dotsm p_r^{a_r}p_{r+1}\dotsm p_k$ for some $0<r\le k$ and $a_i>1$, where the $p_i$ are distinct primes. (Those primes don't have to appear in any particular order, so I'm listing the repeated factors first for convenience.)
MarisaD 2016-05-18 20:57:01
Now, how many square-free proper factors does our new $n$ have? What do they look like?
MarisaD 2016-05-18 20:58:15
Hmm, I'm seeing a mixture of answers. Let's think about what the proper divisors look like (before we count them):
CATAPHRAT 2016-05-18 20:58:19
they look like 1, p1p2, p1p3, p1p2p3, etc.
MarisaD 2016-05-18 20:58:55
Indeed. So, looking at only the proper divisors without squares: The square-free proper factors are all numbers of the form $p_1^{\epsilon_1}\dotsm p_k^{\epsilon_k}$ where $\epsilon_i\in\{0,1\}$ for all $i$.
MarisaD 2016-05-18 20:59:18
(For each $p_i$, you're choosing whether or not to include it in each factor.)
amwmath 2016-05-18 20:59:22
It's the same as the proper factors of $p_1p_2\dotsb p_k$ (without the exponents)
MarisaD 2016-05-18 20:59:41
Indeed, with one notable exception. What is it?
WeiXu27617 2016-05-18 20:59:57
+1
Mario2357 2016-05-18 20:59:59
because p1p2p3...pk
MarisaD 2016-05-18 21:00:02
Exactly.
MarisaD 2016-05-18 21:00:14
So, counting: there are $2^k$ square-free factors
MarisaD 2016-05-18 21:00:24
...and again by applying our strong induction hypothesis, they are all oddly nice.
Mario2357 2016-05-18 21:00:30
which is even
hliu70 2016-05-18 21:00:30
which is even
MarisaD 2016-05-18 21:00:37
Exactly.
MarisaD 2016-05-18 21:00:49
I think of this step as where we see the real heart of the "why": we have noticed that here, $p_1\dotsm p_k$ is a proper factor.
Mario2357 2016-05-18 21:01:00
but there are 2^k oddly proper divisors, not 2^k-1
MarisaD 2016-05-18 21:01:02
Exactly.
MarisaD 2016-05-18 21:01:06
So, to finish the proof: $n$ has an even number of oddly nice factors, and so it is not oddly nice. QED.
MarisaD 2016-05-18 21:01:13
Now, finally, to address the last part of the question: let's use $s(n)$ to denote the number of oddly nice proper divisors of an integer $n$. What values can $s(n$) take?
ioanandrei 2016-05-18 21:02:05
2^x and 2^x-1
amwmath 2016-05-18 21:02:13
$2^k,2^k-1$
MarisaD 2016-05-18 21:02:16
Yes! We start by noticing that a square-free number has $2^k-1$ proper square-free factors for some $k$, while a non-square-free number has $2^k$ square-free factors for some $k$. Then we have to check that we can actually attain all of those possibilities. (This is a step that a lot of people skipped.) Can we?
manick 2016-05-18 21:02:48
yes
CATAPHRAT 2016-05-18 21:02:48
yes
ProGameXD 2016-05-18 21:02:48
yes
MarisaD 2016-05-18 21:02:54
Right. In the first case, each non-negative value of $k$ can be realized by $p_1\dotsm p_k$ (so including $s(1)=0$).
MarisaD 2016-05-18 21:02:59
In the second case, we can use $p_1^2p_2\dotsm p_k$ in the second case for $k>0$ (while $2^0=2^1-1$ is realized by $n=2$).
MarisaD 2016-05-18 21:03:13
So, we can conclude: all the possible values of $s(n)$ are all numbers of the form $2^k$ or $2^k-1$, and each of these is realized by some $n$.
MarisaD 2016-05-18 21:03:23
We saw some other really creative approaches to this problem, like describing oddly nice numbers as a sequence of $n$-dimensional hypercubes of side-length 2!
MarisaD 2016-05-18 21:03:40
We're just passing the 90 minute mark, but we're almost done. Back to Kevin to finish up the Quiz with problem 6.
KevinCarde 2016-05-18 21:04:32
Hello again everyone!
KevinCarde 2016-05-18 21:04:47
PROBLEM 6: Waley's Sequences
KevinCarde 2016-05-18 21:04:57
Waley starts with a list of all the positive integers in order. He can perform the following operations on it:
KevinCarde 2016-05-18 21:05:03
* A $2$-flip, which reverses pairs of elements, turning $1, 2, 3, 4, 5, 6, \dots$ into $2, 1, 4, 3, 6, 5, \dots$ .
* A $3$-flip, which reverses triples of elements, turning $1, 2, 3, 4, 5, 6, \dots$ into $3, 2, 1, 6, 5, 4, \dots$ .
* More generally, an $n$-flip, for any integer $n > 1$: the list is split into groups of $n$ consecutive terms, and then each group is reversed.
KevinCarde 2016-05-18 21:05:27
Waley can perform any number of these operations, in any order. For instance, he can perform a $2$-flip and then a $3$-flip, which will first turn $1, 2, 3, 4, 5, 6, 7, 8, \dots$ into $2, 1, 4, 3, 6, 5, 8, 7, \dots$ and then into $4, 1, 2, 5, 6, 3, 10, 7, 8, \dots$ .
KevinCarde 2016-05-18 21:05:42
If you give Waley a finite sequence of distinct positive integers, when can he put that sequence at the beginning of his list (in order)? You should find a strategy for Waley to follow whenever this can be done, and prove that all other sequences are not attainable.
KevinCarde 2016-05-18 21:06:05
PROBLEM 6 SOLUTION
KevinCarde 2016-05-18 21:06:15
This is a tough problem! Let's start by making some definitions and observations. (I'm already seeing some from you all!)
KevinCarde 2016-05-18 21:06:40
Call a finite sequence of distinct positive integers attainable if we can use $n$-flips to put that sequence in order at the beginning of a list. So the problem is asking us to determine, with proof, what sequences are attainable.
KevinCarde 2016-05-18 21:07:02
Now let's look at all the example lists in the problem statement. What do you notice about the pattern of even and odd numbers? (Several of you have already observed this before I asked!)
EulerMacaroni 2016-05-18 21:07:43
all sequences which alternate in parity
BobaFett101 2016-05-18 21:07:43
alternating parity
hliu70 2016-05-18 21:07:43
alternating
manick 2016-05-18 21:07:43
odd, even, odd, even, etc.
awesomeclaw 2016-05-18 21:07:43
they are of alternating parity
insero1 2016-05-18 21:07:43
they alternate
KevinCarde 2016-05-18 21:07:57
Right -- they always alternate! Let's call a sequence balanced if it alternates between even and odd like this. Note that sometimes a balanced sequence starts with an odd number, and sometimes with an even number -- that's OK, as long as it alternates from there.
KevinCarde 2016-05-18 21:08:24
Before I go on, a few of you have asked what happens if the length of the list is not divisible by the $n$ in our $n$-flip.
KevinCarde 2016-05-18 21:08:39
Keep in mind that we always have an infinite list of all positive integers
KevinCarde 2016-05-18 21:08:45
Our goal is to put a finite portion of them at the front
KevinCarde 2016-05-18 21:09:01
So we can always carry out an $n$-flip for any $n$, since we're acting on the whole infinite list. Does that clear things up a little more?
KevinCarde 2016-05-18 21:09:26
OK, let's go back to balanced sequences!
KevinCarde 2016-05-18 21:09:35
Notice that $n$-flips (for any $n$) always take balanced sequences to balanced sequences.
KevinCarde 2016-05-18 21:09:42
For odd $n$, the parity of the number in each position is unchanged, so balanced certainly stays balanced; for even $n$, the parity of the number in each position always flips, which also results in a balanced sequence if we started balanced.
KevinCarde 2016-05-18 21:10:01
So, since flips take balanced sequences to balanced sequences and we begin with a balanced sequence, we have shown:
All attainable sequences are balanced.
b7de 2016-05-18 21:10:32
so all non-balanced sequences are not obtainable?
KevinCarde 2016-05-18 21:11:27
Yes -- that's the contrapositive of this statement, so it's logically equivalent. We've said:
If attainable, then balanced
so the contrapositive (which is also true!) is:
If not balanced, then not attainable.
KevinCarde 2016-05-18 21:12:00
But what about the converse? If a finite sequence is balanced, is it attainable? (This does not follow logically from the original statement -- if it's true, we'll have to prove it!)
EulerMacaroni 2016-05-18 21:12:26
Yes
ioanandrei 2016-05-18 21:12:26
yes!
ProGameXD 2016-05-18 21:12:26
yes
awesomeclaw 2016-05-18 21:12:32
yes
KevinCarde 2016-05-18 21:12:40
That's right -- but it's going to be tough to prove it, so don't worry if you don't see why!
KevinCarde 2016-05-18 21:13:03
So we now want to prove: All (finite) balanced sequences are attainable.
KevinCarde 2016-05-18 21:13:17
What might be a good strategy proof strategy here?
EulerMacaroni 2016-05-18 21:13:44
I personally didn't use induction, but I believe it can be done
sp1729 2016-05-18 21:13:44
Induction?
ioanandrei 2016-05-18 21:13:44
we can use induction on the lenght of the sequance
pwoulardftw 2016-05-18 21:13:51
induction
ProGameXD 2016-05-18 21:13:57
induction
KevinCarde 2016-05-18 21:14:11
There may be multiple ways to prove this, but we'll use induction!
KevinCarde 2016-05-18 21:14:22
(On the length of the sequence)
KevinCarde 2016-05-18 21:14:35
As a base case, consider a length $1$ balanced sequence -- i.e., a single number. We can easily put any number we want at the start of our list: if we want to put $n$ at the start, we simply perform an $n$-flip.
KevinCarde 2016-05-18 21:15:28
Now that the base case is handled, let's move on to the tricky step. Assume that all length $k$ balanced sequences are attainable; to complete our proof by induction, we must show that all length $k+1$ balanced sequences are also attainable.
KevinCarde 2016-05-18 21:16:03
Let
$a_1, a_2, \dots, a_k, a_{k+1}$
be an arbitrary length $k+1$ balanced sequence. By the induction hypothesis, we can perform a bunch of flips to put
$a_2, a_3, \dots, a_k, a_{k+1}$
at the start of the list (since that's a length $k$ balanced sequence).
KevinCarde 2016-05-18 21:16:33
Now consider the location of $a_1$ after these flips. Is it in an even or odd numbered position?
ProGameXD 2016-05-18 21:17:07
even
Superwiz 2016-05-18 21:17:07
even numbered position
ws5188 2016-05-18 21:17:07
even
KevinCarde 2016-05-18 21:17:18
Since $a_1$ has the opposite parity of $a_2$ and $a_2$ is in an odd numbered position (it's in position 1!), $a_1$ must be in an even numbered position.
KevinCarde 2016-05-18 21:17:43
(There were a lot of guesses of odd -- it's tricky to keep track of the parities!)
KevinCarde 2016-05-18 21:17:55
Since it's even, let $2m$ be the position of $a_1$.
KevinCarde 2016-05-18 21:18:02
We wish now to perform a further series of flips to put the entire sequence
$a_1, a_2, \dots, a_k, a_{k+1}$
at the start of the list.
KevinCarde 2016-05-18 21:18:15
We divide into two cases based on $m$ and $k$:
KevinCarde 2016-05-18 21:18:26
$m \ge k$:
We perform an $m$ flip followed by an $(m+1)$-flip. These two flips shift the first $m$ elements of the list down one position, so
$a_2, a_3, \dots, a_k, a_{k+1}$
end up in positions
$2, 3, \dots, k, k+1$.
That's good!
awesomeclaw 2016-05-18 21:19:03
and $a_1$ goes to position 1
KevinCarde 2016-05-18 21:19:16
Exactly! We claim that the element original at in position $2m$ (which is $a_1$) ends up in position $1$. Let's track its position:
* Start in position $2m$.
* Perform an $m$-flip. If we break up the list into blocks of length $m$, position $2m$ is at the very end of the second block. After the $m$-flip, it's at the very start of the second block, or position $m+1$.
* Perform an $(m+1)$-flip. Breaking up into blocks of length $m+1$ now, position $(m+1)$ is at the very end of the first block. After the $(m+1)$-flip, it's at the very start of the first block, or position $1$, as desired!
KevinCarde 2016-05-18 21:19:58
So when $m \ge k$, the $m$-flip followed by the $(m+1)$-flip puts completes the proof that we can put
$a_1, a_2, \dots, a_k, a_{k+1}$
at the start of the list.
hliu70 2016-05-18 21:20:16
what if k>m?
KevinCarde 2016-05-18 21:20:25
It's going to be fun -- ready?
KevinCarde 2016-05-18 21:20:41
If $m < k$:
We'll have to work a little harder here! Our goal is to reduce this case to the previous one -- i.e., to come up with a series of flips that leaves
$a_2, a_3, \dots, a_k, a_{k+1}$
at the start of the list while moving $a_1$ into a new position $2M$ with $M \ge k$. Since this is now a case we've already handled, this will complete the proof.
KevinCarde 2016-05-18 21:21:38
Now, if you're working on this problem, this is when you get your scratch paper out and try a bunch of flips to try to figure out how in the world you might achieve this.
b7de 2016-05-18 21:21:43
just flip a bunch of times sending $a_1$ as far away as possible
KevinCarde 2016-05-18 21:21:47
This is a good strategy!
KevinCarde 2016-05-18 21:22:12
We want to make it a little more definite, but that's what we want to do -- we want to send $a_1$ far, far away while leaving $a_2, a_3, \dots, a_k, a_{k+1}$ in place.
KevinCarde 2016-05-18 21:22:30
So -- after playing around a lot! -- we claim that if we do a $2k$-, $5k$-, $2k$-, and $3k$-flip, we'll achieve what we want. Let's see what happens.
KevinCarde 2016-05-18 21:22:51
Divide our list into blocks of length $k$. Note that since $k$ is a common divisor of all these flips, we will keep these length $k$ blocks together during this sequence of flips.
KevinCarde 2016-05-18 21:23:04
Let's track what happens to
$a_2, a_3, \dots, a_k, a_{k+1}$,
the first block of $k$ elements:
KevinCarde 2016-05-18 21:23:15
* $2k$-flip: The first block becomes the second block, reversed.
* $5k$-flip: The reversed second block becomes the fourth block, and reverses again back to the original order.
* $2k$-flip: The fourth block becomes the third block, reversed.
* $3k$-flip: The reversed third block becomes the first block, and reverses again back to the original order.
KevinCarde 2016-05-18 21:23:41
Good -- the first block is still the first block at the end, so our list still begins with
$a_2, a_3, \dots, a_k, a_{k+1}$!
KevinCarde 2016-05-18 21:23:57
(Take a moment to absorb this -- we've jumped through a lot of hoops, but $a_2, a_3, \dots, a_k, a_{k+1}$ is intact!)
Superwiz 2016-05-18 21:24:18
what about a1 thats at position m
KevinCarde 2016-05-18 21:24:29
Right -- that's the next thing to consider. Keep in mind that it's actually at $2m$, though.
Satori99 2016-05-18 21:24:48
So it is in the second block.
KevinCarde 2016-05-18 21:24:51
Since $m$ is less than $k$, position $2m$ must be in either the first or second block of length $k$. But since the whole first block is taken up by
$a_2, a_3, \dots, a_k, a_{k+1}$,
$a_1$ must be in the second block.
KevinCarde 2016-05-18 21:25:16
So, which block does it end up in, after our sequence of flips?
KevinCarde 2016-05-18 21:25:37
(Recall that we're doing a $2k$-, $5k$-, $2k$-, then a $3k$-flip)
hliu70 2016-05-18 21:26:13
4th block?
awesomeclaw 2016-05-18 21:26:13
4th
Superwiz 2016-05-18 21:26:22
It ends up in the 4th block
ProGameXD 2016-05-18 21:26:22
4th
KevinCarde 2016-05-18 21:26:24
This is a tough question!
KevinCarde 2016-05-18 21:26:25
So, where does it go?
* $2k$-flip: The second block becomes the first block.
* $5k$-flip: The first block becomes the fifth block.
* $2k$-flip: The fifth block becomes the sixth block.
* $3k$-flip: The sixth block becomes the fourth block.
KevinCarde 2016-05-18 21:26:53
Notice also that since this series of flips left the first $k$ elements unchanged, it must leave the parities of all positions unchanged. Hence $a_1$ must still be in an even position after these flips; call that position $2M$.
Satori99 2016-05-18 21:27:52
And $M>k$.
awesomeclaw 2016-05-18 21:27:58
2M>2K, so M>K
KevinCarde 2016-05-18 21:28:08
Yes -- let's see exactly why. We now know that $a_1$ has ended up in the fourth block. Since the blocks have length $k$, this means that $3k < 2M \le 4k$. In particular, $M > 1.5k > k$, so $M > k$ and we have succeeded in reducing to the previous case.
pandadude 2016-05-18 21:28:47
we are done!
hliu70 2016-05-18 21:28:47
wow
pandadude 2016-05-18 21:28:47
Yay!!!
KevinCarde 2016-05-18 21:28:56
Yes! We've reduced this case to the previous one, which we had successfully handled.
KevinCarde 2016-05-18 21:29:11
\This completes our proof by induction that all finite balanced sequences are attainable, and hence we have proved that a finite sequence is attainable if and only if it is balanced!
ProGameXD 2016-05-18 21:29:12
YAY!!!!
CATAPHRAT 2016-05-18 21:29:12
WOW
hliu70 2016-05-18 21:29:18
How do you get inspiration for such a sequence of flips?
KevinCarde 2016-05-18 21:29:45
Very good question! That's where a lot of trial and error comes into play -- what sequence of flips leave parts unchanged? What sequence of flips move a given element various places?
KevinCarde 2016-05-18 21:30:10
If you've enjoyed this problem, I hope you take some time to play with it a little more!
MarisaD 2016-05-18 21:30:18
Okay, everybody - time to wrap up. Thank you so much for spending your evening with us!
MarisaD 2016-05-18 21:30:28
If we didn't get to your question, you can also post questions in the Mathcamp forum here on AoPS, at http://www.artofproblemsolving.com/community/c135_mathcamp - the Mathcamp staff will post replies, and you'll get student opinions, too!
MarisaD 2016-05-18 21:30:35
I'll stick around for another five minutes and answer non-Quiz questions about the program and the application process, since I didn't get to them all at the beginning of the class.
yan2hua 2016-05-18 21:31:24
thank you
Mario2357 2016-05-18 21:31:24
THank you so much Kevin and Marisa
MarisaD 2016-05-18 21:31:33
Thank *you* guys!
Satori99 2016-05-18 21:31:36
How many students will be at Mathcamp this summer?
MarisaD 2016-05-18 21:31:47
We're aiming for 120 students and 30 staff. I think we'll be on the nose.
sunny2000 2016-05-18 21:31:50
hi, how many people got in through the waitlist so far, how many people are on it, and how many more r expected to get in (based on last year) ?
MarisaD 2016-05-18 21:32:15
Still TBA about the waitlist; currently admitted students have until May 20th to register, so we should have more info in the next few days. Everybody's status will be determined by June 1st.
MarisaD 2016-05-18 21:32:34
(I think we've only made one admit from the waitlist so far, but I expect we'll get to bring a few more!)
ioanandrei 2016-05-18 21:32:38
And how many of them are not from US/Canada?
MarisaD 2016-05-18 21:32:52
Ooh, good question... about 20 out of 120 are international.
ProGameXD 2016-05-18 21:32:56
who is the admin?
MarisaD 2016-05-18 21:33:01
That would be me and Kevin.
ephshal 2016-05-18 21:33:05
Are the problems at the camp going to be around this difficulty or harder or easier (on average)?
MarisaD 2016-05-18 21:33:30
Well, this isn't necessarily the style of math we do at camp. Check out mathcamp.org/academics/ for a little more about the math we teach.
sunny2000 2016-05-18 21:33:37
How was the QQ scored? Was it a point value system and people were ranked based on how they did on the QQ?
MarisaD 2016-05-18 21:33:43
It's a lot more complicated than that.
Yaksher 2016-05-18 21:33:50
Will this text be available somewhere or should I copy paste it into a file for that?
MarisaD 2016-05-18 21:34:00
Yes! There will be a transcript posted here and on the MC website.
insero1 2016-05-18 21:34:09
what grade levels is mathcamp recommended for?
pandadude 2016-05-18 21:34:09
I wanna go next year
ProGameXD 2016-05-18 21:34:09
what grade people get accepted?
MarisaD 2016-05-18 21:34:25
It's for students ages 13 - 18, which usually translates to 7th - 12th grades.
sunny2000 2016-05-18 21:34:28
Can we get feedback on our QQ in the near future?
MarisaD 2016-05-18 21:34:37
We don't have time to give individual feedback, sorry!
Satori99 2016-05-18 21:34:51
How many applicants were there?
MarisaD 2016-05-18 21:34:56
Almost 500.
insero1 2016-05-18 21:35:02
Are campers separated into different classes based on skill, or is everyone learning the same stuff?
MarisaD 2016-05-18 21:35:42
This is a neat feature of Mathcamp: you go to the classes that you're excited about, and you get to pick what they are. You can choose based on topic, style of the class (lecture vs by discovery), teacher - even what classes your friends are going to.
sunny2000 2016-05-18 21:35:56
do applicants who got in the previous year auto get in the following years?
MarisaD 2016-05-18 21:36:19
Yes: once you get in and attend, you don't have to reapply: you can automatically come back as an alum.
MarisaD 2016-05-18 21:36:22
(And lots of people do!)
Superwiz 2016-05-18 21:36:24
is this only canadian citizens
MarisaD 2016-05-18 21:36:31
Nope, students come to camp from all over the world.
sunny2000 2016-05-18 21:36:34
what are the field trips for this year?
MarisaD 2016-05-18 21:36:38
Still TBA!
MarisaD 2016-05-18 21:36:50
But the JCs are hatching plans.
mil246 2016-05-18 21:37:34
How many alumni are there this year?
MarisaD 2016-05-18 21:37:35
55
sunny2000 2016-05-18 21:37:38
is there a mentor system in place that allows students to work on research projects throughout camp?
MarisaD 2016-05-18 21:37:40
Yes!
Satori99 2016-05-18 21:37:47
Will I need a laptop for Mathcamp?
MarisaD 2016-05-18 21:37:55
If you have one, it's useful to bring. You don't need one, though.
MarisaD 2016-05-18 21:38:06
We have a little computer lab in the dorms, as well as access to a campus lab.
MarisaD 2016-05-18 21:38:18
Alrighty, looks like the questions are slowing down, so let's call it a night. Thank you all so much for joining us!
insero1 2016-05-18 21:38:29
thank you
Satori99 2016-05-18 21:38:29
Thanks!
ProGameXD 2016-05-18 21:38:29
thank you!
acegikmoqsuwy2000 2016-05-18 21:38:29
thank you!
sunny2000 2016-05-18 21:38:35
Thank you very much!
ProGameXD 2016-05-18 21:38:47
you guys are awesome
MarisaD 2016-05-18 21:38:51
So are YOU guys!
ioanandrei 2016-05-18 21:38:54
Thank you! Can't wait to see you all this summer!
silkworth54321 2016-05-18 21:39:00
THank you.. Very brain wracking logic..
MathChicken 2016-05-18 21:39:00
Thank You all!
acegikmoqsuwy2000 2016-05-18 21:39:05
good night
lcalvert99 2016-05-18 21:39:10
Thanks for class!!
Chess88 2016-05-18 21:39:10
sank u
sp1729 2016-05-18 21:39:10
Thanks for taking the time!
hliu70 2016-05-18 21:39:10
thank you
ProGameXD 2016-05-18 21:39:12
good night
KevinCarde 2016-05-18 21:39:20
Good night everyone -- thank you for being here!
LauraZed 2016-05-18 21:39:40
Thank you all for joining us, and thanks to Marisa and Kevin for holding an great Math Jam!
LauraZed 2016-05-18 21:40:07
In case you missed or forgot the link – you can learn more about Mathcamp at www.mathcamp.org
ioanandrei 2016-05-18 21:40:22
And from me a good morning!
sp1729 2016-05-18 21:40:34
Bye
CATAPHRAT 2016-05-18 21:40:34
thank you for class
ProGameXD 2016-05-18 21:41:11
Bye!

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