Math Jams

2019 USA(J)MO Discussion

Go back to the Math Jam Archive

Evan Chen, one of the coaches of the USA IMO team, will discuss selected problems from the 2019 USA Math Olympiad.

Copyright © 2019 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: Evan Chen

eminentabyss 2019-04-19 19:22:22
Welcome to the 2019 USA(J)MO Math Jam!
eminentabyss 2019-04-19 19:32:17
In this Math Jam, Evan Chen, one of the coaches of the USA IMO team, will discuss selected problems from the 2019 USA Math Olympiad.
eminentabyss 2019-04-19 19:32:30
Evan Chen (v_Enhance) is one of the coaches of the USA IMO team, serving as a coordinator for the team selection tests and the assistant academic director at MOP. Starting in July 2019, he will also be an editor-in-chief for the USA(J)MO editorial board. As a high school student, Evan was an IMO gold medalist and winner of the 2014 USAMO (which he took from 12:30am to 5am in Taiwan). Outside of math and teaching, Evan enjoys StarCraft and Korean pop dance.
eminentabyss 2019-04-19 19:33:11
For now, please hold your questions -- we'll let you know when you can start asking questions. Also, due to the number of people attending tonight, we may not be able to get to every question.
eminentabyss 2019-04-19 19:33:24
We do have one amazing teaching assistant with us tonight to help answer your questions:
eminentabyss 2019-04-19 19:33:34
Detelin (OlympiadPro2000) won a silver medal in the 1995 IMO and a gold medal in the 1995 Balkan Math Olympiad. He received his M.S. in Mathematics from Sofia University and his Ph.D. in Mathematics from Texas A&M.
eminentabyss 2019-04-19 19:33:56
He can answer questions by whispering to you or by opening a window with you to chat 1-on-1. However, due to the large size of the session tonight, he may not be able to get to you right away (or at all). Repeating your question over and over is more likely to annoy us than to get it answered faster, so please, just ask your question once and be patient, and please understand that we may not be able to answer all the questions tonight.
v_Enhance 2019-04-19 19:34:31
Hello! Welcome to the 2019 USA(J)MO math jam. The last time we had a USAMO Math Jam was in 2004, as far as I can tell, so I'm super excited to be doing the next one.
v_Enhance 2019-04-19 19:34:42
We'll be discussing some of the problems I like from this year's contest. (Not all the problems, alas, since these questions are tough, and I can't keep the AOPS staff here forever.)
v_Enhance 2019-04-19 19:34:50
To start, I'm hoping to go through the problems in this order:
v_Enhance 2019-04-19 19:34:55
JMO5/MO4 (combinatorics with sets $S_{ij}$), proposed by Ricky Liu
JMO6/MO5 (number theory with Evan and a blackboard), proposed by Yannick Yao
JMO4 ($EF$ tangent to $A$-excircle), proposed by Ankan Bhattacharya, Zack Chroman, and Anant Mudgal
MO1 (iterated functional equation), proposed by Evan Chen
JMO3/MO2 (geometry with funny condition), proposed by Ankan Bhattacharya
v_Enhance 2019-04-19 19:35:13
But I only get about two hours, and the USAMO is a nine-hour test, so we may not get to all of these. Probably, if I find myself short on time, I'll skip the MO1 functional equation. We'll see!
v_Enhance 2019-04-19 19:35:26
(Conversely, if somehow we blaze through all five of these, I'll ad-lib problems by popular request until I get cut off. )
v_Enhance 2019-04-19 19:35:39
One quick favor I'd like to ask off-the-bat: I will probably not answer questions of the form "how many points do I get for X?" or "what will cutoff for X be?". The rubrics have not even been decided yet, and I prefer not to be on-record about things I'm not sure about.
v_Enhance 2019-04-19 19:35:49
About the Math Jam itself: A lot of you may have already seen complete solutions to a lot of the problems, and that's fine.
v_Enhance 2019-04-19 19:36:00
However, my goal in this Math Jam is to show you how to incrementally *find* a solution, rather than just telling you. (It's sort of like directing a movie: you only reach the climax after a lot of character development.) So in this Math Jam, I'll be building up slowly, starting from ground zero. Thus it's fine if you haven't tried the problems yet!
v_Enhance 2019-04-19 19:36:19
If you want to read cleaned write-ups later, without the long narrative that'll be in the Math Jam, I will upload full solutions to http://web.evanchen.cc/problems.html for this year's USA(J)MO 2019. (I also recently added all the USAMO and IMO from 2000, so some of you may be interested in that independently.).
v_Enhance 2019-04-19 19:36:29
Alright, ready to start?
cj13609517288 2019-04-19 19:36:42
Let's start!
Brudder 2019-04-19 19:36:42
yes
kevinmathz 2019-04-19 19:36:42
Yep!
andrewwang2623 2019-04-19 19:36:42
yes
AlexLikeMath 2019-04-19 19:36:42
Yes!
cowcow 2019-04-19 19:36:42
yes
Kaiser143 2019-04-19 19:36:42
yeah
azmath333 2019-04-19 19:36:42
yup!
goodball 2019-04-19 19:36:42
Yes!
ilovemath04 2019-04-19 19:36:42
yep
hliu1 2019-04-19 19:36:42
Yeah
Awesome_guy 2019-04-19 19:36:42
yep
ketul 2019-04-19 19:36:42
Yeee
Kagebaka 2019-04-19 19:36:46
ankant wait to start
v_Enhance 2019-04-19 19:36:52
JMO5/MO4. Let $n$ be a nonnegative integer. Determine the number of ways that one can choose \((n+1)^2\) sets \(S_{i,j}\subseteq \{1,2,\ldots, 2n\}\), for integers \(i,j\) with \(0\le i,j\le n\), such that:
$\bullet$ for all \(0\le i,j\le n\), the set \(S_{i,j}\) has \(i+j\) elements; and
$\bullet$ \(S_{i,j}\subseteq S_{k,l}\) whenever \(0\le i\le k\le n\) and \(0\le j\le l\le n\).
v_Enhance 2019-04-19 19:37:08
There's a lot of notation here, so I'll start by doing some book-keeping that will help us all visualize what's happening.
v_Enhance 2019-04-19 19:37:16
The notation $S_{i,j}$ for $0 \le i,j \le n$ means that we have $(n+1)^2$ sets and so it'll be easier to visualize what's going on if I put them in a grid, like so.
v_Enhance 2019-04-19 19:37:23
\[

\begin{bmatrix}

S_{0n} & S_{1n} & \dots & S_{nn} \\

\vdots & \vdots & \ddots & \vdots \\

S_{01} & S_{11} & \dots & S_{1n} \\

S_{00} & S_{10} & \dots & S_{n0}

\end{bmatrix}

\]
v_Enhance 2019-04-19 19:37:41
Let's try to figure out what that condition is saying. We'll start by filling in some of the easy steps.
v_Enhance 2019-04-19 19:37:46
First of all, what does that $S_{00}$ in the bottom-left have to be?
goodbear 2019-04-19 19:38:00
ø
Brendanb4321 2019-04-19 19:38:00
empty set
oldbro 2019-04-19 19:38:00
{}
boomminecraft 2019-04-19 19:38:00
0 elements, so empty set
Eyed 2019-04-19 19:38:00
empty set
v_Enhance 2019-04-19 19:38:04
We should have $S_{00} = \varnothing$: only set with $0$ elements.
v_Enhance 2019-04-19 19:38:09
Next, what does $S_{nn}$ have to be?
Kaiser143 2019-04-19 19:38:42
all of then numbers
Eyed 2019-04-19 19:38:42
{1,2,...2n}
Brendanb4321 2019-04-19 19:38:42
$\{1,2,\ldots,2n\}$
SD2014 2019-04-19 19:38:42
have all the elements
boomminecraft 2019-04-19 19:38:42
the whole set, as it should have 2n elements!
v_Enhance 2019-04-19 19:38:47
We should have $S_{nn} = \{1, \dots, 2n\}$; all $2n$ elements are present.
v_Enhance 2019-04-19 19:39:02
Now imagine we placed an ant at $S_{00}$, and it walked up this grid going right and up, ending at $S_{nn}$. How does the set change as we walk up this grid?
SD2014 2019-04-19 19:39:29
it gains one element each step
Kaiser143 2019-04-19 19:39:29
add an element
bluelinfish 2019-04-19 19:39:29
one more element each time
hliu1 2019-04-19 19:39:29
build up one element at a time.
goodbear 2019-04-19 19:39:29
adds one element at a time
Brendanb4321 2019-04-19 19:39:29
keeps gaining 1 new element each time
v_Enhance 2019-04-19 19:39:37
Right, as you go up and to the right, you add one element each time. Because of the first condition, every time the ant makes a move, the set is one element bigger, and because of the second condition, none of the old elements go away.
v_Enhance 2019-04-19 19:39:42
Therefore, for $n = 1$, one valid example would be:

\[

\begin{bmatrix}

\{1\} & \{1,2\} \\

\varnothing & \{2\}

\end{bmatrix}

\]
v_Enhance 2019-04-19 19:39:51
I'm going to be lazy and abbreviate this to just

\[

\begin{bmatrix}

1 & 12 \\

\varnothing & 2

\end{bmatrix}

\]

because all those commas and curly braces are going to be really hard to type once $n > 1$...
v_Enhance 2019-04-19 19:39:58
Make sense?
v_Enhance 2019-04-19 19:40:11
Cool.
v_Enhance 2019-04-19 19:40:12
Are there other examples for $n = 1$?
porkemon2 2019-04-19 19:40:32
yes, switch 2 and 1
RaggedQuark2 2019-04-19 19:40:32
switch the 1 and the 2
goodbear 2019-04-19 19:40:32
1 12

ø 1
ilovemath04 2019-04-19 19:40:32
the 1 and 2 are switched
v_Enhance 2019-04-19 19:40:44
Yes, we could also swap the order and have

\[

\begin{bmatrix}

2 & 12 \\

\varnothing & 1

\end{bmatrix}

\]

instead.
v_Enhance 2019-04-19 19:42:03
(Hahah yeah. OK, good catch.)
v_Enhance 2019-04-19 19:42:06
Alright, what are the other examples?
hliu1 2019-04-19 19:42:35
1 12

ø 1



2 12

ø 2
porkemon2 2019-04-19 19:42:35
instead of 2 and 1 you can have 1 and 1 or 2 and 2
carzland 2019-04-19 19:42:35
There are more than 2 examples?
Brendanb4321 2019-04-19 19:42:35
S_{1,0}=S_{0,1}
v_Enhance 2019-04-19 19:42:58
Yep, two mor examples:
v_Enhance 2019-04-19 19:43:11
\[

\begin{bmatrix}

2 & 12 \\

\varnothing & 2

\end{bmatrix}

\]
v_Enhance 2019-04-19 19:43:18
\[

\begin{bmatrix}

1 & 12 \\

\varnothing & 1

\end{bmatrix}

\]
v_Enhance 2019-04-19 19:43:29
And those are the only four.
v_Enhance 2019-04-19 19:44:04
Alright, everyone caught up on $n=1$? (Including me, I guess )
cowcow 2019-04-19 19:44:16
yes
P_Groudon 2019-04-19 19:44:16
Yep
AlexLikeMath 2019-04-19 19:44:16
Yes.
rjiangbz 2019-04-19 19:44:16
yeah
v_Enhance 2019-04-19 19:44:43
Alright, let's go on to $n=2$. In that case the answer is way bigger, so we'll start by just filling in a mostly empty grid.
v_Enhance 2019-04-19 19:44:54
So here's a mostly empty $3 \times 3$ grid, except I filled in the easy cases $S_{00}$ and $S_{22}$.\[ \begin{bmatrix}

\color{gray}{S_{02}} &

\color{gray}{S_{12}} &

\color{blue}{1234} \\

\color{gray}{S_{01}} &

\color{gray}{S_{11}} &

\color{gray}{S_{21}} \\

\color{blue}{\varnothing} &

\color{gray}{S_{10}} &

\color{gray}{S_{20}}

\end{bmatrix} \]
v_Enhance 2019-04-19 19:45:07
Let's start throwing in some entries. Where might I put our first number?
RaggedQuark2 2019-04-19 19:45:29
s10 or s01
chenwan2004 2019-04-19 19:45:29
top
carzland 2019-04-19 19:45:29
In S_10 or S_01
goodbear 2019-04-19 19:45:29
S_10
c4raymond 2019-04-19 19:45:29
s_01?
Brendanb4321 2019-04-19 19:45:29
S_10
beiqiang 2019-04-19 19:45:29
S_(01)
annoynymous 2019-04-19 19:45:29
S_{10}
bluelinfish 2019-04-19 19:45:29
put 1 in S10
goodball 2019-04-19 19:45:29
S01 or S10
v_Enhance 2019-04-19 19:45:39
So there's a lot of different things we could fill in. For the sake of narrative, let's start with the $S_{01}$ entry (but $S_{10}$ would have worked fine too).
cj13609517288 2019-04-19 19:45:47
$S_{01}=1$
v_Enhance 2019-04-19 19:45:50
We need to exactly one number in it, so let's just put $1$: right now all the numbers are exactly the same, so we just pick one.
v_Enhance 2019-04-19 19:45:52
\[ \begin{bmatrix}

\color{gray}{S_{02}} &

\color{gray}{S_{12}} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{gray}{S_{11}} &

\color{gray}{S_{21}} \\

\color{blue}{\varnothing} &

\color{gray}{S_{10}} &

\color{gray}{S_{20}}

\end{bmatrix} \]
v_Enhance 2019-04-19 19:45:58
Okay, good. I propose we move on to $S_{02}$ next. What could we put in there?
carzland 2019-04-19 19:46:18
2
Brendanb4321 2019-04-19 19:46:18
12 13 14
snow_monkey 2019-04-19 19:46:18
12, 13, or 14
beiqiang 2019-04-19 19:46:18
1 and any from 2 to 4
v_Enhance 2019-04-19 19:46:22
Right, we could write any of $12$, $13$, $14$, but now, the numbers $2$, $3$, $4$ all play symmetric roles, so it shouldn't matter which one we put.
v_Enhance 2019-04-19 19:46:26
So let's just put $12$.
v_Enhance 2019-04-19 19:46:28
\[ \begin{bmatrix}

\color{blue}{12} &

\color{gray}{S_{12}} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{gray}{S_{11}} &

\color{gray}{S_{21}} \\

\color{blue}{\varnothing} &

\color{gray}{S_{10}} &

\color{gray}{S_{20}}

\end{bmatrix} \]
v_Enhance 2019-04-19 19:46:38
And at this point you might see where this is going. What could $S_{12}$ be, and does it matter?
snow_monkey 2019-04-19 19:47:02
123 or 124
A_drop_of_water 2019-04-19 19:47:02
123
AwesomeYRY 2019-04-19 19:47:02
123
Brendanb4321 2019-04-19 19:47:02
123 124
legolego 2019-04-19 19:47:02
123 or 124 (doesn't matter which)
ilovemath04 2019-04-19 19:47:02
123 or 124 and no it does not matter
hliu1 2019-04-19 19:47:02
123 or 124 but 3 and 4 are symmetris
v_Enhance 2019-04-19 19:47:04
We could put either $123$ or $1234$ in $S_{12}$, and again it doesn't matter which one, so let's put $123$.
v_Enhance 2019-04-19 19:47:07
\[ \begin{bmatrix}

\color{blue}{12} &

\color{blue}{123} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{gray}{S_{11}} &

\color{gray}{S_{21}} \\

\color{blue}{\varnothing} &

\color{gray}{S_{10}} &

\color{gray}{S_{20}}

\end{bmatrix} \]
v_Enhance 2019-04-19 19:47:19
At this point you'll notice that I haven't made any hard decisions yet! At every point, we filled in some entries, but then also argued that our choices didn't matter.
v_Enhance 2019-04-19 19:47:25
So put another way, I propose that to find the answer for $n = 2$, we can find the number of ways to finish our partially filled grid above, and then multiply by a certain number for all our choices. What number is that?
Brendanb4321 2019-04-19 19:48:04
(2n)!
beiqiang 2019-04-19 19:48:04
4 * 3 * 2 = 24
snow_monkey 2019-04-19 19:48:04
4!=24
rjiangbz 2019-04-19 19:48:04
24
AlexLikeMath 2019-04-19 19:48:04
(2n)!
v_Enhance 2019-04-19 19:48:13
Some of you already see what's happening for general $n$
v_Enhance 2019-04-19 19:48:20
But yes, it's just $4 \cdot 3 \cdot 2 \cdot 1 = 4! = 24$. The $4$ comes from picking the number $1$ for $S_{10}$ (as opposed to $2$, $3$, $4$); the $3$ comes from $S_{20}$ and so on.
v_Enhance 2019-04-19 19:48:37
Okay, so let's try to fill in the rest of that $2 \times 2$ grid now.
v_Enhance 2019-04-19 19:48:38
What sets can I choose for $S_{11}$?
AlexLikeMath 2019-04-19 19:49:25
12, or 13
Ttugf 2019-04-19 19:49:25
12 or 13
diamond606 2019-04-19 19:49:25
12, 13
snow_monkey 2019-04-19 19:49:25
12, 13
mathfun5 2019-04-19 19:49:25
Superset of S10 but subset of S21
v_Enhance 2019-04-19 19:49:35
Yeah, I can either put $S_{11} = \{1,2\}$ or $S_{11} = \{1,3\}$. For the first time, these choices are not symmetric, so I need to actually keep track of the two cases.
v_Enhance 2019-04-19 19:49:40
So here they are.
v_Enhance 2019-04-19 19:49:41
\[

\begin{bmatrix}

\color{blue}{12} &

\color{blue}{123} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{red}{12} &

\color{gray}{S_{21}} \\

\color{blue}{\varnothing} &

\color{gray}{S_{10}} &

\color{gray}{S_{20}}

\end{bmatrix}

\quad\text{ OR }\quad

\begin{bmatrix}

\color{blue}{12} &

\color{blue}{123} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{red}{13} &

\color{gray}{S_{21}} \\

\color{blue}{\varnothing} &

\color{gray}{S_{10}} &

\color{gray}{S_{20}}

\end{bmatrix}

\]
v_Enhance 2019-04-19 19:49:56
Okay, let's look at the left case first.
v_Enhance 2019-04-19 19:50:00
In the first case (left), what are the possibilities for $S_{21}$?
goodball 2019-04-19 19:50:30
123 or 124
bluelinfish 2019-04-19 19:50:30
123 and 124
porkemon2 2019-04-19 19:50:30
either add 3 or a 4, two options
v_Enhance 2019-04-19 19:50:33
We could have $S_{21} = \{1,2,3\}$ or $S_{21} = \{1,2,4\}$.
v_Enhance 2019-04-19 19:50:36
In the first case case (still left), what are the possibilities for $S_{10}$?
cowcow 2019-04-19 19:50:48
1 or 2
AwesomeYRY 2019-04-19 19:50:48
1 or 2
annoynymous 2019-04-19 19:50:51
1,2
v_Enhance 2019-04-19 19:50:54
We could have $S_{10} = \{1\}$ or $S_{10} = \{2\}$.
v_Enhance 2019-04-19 19:51:13
So our left case right now looks like: \[

\begin{bmatrix}

\color{blue}{12} &

\color{blue}{123} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{red}{12} &

\color{orange}{123 \text{ or } 124} \\

\color{blue}{\varnothing} &

\color{orange}{1 \text{ or } 2} &

\color{gray}{S_{20}}

\end{bmatrix} \]
v_Enhance 2019-04-19 19:51:19
Let's move on the the right case.
v_Enhance 2019-04-19 19:51:36
(we'll deal with $S_{20}$ shortly )
cj13609517288 2019-04-19 19:51:46
THIS IS GETTING MESSIER EVERY MINUTE!!!
v_Enhance 2019-04-19 19:51:49
Hang in there!
v_Enhance 2019-04-19 19:52:19
Is the right case, what might $S_{21}$ and $S_{10}$ be?
AwesomeYRY 2019-04-19 19:52:48
123 or 134 for S21 and S10 can be 1 or 3
P_Groudon 2019-04-19 19:52:48
S_10 = 1 or 3 while S_21 = 123 or 134
jesun 2019-04-19 19:52:48
123 or 134 for s21 and 1 or 3 for s10
v_Enhance 2019-04-19 19:53:00
In the right case, we have $S_{21} = \{1,2,3\}$ or $S_{21} = \{1,3,4\}$; while $S_{10} = \{1\}$ or $S_{10} = \{3\}$.
v_Enhance 2019-04-19 19:53:21
OK, this is getting messy, so let's step back and see where we are before we keep diving further.
v_Enhance 2019-04-19 19:53:36
Our map right now looks like:

\[

\begin{bmatrix}

\color{blue}{12} &

\color{blue}{123} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{red}{12} &

\color{orange}{123 \text{ or } 124} \\

\color{blue}{\varnothing} &

\color{orange}{1 \text{ or } 2} &

\color{gray}{S_{20}}

\end{bmatrix}

\quad\text{ OR }\quad

\begin{bmatrix}

\color{blue}{12} &

\color{blue}{123} &

\color{blue}{1234} \\

\color{blue}{1} &

\color{red}{13} &

\color{orange}{123 \text{ or } 134} \\

\color{blue}{\varnothing} &

\color{orange}{1 \text{ or } 3} &

\color{gray}{S_{20}}

\end{bmatrix}

\]
v_Enhance 2019-04-19 19:54:02
Now here's the elephant in the room. We have $2^3 = 8$ cases so far, and for each of them we want to think about how many ways there are to fill $S_{20}$. Well, for each case, take a guess: how many might there be?
AlexLikeMath 2019-04-19 19:54:44
2
mathfun5 2019-04-19 19:54:44
2 each time
Ttugf 2019-04-19 19:54:44
2 for each
RaggedQuark2 2019-04-19 19:54:44
2 each
v_Enhance 2019-04-19 19:54:49
Yeah, the big surprise of this problem is that, no matter how we filled in the previous entries above and to the left, it seems there are always two ways to do it!
v_Enhance 2019-04-19 19:55:17
We're starting to see this in the binary choices for the red, and then the binary choices for the orange.
carzland 2019-04-19 19:55:20
So no more cases?
v_Enhance 2019-04-19 19:55:24
Not if I can avoid it
v_Enhance 2019-04-19 19:55:30
So we have a foothold now, but we want to be careful. I haven't told you what order I'm filling in the cells yet.
v_Enhance 2019-04-19 19:55:38
For example, if we were just starting the $n = 2$ example, it would be silly to try and fill in $S_{20}$ (very bottom-right) first: would cause all sorts of issues.
v_Enhance 2019-04-19 19:55:59
So I want to fill in my grid (after all the blue entries) in such a way that it'll be true we always have two ways to do it.
v_Enhance 2019-04-19 19:56:13
What's a reasonable order to hit the grey cells in, in general?
hliu1 2019-04-19 19:56:58
just go in red diagonal, orange diagonal, etc. (aka just diagonals)
snow_monkey 2019-04-19 19:56:58
S11, S21, S10, S20
annoynymous 2019-04-19 19:56:58
top left corner to bottom right corner
mathfun5 2019-04-19 19:56:58
We could fill it starting at the top and going down each row, then moving to the next column and repeating (so this way the cells to the left and above are always filled)
Eyed 2019-04-19 19:56:58
minor diagonals
v_Enhance 2019-04-19 19:57:06
All of these work (and then some)
v_Enhance 2019-04-19 19:57:34
So let me set up a way that will handle all of these:
v_Enhance 2019-04-19 19:57:49
MO4 KEY CLAIM: suppose we are filling in the grid in the order described above. Consider a $2 \times 2$ square, as shown below.
\[ \begin{bmatrix}
\color{red}{ S \cup \{a\}} & \color{red}{ S \cup \{a,b\}} \\
\color{red}{ S} & \color{gray}{ ?}
\end{bmatrix} \]
There are exactly two ways to fill in $\color{gray}{ ?}$.
v_Enhance 2019-04-19 19:58:07
What are they?
Brendanb4321 2019-04-19 19:58:39
SU{a},SU{b}
porkemon2 2019-04-19 19:58:39
add a or add b
Brudder 2019-04-19 19:58:39
s union b and s union a
snow_monkey 2019-04-19 19:58:39
S U {a}

S U {b}
AlexLikeMath 2019-04-19 19:58:39
S U a or S U b
v_Enhance 2019-04-19 19:58:51
Yes, we put either $S \cup \{a\}$ or $S \cup \{b\}$.
v_Enhance 2019-04-19 19:59:10
And as long as we pick a sensible order, the claim will keep giving us the factors of $2$ we want. (Let's just standardize and choose minor diagonals, since that seemed to the most popular.)
v_Enhance 2019-04-19 19:59:43
OK, lots of stuff happened. Let's wrap everything up for general $n$.
v_Enhance 2019-04-19 19:59:59
First, I want to pick that far west and far north border as before: decide on $\varnothing = S_{00} \subset S_{01} \subset \dots S_{0n} \subset S_{1n} \subset \dots \subset S_{nn}$. How many ways can I do this?
v_Enhance 2019-04-19 20:00:09
(This is the generalization of the $4! = 24$ question from before.)
mathfun5 2019-04-19 20:00:25
$(2n)!$
Magnitude 2019-04-19 20:00:25
(2n)!
cj13609517288 2019-04-19 20:00:25
$(2n)!$
ilovemath04 2019-04-19 20:00:28
$(2n)!$
v_Enhance 2019-04-19 20:00:31
It'll be $(2n)!$, like in the previous example. There are $2n$ ways for $S_{01}$, $2n-1$ for $S_{02}$, and so on.
v_Enhance 2019-04-19 20:00:36
For illustration, here's $n = 4$.

\[

\begin{bmatrix}

\color{blue}{ 5 \text{ choices}} &

\color{blue}{4 \text{ choices}} &

\color{blue}{3 \text{ choices}} &

\color{blue}{2 \text{ choices}} &

\color{blue}{ 12345678} \\

\color{blue}{ 6 \text{ choices}} &

\color{gray}{S_{13}} &

\color{gray}{S_{23}} &

\color{gray}{S_{33}} &

\color{gray}{S_{43}} \\

\color{blue}{ 7 \text{ choices}} &

\color{gray}{S_{12}} &

\color{gray}{S_{22}} &

\color{gray}{S_{32}} &

\color{gray}{S_{42}} \\

\color{blue}{ 8 \text{ choices}} &

\color{gray}{S_{11}} &

\color{gray}{S_{21}} &

\color{gray}{S_{31}} &

\color{gray}{S_{41}} \\

\color{blue}{ \varnothing } &

\color{gray}{S_{10}} &

\color{gray}{S_{20}} &

\color{gray}{S_{30}} &

\color{gray}{S_{40}} \\

\end{bmatrix}

\]
v_Enhance 2019-04-19 20:00:46
And like before, since the names of the numbers don't matter, I'll just pick $1$, $2$, $\ldots$, up to $2n$.
v_Enhance 2019-04-19 20:01:01
\[

\begin{bmatrix}

\color{blue}{ 1234 } &

\color{blue}{ 12345} &

\color{blue}{ 123456} &

\color{blue}{ 1234567} &

\color{blue}{ 12345678} \\

\color{blue}{ 123 } &

\color{gray}{S_{13}} &

\color{gray}{S_{23}} &

\color{gray}{S_{33}} &

\color{gray}{S_{43}} \\

\color{blue}{ 12 } &

\color{gray}{S_{12}} &

\color{gray}{S_{22}} &

\color{gray}{S_{32}} &

\color{gray}{S_{42}} \\

\color{blue}{ 1 } &

\color{gray}{S_{11}} &

\color{gray}{S_{21}} &

\color{gray}{S_{31}} &

\color{gray}{S_{41}} \\

\color{blue}{ \varnothing } &

\color{gray}{S_{10}} &

\color{gray}{S_{20}} &

\color{gray}{S_{30}} &

\color{gray}{S_{40}} \\

\end{bmatrix}

\]
v_Enhance 2019-04-19 20:01:09
So we've made our initial $(2n)!$ choices by picking the blue border.
v_Enhance 2019-04-19 20:01:31
Then again we want to fill in the remaining $n \times n$ grid, minor diagonals. (For example, when $n=4$, $S_{13}$ could be either $1234$ or $1235$, then we pick $S_{23}$ and $S_{12}$, etc.)
v_Enhance 2019-04-19 20:01:35
And so how if we keep using our claim, how many ways to go?
RaggedQuark2 2019-04-19 20:02:02
2^(n^2)
ilovemath04 2019-04-19 20:02:02
2^(n^2)
wolfpack 2019-04-19 20:02:02
2^(n^2)
Damalone 2019-04-19 20:02:02
2^{n^2}
v_Enhance 2019-04-19 20:02:11
It's $2$ choices per cell. So $2^{n^2}$.
v_Enhance 2019-04-19 20:02:13
And so what's the final answer?
annoynymous 2019-04-19 20:02:37
total is (2n)!x 2^(n^2)
Generic_Username 2019-04-19 20:02:37
$(2n)!2^{(n^2)}$
jishu2003 2019-04-19 20:02:37
$(2n)!2^{n^2}$
mathfun5 2019-04-19 20:02:37
$(2n)! \cdot 2^{n^2}$
v_Enhance 2019-04-19 20:02:45
Yep, $(2n)! \cdot 2^{n^2}$ is it. We gucci.
Damalone 2019-04-19 20:02:52
Beautiful problem
v_Enhance 2019-04-19 20:03:09
Agreed!
annoynymous 2019-04-19 20:03:13
what makes you think of using this grid
v_Enhance 2019-04-19 20:03:33
You can write the solution without the grid too. However, because the indices are double indexed in this way, I think it's easier to visualize this way.
v_Enhance 2019-04-19 20:03:57
In general you're always welcome to draw pictures for problems if you're not changing the statement. I do it all the time.
chesstoastmaster 2019-04-19 20:04:06
are there other ways than the grid?
v_Enhance 2019-04-19 20:04:12
Yes, check the forums!
cj13609517288 2019-04-19 20:04:15
Consider how many ways will happen if n=100.
v_Enhance 2019-04-19 20:04:18
Bigggg.
v_Enhance 2019-04-19 20:04:40
Any last questions?
P_Groudon 2019-04-19 20:05:05
On to JMO 6 / AMO 5
goodball 2019-04-19 20:05:05
Can we move to the next problem?
v_Enhance 2019-04-19 20:05:09
I guess that works.
v_Enhance 2019-04-19 20:05:16
JMO6/MO5. Two rational numbers \(\tfrac{m}{n}\) and \(\tfrac{n}{m}\) are written on a blackboard, where \(m\) and \(n\) are relatively prime positive integers. At any point, I may pick two of the numbers \(x\) and \(y\) written on the board and write either their arithmetic mean \(\tfrac{x+y}{2}\) or their harmonic mean \(\tfrac{2xy}{x+y}\) on the board as well. Find all pairs \((m,n)\) such that I can write 1 on the board in finitely many steps.
mathfun5 2019-04-19 20:05:42
Ooh my favorite problem
CantonMathGuy 2019-04-19 20:05:50
where did Evan go?
v_Enhance 2019-04-19 20:05:53
Teaching class.
v_Enhance 2019-04-19 20:06:06
House-keeping reminders: this is another "find all" problem. So it automatically has two parts: we need to prove a statement of the form "the goal is possible if and only if [answer]".
cj13609517288 2019-04-19 20:06:41
Where do x and y come from here?
v_Enhance 2019-04-19 20:07:00
$x$ and $y$ can be any two numbers on the blackboard. So after the first step, you'll have three numbers to choose from, etc.
v_Enhance 2019-04-19 20:07:27
In the previous problem, we broke it down by considering specific cases like $n = 2$ first. In this problem, I'm going to do the opposite: I'm going to try to talk about a more GENERAL problem, and see where it goes. We won't be able to solve it, but we'll see the right idea come out.
v_Enhance 2019-04-19 20:07:41
So I'm going to for now ignore the condition that the two given rational numbers are reciprocals.
v_Enhance 2019-04-19 20:07:51
Instead, let's suppose the problem started off with two ARBITRARY positive rational numbers $a$ and $b$ on the blackboard, and see what we can say there.
v_Enhance 2019-04-19 20:07:58
(Zen philosophy comment for experts: this is worth thinking about because there's no reason why the reciprocal of the first number should matter; after some point we get all sorts of numbers on the board anyways.)
v_Enhance 2019-04-19 20:08:05
MO5, FIRST PART: IMPOSSIBILITY.
v_Enhance 2019-04-19 20:08:09
Okay, well, let me start with a dumb case. What if $a = b$?
eisirrational 2019-04-19 20:08:40
Only $a$ can be written
ev3commander 2019-04-19 20:08:40
lost unless a=1=b
azmath333 2019-04-19 20:08:40
Good luck getting anywhere
ketul 2019-04-19 20:08:40
you only get one number
snow_monkey 2019-04-19 20:08:40
same number over and over
v_Enhance 2019-04-19 20:08:43
Yeah, then you can only ever write one number on the board. So that case is very easy.
v_Enhance 2019-04-19 20:08:55
Applying wishful thinking, though, I want something that works like $a = b$.
v_Enhance 2019-04-19 20:09:05
So here's the key idea: what if we had \[ a \equiv b \pmod p \] instead of the (too-strong) $a=b$?
porkemon2 2019-04-19 20:09:25
every number will always be the same mod p
v_Enhance 2019-04-19 20:09:28
Maybe all the numbers would then be the same modulo $p$?
v_Enhance 2019-04-19 20:09:33
Well, okay, this is already going to cause problems because what does it mean to have a fraction modulo $p$?
v_Enhance 2019-04-19 20:09:41
Well, it turns out you can do this: the short version you can remember is: "as long as you don't divide by zero, everything is okay".
v_Enhance 2019-04-19 20:09:49
I really could dedicate a whole class to working with inverses modulo $p$, but here's the spark-notes version.
v_Enhance 2019-04-19 20:10:00
Definition. Let $a = \frac xy$ and let $p$ be a prime. Then we say $a \pmod p$ is congruent to $k$ if
$\bullet$ $x \equiv yk \pmod p$, and
$\bullet$ $y \not\equiv 0 \pmod p$.
We don't define $a \pmod p$ if the denominator is divisible by $p$ though.
kevinmathz 2019-04-19 20:10:20
inverse
hliu1 2019-04-19 20:10:20
x*1/y i guess
Damalone 2019-04-19 20:10:20
inverses
v_Enhance 2019-04-19 20:10:32
Yep, those of you that know about modular inverses already see where this is going.
v_Enhance 2019-04-19 20:11:07
I won't use that word, but here's an example for those of you new to it. What is $\frac{13}{5} \pmod 7$?
beiqiang 2019-04-19 20:11:42
13 * 3 = 39 = 4
jishu2003 2019-04-19 20:11:42
4
Brendanb4321 2019-04-19 20:11:42
4
v_Enhance 2019-04-19 20:11:46
We say $\frac{13}{5} \equiv 4 \pmod 7$, since $7 \mid 13 - 4 \cdot 5$. (I'm sweeping under the rug that there's a "unique" answer, but maybe some of you can already see why.)
v_Enhance 2019-04-19 20:11:59
OK, so with that definition set, here's our hope.
v_Enhance 2019-04-19 20:12:00
MO5 CONJECTURE 1: If $a$ and $b$ are both $k \pmod p$, for some prime $p$, then $\frac{a+b}{2}$ is $k \pmod p$ too.
v_Enhance 2019-04-19 20:12:13
Do we think that's true?
Brendanb4321 2019-04-19 20:12:40
iff p>2
mathfun5 2019-04-19 20:12:40
True for all p except 2
v_Enhance 2019-04-19 20:12:45
It's ALMOST true. Let's work it out and see what could go wrong.
v_Enhance 2019-04-19 20:13:04
Suppose $a = \frac{x}{y}$ and $b = \frac{x'}{y'}$ are both $k \pmod p$, meaning $ky-x \equiv ky'-x' \equiv 0 \pmod p$ and $p$ does not divide $y$ or $y'$.
v_Enhance 2019-04-19 20:13:08
Can someone compute $\frac{a+b}{2}$ for me?
hliu1 2019-04-19 20:13:38
$\frac{xy'+yx'}{2yy'}$
v_Enhance 2019-04-19 20:13:54
It equals \[ \frac{a+b}{2} = \frac{\frac xy + \frac{x'}{y'}}{2} = \frac{xy'+x'y}{2yy'}. \]
v_Enhance 2019-04-19 20:13:55
Well we wanted $xy' + x'y \equiv k \cdot 2yy' \pmod p$. As $x \equiv ky$ and $x' \equiv ky'$, that part is good.
v_Enhance 2019-04-19 20:14:03
But we also required that the denominators were never divisible by $p$. And we have a denominator of $2yy'$.
v_Enhance 2019-04-19 20:14:10
So if $p=2$ we are in trouble. But otherwise, we're okay.
porkemon2 2019-04-19 20:14:28
can you do (k+k)/2 instead?
v_Enhance 2019-04-19 20:14:44
Yes, if you have fully set up modular inverses well. I'm working mostly with bare hands here for the sake of people who haven't seen that yet.
v_Enhance 2019-04-19 20:14:55
So the fixed claim is:
v_Enhance 2019-04-19 20:14:57
MO5 CLAIM 1: Let $p$ be an odd prime. If $a$ and $b$ are rational numbers both $k \pmod p$, then $\frac{a+b}{2} \equiv k \pmod p$ too.
v_Enhance 2019-04-19 20:15:11
Just don't divide by zero. All good?
EricK0504 2019-04-19 20:15:26
yes mr chen
v_Enhance 2019-04-19 20:15:31
You can just call me Evan.
beibeizhu 2019-04-19 20:15:38
why would this involve dividing by 0?
v_Enhance 2019-04-19 20:15:58
When $p=2$, we get $2=0$, so then when we take the average we divide by zero. It's a bit tragic, really...
v_Enhance 2019-04-19 20:16:33
Let's also try to check the harmonic mean. What we're hoping is:
v_Enhance 2019-04-19 20:16:36
MO5 CONJECTURE 2: If $a$ and $b$ are rational numbers both $k \pmod p$, and $p > 2$, then $\frac{2ab}{a+b}$ is $k \pmod p$ too.
v_Enhance 2019-04-19 20:16:48
This time we've learned to be afraid of $2$ already, so I already took care of that. Do you think that's true now?
azmath333 2019-04-19 20:17:19
a+b can't divide p either
mathfun5 2019-04-19 20:17:19
If a+b is not 0 mod p
v_Enhance 2019-04-19 20:17:22
Good eyes.
v_Enhance 2019-04-19 20:17:36
Again, it's almost true, but not quite.
v_Enhance 2019-04-19 20:17:51
I'll write down the proof for completeness, for the paranoid out there.
v_Enhance 2019-04-19 20:17:58
If $a = \frac{x}{y}$ and $b = \frac{x'}{y'}$, one finds \[ \frac{2ab}{a+b} = \frac{2xx'}{xy' + x'y}. \]
v_Enhance 2019-04-19 20:18:06
Well, if we want $2xx' \equiv k \cdot (xy' + x'y)$, then again that just follows since $x \equiv ky \pmod p$, $x' \equiv ky' \pmod p$.
v_Enhance 2019-04-19 20:18:26
However, we're worried that the denominator $xy' + x'y$ might be divisible by $p$.
v_Enhance 2019-04-19 20:18:39
We have \[ xy' + x'y \equiv 2kyy' \pmod p \] and so this happens not only if $p = 2$, but also possibly when $k \equiv 0$.
v_Enhance 2019-04-19 20:18:54
But otherwise we're okay.
v_Enhance 2019-04-19 20:18:57
So here is the updated fix:
v_Enhance 2019-04-19 20:19:03
MO5 CLAIM 2: If $p > 2$ is prime, and $a$ and $b$ are rational numbers both $k \pmod p$, and $k \not\equiv 0 \pmod p$, then $\frac{2ab}{a+b}$ is $k \pmod p$ too.
carzland 2019-04-19 20:19:30
We good now?
v_Enhance 2019-04-19 20:19:34
Thankfully.
v_Enhance 2019-04-19 20:19:49
So here's the abridged version: subject to some worrisome divide-by-zero conditions, we can try to take the initial fractions on our board modulo $p$, and if they happen to both be some nonzero residue $k \pmod p$, then all the numbers on the board will forever be $k \pmod p$ as well.
v_Enhance 2019-04-19 20:19:54
And that gives us a way to try and get an invariant.
v_Enhance 2019-04-19 20:20:09
With me so far?
ketul 2019-04-19 20:20:23
Yes, God
v_Enhance 2019-04-19 20:20:29
Again, "Evan" is fine...
v_Enhance 2019-04-19 20:20:34
Okay, now let's see how many cases this lets us rule out in the original problem where $a = \frac mn$ and $b = \frac nm$.
v_Enhance 2019-04-19 20:20:44
Given relatively prime integers $m$ and $n$, for which primes $p$ do we have $\frac mn \equiv \frac nm \pmod p$?
v_Enhance 2019-04-19 20:20:59
(In terms of $m$ and $n$.)
mathfun5 2019-04-19 20:21:31
we need a/b = -1 or 1 mod p, so p divides a+b or a-b
Damalone 2019-04-19 20:21:31
m^2-n^2 is divisible by p
v_Enhance 2019-04-19 20:21:38
Yeah, by the definition it's just the primes $p \mid m^2-n^2$.
v_Enhance 2019-04-19 20:21:42
I'll point a different conceptual (and more natural) way of thinking about it though: if $x = \frac mn$ we are hoping for \begin{align*} x &\equiv \frac 1x \pmod p \\ \iff x^2 - 1 &\equiv 0 \pmod p \\ \iff x &\equiv 1 \pmod p \quad\text{ or }\quad x \equiv -1 \pmod p. \end{align*}
v_Enhance 2019-04-19 20:21:54
Now the target number is $1$.
v_Enhance 2019-04-19 20:22:01
So if there's a single prime $p > 2$ such that $\frac mn \equiv -1 \pmod p$, then all numbers on the board will always be $-1 \pmod p$, and we are all good to go.
v_Enhance 2019-04-19 20:22:24
That should narrow down things a lot! What's left at the end of the day?
mathfun5 2019-04-19 20:22:43
m+n is a power of 2
cj13609517288 2019-04-19 20:22:43
So they must be powers of $2$. Whoa!!!
mathguy623 2019-04-19 20:22:58
m+n cant be divisible by any odd prime
v_Enhance 2019-04-19 20:23:00
We have $\frac mn \equiv -1 \pmod p \iff p \mid m+n$, so unless $m+n$ is a power of $2$, we're actually all set.
v_Enhance 2019-04-19 20:23:33
Taking fractions modulo $p$ is real strong. Keep that in mind in future number theory.
porkemon2 2019-04-19 20:24:01
what if p|(x-1)?
v_Enhance 2019-04-19 20:24:23
If $x \equiv 1 \pmod p$, then all the numbers on the board will indeed stay $1 \pmod p$ forever. However, that's not the invariant we want, because the target number is also $1$. That's why we switch to $-1$ instead.
v_Enhance 2019-04-19 20:24:40
MO5, SECOND PART: CONSTRUCTION.
v_Enhance 2019-04-19 20:24:59
We've already ruled out so many cases, we might expect the construction to not be so bad.
v_Enhance 2019-04-19 20:25:06
Let's go back again to having two general numbers $a$ and $b$. Here's again an easier special case: how far can we get from just using the arithmetic mean? (You'll see in a moment why this is related to powers of $2$.)
v_Enhance 2019-04-19 20:25:12
For starters, here is $a$ and $b$ and their average, $\dfrac{a+b}{2}.$
v_Enhance 2019-04-19 20:25:14
v_Enhance 2019-04-19 20:25:25
Now if use our operation again, what numbers could we get?
P_ksAreAllEquivalent 2019-04-19 20:25:56
a+3b/4, 3a+b/4
goodball 2019-04-19 20:25:56
The quarters
AwesomeYRY 2019-04-19 20:25:56
3a+b/4 and a+3b/4
carzland 2019-04-19 20:25:56
The midpoints of the two segments
v_Enhance 2019-04-19 20:25:59
We can get $\frac{3a+b}{4}$ and $\frac{a+3b}{4}$. So let's just put them all on the board.
v_Enhance 2019-04-19 20:26:01
v_Enhance 2019-04-19 20:26:06
Okay, where can I get if I try to get more arithmetic means?
P_ksAreAllEquivalent 2019-04-19 20:26:23
more midpoints!
goodball 2019-04-19 20:26:23
The eighths
mhuangw 2019-04-19 20:26:23
The midpoints of the 4 segments
v_Enhance 2019-04-19 20:26:36
Yeah, by now you probably see the pattern. We get those fractions with denominator $8$.
beiqiang 2019-04-19 20:26:55
dyadic rational sections between a and b
kevinmathz 2019-04-19 20:26:55
you get every $2^k$th index
v_Enhance 2019-04-19 20:27:12
Huh, that picture is also obviously wrong. Let's see how fast I can fix asy pictures.
mhuangw 2019-04-19 20:27:29
6 min later...
v_Enhance 2019-04-19 20:27:32
AMT1954 2019-04-19 20:27:39
there we go
azmath333 2019-04-19 20:27:51
wow that was fast
budu 2019-04-19 20:27:51
how r u so good
goodball 2019-04-19 20:27:51
Whoa that was fast!
v_Enhance 2019-04-19 20:27:54
Lots of practice.
v_Enhance 2019-04-19 20:28:08
We can get any "power of $2$" combination: that is, if $u$ and $v$ are fractions with $u+v = 1$ and whose denominator is a power of $2$, then we can get $u \cdot a + v \cdot b = 1$.
v_Enhance 2019-04-19 20:28:13
So now let's go back to the original problem and see how many numbers we can get out of it. Our initial numbers were $\frac mn$ and $\frac nm$. What are the weights $u$ and $v$ for which we can get our target \[ u \cdot \frac mn + v \cdot \frac nm = 1 \] and $u+v=1$?
v_Enhance 2019-04-19 20:28:49
(So, I'm just asking you to solve the system of equations for $u$ and $v$.)
P_ksAreAllEquivalent 2019-04-19 20:29:32
n/(m+n), m/(m+n)
mathfun5 2019-04-19 20:29:32
u=n/(m+n), v=m/(m+n) which works because m+n is a power of 2
v_Enhance 2019-04-19 20:29:46
Yeah, it's $u = \frac{n}{m+n}$ and $v = \frac{m}{m+n}$, which has powers of $2$ in the denominator by hypothesis!
P_ksAreAllEquivalent 2019-04-19 20:30:06
we win
v_Enhance 2019-04-19 20:30:14
Yep. That means our dyadic construction in the picture just works out of the box. No need to even use harmonic mean.
v_Enhance 2019-04-19 20:30:20
That is game, set, match. The answer is that the goal is possible if $m+n$ is a power of $2$.
SpecialBeing2017 2019-04-19 20:30:34
This is brilliant...
v_Enhance 2019-04-19 20:30:41
Phew. That was a long explanation. Hopefully some of you learned a bit of new number theory in doing this: fractions work modulo $p$ as long as you don't divide by zero. Super useful fact, so remember that if you ever run into integer equations that have fractions in them.
chesstoastmaster 2019-04-19 20:30:56
cool math
v_Enhance 2019-04-19 20:30:57
And for those of you that do know this already, hopefully you learned some more zen philosophy. In my opinion, the most unnatural thing about the entire problem was why the given involved two reciprocal fractions $\frac mn$ and $\frac nm$, when they really could have been any numbers $a$ and $b$.
v_Enhance 2019-04-19 20:31:08
That's why so much of my motivation was of the form "let's think about the general situation with $a$ and $b$": because there is no clear reason that $ab = 1$ is related to either operation that's happening.
v_Enhance 2019-04-19 20:31:26
(Of course, I'm also telling an idealized version of the story of how I came up with this solution, since I don't have time during the Math Jam to lead you down wrong paths too far. There are other promising-looking approaches that fail, like for example trying to look at size of the numbers, that don't pan out.)
bluelinfish 2019-04-19 20:31:31
time for JMO 4
v_Enhance 2019-04-19 20:31:42
Yep.
v_Enhance 2019-04-19 20:31:47
JMO4. Let $ABC$ be a triangle with $\angle ABC$ obtuse. The $A$-excircle is a circle in the exterior of $\triangle ABC$ that is tangent to side $BC$ of the triangle and tangent to the extensions of the other two sides. Let $E$, $F$ be the feet of the altitudes from $B$ and $C$ to lines $AC$ and $AB$, respectively. Can line $EF$ be tangent to the $A$-excircle?
v_Enhance 2019-04-19 20:31:57
Yes/no geometry. Been a while since that's happened, huh?
v_Enhance 2019-04-19 20:32:01
Well, how do we start every geometry problem?
Math4Fun04 2019-04-19 20:32:11
diagram
carzland 2019-04-19 20:32:11
A wild geometry appeared
goodball 2019-04-19 20:32:11
Geometry= draw a diagram
Brendanb4321 2019-04-19 20:32:11
diagram
P_ksAreAllEquivalent 2019-04-19 20:32:11
diagram
v_Enhance 2019-04-19 20:32:20
Yep.
Charmander3333 2019-04-19 20:32:23
coordinate bash
v_Enhance 2019-04-19 20:32:25
v_Enhance 2019-04-19 20:32:31
So anyways here's a diagram.
v_Enhance 2019-04-19 20:32:43
I think that just about settles it. Ready to move on?
P_ksAreAllEquivalent 2019-04-19 20:33:14
wow so accurate!
Brendanb4321 2019-04-19 20:33:14
no
molocyxu 2019-04-19 20:33:14
No but yes
v_Enhance 2019-04-19 20:33:21
Of course that's not a proof. (And the figure is actually distorted slightly: otherwise $A$ would be way off-screen.)
Eyed 2019-04-19 20:34:15
Wait aren't F and E switched?
v_Enhance 2019-04-19 20:34:18
v_Enhance 2019-04-19 20:34:28
Didn't see nothing there. ;)
deadwindow 2019-04-19 20:34:35
all hail edit god
molocyxu 2019-04-19 20:34:58
CALL HIM EVAN
v_Enhance 2019-04-19 20:35:01
So let's start with the geometry...
v_Enhance 2019-04-19 20:35:13
First of all, what do people know about quadrilateral $BECF$, even without the excircle involved?
snow_monkey 2019-04-19 20:35:39
cyclic
Magnitude 2019-04-19 20:35:39
concyclic
epicjing333 2019-04-19 20:35:39
cyclic
ketul 2019-04-19 20:35:39
Cyclic
porkemon2 2019-04-19 20:35:39
its cyclic with opposite right angles
v_Enhance 2019-04-19 20:35:42
The quadrilateral $BFCE$ is cyclic, inscribed in a circle with diameter $BC$.
v_Enhance 2019-04-19 20:35:56
Now you can think of the excircle as follows: it's actually a circle tangent to lines $BC$, $EF$, $CF$, $BE$.
v_Enhance 2019-04-19 20:36:08
That is, "self-intersecting quadrilateral $BCFE$ has an excircle". So we actually don't have to think about $A$ in the problem.
AlexLikeMath 2019-04-19 20:36:17
How is it cyclic?
v_Enhance 2019-04-19 20:36:49
We have $\angle E = \angle F = 90^{\circ}$, so the opposite angles sum to $90^{\circ}$.
v_Enhance 2019-04-19 20:36:55
Now I realize most of you probably aren't so comfortable with self-intersecting quadrilaterals, so let's talk about a case you're more used to. Do you know anything about normal convex quadrilaterals that have incircles?
The_Turtle 2019-04-19 20:37:09
sum to 180*
cj13609517288 2019-04-19 20:37:17
Um it is supposed to be 180 degrees.
v_Enhance 2019-04-19 20:37:20
Man I'm really slipping up today.
v_Enhance 2019-04-19 20:37:37
But anyways, as far as incircles go...
annoynymous 2019-04-19 20:37:49
Pitot
mathfun5 2019-04-19 20:37:49
Pitots theorem: sum of opposite sides is equal
jj_ca888 2019-04-19 20:37:49
pitots => AB + CD = BC + AD
Harry0531 2019-04-19 20:37:49
Opposite sides add up to be equal in quadrilaterals with incircles
Kagebaka 2019-04-19 20:37:49
pithot --> sum of opposite sides are equal
franchester 2019-04-19 20:37:49
Pitot’s theorem
v_Enhance 2019-04-19 20:37:57
The so-called Pitot theorem states that in a normal convex quadrilateral with an incircle, the opposite sides have equal length. And you can see why from the picture below.
v_Enhance 2019-04-19 20:38:02
//cdn.artofproblemsolving.com/images/c/f/d/cfddfe83ba4f0b7e247c39184da069fc43d4a55e.png
v_Enhance 2019-04-19 20:38:03
(Relevant link: https://en.wikipedia.org/wiki/Pitot_theorem)
v_Enhance 2019-04-19 20:38:24
So now I claim you can say something similar here. Anyone able to work out what side relations we get?
v_Enhance 2019-04-19 20:38:43
(For our quadrilateral $BECF$.)
Harry0531 2019-04-19 20:39:03
I heard that proving the converse of Pitot is way harder.
v_Enhance 2019-04-19 20:39:05
It is indeed more involved. However, we won't need the converse tonight, so I won't use it, but it's good to know.
cj13609517288 2019-04-19 20:39:09
EB+CF=EC+BF
P_ksAreAllEquivalent 2019-04-19 20:39:09
EF + FB = BC + EC?
Awesome_guy 2019-04-19 20:39:09
EB+CF=CE+BF
Ashrafuzzaman_Nafees 2019-04-19 20:39:09
EC + BF = EB + CF
P_ksAreAllEquivalent 2019-04-19 20:40:18
isn't the above for incircle?
v_Enhance 2019-04-19 20:40:26
Oh geez, I think I flipped all the $E$'s and $F$'s in my notes.
v_Enhance 2019-04-19 20:41:07
Well, let's just run with it, and hope I work out the right formula at the end
v_Enhance 2019-04-19 20:41:25
Let's prove this. Let $t(B)$ denote the length of the tangent from $B$ to the $A$-excircle, and define $t(C)$, $t(E)$, $t(F)$ in the same way.
v_Enhance 2019-04-19 20:41:34
Can someone write $BF$ in terms of these tangent lengths for me?
P_ksAreAllEquivalent 2019-04-19 20:41:38
also what if there are config issues , could it change depending on config
v_Enhance 2019-04-19 20:41:55
Thankfully, the problem tells you $\angle B > 90^{\circ}$, so most of thm go away.
ketul 2019-04-19 20:42:06
$BF=t(b)-t(f)$
hliu1 2019-04-19 20:42:06
tB-tF
v_Enhance 2019-04-19 20:42:23
We have $BF = t(B) - t(F)$.
v_Enhance 2019-04-19 20:42:44
Now what about $EF$? In the picture, I claim $EF$ is the sum of two tangent lengths. Which?
ketul 2019-04-19 20:43:11
$EF = t(E)+t(F)$
Magnitude 2019-04-19 20:43:11
t(E) + t(f)
snow_monkey 2019-04-19 20:43:11
t(E) + t(F)
v_Enhance 2019-04-19 20:43:20
Great.
ketul 2019-04-19 20:43:24
$BC=t(B)+t(C)$
v_Enhance 2019-04-19 20:43:27
And there's $BC$.
ketul 2019-04-19 20:43:33
$EC=t(e)-t(c)$
v_Enhance 2019-04-19 20:43:42
And there's $CE$. We have $BC = t(B) + t(C)$ and $EC = t(E) - t(C)$.
v_Enhance 2019-04-19 20:43:59
So if I put these four equations together, what length relation do I get?
v_Enhance 2019-04-19 20:44:16
i.e. what Pitot-like theorem holds for our self-intersecting quadrilateral?
hliu1 2019-04-19 20:44:19
doesn't EF=t(E)+t(F) assume that EF is tangent to the A-excircle?
v_Enhance 2019-04-19 20:44:40
Yes, sorry. I'm assuming $EF$ is tangent to the $A$-excircle, and then seeing what comes out of it.
mathfun5 2019-04-19 20:44:52
BF+EF=BC+EC
snow_monkey 2019-04-19 20:44:52
BC + EC = BF + EF
v_Enhance 2019-04-19 20:45:24
We get \[ BC + EC = BF + EF \] as the $t$ terms now all line up: both sides are equal to $t(B) + t(E)$.
cj13609517288 2019-04-19 20:45:42
Ptolemy?
v_Enhance 2019-04-19 20:45:58
Good idea. Let's try it!
awesomemaths 2019-04-19 20:46:29
on wwhich quadrilateral??
v_Enhance 2019-04-19 20:46:37
We will apply Ptolemy on $BECF$, our cyclic quadrilateral.
v_Enhance 2019-04-19 20:46:50
Let me scale so that $BC = 1$, and then let $x = BF$, $y = CE$.
v_Enhance 2019-04-19 20:47:01
First of all, I need the other two sides. Can someone tell me $BE$ and $CF$ in terms of $x$ and $y$?
v_Enhance 2019-04-19 20:47:38
(Remember: $\angle E$ and $\angle F$ are right angles, and $BC=1$ is a hypotenuse!)
Awesome_guy 2019-04-19 20:48:13
sqrt(1-x^2)
hliu1 2019-04-19 20:48:13
sqrt(1-x^2) and sqrt(1-y^2)
porkemon2 2019-04-19 20:48:13
BE = sqrt(1-y^2), CF = sqrt(1-x^2)
rjiangbz 2019-04-19 20:48:13
sqrt(1-x^2)
Eyed 2019-04-19 20:48:13
$\sqrt{1-x^{2}}$, $\sqrt{1-y^{2}}$
v_Enhance 2019-04-19 20:48:31
By the Pythagorean theorem, we have $BE = \sqrt{1-y^2}$, $CF = \sqrt{1-x^2}$.
cj13609517288 2019-04-19 20:48:57
Let's do some ultimate bashing now!
v_Enhance 2019-04-19 20:49:05
It'll be a bit cleaner than that.
v_Enhance 2019-04-19 20:49:08
So Ptolemy's theorem tells us that
v_Enhance 2019-04-19 20:49:21
\[ BE \cdot CF + BF \cdot CE = BC \cdot EF \]
v_Enhance 2019-04-19 20:49:41
We know everything on the left-hand side, so the last term not in terms of $x$ and $y$ is that $EF$.
v_Enhance 2019-04-19 20:49:58
But since we know $BC+EC = BF+EF$, can we write $EF$ in terms of $x$ and $y$?
snow_monkey 2019-04-19 20:50:15
1+y-x
v_Enhance 2019-04-19 20:50:31
The equation becomes $EF = 1+y-x$.
v_Enhance 2019-04-19 20:50:34
And so now Ptolemy's theorem says that
v_Enhance 2019-04-19 20:50:56
\[ \sqrt{1-y^2} \cdot \sqrt{1-x^2} + xy = 1 \cdot (1+y-x). \]
v_Enhance 2019-04-19 20:51:26
A bit messy. Anyone want to clean it up for me?
molocyxu 2019-04-19 20:52:14
WAIT
molocyxu 2019-04-19 20:52:14
move xy to the right to get (1+y)(1-x)
beiqiang 2019-04-19 20:52:14
move xy, factor, square, cancel?
Generic_Username 2019-04-19 20:52:14
$(1-y^2)(1-x^2)=((1+y)(1-x))^2$
mathguy623 2019-04-19 20:52:14
$\sqrt{1-y^2} \cdot \sqrt{1-x^2} = (1+y)(1-x)$
v_Enhance 2019-04-19 20:52:27
This rearranges to give \[ (1+y)(1-x) = \sqrt{(1-x^2)(1-y^2)} \implies \frac{1+y}{1-y} = \frac{1+x}{1-x}. \]
v_Enhance 2019-04-19 20:52:41
So... what do you think that gives?
awesomemaths 2019-04-19 20:52:59
X = Y
awesomemaths 2019-04-19 20:52:59
x = y
molocyxu 2019-04-19 20:52:59
um x=y
v_Enhance 2019-04-19 20:53:03
And that implies $x=y$.
v_Enhance 2019-04-19 20:53:10
So actually, what can we say about $BFCE$?
Awesome_guy 2019-04-19 20:53:19
its a rectangle
molocyxu 2019-04-19 20:53:25
its a rectangle
v_Enhance 2019-04-19 20:53:30
It means $BFCE$ is a rectangle.
v_Enhance 2019-04-19 20:53:32
cj13609517288 2019-04-19 20:53:43
AMAZING
awesomemaths 2019-04-19 20:53:43
this whole time
v_Enhance 2019-04-19 20:53:56
And the means the answer is no. Because we have run into a contradiction: $BE$ and $CF$ are parallel, so they cannot intersect at any point $A$.
v_Enhance 2019-04-19 20:54:19
Summary: we assumed $EF$ was tangent, wrote down the Pitot theorem, and concluded that $BECF$ is a rectangle. But that causes lines $BF$ and $CE$ to not intersect.
v_Enhance 2019-04-19 20:54:26
Thus the point $A$ we thought was useless comes back to give a contradiction at the last moment.
cocohearts 2019-04-19 20:55:11
encore
jamesyhr 2019-04-19 20:55:11
wow
rjiangbz 2019-04-19 20:55:11
Woohoo for point A! You don't exist, point A!
v_Enhance 2019-04-19 20:55:32
Incidentally, this is not the shortest solution. I chose it because I wanted to showcase the Pitot theorem, and sort of do it without using too many ideas.
v_Enhance 2019-04-19 20:55:33
But:
jeffisepic 2019-04-19 20:55:37
I have a one liner: If ABC and AEF can't have the same excircle because AEF is similar but not congruent to ABC
budu 2019-04-19 20:55:43
you can also use AEF ~ ABC to get a nice solution
alifenix- 2019-04-19 20:55:50
reflection over angle bisector!
v_Enhance 2019-04-19 20:56:27
I'll let anyone who wants to work out the details.
mhuangw 2019-04-19 20:57:55
how many questions left?
Jupiter123 2019-04-19 20:57:55
To be exact, we have less than 30 minutes.
v_Enhance 2019-04-19 20:57:58
Alright, I only have half an hour left, so I'll probably skip to the MO2 geometry now --- as the MO1 functional equation is really very involved.
v_Enhance 2019-04-19 20:58:06
Sorry for any algebra fans.
v_Enhance 2019-04-19 20:58:20
JMO3/MO2. Let $ABCD$ be a cyclic quadrilateral satisfying $AD^2 + BC^2 = AB^2$. The diagonals of $ABCD$ intersect at $E$. Let $P$ be a point on side $\overline{AB}$ satisfying $\angle APD = \angle BPC$. Show that line $PE$ bisects $\overline{CD}$.
v_Enhance 2019-04-19 20:58:37
Well, okay, how do we start every geometry problem?
Jupiter123 2019-04-19 20:58:53
DRAW
cooljoseph 2019-04-19 20:58:53
We draw a diagram
rjiangbz 2019-04-19 20:58:53
draw a piccher!
Deegs 2019-04-19 20:58:53
DIAGRAM
hliu1 2019-04-19 20:58:53
then draw a diagram
v_Enhance 2019-04-19 20:58:56
We begin by drawing a diagram. Let me say a bit this time about how you might do it.
v_Enhance 2019-04-19 20:59:03
Because of the condition $AD^2 + BC^2 = AB^2$, you'll have to improvise a bit. So maybe in a contest, I would draw some big enough circle, then draw a chord of length $5$, then create chords of length $3$ and $4$ to get $ABCD$.
v_Enhance 2019-04-19 20:59:12
As for $P$, the condition $\angle DAP = \angle BPC$ is hard to work with. So what might we do instead?
alifenix- 2019-04-19 20:59:35
look at other condition and phantom point
cooljoseph 2019-04-19 20:59:42
Redefine P
v_Enhance 2019-04-19 20:59:45
Well, we can construct $E$, and the midpoint of $CD$. And we allegedly think $P$ is the intersection of $AB$ and $ME$. So that gives us a way to draw it without the angle conditions.
v_Enhance 2019-04-19 20:59:52
Okay, with that said, here's the diagram I promised you all.
v_Enhance 2019-04-19 20:59:55
awesomemaths 2019-04-19 21:00:14
wow thats an accurate diagram
v_Enhance 2019-04-19 21:00:16
Thanks.
v_Enhance 2019-04-19 21:00:28
But again I want to stress, if you set it up the right way, you can get an accurate one during the test with ruler and compass. No eyeball needed.
v_Enhance 2019-04-19 21:00:49
*eyeballing. You do need eyes.
v_Enhance 2019-04-19 21:00:54
Anyways that condition $AD^2 + BC^2 = AB^2$ is really weird. What are we going to do with it? (The condition $\angle DAP = \angle BPC$ is also not great.)
v_Enhance 2019-04-19 21:01:02
Well, does $AD^2 + BC^2 = AB^2$ remind people of anything?
awesomemaths 2019-04-19 21:01:29
pytahgeroen theorem
AwesomeYRY 2019-04-19 21:01:29
Pythagorean theorem
kevinmathz 2019-04-19 21:01:29
pythagorean theorem
jeffisepic 2019-04-19 21:01:29
pythagorean theorem
mathfun5 2019-04-19 21:01:29
Pythag!
v_Enhance 2019-04-19 21:01:53
Yeah, it sure looks like Pythag, sort of.
v_Enhance 2019-04-19 21:01:59
So here's what I'm going to do: construct right triangles with hypotenuse $AB$ and legs of length $AD$ and $BC$.
v_Enhance 2019-04-19 21:02:03
If I had a compass, how would I do that in the picture I gave you?
budu 2019-04-19 21:02:35
The length condition motivates the construction of the intersection of the circles centered at A through D and centered at B through C (let the point be F), as AFB is a right triangle by pythagorean theorem (and this also helps to construct the diagram)
mathfun5 2019-04-19 21:02:35
Circle centered at A with radius AD and likewise for B
Awesome_guy 2019-04-19 21:02:35
circle with center A and B
alifenix- 2019-04-19 21:02:45
draw a circle centered at A through D, one at B through C, intersect
v_Enhance 2019-04-19 21:02:49
Let's take the circle centered at $A$ with radius $AD$, and intersect it with the circle centered at $B$ with radius $BC$.
v_Enhance 2019-04-19 21:03:02
(If you followed my advice for drawing the initial diagram, you would even have these circles already.)
v_Enhance 2019-04-19 21:03:04
They'll meet at two points $X$ and $Y$. Here's the picture.
v_Enhance 2019-04-19 21:03:05
v_Enhance 2019-04-19 21:03:29
(You can pop out this diagram by double-clicking it, if it's distorted. Large diagram.)
v_Enhance 2019-04-19 21:03:50
Now here's the hardest part of the problem: in this diagram, do you see anything that looks like it might be true, that you didn't expect before?
jeffisepic 2019-04-19 21:05:10
X,P,Y are collinear?
mira74 2019-04-19 21:05:10
P is on XY?
cooljoseph 2019-04-19 21:05:10
They intersect on the same places as the intersections of DP and AC and the lines PC and BD! In fact, when these are reflected over the line AB they also hit the circle!
budu 2019-04-19 21:05:10
XP perpendicular to AB
alifenix- 2019-04-19 21:05:10
X, Y, P collinear....?
mathfun5 2019-04-19 21:05:10
Intersection of DB and CP lies on the circle
porkemon2 2019-04-19 21:05:18
AC, PD (CXY) looks like it coincides
khina 2019-04-19 21:05:18
xp is perpendicular to ab
v_Enhance 2019-04-19 21:05:24
Yep, I see two big ones:
v_Enhance 2019-04-19 21:05:25
First, it looks like lines $BD$ and $CP$ meet on the red circle. Symmetrically, lines $AC$ and $DP$ meet on the orange circle.
v_Enhance 2019-04-19 21:05:29
Second, $P$ looks like the midpoint of $XY$.
v_Enhance 2019-04-19 21:05:36
Let's mark these all in.
v_Enhance 2019-04-19 21:05:37
v_Enhance 2019-04-19 21:05:54
Let's think about the point $P$ first, since it's the main player of this problem.
v_Enhance 2019-04-19 21:06:16
We haven't proven any of our conjectures yet, so to emphasize this, I'm going to mark everything that follows as "wishful thinking."
v_Enhance 2019-04-19 21:06:17
BEGIN DREAM MODE
v_Enhance 2019-04-19 21:06:24
If $P$ really were the foot from $X$ to $AB$, then if we consider right triangle $AXB$, can you get some similarities?
mhuangw 2019-04-19 21:06:57
move it around
mathfun5 2019-04-19 21:06:57
AP*AB=AX^2
mira74 2019-04-19 21:06:57
APX similar to XPB
alifenix- 2019-04-19 21:06:57
AXP sim XBP sim ABX..?
hliu1 2019-04-19 21:06:57
APX and BPX
v_Enhance 2019-04-19 21:07:06
We would have $\triangle XAP \sim \triangle AXB$, among many other pairs.
v_Enhance 2019-04-19 21:07:11
The corollary I want to draw your attention to is then

\[ AD^2 = AX^2 = AP \cdot AB. \]
v_Enhance 2019-04-19 21:07:19
Which triangles does that imply are similar?
mathfun5 2019-04-19 21:07:44
So APD and ADB are similar!
budu 2019-04-19 21:07:44
APD ~ ADB
alifenix- 2019-04-19 21:07:44
ADP and ABD
v_Enhance 2019-04-19 21:07:49
It means $\triangle ADP \sim \triangle ABD$.
v_Enhance 2019-04-19 21:08:01
Similarly, can we make a statement about $BC^2$?
budu 2019-04-19 21:08:10
similarly BPC ~ BCA
v_Enhance 2019-04-19 21:08:16
By similar logic,

\[ BC^2 = BX^2 = BP \cdot BA. \]

So $\triangle BCP \sim \triangle BAC$.
v_Enhance 2019-04-19 21:08:46
Great.
v_Enhance 2019-04-19 21:09:15
We're starting to see the lengths come out. Now I actually want to draw attention to the angles, though.
v_Enhance 2019-04-19 21:09:30
Given these similar triangles, how can we play with $\angle DPA$?
budu 2019-04-19 21:09:59
$\angle DPA = \angle BDA$
v_Enhance 2019-04-19 21:10:07
Good. But $ABCD$ is cyclic, so can we chase that further?
mathisawesome2169 2019-04-19 21:10:30
<APD = <ADB = <ACB = <BPC yay
alifenix- 2019-04-19 21:10:30
and BPC is BCA
OrangeToesWizard 2019-04-19 21:10:30
DPA = BDA
jj_ca888 2019-04-19 21:10:30
BCA!
hliu1 2019-04-19 21:10:30
=<BCA=<BPC
budu 2019-04-19 21:10:30
in fact $\angle DBA = \angle BDA = \angle BCA = \angle BPC$
v_Enhance 2019-04-19 21:10:45
We have

\[ \angle DPA = \angle ADB = \angle ACB = \angle BPC \]

where the first equality is by $\triangle ADP \sim \triangle ABD$, the second by cyclic $ABCD$, the third by $\triangle BCP \sim \triangle BAC$.
v_Enhance 2019-04-19 21:11:26
And that explains the angle condition.
v_Enhance 2019-04-19 21:11:36
END DREAM MODE
v_Enhance 2019-04-19 21:11:58
All of this has been wishful thinking up to now, if $P$ really did lie on line $XY$.
cj13609517288 2019-04-19 21:12:10
AW...
deadwindow 2019-04-19 21:12:10
oh no
v_Enhance 2019-04-19 21:12:23
But I like these similarities a lot.
v_Enhance 2019-04-19 21:12:33
And so let's change up the problem: we will DEFINE $P$ to be the point satisfying \[ AD^2 = AP \cdot AB \quad\text{and}\quad BC^2 = BP \cdot BA. \]
westford_flying_fish 2019-04-19 21:12:44
Set it as a ghost point then
v_Enhance 2019-04-19 21:12:47
Yep.
v_Enhance 2019-04-19 21:13:00
So I claim I can actually define a point $P$ satisfying these two length conditions, and therefore all the beautiful similar triangles we found.
v_Enhance 2019-04-19 21:13:07
Why is that?
algebra_star1234 2019-04-19 21:13:36
if you add them you get the length condition
mathguy623 2019-04-19 21:14:07
Just let P be the foot from X to AB
v_Enhance 2019-04-19 21:14:15
One way to see it is from just the pure lengths:
v_Enhance 2019-04-19 21:14:27
If we let $P$ obey the first equation then

\begin{align*}

BP \cdot BA &= (BA - AP) \cdot BA \\

&= AB^2 - AP \cdot AB = AB^2 - AD^2 = BC^2.

\end{align*}
v_Enhance 2019-04-19 21:14:36
Alternatively, if you define $P$ to be the foot of that point $X$,
v_Enhance 2019-04-19 21:14:44
then those similar triangles will do it for you.
v_Enhance 2019-04-19 21:15:05
After changing the problem, we now have to prove TWO things:

(I) this point $P$ is the one in the problem statement (i.e. it satisfies the angle condition $\angle BPC = \angle DPA$), and

(II) line $PE$ bisects $CD$.
khina 2019-04-19 21:15:32
don't u have to prove uniqueness? or is it citable
hliu1 2019-04-19 21:15:35
we already proved the first one right?
cj13609517288 2019-04-19 21:15:52
Yeah we already did the first one yay
v_Enhance 2019-04-19 21:16:02
We basically proved (I) already in our dream. We just need to add one extra remark: there's only one point $P$ satisfying the angle condition, so it coincides with our re-defined point.
v_Enhance 2019-04-19 21:16:17
(To see why there's only one point, note that if you imagine starting $P$ at $A$ and moving from left to right, then one angle increases, the other decreases.)
v_Enhance 2019-04-19 21:16:37
So after waking up from our dream we already have half the problem. Just need (II).
alifenix- 2019-04-19 21:17:23
so we just have to show foot of X perp AB lies on EM
cj13609517288 2019-04-19 21:17:23
So we dreamt the whole dream just to prove some similarities?
v_Enhance 2019-04-19 21:17:32
Yes, and those similarities are (I).
khina 2019-04-19 21:17:51
ummm symmedian
v_Enhance 2019-04-19 21:17:56
If you know what a "symmedian" is you can actually finish the problem quite quickly from here. However, I have enough time that I want to present the completely low-tech solution.
v_Enhance 2019-04-19 21:18:36
Specifically: what points in the diagram did I draw that I haven't used yet?
jj_ca888 2019-04-19 21:19:00
E
Jupiter123 2019-04-19 21:19:00
K and L
alifenix- 2019-04-19 21:19:00
K, L
v_Enhance 2019-04-19 21:19:13
Point $E$, and $K$ and $L$ still haven't played much yet
v_Enhance 2019-04-19 21:20:30
This is where the points $K$ and $L$ from before come in. Let us define $K$ as the intersection of $DP$ and $AC$, and $L$ as the intersection of $CP$ and $DB$.
jj_ca888 2019-04-19 21:20:55
wait is it necessarily true that KL || DC?? it seems true
alifenix- 2019-04-19 21:20:55
looks like $KL || DC$
jishu2003 2019-04-19 21:20:55
It is enough to prove that $KL||AB$
v_Enhance 2019-04-19 21:21:10
Yeah, some of you see the last crux already!
v_Enhance 2019-04-19 21:21:29
To make it clear this is also wishful, I'll use another pair of dream tags, but this will be short.
v_Enhance 2019-04-19 21:21:38
v_Enhance 2019-04-19 21:21:48
BEGIN DREAM MODE
v_Enhance 2019-04-19 21:21:52
Suppose $PE$ really bisected $CD$. If we apply Ceva's theorem to $\triangle PCD$ what does that give?
cooljoseph 2019-04-19 21:22:25
DK/DP = CL/CP
jj_ca888 2019-04-19 21:22:25
DK/KP * PL/LC = 1
v_Enhance 2019-04-19 21:22:29
If $M$ is the midpoint of $CD$, we would have

\[ \frac{PK}{KD} \cdot \underbrace{\frac{DM}{MC}}_{=1} \cdot \frac{CL}{LP}

= 1 \implies \frac{PK}{KD} = \frac{PL}{LC}. \]

This is just the same as saying $\overline{KL} \parallel \overline{CD}$.
v_Enhance 2019-04-19 21:22:51
Since the converse of Ceva is true, that means our desired conclusion is also just the same as saying $\overline{KL} \parallel \overline{CD}$.
v_Enhance 2019-04-19 21:22:56
So when we wake up again, that's our goal: if we can get $\overline{KL} \parallel \overline{CD}$, we win.
v_Enhance 2019-04-19 21:23:02
END DREAM MODE
v_Enhance 2019-04-19 21:23:17
Alright, now that naptime is over, we're in really good shape. We've now gotten rid of all the weird conditions we didn't like. And so now we just need to angle chase the rest of the problem.
v_Enhance 2019-04-19 21:24:25
We also have four angles we already like, from our proof of (I).
v_Enhance 2019-04-19 21:24:32
I'll mark them in the diagram now and call that common angle $\theta$.
v_Enhance 2019-04-19 21:25:30
v_Enhance 2019-04-19 21:25:36
There we go.
v_Enhance 2019-04-19 21:25:55
Alright, i spot some cyclic quadrilaterals due to $\theta$ already. Where are they?
azxc 2019-04-19 21:26:44
only need to show that A,K,L.B cyclic
cj13609517288 2019-04-19 21:26:44
DLPA
Jupiter123 2019-04-19 21:26:44
KPBC
mathfun5 2019-04-19 21:26:44
PKCB,ADLP
Jupiter123 2019-04-19 21:26:44
ADLP
MinecraftPlayer657 2019-04-19 21:26:44
DAPL
cj13609517288 2019-04-19 21:26:44
KPBC and DLPA
hliu1 2019-04-19 21:26:44
BPCK and APLD
v_Enhance 2019-04-19 21:26:53
Yeah, since $\angle KPA = \angle KCB = \theta$, we get $KPBC$ is cyclic. Similarly, $\angle BPL = \angle ALD$ means $ADLP$ is cyclic.
v_Enhance 2019-04-19 21:27:00
Now, can someone find $\angle AKB$ in terms of $\theta$ for me?
v_Enhance 2019-04-19 21:27:26
(You'll need $CKPB$ cyclic.)
mathfun5 2019-04-19 21:27:50
180 - theta
jj_ca888 2019-04-19 21:27:50
180 - theta!
v_Enhance 2019-04-19 21:27:53
We have \[ \angle AKB = 180^{\circ} - \angle BKC

= 180^{\circ} - \angle BPC = 180^{\circ} - \theta. \]
v_Enhance 2019-04-19 21:28:02
But similarly $\angle ALB = 180^{\circ} - \theta$.
goodball 2019-04-19 21:28:19
AKLB cyclic!
v_Enhance 2019-04-19 21:28:23
It means $AKLB$ is cyclic too.
v_Enhance 2019-04-19 21:28:40
That should be all the ingredients I need to get the parallelism. Anyone see how to do it? Just a bit more angle chasing.
mathfun5 2019-04-19 21:29:20
CDL=CAB=DLK
v_Enhance 2019-04-19 21:29:40
We have \[ \angle LKC = \angle LBA = \angle DBA = \angle DCA = \angle DCK \] which gives us the desired parallel lines. (You'll sometimes here this called "Reim's theorem", but you can basically ignore that name, since it always is the same three-step angle chase.)
v_Enhance 2019-04-19 21:29:51
*hear
v_Enhance 2019-04-19 21:29:59
So $\overline{KL} \parallel \overline{CD}$, and thus by Ceva's theorem, it follows $\overline{PE}$ bisects $\overline{CD}$.
v_Enhance 2019-04-19 21:30:02
The end!
cj13609517288 2019-04-19 21:30:07
WE WIN!!!!!
jishu2003 2019-04-19 21:30:20
What's the symmedian proof?
Maxninga938 2019-04-19 21:30:20
yee
jj_ca888 2019-04-19 21:30:26
dang that's relly pro
v_Enhance 2019-04-19 21:30:39
Some shorter solutions on the forums with symmedian, so feel free to check those out.
carzland 2019-04-19 21:30:46
Yay!
Maxninga938 2019-04-19 21:30:59
1000 IQ
jj_ca888 2019-04-19 21:30:59
i think i just doubled my iq
Jupiter123 2019-04-19 21:30:59
GREAT LECTURE!!
goodball 2019-04-19 21:30:59
nice dreaming
ketul 2019-04-19 21:30:59
This is the most instructive solution I've seen in a while.
pandadude 2019-04-19 21:30:59
hello v_Enhance!
v_Enhance 2019-04-19 21:31:15
Thanks all. I'm just about out of time, but I did promise people a story about MO1 on the forums.
v_Enhance 2019-04-19 21:31:27
So here's the story of how I wrote the MO1 that we skipped.
v_Enhance 2019-04-19 21:31:39
A couple days before the grading of USAMO 2017, I woke up from a dream (maybe nightmare) that I had been assigned to grading some functional equation, and was slogging through pages of student's $f$-riddled papers.
v_Enhance 2019-04-19 21:31:50
When I woke up, I found that I actually still remembered the "problem" I was grading, and wrote it down.
v_Enhance 2019-04-19 21:31:59
It was ``$f^{f(n)}(n) = \frac{n^2}{f(f(n))}$''.
Jupiter123 2019-04-19 21:32:13
Hahahaha.
khina 2019-04-19 21:32:13
what
v_Enhance 2019-04-19 21:32:16
You can guess the rest of the story from there!
v_Enhance 2019-04-19 21:32:40
Alright, back to reality. We all done for today. Thanks for coming through!
eminentabyss 2019-04-19 21:32:52
Holy moly, what a great ending to an excellent math jam!
eminentabyss 2019-04-19 21:33:01
Thank you all for joining us, and huge thanks to Evan for making this possible and Detelin for fielding all of your questions!
molocyxu 2019-04-19 21:33:24
THANK YOU!!!
jishu2003 2019-04-19 21:33:24
Thanks for the JAM.
cj13609517288 2019-04-19 21:33:24
That is actually so cool.
goodball 2019-04-19 21:33:24
Thanks!
Jupiter123 2019-04-19 21:33:24
Thank you!
hliu1 2019-04-19 21:33:24
thank you v_enhance
Maxninga938 2019-04-19 21:33:24
thanks
lisali666 2019-04-19 21:33:24
*end dream*
cj13609517288 2019-04-19 21:33:24
THANKS!!!
Damalone 2019-04-19 21:33:24
Thanks!
Awesome_guy 2019-04-19 21:33:24
thanks
kevinmathz 2019-04-19 21:33:24
Thank you very much!
cooljoseph 2019-04-19 21:33:57
Thanks everyone!
wertguk 2019-04-19 21:33:57
THANKS
mathfun5 2019-04-19 21:33:57
Thanks so much Evan!
porkemon2 2019-04-19 21:33:57
Thank you!
azxc 2019-04-19 21:33:57
Thank you very much!
stroller 2019-04-19 21:33:57
Thanks! Nice explanation!
ketul 2019-04-19 21:33:57
Thanks Evan, was definitely worth staying up until 3:30 AM.
Ben_Chen 2019-04-19 21:33:57
Thanks
AlexLikeMath 2019-04-19 21:33:57
thanks!
aopssolver2 2019-04-19 21:33:57
thanks
azxc 2019-04-19 21:33:57
THANK YOU!

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

Invalid username
Sign In