Canada/USA Mathcamp Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveMathcamp admissions committee members discuss the problems from the 2016 Mathcamp Qualifying Quiz.
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: Marisa Debowsky
LauraZed
2016-05-18 19:30:11
Hello and welcome to the Canada/USA Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Qualifying Quiz Math Jam!
Zer0waltz
2016-05-18 19:30:25
hello
hello
skipiano
2016-05-18 19:30:25
Hi!
Hi!
lcalvert99
2016-05-18 19:30:25
Awesome!!
Awesome!!
claserken
2016-05-18 19:30:25
Hi!
Hi!
reLAXer12
2016-05-18 19:30:27
Hi! Thanks for having us!
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.
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.
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.
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.
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:
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.
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.
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!
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!
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.
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.
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?
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.
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
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.
Not yet.
Minimons
2016-05-18 19:32:22
do you know where it will be next year?
do you know where it will be next year?
MarisaD
2016-05-18 19:32:26
Not yet.
Not yet.
pandadude
2016-05-18 19:32:34
what is the acceptance ratio to mathcamp
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%
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!
Okay, onto problems!
GeneralCobra19
2016-05-18 19:32:50
Yay problems!
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
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!).
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!
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}$.
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).
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.
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 .
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…).
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?
Ready?
MarisaD
2016-05-18 19:34:02
PROBLEM 1: Alchemy
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.
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$.
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
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.
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.
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.
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$.
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$.
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:
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*}
\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.
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?
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?
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$
$x+\phi y$
hliu70
2016-05-18 19:36:56
x+y(phi)
x+y(phi)
CATAPHRAT
2016-05-18 19:36:56
x+phi*y
x+phi*y
Shri333
2016-05-18 19:36:56
x + phi*y
x + phi*y
speck
2016-05-18 19:36:56
$x + \phi y$
$x + \phi y$
lcalvert99
2016-05-18 19:36:56
y*phi+x
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.
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?
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
y+(x+y)phi
aopssolver2
2016-05-18 19:37:43
This is like fibonacci!!
This is like fibonacci!!
aq1048576
2016-05-18 19:37:43
$\phi x+y+\phi y$
$\phi x+y+\phi y$
Mario2357
2016-05-18 19:37:43
y+(x+y)phi
y+(x+y)phi
sunny2000
2016-05-18 19:37:43
y+(x+y)phi
y+(x+y)phi
speck
2016-05-18 19:37:43
$y + \phi (x+y)$
$y + \phi (x+y)$
CATAPHRAT
2016-05-18 19:37:43
y+(x+y)phi
y+(x+y)phi
GeneralCobra19
2016-05-18 19:37:43
y+phi(x+y)
y+phi(x+y)
Shri333
2016-05-18 19:37:43
x*phi + y + y*phi
x*phi + y + y*phi
rb100
2016-05-18 19:37:43
$\phi y + \phi x$
$\phi y + \phi x$
claserken
2016-05-18 19:37:43
$y+\phi\cdot(x+y)$
$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.
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?
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
yes
CATAPHRAT
2016-05-18 19:38:31
yes
yes
hliu70
2016-05-18 19:38:31
phi+1=phi^2
phi+1=phi^2
CATAPHRAT
2016-05-18 19:38:31
phi+1=phi^2
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)$
$\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$.)
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$.
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 ).
(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?
What's our base case?
Shri333
2016-05-18 19:39:22
day 1?
day 1?
GeneralCobra19
2016-05-18 19:39:22
1
1
claserken
2016-05-18 19:39:36
$n=1$
$n=1$
ephshal
2016-05-18 19:39:36
day 1?
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$.
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?
What's our inductive hypothesis?
hliu70
2016-05-18 19:40:50
each day after, it will be worth phi^n
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}$.
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}$
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
D(n+1)/Dn=phi
MarisaD
2016-05-18 19:41:06
Great, you guys are on top of this.
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}$.
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
It must be because we just showed it above
MarisaD
2016-05-18 19:41:30
Exactly!
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.
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.
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?
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$.
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!)
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$).
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.
Ready? Over to KevinCarde for problem 2.
KevinCarde
2016-05-18 19:42:49
Thanks, MarisaD, and hello everyone!
Thanks, MarisaD, and hello everyone!
KevinCarde
2016-05-18 19:43:03
PROBLEM 2: Francisco and Savannah's Game
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:
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.
* 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.
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?
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.)
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
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
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
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:
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.
* 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?
How many tokens can be moved per turn?
KevinCarde
2016-05-18 19:45:38
Each player moves a single token each turn.
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!
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
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!)
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
The bottom left token has to end up in the bottom left square
hliu70
2016-05-18 19:47:58
(0,0) (1,1)
(0,0) (1,1)
fishy15
2016-05-18 19:47:58
in a corner?
in a corner?
Yaksher
2016-05-18 19:47:58
Bottom Left corner and 1 to the right and up from there.
Bottom Left corner and 1 to the right and up from there.
WeiXu27617
2016-05-18 19:47:58
lower left corner
lower left corner
KevinCarde
2016-05-18 19:48:05
The tokens must both be in the bottom left, like this:
The tokens must both be in the bottom left, like this:
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.
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!)
(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?
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)
the first person (if good strategy)
ioanandrei
2016-05-18 19:49:10
next player
next player
Mario2357
2016-05-18 19:49:10
the person whose turn it is
the person whose turn it is
alismith01
2016-05-18 19:49:10
Francisco
Francisco
awesomeclaw
2016-05-18 19:49:10
the person making the move, since they can just put it in the final position
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.
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:
(with the F labels continuing off upwards and rightwards)
We can summarize this in the following diagram:
(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.
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.
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!)
(Several of you have already reached that conclusion!)
KevinCarde
2016-05-18 19:50:23
(And recall that Francisco plays First, Savannah Second)
(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?
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
one up and one over
fishy15
2016-05-18 19:51:21
right next to it diagonally
right next to it diagonally
aopssolver2
2016-05-18 19:51:21
copy
copy
turnip123
2016-05-18 19:51:21
The other piece immediately above and to the right
The other piece immediately above and to the right
Shri333
2016-05-18 19:51:21
right up
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!
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?
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?
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)
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
Francisco could win
ephshal
2016-05-18 19:52:29
Then fransisco makes it this case
Then fransisco makes it this case
hliu70
2016-05-18 19:52:29
move it to the spot one up and one over
move it to the spot one up and one over
Zer0waltz
2016-05-18 19:52:29
move it there
move it there
Mario2357
2016-05-18 19:52:39
well then the person going first makes it go in that position
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.
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!
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
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.
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?
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!
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?
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!
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"
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
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.
Let's move on to Part (b), which is a little trickier.
KevinCarde
2016-05-18 19:55:23
PROBLEM 2b SOLUTION
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?
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)
(0,1) and (1,0)
skipiano
2016-05-18 19:56:16
top left, bottom right?
top left, bottom right?
hliu70
2016-05-18 19:56:16
(0,1) (1,0)
(0,1) (1,0)
aopssolver2
2016-05-18 19:56:16
0,1 and 1,0?
0,1 and 1,0?
ioanandrei
2016-05-18 19:56:16
(1, 0) and (0, 1)
(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:
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:
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!)
(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.
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.)
(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:
We can summarize this claim in the following picture:
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)
(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:
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.
* 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.
* 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!)
(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?
Now: what's the winning strategy?
fishy15
2016-05-18 20:00:24
stay on the diagonal
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.
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
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
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.
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
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!
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!
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.
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!
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!
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.
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!
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!
Onwards to Problem 3!
KevinCarde
2016-05-18 20:03:29
PROBLEM 3: Folding Triangles
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:
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:
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:
Unfolding and repeating with the other two sides, we get two more creases, as in the following figure:
KevinCarde
2016-05-18 20:04:20
a) If two of the three creases have the same length, must the triangle be isosceles?
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?
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
do the points touch
KevinCarde
2016-05-18 20:04:53
Yes -- we fold the triangle so that the two vertices touch
Yes -- we fold the triangle so that the two vertices touch
KevinCarde
2016-05-18 20:05:14
NOTES ON PROBLEM 3
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.
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!
I'm already seeing a lot from you all about what these creases are!
bluek
2016-05-18 20:05:51
perpendicular Bisector
perpendicular Bisector
cimatecest01
2016-05-18 20:05:51
the creases are perpendicular to the sides?
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
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?
so its the perpendicular bisector right?
aopssolver2
2016-05-18 20:05:51
they are perpendicular bisectors
they are perpendicular bisectors
awesomeclaw
2016-05-18 20:05:51
the creases are the perpendicular bisectors of the triangles
the creases are the perpendicular bisectors of the triangles
fishy15
2016-05-18 20:05:51
perpendicular bisectors
perpendicular bisectors
KevinCarde
2016-05-18 20:06:13
The creases form segments of perpendicular bisectors of the sides!
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
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?
How can we tell which of the other two sides a crease intersects?
pandadude
2016-05-18 20:07:20
the longer one
the longer one
awesomeclaw
2016-05-18 20:07:20
the longer of the other sides
the longer of the other sides
turnip123
2016-05-18 20:07:20
It intersects the longer of the two sides
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
Whichever side is longer, hence is across from the larger angle measure
bluek
2016-05-18 20:07:20
the longer side
the longer side
b7de
2016-05-18 20:07:20
the longer side!
the longer side!
KevinCarde
2016-05-18 20:07:23
Exactly!
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.
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!)
(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.
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!
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!
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.
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)!
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
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:
If two out of three creases have the same length, the triangle is not necessarily isosceles. Here's a diagram of one counterexample:
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.
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$?
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}$
$\frac{\sqrt{2}}{2}$
BobaFett101
2016-05-18 20:11:53
$\frac{\sqrt{2}}{2}$
$\frac{\sqrt{2}}{2}$
ProGameXD
2016-05-18 20:11:53
sqrt2/2
sqrt2/2
aopssolver2
2016-05-18 20:11:53
1/2
1/2
ioanandrei
2016-05-18 20:11:53
AB sin A
AB sin A
Shri333
2016-05-18 20:11:53
sqrt(2)/2
sqrt(2)/2
derpli
2016-05-18 20:11:53
$\frac{1}{2}$ and $\frac{\sqrt2}{2}$
$\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$)
(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.
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.
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$.
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$?
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
it becomes smaller and smaller
pandadude
2016-05-18 20:14:13
smaller
smaller
KevinCarde
2016-05-18 20:14:18
What's the smallest it can get?
What's the smallest it can get?
KevinCarde
2016-05-18 20:14:31
(This is tricky!)
(This is tricky!)
BobaFett101
2016-05-18 20:15:18
$BH/2$
$BH/2$
Mario2357
2016-05-18 20:15:18
sqrt(2)/4
sqrt(2)/4
pandadude
2016-05-18 20:15:18
Sqrt(2)/4
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$.
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
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!
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
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.
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
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
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!
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).
But let's move on to Part (b).
KevinCarde
2016-05-18 20:18:20
PROBLEM 3b SOLUTION
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.
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:
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:
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?
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
AAA, and they share the same side length
claserken
2016-05-18 20:19:38
SAA
SAA
aopssolver2
2016-05-18 20:19:38
by AAS
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$.
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):
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):
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$.
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?
Which of these areas is bigger?
aopssolver2
2016-05-18 20:21:08
ABC
ABC
claserken
2016-05-18 20:21:08
$\bigtriangleup ABC$
$\bigtriangleup ABC$
awesomeclaw
2016-05-18 20:21:08
$\triangle ABC$
$\triangle ABC$
hliu70
2016-05-18 20:21:08
ABC
ABC
manick
2016-05-18 20:21:08
ABC
ABC
insero1
2016-05-18 20:21:08
ABC
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$.
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?
What can we cancel from both sides?
BobaFett101
2016-05-18 20:21:39
1/2
1/2
bluek
2016-05-18 20:21:39
1/2
1/2
insero1
2016-05-18 20:21:39
1/2
1/2
KevinCarde
2016-05-18 20:21:44
What else?
What else?
KevinCarde
2016-05-18 20:22:00
(Think about the creases!)
(Think about the creases!)
hliu70
2016-05-18 20:22:19
RA and MN
RA and MN
ioanandrei
2016-05-18 20:22:19
MN and RA
MN and RA
awesomeclaw
2016-05-18 20:22:19
$MN=RA$
$MN=RA$
Mario2357
2016-05-18 20:22:19
mn and ra
mn and ra
BobaFett101
2016-05-18 20:22:22
$MN = RA$ from assumption
$MN = RA$ from assumption
bluek
2016-05-18 20:22:22
RA and MN because they are equal
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!
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
After canceling, then
KevinCarde
2016-05-18 20:22:47
We just have $AB \le BC$!
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.
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!
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!
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.
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.
Ready? Here we go.
fishy15
2016-05-18 20:24:11
1/2 done yay
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
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".
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:
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$.
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$?
What was $x$?
MarisaD
2016-05-18 20:24:47
PROBLEM 4a SOLUTION
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.
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!!!
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?
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
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.
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.
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$."
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
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?
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.
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?
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.
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.
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:
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.
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$.
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$.
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?
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).
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
this is for x=1
MarisaD
2016-05-18 20:29:43
Yep, just as a warm-up.
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
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.
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$."
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$.
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$
So $x \neq 1$
sp1729
2016-05-18 20:30:58
But how does the answer change. Does Drake give them more clues?
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.
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:
Let's see what happens at the next step:
MarisaD
2016-05-18 20:31:28
Ivy says "I don't know $x$".
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$.
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
And 2 is eliminated
aopssolver2
2016-05-18 20:32:23
can you keep on going up like that?
can you keep on going up like that?
MarisaD
2016-05-18 20:32:27
Let's see!
Let's see!
MarisaD
2016-05-18 20:32:37
What happens after Misha's next statement?
What happens after Misha's next statement?
sumeetk
2016-05-18 20:32:55
This is a very interesting logic problem
This is a very interesting logic problem
MarisaD
2016-05-18 20:32:57
I agree!
I agree!
lcalvert99
2016-05-18 20:33:09
Then Masha known it's three
Then Masha known it's three
aopsmathabc
2016-05-18 20:33:09
3!
3!
skipiano
2016-05-18 20:33:09
x=3?
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$
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$.
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.)
(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.
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.
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.
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!
I love these logic problems!
MarisaD
2016-05-18 20:34:38
Me, too!
Me, too!
MarisaD
2016-05-18 20:34:39
On to part b:
On to part b:
MarisaD
2016-05-18 20:34:45
PROBLEM 4b: Drake's functions
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.
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?
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
PROBLEM 4b SOLUTION
MarisaD
2016-05-18 20:35:17
Let's start with: yes or no? Can he do it?
Let's start with: yes or no? Can he do it?
awesomeclaw
2016-05-18 20:35:30
yes
yes
ProGameXD
2016-05-18 20:35:30
yes
yes
inavda
2016-05-18 20:35:30
YES
YES
orangekelp
2016-05-18 20:35:30
yes
yes
ephshal
2016-05-18 20:35:30
yes
yes
CATAPHRAT
2016-05-18 20:35:30
I think so.....
I think so.....
b7de
2016-05-18 20:35:30
he can!
he can!
MarisaD
2016-05-18 20:35:40
Yes! What's a pair of functions that works?
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)
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
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)
f(x)=floor(x/2), g(x)=ceil(x/2)
mil246
2016-05-18 20:36:05
floor x/2, ceiling x/2
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.
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)
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.
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.)
(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.
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$."?
Now, starting small: what can $x$ be if Misha's first statement is "I know $x$."?
pandadude
2016-05-18 20:37:35
1
1
BobaFett101
2016-05-18 20:37:35
1
1
ephshal
2016-05-18 20:37:35
1
1
manick
2016-05-18 20:37:35
1
1
ioanandrei
2016-05-18 20:37:35
1
1
MarisaD
2016-05-18 20:37:38
Right. In fact, Misha knows $x$ immediately iff $x = 1$.
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$.
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!)
(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
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.
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).
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.)
(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.)
(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?
For problem 4B, are we assuming functions f and g are inversable?
MarisaD
2016-05-18 20:39:53
Not necessarily, no.
Not necessarily, no.
Superwiz
2016-05-18 20:40:13
because f(x) = 0, so x = 0 or 1
because f(x) = 0, so x = 0 or 1
MarisaD
2016-05-18 20:40:18
Exactly.
Exactly.
MarisaD
2016-05-18 20:40:23
That's our base case right there.
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.
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...
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$.
...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.
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!
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$.
But if Ivy says "No", then $g(x) > 2n$.
MarisaD
2016-05-18 20:42:07
(Pausing for scratch paper work.)
(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.
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!)
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$.
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.
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!
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$.
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!)
(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?
Is that f(x) and g(x) the only functions?
MarisaD
2016-05-18 20:45:05
Nope, there are lots of choices.
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$?
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
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.
Ooh, great question.
MarisaD
2016-05-18 20:45:56
PROBLEM 5: Oddly Nice Numbers
PROBLEM 5: Oddly Nice Numbers
MarisaD
2016-05-18 20:46:02
We call some positive integers oddly nice according to the following rules:
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.
* 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.
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
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.
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?
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
squarefree
BobaFett101
2016-05-18 20:47:35
square free numbers
square free numbers
Mario2357
2016-05-18 20:47:35
proper divisors dont include the number itself right
proper divisors dont include the number itself right
math1012
2016-05-18 20:47:35
product of primes to the first power
product of primes to the first power
ioanandrei
2016-05-18 20:47:35
sqare-free numbers
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.
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
what is a proper divisor
MarisaD
2016-05-18 20:48:11
A number $a$ which divides $b$, but is strictly less than $b$.
A number $a$ which divides $b$, but is strictly less than $b$.
manick
2016-05-18 20:48:20
no squares
no squares
awesomeguy720
2016-05-18 20:48:20
none of them can be squared!
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.
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).
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.
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?
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
all primes are oddly nice
awesomeclaw
2016-05-18 20:49:22
yes
yes
awesomeguy720
2016-05-18 20:49:22
yup
yup
math1012
2016-05-18 20:49:22
yes
yes
ProGameXD
2016-05-18 20:49:22
yes
yes
manick
2016-05-18 20:49:22
yes
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.
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?
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$
1, $p_1$ and $p_2$
math1012
2016-05-18 20:50:14
1, p_1, p_2 yes
1, p_1, p_2 yes
Mario2357
2016-05-18 20:50:14
1, p1 and p2, so yes it is oddly nice
1, p1 and p2, so yes it is oddly nice
turnip123
2016-05-18 20:50:14
$1,p_1,p_2$ yes
$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
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.
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$?
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
no
insero1
2016-05-18 20:51:14
no
no
manick
2016-05-18 20:51:14
no
no
skipiano
2016-05-18 20:51:14
then $1, p_1, p_2,$ and $p_1*p_2$
then $1, p_1, p_2,$ and $p_1*p_2$
CATAPHRAT
2016-05-18 20:51:14
p1,p2, p1p2,
p1,p2, p1p2,
awesomeguy720
2016-05-18 20:51:14
p2
p2
Mario2357
2016-05-18 20:51:14
1, p2, p1, p2p1
1, p2, p1, p2p1
ProGameXD
2016-05-18 20:51:14
Then it is not oddly nice?
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.
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?
wat is the dot in the middle?
MarisaD
2016-05-18 20:51:31
Sorry, multiplication.
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.
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?
Starting from our conjecture: what tool shall we use to prove it?
awesomeclaw
2016-05-18 20:52:30
induction
induction
CATAPHRAT
2016-05-18 20:52:30
induction?
induction?
ephshal
2016-05-18 20:52:30
Induction?
Induction?
eisirrational
2016-05-18 20:52:30
induction
induction
turnip123
2016-05-18 20:52:30
Induction
Induction
ioanandrei
2016-05-18 20:52:30
induction on n
induction on n
Mario2357
2016-05-18 20:52:30
induction
induction
MarisaD
2016-05-18 20:52:33
Induction it is! In fact, let's use strong induction.
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$.
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$.
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.)
(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?
What's the base case?
ephshal
2016-05-18 20:53:41
n=1
n=1
math1012
2016-05-18 20:53:41
1
1
Satori99
2016-05-18 20:53:41
$n=1$
$n=1$
ioanandrei
2016-05-18 20:53:41
n=1
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.
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.
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.
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?
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
$2^k-1$, and all the proper factors are oddly nice
BobaFett101
2016-05-18 20:54:31
2^k - 1
2^k - 1
Satori99
2016-05-18 20:54:31
$2^k-1$
$2^k-1$
bluek
2016-05-18 20:54:31
2^k - 1
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?
Right: it has $2^{k}-1$ proper factors. How many of them are square-free?
amwmath
2016-05-18 20:54:59
All
All
Satori99
2016-05-18 20:54:59
All
All
math1012
2016-05-18 20:54:59
all of them
all of them
bluek
2016-05-18 20:54:59
none have square factors
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?
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
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
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.
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")
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!
I agree!
MarisaD
2016-05-18 20:56:22
So: we conclude that $n$ is oddly nice.
So: we conclude that $n$ is oddly nice.
awesomeclaw
2016-05-18 20:56:30
thus $n$ is oddly nice
thus $n$ is oddly nice
aopssolver2
2016-05-18 20:56:30
wow!
wow!
MarisaD
2016-05-18 20:56:34
Let's look at the other direction: suppose $n$ is not square-free.
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.)
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?
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):
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.
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$.
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.)
(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)
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?
Indeed, with one notable exception. What is it?
WeiXu27617
2016-05-18 20:59:57
+1
+1
Mario2357
2016-05-18 20:59:59
because p1p2p3...pk
because p1p2p3...pk
MarisaD
2016-05-18 21:00:02
Exactly.
Exactly.
MarisaD
2016-05-18 21:00:14
So, counting: there are $2^k$ square-free factors
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.
...and again by applying our strong induction hypothesis, they are all oddly nice.
Mario2357
2016-05-18 21:00:30
which is even
which is even
hliu70
2016-05-18 21:00:30
which is even
which is even
MarisaD
2016-05-18 21:00:37
Exactly.
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.
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
but there are 2^k oddly proper divisors, not 2^k-1
MarisaD
2016-05-18 21:01:02
Exactly.
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.
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?
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
2^x and 2^x-1
amwmath
2016-05-18 21:02:13
$2^k,2^k-1$
$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?
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
yes
CATAPHRAT
2016-05-18 21:02:48
yes
yes
ProGameXD
2016-05-18 21:02:48
yes
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$).
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$).
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$.
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!
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.
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!
Hello again everyone!
KevinCarde
2016-05-18 21:04:47
PROBLEM 6: Waley's Sequences
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:
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.
* 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$ .
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.
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
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!)
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.
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!)
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
all sequences which alternate in parity
BobaFett101
2016-05-18 21:07:43
alternating parity
alternating parity
hliu70
2016-05-18 21:07:43
alternating
alternating
manick
2016-05-18 21:07:43
odd, even, odd, even, etc.
odd, even, odd, even, etc.
awesomeclaw
2016-05-18 21:07:43
they are of alternating parity
they are of alternating parity
insero1
2016-05-18 21:07:43
they alternate
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.
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.
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
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
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?
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!
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.
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.
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.
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?
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.
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!)
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
Yes
ioanandrei
2016-05-18 21:12:26
yes!
yes!
ProGameXD
2016-05-18 21:12:26
yes
yes
awesomeclaw
2016-05-18 21:12:32
yes
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!
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.
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?
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
I personally didn't use induction, but I believe it can be done
sp1729
2016-05-18 21:13:44
Induction?
Induction?
ioanandrei
2016-05-18 21:13:44
we can use induction on the lenght of the sequance
we can use induction on the lenght of the sequance
pwoulardftw
2016-05-18 21:13:51
induction
induction
ProGameXD
2016-05-18 21:13:57
induction
induction
KevinCarde
2016-05-18 21:14:11
There may be multiple ways to prove this, but we'll use induction!
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)
(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.
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.
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).
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?
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
even
Superwiz
2016-05-18 21:17:07
even numbered position
even numbered position
ws5188
2016-05-18 21:17:07
even
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.
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!)
(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$.
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.
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$:
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!
$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
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!
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.
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?
what if k>m?
KevinCarde
2016-05-18 21:20:25
It's going to be fun -- ready?
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.
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.
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
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!
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.
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.
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.
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:
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.
* $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}$!
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!)
(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
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.
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.
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.
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?
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)
(Recall that we're doing a $2k$-, $5k$-, $2k$-, then a $3k$-flip)
hliu70
2016-05-18 21:26:13
4th block?
4th block?
awesomeclaw
2016-05-18 21:26:13
4th
4th
Superwiz
2016-05-18 21:26:22
It ends up in the 4th block
It ends up in the 4th block
ProGameXD
2016-05-18 21:26:22
4th
4th
KevinCarde
2016-05-18 21:26:24
This is a tough question!
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.
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$.
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$.
And $M>k$.
awesomeclaw
2016-05-18 21:27:58
2M>2K, so M>K
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.
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!
we are done!
hliu70
2016-05-18 21:28:47
wow
wow
pandadude
2016-05-18 21:28:47
Yay!!!
Yay!!!
KevinCarde
2016-05-18 21:28:56
Yes! We've reduced this case to the previous one, which we had successfully handled.
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!
\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!!!!
YAY!!!!
CATAPHRAT
2016-05-18 21:29:12
WOW
WOW
hliu70
2016-05-18 21:29:18
How do you get inspiration for such a sequence of flips?
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?
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!
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!
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!
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.
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
thank you
Mario2357
2016-05-18 21:31:24
THank you so much Kevin and Marisa
THank you so much Kevin and Marisa
MarisaD
2016-05-18 21:31:33
Thank *you* guys!
Thank *you* guys!
Satori99
2016-05-18 21:31:36
How many students will be at Mathcamp this summer?
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.
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) ?
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.
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!)
(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?
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.
Ooh, good question... about 20 out of 120 are international.
ProGameXD
2016-05-18 21:32:56
who is the admin?
who is the admin?
MarisaD
2016-05-18 21:33:01
That would be me and Kevin.
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)?
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.
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?
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.
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?
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.
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?
what grade levels is mathcamp recommended for?
pandadude
2016-05-18 21:34:09
I wanna go next year
I wanna go next year
ProGameXD
2016-05-18 21:34:09
what grade people get accepted?
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.
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?
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!
We don't have time to give individual feedback, sorry!
Satori99
2016-05-18 21:34:51
How many applicants were there?
How many applicants were there?
MarisaD
2016-05-18 21:34:56
Almost 500.
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?
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.
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?
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.
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!)
(And lots of people do!)
Superwiz
2016-05-18 21:36:24
is this only canadian citizens
is this only canadian citizens
MarisaD
2016-05-18 21:36:31
Nope, students come to camp from all over the world.
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?
what are the field trips for this year?
MarisaD
2016-05-18 21:36:38
Still TBA!
Still TBA!
MarisaD
2016-05-18 21:36:50
But the JCs are hatching plans.
But the JCs are hatching plans.
mil246
2016-05-18 21:37:34
How many alumni are there this year?
How many alumni are there this year?
MarisaD
2016-05-18 21:37:35
55
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?
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!
Yes!
Satori99
2016-05-18 21:37:47
Will I need a laptop for Mathcamp?
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.
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.
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!
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
thank you
Satori99
2016-05-18 21:38:29
Thanks!
Thanks!
ProGameXD
2016-05-18 21:38:29
thank you!
thank you!
acegikmoqsuwy2000
2016-05-18 21:38:29
thank you!
thank you!
sunny2000
2016-05-18 21:38:35
Thank you very much!
Thank you very much!
ProGameXD
2016-05-18 21:38:47
you guys are awesome
you guys are awesome
MarisaD
2016-05-18 21:38:51
So are YOU guys!
So are YOU guys!
ioanandrei
2016-05-18 21:38:54
Thank you! Can't wait to see you all this summer!
Thank you! Can't wait to see you all this summer!
silkworth54321
2016-05-18 21:39:00
THank you.. Very brain wracking logic..
THank you.. Very brain wracking logic..
MathChicken
2016-05-18 21:39:00
Thank You all!
Thank You all!
acegikmoqsuwy2000
2016-05-18 21:39:05
good night
good night
lcalvert99
2016-05-18 21:39:10
Thanks for class!!
Thanks for class!!
Chess88
2016-05-18 21:39:10
sank u
sank u
sp1729
2016-05-18 21:39:10
Thanks for taking the time!
Thanks for taking the time!
hliu70
2016-05-18 21:39:10
thank you
thank you
ProGameXD
2016-05-18 21:39:12
good night
good night
KevinCarde
2016-05-18 21:39:20
Good night everyone -- thank you for being here!
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!
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
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!
And from me a good morning!
sp1729
2016-05-18 21:40:34
Bye
Bye
CATAPHRAT
2016-05-18 21:40:34
thank you for class
thank you for class
ProGameXD
2016-05-18 21:41:11
Bye!
Bye!
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
