USAMOGo back to the Math Jam Archive
We will discuss the problems from the first day of the 2004 USAMO.
Copyright © 2021 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: Mathew Crawford
Day 1 of the 2004 USAMO
1. Let ABCD be a quadrilateral circumscribed about a circle, whose interior and exterior angles are at least 60 degrees. Prove that
When does equality hold?
What initial observations can we make?
the right side is nine times the left side
Seeing that the far right and far left are so similar, what can we note right away?
The first inequality and the second are equivalent
First, we note that though this looks like 2 different inequalities, they are really the same. If we divide
|BC^3 - CD^3| <= 3|AB^3 - AD^3|
by 3, we get
(1/3)|BC^3 - CD^3| <= |AB^3 - AD^3|,
which is exactly the same as
(1/3)|AB^3 - AD^3| <= |BC^3 - CD^3|,
because you can cycle the vertices of the quadrangle
But with the vertices relabeled. Therefore, we really only have to prove one side of this inequality and by symmetry we'll have the other.
we can separate the diff of cubes into factors
Right - any time we see difference of cubes, we should have factoring in mind:
Differences of cubes suggest factoring:
and |BC - CD| = |AB- AD|
and use the condition AB + CD = AD + BC
Since ABCD is circumscribed about a circle, AB + CD = BC + AD. (This is one of those things every experienced geometer should know.) How could we prove this?
tangents to a circle
tangents to a circle are equal
We have equal tangents from a point to a circle; the proof is straightforward:
This is probably something you could leave out of a USAMO proof, but if you have time, there's no harm including it since it's so short.
So, we have our difference of cubes factored:
Why does this make us happy?
because BC - CD = AB - AD
First, we have BC - CD = AB - AD, which definitely pops up in the inequality we want to prove. What about that other factor?
The right factor reminds me of law of cosines...
That other factor just plain looks like the law of cosines. Plus, that weird 60 degree restriction should have us thinking cosine, too, since cos (60) = 1/2. Thus, the law of cosines applied to a triangle with a 60 or 120 degree angle gives us a relatively nice expression like c^2 = a^2 + b^2 + ab (or -ab for a 60 degree angle).
60 degrees, 120 degrees, a^2 + b^2 +/- ab : these are all clues that the law of cosines might be useful.
How can we use law of cosines here?
What triangle should we be looking at for law of cosines?
Right, our factored cubes:
Involves BCD. We know we can do this for ABD for the other side, too.
Law of cosines on BCD gives
We haven't used our 60 degree restriction. We break it out now:
Since 60 <= angle C <= 120, we have -1/2 <= cos C <= 1/2, so
How does this help?
it's part of our inequality!
Which part, the left part or the right part?
the left part
Right, now we have:
Now, we think we're close - what do we have to do?
use the law of cosines on ABD
you can do the same thing on the other side
AB^3 - AD^3 is (AB - AD)(AB^2 + (AB)(AD) + AD^2), so we have to turn BD^2 into AB^2 + (AB)(AD) + AD^2 somehow - looks a lot like law of cosines again.
As we did with BCD, we can to with ABD, and we find:
Are we done? Can we just turn BD^2 into AB^2 + AD^2 + (AB)(AD)?
Can we just put the left hand side of that inequality we just found in our original and say 'done'!
We have BC^3 - CD^3 >= (AB - BD)BD^2 from before.
We just showed AB^2 + AD^2 +(AB)(AD) >= BD^2.
Can we just put these together and say done!
but we want 1/3 somewhere in there...
Yep - and the problem is worse than that - look closely.
(This is an important lesson)
the signs are going the same way?
um...it's greater than
if the thing were less than BD^2, we'd be ok
Right - the inequality is 'going the wrong way'
We can't just stick AB^2 + AD^2 +(AB)(AD) in for BD^2 in our BC^3 - CD^3 >= (AB - BD)BD^2
What's the only part of
we can use?
no...we would get both sides >= the same thing
the right hand side
the right side
the RH ineq
we can only turn BD^2 into AB^2 + AD^2 - (AB)(AD):
Very important to always pay attention to which ways your inequalities are going. Have to make sure you aren't saying 5>3 and 4>3, so 4>5.
Obviously, that's not true.
Waht do we have to show now?
the 1/3 part
That's part of the problem, what else?
that RHS >= 1/3 (AB^3 - AD^3)
AB^2+AD^2-(AB)(AD) >= 1/3(AB^2+AD^2+(AB)(AD))
Exactly, if we prove zfzf21's inequality, we'll get masamune2387's and be done
How can we show AB^2 + AD^2 - (AB)(AD) >= [AB^2 + AD^2 + (AB)(AD)]/3 to complete our proof?
try to use ""no square is negative"" somehow?
Either/both. For those that don't see it, do this:
work backwards, and you can:
just factor into a square
If we work backward from the above, we find it follows straight from AM-GM (or the Trivial Inequality - any square is nonnegative). Writing it forwards looks like this:
The first step is a direct result of AM-GM applied to AB^2 and AD^2. Or you can rearrange to a perfect square.
If you look at the steps backwards, you'll see how we figured out to do it this way.
So, we have shown that
By symmetry, the other half of the inequality follows directly.
Where does equality hold?
when AB = AD and BC = CD
What does that mean ABCD is?
AB = AD, BC = CD makes ABCD a kite.
Do we have any other conditions?
We obviously don't have any others where both equalities hold.
How about one equality or the other?
We have to make sure each step in our chain maintains equality
when the opposite angles are 60 and 120 degrees...?
the angles have to be 60 or 120
so AB=AD follows from the second to third line.
Right - Nukular points out how we can find our equality conditions.
Go through our inequalities and look for equality conditions.
If the angles are 60 or 120, we still need AB = AD in that last step.
Are there any questions?
(Note that we don't need AB = AD, BC = CD and the angles equal to 120 - once we have AB = AD, BC = CD, obviously we have equality everywhere)
of course, there are other proofs, right?
Yes, there are often many ways to skin Olympiad cats.
aren't there always?
Maybe not always, but usually.
would all rely around law of cosines?
I'd be surprised if that weren't the case
But it's not impossible.
i did mine without law of cosines...but im not sure if its right
hehe, i bet some scary analytical geometry proof exists that wouldn't need law of cosines
ewww.... (but you may be right)
#4 had about 20 solutions probably :)
I'd bet more!
Are there any more questions for this one?
I think #2 is quite possibly the most misread question ever...
2. Suppose a_1, ..., a_n are integer whose greatest common divisor is 1. Let S be a set of integers with the following properties.
Prove that S must be equal to the set of all integers.
How might we begin to approach this problem?
you only need the first two numbers
Not true. This is the misreading Nukular referred to.
Not every pair has a gcd of 1 -- the group as a WHOLE has a gcd of 1.
experiment with two numbers?
Try out a few cases
When faced with a problem involving many variables such as this one it's sometimes a good idea to try a couple of special cases to see what we come up with. Let's examine for n = 2 the integers a_1 = 3 and a_2 = 4. What integers can we conclude are elements of S?
3, 4, 1, 0
0, 1, 3, and 4
From (a) we know that 3 and 4 are in S.
From (b) we know that 3 - 4 = -1, 3 - 3 = 4 - 4 = 0, and 4 - 3 = 1 are elements of S.
What else can we determine?
And, once you get one, you've got them all
and with 0 and 1 you can get every integer
all the negatives also
all integers :)
proven easily by induction
Since 1 + (-1) = 0 is in S, so is 1 - (-1) = 2.
Since 0 + 2 = 2 is in S, so is 0 - 2 = -2.
Since 1 + (-2) = -1 is in S, so is 1 - (-2) = 3.
Since 0 + 3 = 3 is in S, so is 0 - 3 = -3.
We can now demonstrate a lemma:
If -1, 0, and 1 are in S, then all integers are in S.
What does the proof of this lemma look like?
it looks like the above, only inductively applied to all n
We can establish the lemma by induction.
-1, 0, 1 are all in S. These compose our base case starting with n = 1.
If 1 + (-n) = -(n - 1) is in S, so is 1 - (-n) = n + 1.
If 0 + (n + 1) is in S, so is 0 - (n + 1) = -(n + 1).
This demonstrate the inductive step. If -n, 0, 1 are in S, then so are -(n + 1) and (n + 1).
We could establish this induction in various ways, but this gets the point across.
We need to keep our eyes on the prize, guys. GCD = 1 => we should be thinking of how to get 1. Once we get 1 we are golden because we use that and 0 + induction to take everything.
Now, we can already show that a_i - a_i = 0 is in S due to (b). We would like to show that 1 is in S.
Looking at our case for 3 and 4 from earlier didn't necessarily illuminate the hardest possible examples. Let's see what happens if the first two elements we examine are 42 and 30. What elements can we conclude are in S?
12, 18, 6, 0, 24, 36...
all multiples of 6
you can eventually get the GCD of the two numbers through repeated application of rule c.
In this case, 0, 6, 12, 18, 24,
Every number that is a multiple of GCF(42,30)
Ah, so we have a second lemma.
All linear combinations of 42 and 30 are in S
While I was writing it out, it helped to prove the converse of (c):
For any integers x,y in S, if x-y is in S, then x+y is in S... this shortened my proof significantly, for some reason.
So, any time we examine two numbers in the list, we have all multiples of their GCD.
How can we use what we have learned to filter down to including 1 in S?
Take the gcd one at a time and get gcd(a1...an) is in S
use gcd(gcd(a1, a2), a3)...
Yes, but we need to show that each time we include another a_i, we can still filter down the the GCD of all the a_i we have included. How do we show this?
yeah but once you throw gcd(a1, a2) into the mix, and induct, you lose (b) and things go out the window.
Oh? What about you're nice extra lemma above. If x - y is in S, then x + y is in S.
well, all diophantine equations of the form ax + by = 1 have solutions if a and b are relatively prime
what DS wrote is extendable into more than two integers, nicely enough.
Why is it that we can create any linear combination of the original elements?
Let's take a look at a quick example so that we can make this rigorous.
Suppose we start with 221, 187, and 143.
(221, 187) = 17, (187, 143) = 11, (221, 143) = 13.
Now, how do we make linear combinations of 11, 13, and 17?
Something like 11x + 13y = 1 + 17z ?
2*17 - 3*11 = 1
True, but that doesn't show us WHY we can just take the linear combinations.
We need to stick to the rules and SHOW that we can just start taking linear combinations.
all multiples of 17 are in S... some linear combo of 11 and 13 = a multiple of 17, so then we can cycle down and be happy... maybe. ( I did it differently on the actual contest)
We could solve 13x + 11y = 17 for instance.
As long as we eventually get it to two rel. prime #'s we can finish like this.
So, each time we add a new a_i to this process, we end up with the GCD of each of the numbers we have included. Finally we end up with 1.
But what if 11 and 13 weren't relatively prime
Suppose instead of having 11, 13, and 17 we had 22, 26, and 34...
Then there must be another a_i that we can use because they can't ALL include 2 as a prime.
Really, in order to get rid of any single prime, you just need one a_i that isn't a multiple of that prime.
Any questions about this problem?
can you induct from two?
We don't really need to make an induction argument on number 2.
We do go down a chain, but it's a finite chain and we are only looking to filter out each prime.
We filter out any prime once we include some a_i that isn't a multiple of that prime.
I hope my induction worked, looked like it did
Of course, some people DID use induction. I'm just saying we don't have to (at this point in the proof)./
Ready for number 3?
Let the fun begin...
Pain and anguish!
3. For what real values of k > 0 is it possible to dissect a 1 x k rectangle into two similar but noncongruent polygons?
The approach we'll show you is exactly how we found the solution to the problem - we had a wrong assumption, tried to prove it, then stumbled on the right answer (actually, something close to the right answer - props to ComplexZeta for cleaning up our algebra and putting us right on top of the answer).
did anyone here get it?
No yesses - a lot of people with the 'mistake answer'.
So, I'll take you on a guided tour of MCrawford and my brains as we went through this problem. The actual solution that we'd write up is considerably shorter, but I'd like to show you how we got there.
What's our first instinct when we look at the problem? What do we think the answer is on a glance?
two similar rectangles
two similar rectangles
That's what we thought, too.
Cut it into two rectangles, slide the divider over enough and you'll be ok.
Then, we set down to proving our instincts. Where do we start?
We can see off the bat though that if c works, 1/c works, so thats good to note.
First, we can deal just with k >= 1. For all k we find >= 1, we can argue by symmetry that 1/k works, too (rotate the rectangle 90 degrees, then cut).
Intuitively, it seems like the only way to perform the dissection is to make two rectangles. However, we have to prove that this is the only way to perform the dissection. What cases do we have to consider?
(Notice that I'm not just diving into the two rectangles - I'm trying to prove that the two rectangle is the only dissection that works.)
I started showing that the line of dissection must travel from one side to the opposite side
maybe right-angle zig-zag cuts
Going from corner to corner
or diagonal cuts...
Right - there are all sorts of ways we can cut this thing. We have to investigate them all.
This can get pretty scary. What cases can we get rid of easily?
count the vertices if it doesn't go from one side to the opposite...
if we dont go from side to side i think we'll get more vertices on one than on the other
the cut goes through 2 adjacent sides of the rectangle
We can take care of any cuts that start and end on a side, or that start on one side and end on an adjacent side just by counting sides.
Let's take a look at starting through the corner of a rectangle:
Can we have similar polygons in this case?
not without congruent ones
They'd have to be congruent
How can we prove they have to be congruent?
The cut has to go through B, right?
How can we prove that?
First, by counting sides, we see that the cut has to go thru B
yeah, in order for they polygons to have the same number of sides
If we have a dissection through D that results in two similar polygons, it must eventually go through B; otherwise, the two polygons will have a different number of sides and thus be dissimilar.
What do we conclude if this dissection goes through D and B and the polygons are similar?
they are congruent
Why? What's an easy way to prove it?
right angle at C and A...then use corresponding sides?
The length of the segment going through B has to equal that through D?
the two longest sides are the same
Let's put these together and tighten it up.
What can we say about the sides of the two polygons?
(Note, we don't know that BC and AB are the longest sides)
they're the same
No matter what, if the dissection goes through D and B, the sides of the two polygons are all the same (BC = AD, DC = AB, and they share all other sides). Hence, the two polygons would be congruent if they are similar.
Any questions about that?
Wow, that was easy enough
So, our dissection must go through sides, and it must go through opposite sides (else, we produce polygons with different numbers of sides as before).
So, what cases should we worry about now?
A dissector with a non-right angle
Right - we're aiming at proving we have 2 rectangles, so we have to prove we can throw out the non-right angles.
How can we show that there's no funky cut that makes similar polygons - that our only option is right angles?
Without loss of generality, say our dissection cuts sides AD and BC. We call the polygon that includes DC the 'right' polygon and the one that includes AB the 'left' polygon. We must map the right angles and D and at C to angles of the 'left' polygon. (By mapping we mean which point corresponds to which in our similarity)
What do we want to show?
We would want to show that the left polygon, if similar to the right polygon, is congruent to the right polygon
the polygons are dissimilar or congruent
How are we going to show that?
That they map to A and B?
That what maps to A and B?
C and D?
D with B and C with A?
We want to show that the angles at D and C map to B and A if there is similarity in any case besides a dissection into two similar rectangles, and hence the similar polygons are congruent. How do we do it?
What general tactic should we take?
(In general, if we're completely at a loss trying to prove a given statement is true, what should we try to do?)
prove it can't be false
Let's try a contradiction. What do we have to assume?
assume the polygons are similar but not congruent
The two figures are similar and noncongruent.
assume they are similar and noncongruent
OK - remember we were focusing on mapping C and D to A and B, so:
We have to assume that AB doesn't map to CD
Suppose DC maps to a side other than AB.
In our diagram, suppose our dissection includes path WC'D'Z, where WC' and ZD' are perpendicular and in our similarity, CD maps to C'D'. Can we prove this is impossible?
heh - thanks.
Focusing just on C and D going to C' and D' doesn't seem to do it.
But knowing where C and D go to (where C' and D' are), what else can we locate?
I see a lot of 'A' and 'B' - do we know for sure where they go?
Do we know where any points at all go?
(besides C and D)
we know where W and Z are
The point on AD that is connected to Y
We know where W and Z are - and we know what segment they came from. We also know what line the portion of AD on the right polygon is going (and same for the right polygon portion of BC).
We have to use what we know - how do we use knowing where those lines go?
How do we know where W and Z are mapped to?
We don't know exactly where they are coming from, but we know they are images of points on the AD and BC.
How does that help? What can we say about those sides with respect to the right polygon?
hmm, how do we know that they are images of points on Ad and BC
Because CD maps to C'D'. W and Z are on the perpendiculars out of those points.
W is the image of point adjacent to C that's not D
Here's the diagram again:
What is special about lines BC and AD with respect to the right polygon?
wait, then don't we know that D'C'WZ must be enclosed?
Clarify - I think you've got it.
since D'Z is the image of DA, and C'W is the image of CB, and C'D' is the image of CD, the WZ must be the image of AB, so it's enclosed
What is enclosed (I think you have it - just trying to get it to be clear to everyone)?
D'Z isn't the image of DA, is it? Neither is C'W the image of CB
They are images of the segments on DA and CB
the polygon WZC'D'
Does this give us a contradiction & why?
Well how are we supposed to dissect ABCD then?
and this is a contradction because the outside polygon shouldn't have a loop in the center.
Since WZC'D' is enclosed, we have 3 regions, and we only want 2
Let's see if we can clean this up and make it neat.
The entirety of the right polygon is between lines BC and AD.
How does this observation complete this case?
all points in the left polygon must be between C'W and D'Z?
Since all of the right polygon is between BC and AD, all of the left polygon must be between the images of them.
Since the image of CD is inside ABCD, this is clearly impossible.
We note that the lines through D and C perpendicular to CD bound the right polygon - the entire right polygon is between these lines. Hence, the corresponding lines through C' and D' perpendicular to C'D' must contain the entirety of the left polygon. This can only occur if C'D' is AB (in which case the two similar polygons are congruent, since CD = AB), or if C'D' is along either BC or AD.
Are there any questions about that? I think this was the most subtle part of arriving at the final answer (ironic, because we don't even need it in the final solution).
so what exactly did we just proved? that if we have two such polygons that CD maps to one of the other sides?
We proved that if we try to use diagonal cuts from the sides, then we can't get similarity without congruence.
No, that there must be all right angles in your line of dissection
Actually, all we've proved so far is that our first cut on one of the sides has to be a right angle (i.e. they can't both be diagonal cuts).
i think its stronger to say we proved that CD cant map to the interior of ABCD
Indeed - we have proved that, and it is stronger.
(rrusczyk note: This process could have been made even more concise had
we taken Teddy's observation from the beginning; had we considered as this case
'mapping CD to the interior of ABCD' rather than 'start with a non-perpendicular
cut', we could have perhaps made the casework a little more clear)
It must map to something on the side BC (or AD).
What two cases do we have to consider now?
it maps to the interior of the side or it maps to a segment containing an endpoint of the side
Do we have to worry about the interior of the side?
no, then there would be two cuts from the same side
no,we get a cut from a side to itself
Right - so CD must map to a segment with A or B as a endpoint.
Suppose B is that endpoint.
What are our options?
C maps to B or D maps to B
We have two possibilities: C maps to B, D maps to B. The first leads to our two rectangles:
How can we see in this case that we must get two rectangles?
(think about the bounding argument we used before)
Can the left polygon go beyond D' to the right?
The left polygon is contained between C'A and the line through D' parallel to it
the left polygon is bounded by C'D' since the right is bounded by CD
It's the same thing as before - the perpendiculars to C' and D' must bound the left polygon, since perpendicular to C and D bound the right one.
Can the right polygon extend past D' to the left?
the right polygon can't go above AD
if it did, then an image point would have to be above AD
Right - since the image of D' of the right polygon must be A of the left, the image of anypoint to the left of D' in the right polygon would go 'above' AD.
Here's another way to look at it:
Since C maps to B, we must have D' of the right polygon map to A on the left polygon. Just as the perpendicular lines to C'D' through C' and D' must contain all of the left polygon, so must the perpendicular lines through C and D' to CD' contain the entire right polygon (since the lines through A and B perpendicular to AB contain the left polygon, the lines through the points the map to, C and D', must be perpendicular to the segment AB maps to, CD'). Hence, the right polygon must be entirely to the right of the perpendicular through D', and the left entirely to the left. Thus, the only dissection that results in similarity in which C maps to B is the dissection that cuts the rectangle into two rectangles.
Many of you have already talked about dealing with the two rectangles.
How do we deal with the two non-congruent rectangles?
How do we find what k work?
(This is the part many of you did as your solution)
What k work when we cut into two rectangles and why?
set up the ratio of the corresponding sides and solve
There are our rectangles and some variables - what's our equation?
(k-j)/1 = 1/j
1/k-j = j/1
we use our similarity to find (k-j)/1 = 1/j, or j^2 - kj + 1 = 0.
Therefore, we have:
This only has solutions if k >= 2, and when k = 2, j = 1 and our rectangles are congruent. By symmetry, this means we have dissections into similar rectangles for k > 2 and k < 1/2.
This is probably what a lot of you did, and what I did at first before trying to prove this was the only possibility that worked.
It's not a hard possibility to see. For those of you that got to right here, and stopped, here's a lesson: If it seems pretty easy for a #3, then you're probably wrong.
At this point, I still believed this was the only solution.
Before diving into our other case (where D maps to B), let's talk about this:
Wouldnt we also need to consider AB to CD afterward?
Why don't we worry about AB to CD for k > 1?
1 to 1 ratio = congruency
Why do we have a 1:1 ratio?
Ah, I see - Nukular's comment was from a while ago - he means, don't we need to consider a path cutting from AB to CD?
Why don't we worry about that?
because AB = CD
well it's just turned 90 degrees, right?
you can deal with it by renaming vertices and rotating and scaling the rectangle to become what it is now
We can't quite do that.
Nukular is talking about cutting from short side to short side, not long to long.
This is fundamentally different from what we're doing.
How can we 1-line dismiss that case?
the longest sides of the two rectangles would be equal
Bingo - if the longest side of the 'top' is AD, then the longest side of the bottom must be, too (since then all the sides on the cut are part of both polygons, and any parts of AB and CD are shorter than AD)
If the longest side of the 'top' is along the cut, that must also be the longest side of the bottom by much the same reasoning.
Same longest side = congruency.
So, we're left with D maps to B.
Once again, our first line of the dissection must be a vertical line from C'. Suppose we do something we couldn't do in the earlier case - we don't just cut all the way across. Suppose we turn at point W and go to a point X. Since our path in the right polygon from D to C to C' to W is two right angles, the corresponding path in the other polygon, which is D'C'WX, must also have right angles at C' and W as shown. Continuing in this vein, we get the stepladder shown.
(Make sure you see both why we can choose not to go all the way across, and why each step must be a right angle.)
What do we wonder about this?
so (k-j)*(1+j^2+j^4+...) < or = k?
Why? What does that mean?
well the horizontal cuts add up to be less than k so you don't go outside the rectangle.
We wonder: does this step ladder hit AD? And is the result a pair of similar polygons that we hadn't thought of before?
And if that's true, I believe it follows that the vertical cuts also don't go too far.
Thus, our rigorously trying to prove our first instinct - the dissection must be two rectangles and that's it. - has uncovered a little wrinkle. Time to investigate that wrinkle. We draw a stepladder:
Let Z be the point where the ladder eventually hits AD. (Note, we don't want it to hit AB because then the two polygons will have a different number of sides.)
A few things to note here: Since CD maps to BC', AB maps to DZ. Since all the lengths on the left are j times those on the right, we have ZD = j.
We can find all the lengths on our ladder as before - we just multiply each leg by j.
Now, can we build an equation?
(k-j)(j+j^3+...) = 1
Where does that come from?
the vertical parts of the ladder
Right - is there an even simpler equation we can see in the diagram?
(SuperNova's equation is right, and we can use that, but we can get to the equation it will simplify to even faster - how)
1/j + kj^(2n-2) - j ^ (2n-1)=k
Since AD = k and AD = AZ + ZD, we have
We take the j out of the denominator:
Notice that we could also have arrived at this equation by adding up all the vertical parts of the ladder and equating the result to 1 (try it on your own, you should get either the same equation, or this equation divided by j^2 - 1).
What do we wonder about this equation?
Does it have a sensible solution?
for which k does it have a solution for j, 0<j<k?
Exactly - does it have a sensible solution. What are 'sensible solutions'?
is a solution in 0 < j < k sufficient to make us happy?
everything but 1
Why does 1 make us sad?
We then have congruence
Right. If j =1, we have congruence.
Nonnegative, the stepladder doesn't crash into AB.
We have to worry about where our ladder goes.
Look at it - what are the bounds on j?
Obviously it can't be negative.
What about the top of the rectangle?
1/j < k
We need j > 1/k, or else DZ will be > k, which is bad.
So, we go hunting. How?
Do we need to actually find a solution?
By taking n arbitrarily large, we can take k as close to 1 as we like
Are we guaranteed to have j in our desired range?
Not sure. :)
We wish to show that there is a j in a certain interval that solves:
for a given k.
We don't have to find the solution. We just have to show it exists.
How do we do that?
substitute j = 1/k and j = k?
Is the equation < 0 at one end of the interval and > 0 at the other end of the interval?
We can rearrange and write our equation as a polynomial equal to 0:
What happens when we put k in there?
f(k) = k^2 - 1 > 0
What happens if we put in 1/k?
1/k^2n - 1/k^(2n-2) < 0
1/k^2 - 1 < 0 (obviously true, right?)
f(1/k) = (1/k)^2n - (1/k)^(2n-2) < 0
Are we done?
Does this make us happy?
yes, because f is continuous
But what might j be?
That would make us sad.
We have f(1/k) < 0, and we have f(k) > 0, so there's a soluition between them.
Unfortunately, it could be 1.
What is f(1)?
or did we already do that?
And now we are sad.
What should we do?
Look for other solutions?
Indeed, but if we use the range 1/k to k, we may always hit 1.
What range should we look at?
maybe 1 to k (not inclusive)
1/k to 1 (not inclusive)
We can also look between 1/k to 1.
Trouble is, f(1) = 0.
How do we deal with that problem?
Since f(1) =0, what can we do to f?
We can take the 1 factor out. If we factor out j-1, we get:
Why does this make us happy?
What can we do with that big expression on the right?
(I think y'all are just assuming what I'm driving at:
We can call that long polynomial g(j) and continue our quest. If we can show that g(1) and g(1/k) have opposite signs, then g(j), and hence f(j), has a root between 1/k and 1.
So, we are investigating:
We now can do the same thing we tried before: try finding an interval that must have a soluiton.
What is g(1)?
1 - (k-1)(2n-2) + 1
2 - (k-1)(2n-2)
g(1) = 1 - (k-1)(2n-2) + 1 = 2 - (k-1)(2n-2).
What do we know about this?
Can we always make this negative?
By taking n large?
Remember, we get to pick n! As long as k > 1, we can pick an n such that g(1) < 0
So what's left to show?
g(1/k) > 0
We want to show that g(1/k) > 0.
Do we have to stick 1/k in that nasty expression, or is there a slick way we can get around that?
(What have we already discovered about j = 1/k)
g(1/k) = f(1/k)/(j-1) = negative/negative = positive
We know that f(1/k) < 0, and that f(j) = (j-1) g(j).
Hence, g(1/k) = f(1/k)/(1/k-1) > 0, since it is the ratio of negative numbers.
For those of you who wanted to evaluate g(1/k) explicitly:
g(1/k) > 0,
Are we happy?
We have thus shown than g(1/k) > 0 > g(1), so there is a solution for j between 1/k and 1. Hence, there is a stepladder.
yay, we found a solution
We're happy, but not finished.
(Notice : our trying to prove our original incorrect instinct rigorously led us to the correct solution - it was only right at the end of this that I abandoned the rectangle dissection as the solution.)
We of course have to disprove k=1 from being a possibiility don't we.
Might we need to prove that k <> 1?
Yep. How can we do that quickly?
What method that we've already used can we re-use to knock off that case.
g(1/1) = g(1)
Sticking 1 in our formulas is a big problem for a bunch of reasons - we've used our assumption k > 1 in a number of places.
I'm looking for a quick way to say we can't cut a square in such a way that we get two similar, noncongruent polygons.
Think of how we knocked out other cases quickly: will any of those methods work?
(Things we did already: bounding argument, vertex counting, longest side)
well 1 has to be the longest since the adjacent side of length 1 is partitioned.
the longest sides are always AB and CD, so the parts are congruent!
If AB and CD aren't the longest side, then the longest side is part of both, and we're done.
Although this took a long time (it is a #3, after all), it was not impossible. We did no magic. Probably our biggest leap of insight was the bounding argument we used early on. Other than that, we mostly took a hunch - that the solution was two rectangles - and tried to prove it. We methodically worked through cases.
When we got to the last case, we discovered that our hunch was wrong.
And there we found the solution.
Even working through the stepladder portion wasn't so hard.
Mostly, I want to stress that we didn't 'just see' this solution.
We reasoned our way to it.
The solution I 'just saw' was wrong.
I'll quickly summarize our solution:
First, we let k>1 since we could argue symmetry.
Next, we showed we have to connect opposite sides by counting vertices. (We used a longest side argument to show that corner to corner meant congruence; we did the same to knock out connecting opposite short sides.)
Next, we showed that CD could not map to something inside ABCD.
We deduced that it must map to something on the side of ABCD.
We did this by making a bounding argument, noting that AD and BC bound the right polygon, so the images of the righthand segments on that side must bound the left polygon.
Thus, we concluded that C or D mapped to either A or B. It didn't matter which of A or B we mapped to, we we chose B.
Then we dealt with the case of C mapping to B.
We used a bounding argument again to show that the only possibility there was two rectangles.
Then we went to D mapping to B.
There, we couldn't bound it. We could easily show that our path must consist of right angles all the way through by considering what each successive segment mapped to.
Then we set j = our ratio of similarity, built an equation that must hold if our step ladder were to make it across the rectangle.
We then showed that for and k>1, we could eventually have enough steps to make our similar figures by showing there was a solution in which 1/k < j < 1 to the equation we built.
Then we knocked out k = 1 with a longest side argument.
No brilliant insights.
One deduction after another, and:
But lots and lots of work.
it took a long time though
But a looot of work
Curiously, your solution would only have to have the stepladder.
The rest turns out just to be scratch (and you knock out k =1)
All the rest was the work that goes that we could do if we didn't just see the ladder.
(I sure didn't)
Copyright © 2021 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.