## USAMO

Go back to the Math Jam ArchiveWe 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

Problem 1

Problem 2

Problem 3

**rrusczyk** (19:03:08)

**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? **

**rrusczyk** (19:03:25)

What initial observations can we make?

**SuperNova** (19:03:39)

the right side is nine times the left side

**rrusczyk** (19:04:15)

Seeing that the far right and far left are so similar, what can we note right
away?

**dareonion** (19:04:13)

The first inequality and the second are equivalent

**rrusczyk** (19:04:28)

First, we note that though this looks like 2 different inequalities, they are
really the same. If we divide

**rrusczyk** (19:04:30)

|BC^3 - CD^3| <= 3|AB^3 - AD^3|

**rrusczyk** (19:04:34)

by 3, we get

**rrusczyk** (19:04:38)

(1/3)|BC^3 - CD^3| <= |AB^3 - AD^3|,

**rrusczyk** (19:04:43)

which is exactly the same as

**rrusczyk** (19:04:46)

(1/3)|AB^3 - AD^3| <= |BC^3 - CD^3|,

**dareonion** (19:04:31)

because you can cycle the vertices of the quadrangle

**rrusczyk** (19:04:55)

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.

**jelyman** (19:03:40)

we can separate the diff of cubes into factors

**rrusczyk** (19:05:18)

Right - any time we see difference of cubes, we should have factoring in mind:

**rrusczyk** (19:05:23)

Differences of cubes suggest factoring:

**rrusczyk** (19:05:30)

**polymorphic** (19:05:32)

and |BC - CD| = |AB- AD|

**tetrahedr0n** (19:05:33)

and use the condition AB + CD = AD + BC

**rrusczyk** (19:06:08)

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?

**tetrahedr0n** (19:06:18)

tangents to a circle

**masamune2387** (19:06:19)

tangents to a circle are equal

**rrusczyk** (19:06:26)

We have equal tangents from a point to a circle; the proof is straightforward:

**rrusczyk** (19:06:55)

**rrusczyk** (19:06:58)

http://www.artofproblemsolving.com/Images/PB/2004USAMO1opp.gif

**rrusczyk** (19:07:02)

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.

**rrusczyk** (19:07:12)

So, we have our difference of cubes factored:

**rrusczyk** (19:07:20)

**rrusczyk** (19:07:29)

Why does this make us happy?

**masamune2387** (19:07:38)

because BC - CD = AB - AD

**rrusczyk** (19:07:48)

First, we have BC - CD = AB - AD, which definitely pops up in the inequality
we want to prove. What about that other factor?

**dareonion** (19:07:42)

The right factor reminds me of law of cosines...

**rrusczyk** (19:08:08)

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).

**rrusczyk** (19:08:37)

60 degrees, 120 degrees, a^2 + b^2 +/- ab : these are all clues that the law
of cosines might be useful.

**rrusczyk** (19:08:41)

How can we use law of cosines here?

**rrusczyk** (19:09:18)

What triangle should we be looking at for law of cosines?

**SuperNova** (19:09:34)

BCD

**tetrahedr0n** (19:09:44)

and CBD

**captcha000** (19:09:46)

bcd

**rrusczyk** (19:10:02)

Right, our factored cubes:

**rrusczyk** (19:10:09)

**rrusczyk** (19:10:23)

Involves BCD. We know we can do this for ABD for the other side, too.

**rrusczyk** (19:10:27)

Law of cosines on BCD gives

**rrusczyk** (19:10:33)

**rrusczyk** (19:10:42)

Now what?

**hmmm** (19:11:05)

-1/2<=cosC<=1/2

**rrusczyk** (19:11:25)

We haven't used our 60 degree restriction. We break it out now:

**rrusczyk** (19:11:31)

Since 60 <= angle C <= 120, we have -1/2 <= cos C <= 1/2, so

**rrusczyk** (19:11:37)

**rrusczyk** (19:11:49)

How does this help?

**masamune2387** (19:11:58)

it's part of our inequality!

**rrusczyk** (19:12:25)

Which part, the left part or the right part?

**krustyteklown** (19:12:31)

left

**masamune2387** (19:12:31)

the left

**captcha000** (19:12:36)

the left part

**rrusczyk** (19:12:51)

Right, now we have:

**rrusczyk** (19:12:58)

**rrusczyk** (19:13:03)

Now, we think we're close - what do we have to do?

**SuperNova** (19:12:27)

use the law of cosines on ABD

**dareonion** (19:12:14)

you can do the same thing on the other side

**rrusczyk** (19:13:28)

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.

**rrusczyk** (19:13:31)

As we did with BCD, we can to with ABD, and we find:

**rrusczyk** (19:13:36)

**rrusczyk** (19:13:46)

Are we done? Can we just turn BD^2 into AB^2 + AD^2 + (AB)(AD)?

**rrusczyk** (19:14:15)

Can we just put the left hand side of that inequality we just found in our original
and say 'done'!

**rrusczyk** (19:15:15)

We have BC^3 - CD^3 >= (AB - BD)BD^2 from before.

**rrusczyk** (19:15:32)

We just showed AB^2 + AD^2 +(AB)(AD) >= BD^2.

**rrusczyk** (19:15:42)

Can we just put these together and say done!

**masamune2387** (19:16:07)

but we want 1/3 somewhere in there...

**rrusczyk** (19:16:25)

Yep - and the problem is worse than that - look closely.

**rrusczyk** (19:16:31)

(This is an important lesson)

**dareonion** (19:16:38)

the signs are going the same way?

**polymorphic** (19:16:38)

um...it's greater than

**polymorphic** (19:16:44)

if the thing were less than BD^2, we'd be ok

**rrusczyk** (19:17:14)

Right - the inequality is 'going the wrong way'

**rrusczyk** (19:17:46)

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

**rrusczyk** (19:18:02)

What's the only part of

**rrusczyk** (19:18:06)

**rrusczyk** (19:18:08)

we can use?

**zfzf21** (19:16:49)

no...we would get both sides >= the same thing

**hmmm** (19:18:17)

the right hand side

**zfzf21** (19:18:20)

the right side

**jelyman** (19:18:23)

the RH ineq

**rrusczyk** (19:18:30)

we can only turn BD^2 into AB^2 + AD^2 - (AB)(AD):

**rrusczyk** (19:18:37)

**rrusczyk** (19:19:06)

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.

**rrusczyk** (19:19:11)

Obviously, that's not true.

**rrusczyk** (19:19:24)

Waht do we have to show now?

**jelyman** (19:19:37)

the 1/3 part

**rrusczyk** (19:19:57)

That's part of the problem, what else?

**masamune2387** (19:19:59)

that RHS >= 1/3 (AB^3 - AD^3)

**zfzf21** (19:20:13)

AB^2+AD^2-(AB)(AD) >= 1/3(AB^2+AD^2+(AB)(AD))

**rrusczyk** (19:20:39)

Exactly, if we prove zfzf21's inequality, we'll get masamune2387's and be done

**rrusczyk** (19:20:43)

How can we show AB^2 + AD^2 - (AB)(AD) >= [AB^2 + AD^2 + (AB)(AD)]/3 to complete
our proof?

**Nukular** (19:21:09)

AM-GM

**dareonion** (19:21:25)

try to use ""no square is negative"" somehow?

**rrusczyk** (19:21:46)

Either/both. For those that don't see it, do this:

**zfzf21** (19:21:39)

simplify

**rrusczyk** (19:21:58)

work backwards, and you can:

**zscool** (19:21:47)

just factor into a square

**rrusczyk** (19:22:16)

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:

**rrusczyk** (19:22:23)

**rrusczyk** (19:23:14)

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.

**rrusczyk** (19:23:32)

If you look at the steps backwards, you'll see how we figured out to do it this
way.

**rrusczyk** (19:23:37)

So, we have shown that

**rrusczyk** (19:23:44)

**rrusczyk** (19:23:53)

By symmetry, the other half of the inequality follows directly.

**rrusczyk** (19:23:58)

Where does equality hold?

**masamune2387** (19:24:14)

when AB = AD and BC = CD

**rrusczyk** (19:24:45)

What does that mean ABCD is?

**SuperNova** (19:24:53)

a kite

**Nukular** (19:24:54)

A kite

**zfzf21** (19:24:59)

kite?

**MPS-vras** (19:25:07)

a kite

**rrusczyk** (19:25:22)

AB = AD, BC = CD makes ABCD a kite.

**rrusczyk** (19:25:28)

Do we have any other conditions?

**rrusczyk** (19:26:16)

We obviously don't have any others where both equalities hold.

**rrusczyk** (19:26:28)

How about one equality or the other?

**Nukular** (19:26:50)

We have to make sure each step in our chain maintains equality

**Dark_Shadow** (19:26:56)

when the opposite angles are 60 and 120 degrees...?

**zfzf21** (19:27:13)

the angles have to be 60 or 120

**Nukular** (19:27:14)

so AB=AD follows from the second to third line.

**rrusczyk** (19:27:36)

Right - Nukular points out how we can find our equality conditions.

**rrusczyk** (19:28:05)

Go through our inequalities and look for equality conditions.

**rrusczyk** (19:29:02)

If the angles are 60 or 120, we still need AB = AD in that last step.

**rrusczyk** (19:29:11)

Are there any questions?

**rrusczyk** (19:29:55)

(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)

**Dark_Shadow** (19:26:16)

of course, there are other proofs, right?

**rrusczyk** (19:30:19)

Yes, there are often many ways to skin Olympiad cats.

**dareonion** (19:30:19)

aren't there always?

**rrusczyk** (19:30:37)

Maybe not always, but usually.

**tetrahedr0n** (19:30:33)

would all rely around law of cosines?

**rrusczyk** (19:30:57)

I'd be surprised if that weren't the case

**rrusczyk** (19:31:10)

But it's not impossible.

**zfzf21** (19:30:56)

i did mine without law of cosines...but im not sure if its right

**dareonion** (19:31:07)

hehe, i bet some scary analytical geometry proof exists that wouldn't need law
of cosines

**rrusczyk** (19:31:22)

ewww.... (but you may be right)

**Nukular** (19:30:38)

#4 had about 20 solutions probably :)

**rrusczyk** (19:31:30)

I'd bet more!

**rrusczyk** (19:31:40)

Are there any more questions for this one?

**Nukular** (19:32:37)

I think #2 is quite possibly the most misread question ever...

**MCrawford** (19:32:58)

**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. **

**MCrawford** (19:33:06)

**MCrawford** (19:33:14)

Prove that S must be equal to the set of all integers.

**MCrawford** (19:33:22)

How might we begin to approach this problem?

**SuperNova** (19:33:32)

you only need the first two numbers

**MCrawford** (19:34:01)

Not true. This is the misreading Nukular referred to.

**MCrawford** (19:34:20)

Not every pair has a gcd of 1 -- the group as a WHOLE has a gcd of 1.

**zfzf21** (19:33:44)

experiment with two numbers?

**jelyman** (19:33:44)

Try out a few cases

**MCrawford** (19:34:51)

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?

**Dark_Shadow** (19:35:07)

3, 4, 1, 0

**SuperNova** (19:35:16)

0, 1, 3, and 4

**MCrawford** (19:35:39)

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.

**MCrawford** (19:35:47)

What else can we determine?

**dareonion** (19:35:43)

And, once you get one, you've got them all

**Dark_Shadow** (19:35:44)

and with 0 and 1 you can get every integer

**tetrahedr0n** (19:35:59)

all the negatives also

**hmmm** (19:35:25)

all integers :)

**dareonion** (19:36:06)

proven easily by induction

**MCrawford** (19:36:19)

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.

**MCrawford** (19:36:32)

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?

**tetrahedr0n** (19:36:41)

induction

**jelyman** (19:36:53)

it looks like the above, only inductively applied to all n

**hmmm** (19:36:54)

Induction

**MCrawford** (19:37:07)

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).

**MCrawford** (19:37:16)

We could establish this induction in various ways, but this gets the point across.

**hilbert** (19:34:57)

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.

**MCrawford** (19:37:47)

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.

**MCrawford** (19:38:10)

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?

**jelyman** (19:38:50)

12, 18, 6, 0, 24, 36...

**jelyman** (19:38:58)

all multiples of 6

**dareonion** (19:39:00)

you can eventually get the GCD of the two numbers through repeated application
of rule c.

In this case, 0, 6, 12, 18, 24,

**GreenTwilight** (19:39:07)

Every number that is a multiple of GCF(42,30)

**MCrawford** (19:39:24)

Ah, so we have a second lemma.

**Nukular** (19:39:22)

All linear combinations of 42 and 30 are in S

**Nukular** (19:38:01)

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.

**MCrawford** (19:39:58)

So, any time we examine two numbers in the list, we have all multiples of their
GCD.

**MCrawford** (19:40:13)

How can we use what we have learned to filter down to including 1 in S?

**hmmm** (19:40:55)

Take the gcd one at a time and get gcd(a1...an) is in S

**SuperNova** (19:40:58)

use gcd(gcd(a1, a2), a3)...

**MCrawford** (19:41:46)

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?

**Nukular** (19:41:44)

yeah but once you throw gcd(a1, a2) into the mix, and induct, you lose (b) and
things go out the window.

**MCrawford** (19:42:30)

Oh? What about you're nice extra lemma above. If x - y is in S, then x + y is
in S.

**Dark_Shadow** (19:38:27)

well, all diophantine equations of the form ax + by = 1 have solutions if a
and b are relatively prime

**Nukular** (19:43:27)

what DS wrote is extendable into more than two integers, nicely enough.

**MCrawford** (19:44:19)

Why is it that we can create any linear combination of the original elements?

**MCrawford** (19:45:19)

Let's take a look at a quick example so that we can make this rigorous.

**MCrawford** (19:45:30)

Suppose we start with 221, 187, and 143.

**MCrawford** (19:45:54)

(221, 187) = 17, (187, 143) = 11, (221, 143) = 13.

**MCrawford** (19:46:19)

Now, how do we make linear combinations of 11, 13, and 17?

**dareonion** (19:47:06)

Something like 11x + 13y = 1 + 17z ?

**zscool** (19:47:37)

2*17 - 3*11 = 1

**MCrawford** (19:48:11)

True, but that doesn't show us WHY we can just take the linear combinations.

**MCrawford** (19:48:28)

We need to stick to the rules and SHOW that we can just start taking linear
combinations.

**Nukular** (19:48:58)

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)

**MCrawford** (19:49:12)

Exactly.

**MCrawford** (19:49:37)

We could solve 13x + 11y = 17 for instance.

**Nukular** (19:49:39)

As long as we eventually get it to two rel. prime #'s we can finish like this.

**MCrawford** (19:50:20)

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.

**GreenTwilight** (19:50:00)

But what if 11 and 13 weren't relatively prime

**MCrawford** (19:50:58)

Suppose instead of having 11, 13, and 17 we had 22, 26, and 34...

**MCrawford** (19:51:16)

Then there must be another a_i that we can use because they can't ALL include
2 as a prime.

**MCrawford** (19:51:37)

Really, in order to get rid of any single prime, you just need one a_i that
isn't a multiple of that prime.

**MCrawford** (19:51:57)

Any questions about this problem?

**Fermatprime** (19:52:45)

can you induct from two?

**MCrawford** (19:53:52)

We don't really need to make an induction argument on number 2.

**MCrawford** (19:54:08)

We do go down a chain, but it's a finite chain and we are only looking to filter
out each prime.

**MCrawford** (19:54:25)

We filter out any prime once we include some a_i that isn't a multiple of that
prime.

**Nukular** (19:54:12)

I hope my induction worked, looked like it did

**MCrawford** (19:54:56)

Of course, some people DID use induction. I'm just saying we don't have to (at
this point in the proof)./

**rrusczyk** (19:55:32)

Ready for number 3?

**GreenTwilight** (19:55:38)

Let the fun begin...

**Nukular** (19:55:49)

Pain and anguish!

**rrusczyk** (19:55:58)

**3. For what real values of k > 0 is it possible to
dissect a 1 x k rectangle into two similar but noncongruent polygons? **

**rrusczyk** (19:56:12)

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).

**zfzf21** (19:55:59)

did anyone here get it?

**rrusczyk** (19:56:20)

Did anyone?

**rrusczyk** (19:56:46)

No yesses - a lot of people with the 'mistake answer'.

**rrusczyk** (19:56:50)

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.

**rrusczyk** (19:57:13)

What's our first instinct when we look at the problem? What do we think the
answer is on a glance?

**dareonion** (19:57:26)

two similar rectangles

**hmmm** (19:57:26)

two similar rectangles

**zhugeliang** (19:57:35)

rectangle

**rrusczyk** (19:57:45)

That's what we thought, too.

**rrusczyk** (19:58:02)

Cut it into two rectangles, slide the divider over enough and you'll be ok.

**rrusczyk** (19:58:24)

Then, we set down to proving our instincts. Where do we start?

**Nukular** (19:57:58)

We can see off the bat though that if c works, 1/c works, so thats good to note.

**rrusczyk** (19:58:45)

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).

**rrusczyk** (19:59:10)

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?

**rrusczyk** (19:59:46)

(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.)

**GreenTwilight** (19:58:50)

I started showing that the line of dissection must travel from one side to the
opposite side

**probability1.01** (19:59:41)

maybe right-angle zig-zag cuts

**GreenTwilight** (19:59:52)

Going from corner to corner

**probability1.01** (20:00:09)

or diagonal cuts...

**rrusczyk** (20:00:24)

Right - there are all sorts of ways we can cut this thing. We have to investigate
them all.

**rrusczyk** (20:00:55)

This can get pretty scary. What cases can we get rid of easily?

**Fermatprime** (20:01:01)

count the vertices if it doesn't go from one side to the opposite...

**zfzf21** (20:01:15)

if we dont go from side to side i think we'll get more vertices on one than
on the other

**hmmm** (20:01:22)

the cut goes through 2 adjacent sides of the rectangle

**rrusczyk** (20:02:17)

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.

**rrusczyk** (20:02:46)

Let's take a look at starting through the corner of a rectangle:

**rrusczyk** (20:02:52)

**rrusczyk** (20:03:13)

Can we have similar polygons in this case?

**probability1.01** (20:03:26)

not without congruent ones

**JamesMatthews** (20:03:36)

They'd have to be congruent

**rrusczyk** (20:04:13)

How can we prove they have to be congruent?

**probability1.01** (20:04:02)

The cut has to go through B, right?

**rrusczyk** (20:04:35)

How can we prove that?

**JamesMatthews** (20:04:39)

First, by counting sides, we see that the cut has to go thru B

**MysticTerminator** (20:04:39)

yeah, in order for they polygons to have the same number of sides

**Fermatprime** (20:04:42)

count vertices

**Nukular** (20:04:42)

count sides

**probability1.01** (20:04:42)

Counting sides

**rrusczyk** (20:04:54)

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.

**rrusczyk** (20:05:03)

What do we conclude if this dissection goes through D and B and the polygons
are similar?

**dareonion** (20:05:14)

also congruent

**Nukular** (20:05:25)

they are congruent

**rrusczyk** (20:05:35)

Why? What's an easy way to prove it?

**masamune2387** (20:06:27)

right angle at C and A...then use corresponding sides?

**probability1.01** (20:06:00)

The length of the segment going through B has to equal that through D?

**Dark_Shadow** (20:06:55)

the two longest sides are the same

**rrusczyk** (20:07:08)

Let's put these together and tighten it up.

**rrusczyk** (20:07:23)

What can we say about the sides of the two polygons?

**rrusczyk** (20:07:57)

(Note, we don't know that BC and AB are the longest sides)

**Dark_Shadow** (20:08:07)

they're the same

**rrusczyk** (20:08:21)

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.

**rrusczyk** (20:08:38)

Any questions about that?

**masamune2387** (20:08:59)

Wow, that was easy enough

**rrusczyk** (20:09:11)

Yep.

**rrusczyk** (20:09:12)

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).

**rrusczyk** (20:09:36)

So, what cases should we worry about now?

**GreenTwilight** (20:10:02)

A dissector with a non-right angle

**rrusczyk** (20:10:41)

Right - we're aiming at proving we have 2 rectangles, so we have to prove we
can throw out the non-right angles.

**rrusczyk** (20:10:46)

How can we show that there's no funky cut that makes similar polygons - that
our only option is right angles?

**rrusczyk** (20:10:52)

**rrusczyk** (20:10:55)

http://www.artofproblemsolving.com/Images/PB/2004USAMO3cut2.gif

**rrusczyk** (20:11:02)

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)

**rrusczyk** (20:11:18)

What do we want to show?

**Nukular** (20:12:09)

We would want to show that the left polygon, if similar to the right polygon,
is congruent to the right polygon

**Fermatprime** (20:12:16)

the polygons are dissimilar or congruent

**rrusczyk** (20:13:13)

How are we going to show that?

**JamesMatthews** (20:13:00)

That they map to A and B?

**rrusczyk** (20:13:22)

That what maps to A and B?

**JamesMatthews** (20:13:30)

C and D?

**zfzf21** (20:13:37)

D with B and C with A?

**rrusczyk** (20:13:55)

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?

**rrusczyk** (20:14:09)

What general tactic should we take?

**rrusczyk** (20:15:05)

(In general, if we're completely at a loss trying to prove a given statement
is true, what should we try to do?)

**Nukular** (20:15:15)

Disprove it.

**Fermatprime** (20:15:16)

contradiction

**masamune2387** (20:15:16)

contradiction?

**SuperNova** (20:15:17)

prove it can't be false

**rrusczyk** (20:15:38)

Let's try a contradiction. What do we have to assume?

**masamune2387** (20:15:49)

assume the polygons are similar but not congruent

**Nukular** (20:15:50)

The two figures are similar and noncongruent.

**hmmm** (20:15:54)

assume they are similar and noncongruent

**rrusczyk** (20:16:21)

OK - remember we were focusing on mapping C and D to A and B, so:

**GreenTwilight** (20:16:12)

We have to assume that AB doesn't map to CD

**rrusczyk** (20:16:28)

Suppose DC maps to a side other than AB.

**rrusczyk** (20:16:35)

**rrusczyk** (20:16:50)

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?

**Fermatprime** (20:16:50)

""connects""...

**rrusczyk** (20:17:01)

heh - thanks.

**rrusczyk** (20:19:55)

Focusing just on C and D going to C' and D' doesn't seem to do it.

**rrusczyk** (20:20:48)

But knowing where C and D go to (where C' and D' are), what else can we locate?

**rrusczyk** (20:21:33)

I see a lot of 'A' and 'B' - do we know for sure where they go?

**rrusczyk** (20:22:14)

Do we know where any points at all go?

**rrusczyk** (20:22:21)

(besides C and D)

**zfzf21** (20:22:26)

we know where W and Z are

**Nukular** (20:22:34)

The point on AD that is connected to Y

**rrusczyk** (20:23:33)

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).

**rrusczyk** (20:23:49)

We have to use what we know - how do we use knowing where those lines go?

**jelyman** (20:24:03)

How do we know where W and Z are mapped to?

**rrusczyk** (20:24:36)

We don't know exactly where they are coming from, but we know they are images
of points on the AD and BC.

**rrusczyk** (20:24:53)

How does that help? What can we say about those sides with respect to the right
polygon?

**jelyman** (20:25:19)

hmm, how do we know that they are images of points on Ad and BC

**rrusczyk** (20:26:08)

Because CD maps to C'D'. W and Z are on the perpendiculars out of those points.

**zfzf21** (20:26:27)

W is the image of point adjacent to C that's not D

**rrusczyk** (20:26:36)

Right.

**rrusczyk** (20:27:31)

Here's the diagram again:

**rrusczyk** (20:27:37)

**rrusczyk** (20:27:38)

http://www.artofproblemsolving.com/Images/PB/2004USAMO3cut3.gif

**rrusczyk** (20:27:58)

What is special about lines BC and AD with respect to the right polygon?

**masamune2387** (20:27:40)

wait, then don't we know that D'C'WZ must be enclosed?

**rrusczyk** (20:28:24)

Clarify - I think you've got it.

**masamune2387** (20:29:04)

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

**rrusczyk** (20:29:35)

What is enclosed (I think you have it - just trying to get it to be clear to
everyone)?

**grommit** (20:30:02)

D'Z isn't the image of DA, is it? Neither is C'W the image of CB

**rrusczyk** (20:30:36)

They are images of the segments on DA and CB

**masamune2387** (20:29:48)

the polygon WZC'D'

**rrusczyk** (20:30:52)

Does this give us a contradiction & why?

**masamune2387** (20:31:09)

Well how are we supposed to dissect ABCD then?

**grommit** (20:31:22)

and this is a contradction because the outside polygon shouldn't have a loop
in the center.

**masamune2387** (20:31:29)

Since WZC'D' is enclosed, we have 3 regions, and we only want 2

**rrusczyk** (20:31:41)

Let's see if we can clean this up and make it neat.

**rrusczyk** (20:32:02)

The entirety of the right polygon is between lines BC and AD.

**rrusczyk** (20:32:13)

How does this observation complete this case?

**Teddy** (20:32:46)

all points in the left polygon must be between C'W and D'Z?

**rrusczyk** (20:32:58)

Bingo.

**rrusczyk** (20:33:50)

Since all of the right polygon is between BC and AD, all of the left polygon
must be between the images of them.

**rrusczyk** (20:34:08)

Since the image of CD is inside ABCD, this is clearly impossible.

**rrusczyk** (20:34:20)

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.

**rrusczyk** (20:35:07)

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).

**grommit** (20:35:49)

so what exactly did we just proved? that if we have two such polygons that CD
maps to one of the other sides?

**rrusczyk** (20:36:24)

We proved that if we try to use diagonal cuts from the sides, then we can't
get similarity without congruence.

**GreenTwilight** (20:36:23)

No, that there must be all right angles in your line of dissection

**rrusczyk** (20:37:21)

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).

**Teddy** (20:37:30)

i think its stronger to say we proved that CD cant map to the interior of ABCD

**rrusczyk** (20:37:49)

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)*

**rrusczyk** (20:38:11)

It must map to something on the side BC (or AD).

**rrusczyk** (20:38:36)

What two cases do we have to consider now?

**MPS-vras** (20:39:19)

it maps to the interior of the side or it maps to a segment containing an endpoint
of the side

**rrusczyk** (20:39:38)

Do we have to worry about the interior of the side?

**SuperNova** (20:40:25)

no, then there would be two cuts from the same side

**Teddy** (20:40:35)

no,we get a cut from a side to itself

**rrusczyk** (20:40:54)

Right - so CD must map to a segment with A or B as a endpoint.

**rrusczyk** (20:41:17)

Suppose B is that endpoint.

**rrusczyk** (20:41:22)

What are our options?

**zfzf21** (20:42:32)

C maps to B or D maps to B

**rrusczyk** (20:42:52)

We have two possibilities: C maps to B, D maps to B. The first leads to our
two rectangles:

**rrusczyk** (20:42:58)

**rrusczyk** (20:43:10)

How can we see in this case that we must get two rectangles?

**rrusczyk** (20:44:07)

(think about the bounding argument we used before)

**rrusczyk** (20:45:02)

Can the left polygon go beyond D' to the right?

**hmmm** (20:45:28)

no

**rrusczyk** (20:45:38)

Why not?

**hmmm** (20:46:52)

The left polygon is contained between C'A and the line through D' parallel to
it

**zfzf21** (20:46:56)

the left polygon is bounded by C'D' since the right is bounded by CD

**rrusczyk** (20:47:11)

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.

**rrusczyk** (20:47:29)

Can the right polygon extend past D' to the left?

**SuperNova** (20:46:14)

the right polygon can't go above AD

**MPS-vras** (20:46:24)

if it did, then an image point would have to be above AD

**rrusczyk** (20:48:25)

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.

**rrusczyk** (20:48:29)

Here's another way to look at it:

**rrusczyk** (20:48:41)

http://www.artofproblemsolving.com/Images/PB/2004USAMO3cut4.gif

**rrusczyk** (20:49:04)

**rrusczyk** (20:49:08)

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.

**rrusczyk** (20:49:44)

Many of you have already talked about dealing with the two rectangles.

**rrusczyk** (20:49:54)

How do we deal with the two non-congruent rectangles?

**rrusczyk** (20:50:41)

How do we find what k work?

**rrusczyk** (20:51:18)

(This is the part many of you did as your solution)

**rrusczyk** (20:51:29)

What k work when we cut into two rectangles and why?

**hmmm** (20:51:30)

set up the ratio of the corresponding sides and solve

**rrusczyk** (20:51:38)

**rrusczyk** (20:51:56)

There are our rectangles and some variables - what's our equation?

**JamesMatthews** (20:52:08)

(k-j)/1 = 1/j

**hmmm** (20:52:13)

1/(k-j)=j

**SuperNova** (20:52:16)

1/k-j = j/1

**rrusczyk** (20:52:26)

we use our similarity to find (k-j)/1 = 1/j, or j^2 - kj + 1 = 0.

**rrusczyk** (20:52:29)

Therefore, we have:

**rrusczyk** (20:52:34)

**rrusczyk** (20:52:43)

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.

**rrusczyk** (20:53:09)

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.

**rrusczyk** (20:53:41)

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.

**rrusczyk** (20:53:54)

At this point, I still believed this was the only solution.

**rrusczyk** (20:54:19)

Before diving into our other case (where D maps to B), let's talk about this:

**Nukular** (20:11:30)

Wouldnt we also need to consider AB to CD afterward?

**rrusczyk** (20:54:32)

Why don't we worry about AB to CD for k > 1?

**Teddy** (20:54:39)

1 to 1 ratio = congruency

**rrusczyk** (20:54:55)

Why do we have a 1:1 ratio?

**rrusczyk** (20:55:49)

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?

**rrusczyk** (20:55:58)

Why don't we worry about that?

**rrusczyk** (20:56:25)

(For k>1)

**probability1.01** (20:55:02)

because AB = CD

**Fermatprime** (20:56:17)

WLOG

**probability1.01** (20:56:17)

well it's just turned 90 degrees, right?

**dareonion** (20:56:27)

you can deal with it by renaming vertices and rotating and scaling the rectangle
to become what it is now

**rrusczyk** (20:56:38)

We can't quite do that.

**rrusczyk** (20:56:53)

Nukular is talking about cutting from short side to short side, not long to
long.

**rrusczyk** (20:57:04)

This is fundamentally different from what we're doing.

**rrusczyk** (20:57:15)

How can we 1-line dismiss that case?

**zfzf21** (20:57:52)

the longest sides of the two rectangles would be equal

**rrusczyk** (20:59:05)

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)

**rrusczyk** (20:59:29)

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.

**rrusczyk** (20:59:36)

Same longest side = congruency.

**rrusczyk** (20:59:46)

So, we're left with D maps to B.

**rrusczyk** (20:59:53)

**rrusczyk** (20:59:59)

http://www.artofproblemsolving.com/Images/PB/2004USAMO3cut6.gif

**rrusczyk** (21:00:12)

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.

**rrusczyk** (21:00:45)

(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.)

**rrusczyk** (21:02:00)

What do we wonder about this?

**probability1.01** (21:02:07)

so (k-j)*(1+j^2+j^4+...) < or = k?

**rrusczyk** (21:02:29)

Why? What does that mean?

**probability1.01** (21:02:47)

well the horizontal cuts add up to be less than k so you don't go outside the
rectangle.

**rrusczyk** (21:03:06)

We wonder: does this step ladder hit AD? And is the result a pair of similar
polygons that we hadn't thought of before?

**probability1.01** (21:03:07)

And if that's true, I believe it follows that the vertical cuts also don't go
too far.

**rrusczyk** (21:03:17)

Let's see.

**rrusczyk** (21:03:26)

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:

**rrusczyk** (21:03:31)

**rrusczyk** (21:03:34)

http://www.artofproblemsolving.com/Images/PB/2004USAMO3cut7.gif

**rrusczyk** (21:03:46)

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.)

**rrusczyk** (21:03:53)

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.

**rrusczyk** (21:04:05)

We can find all the lengths on our ladder as before - we just multiply each
leg by j.

**rrusczyk** (21:04:11)

Now, can we build an equation?

**SuperNova** (21:05:15)

(k-j)(j+j^3+...) = 1

**rrusczyk** (21:05:27)

Where does that come from?

**SuperNova** (21:05:43)

the vertical parts of the ladder

**rrusczyk** (21:06:05)

Right - is there an even simpler equation we can see in the diagram?

**rrusczyk** (21:06:42)

(SuperNova's equation is right, and we can use that, but we can get to the equation
it will simplify to even faster - how)

**dareonion** (21:06:41)

1/j + kj^(2n-2) - j ^ (2n-1)=k

**rrusczyk** (21:06:55)

Since AD = k and AD = AZ + ZD, we have

**rrusczyk** (21:07:02)

**rrusczyk** (21:07:10)

We take the j out of the denominator:

**rrusczyk** (21:07:17)

**rrusczyk** (21:07:40)

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).

**rrusczyk** (21:08:06)

What do we wonder about this equation?

**JamesMatthews** (21:09:02)

Does it have a sensible solution?

**hmmm** (21:09:07)

for which k does it have a solution for j, 0<j<k?

**rrusczyk** (21:09:36)

Exactly - does it have a sensible solution. What are 'sensible solutions'?

**rrusczyk** (21:10:06)

is a solution in 0 < j < k sufficient to make us happy?

**zhugeliang** (21:10:05)

everything but 1

**rrusczyk** (21:10:16)

Why does 1 make us sad?

**JamesMatthews** (21:10:32)

We then have congruence

**rrusczyk** (21:10:42)

Right. If j =1, we have congruence.

**JamesMatthews** (21:10:14)

Nonnegative, the stepladder doesn't crash into AB.

**rrusczyk** (21:10:59)

We have to worry about where our ladder goes.

**rrusczyk** (21:11:06)

Look at it - what are the bounds on j?

**rrusczyk** (21:11:22)

Obviously it can't be negative.

**rrusczyk** (21:11:28)

What about the top of the rectangle?

**SuperNova** (21:11:33)

1/j < k

**hmmm** (21:11:46)

1/k<j<k

**rrusczyk** (21:12:07)

We need j > 1/k, or else DZ will be > k, which is bad.

**rrusczyk** (21:12:31)

So, we go hunting. How?

**rrusczyk** (21:12:49)

Do we need to actually find a solution?

**JamesMatthews** (21:13:36)

By taking n arbitrarily large, we can take k as close to 1 as we like

**rrusczyk** (21:14:02)

Are we guaranteed to have j in our desired range?

**JamesMatthews** (21:14:15)

Not sure. :)

**rrusczyk** (21:14:38)

We wish to show that there is a j in a certain interval that solves:

**rrusczyk** (21:14:46)

**rrusczyk** (21:14:53)

for a given k.

**rrusczyk** (21:15:03)

We don't have to find the solution. We just have to show it exists.

**rrusczyk** (21:15:10)

How do we do that?

**zfzf21** (21:15:14)

substitute j = 1/k and j = k?

**Fermatprime** (21:15:24)

limiting behavior?...

**rrusczyk** (21:15:34)

Explain more.

**JamesMatthews** (21:15:39)

Is the equation < 0 at one end of the interval and > 0 at the other end
of the interval?

**rrusczyk** (21:15:49)

OK

**rrusczyk** (21:15:50)

We can rearrange and write our equation as a polynomial equal to 0:

**rrusczyk** (21:15:58)

**rrusczyk** (21:16:27)

What happens when we put k in there?

**JamesMatthews** (21:16:53)

K^2-1

**zfzf21** (21:16:54)

k^2 -1>0

**rrusczyk** (21:17:00)

f(k) = k^2 - 1 > 0

**rrusczyk** (21:17:16)

What happens if we put in 1/k?

**JamesMatthews** (21:17:49)

1/k^(2n)-1/k^(2n-2)

**zfzf21** (21:17:50)

1/k^2n - 1/k^(2n-2) < 0

**hmmm** (21:17:58)

1/k^(2n)-1/k^(2n-2)

**probability1.01** (21:18:28)

1/k^2 - 1 < 0 (obviously true, right?)

**rrusczyk** (21:18:39)

f(1/k) = (1/k)^2n - (1/k)^(2n-2) < 0

**rrusczyk** (21:18:42)

Are we done?

**rrusczyk** (21:18:52)

Does this make us happy?

**hmmm** (21:19:11)

yes, because f is continuous

**rrusczyk** (21:19:24)

But what might j be?

**rrusczyk** (21:19:41)

That would make us sad.

**zfzf21** (21:20:06)

1

**rrusczyk** (21:20:20)

We have f(1/k) < 0, and we have f(k) > 0, so there's a soluition between
them.

**rrusczyk** (21:20:25)

Unfortunately, it could be 1.

**rrusczyk** (21:20:37)

What is f(1)?

**dareonion** (21:19:15)

or did we already do that?

**probability1.01** (21:20:45)

0

**SuperNova** (21:20:48)

0

**rrusczyk** (21:20:57)

And now we are sad.

**rrusczyk** (21:21:03)

What should we do?

**JamesMatthews** (21:21:17)

Look for other solutions?

**rrusczyk** (21:21:51)

Indeed, but if we use the range 1/k to k, we may always hit 1.

**rrusczyk** (21:21:57)

What range should we look at?

**probability1.01** (21:22:12)

maybe 1 to k (not inclusive)

**rrusczyk** (21:22:30)

Or?

**probability1.01** (21:22:38)

1/k to 1 (not inclusive)

**JamesMatthews** (21:22:52)

(1/k,1]

**rrusczyk** (21:23:06)

We can also look between 1/k to 1.

**rrusczyk** (21:23:11)

Trouble is, f(1) = 0.

**rrusczyk** (21:23:17)

How do we deal with that problem?

**rrusczyk** (21:23:57)

Since f(1) =0, what can we do to f?

**probability1.01** (21:24:08)

factor?

**Nukular** (21:24:18)

factor

**rrusczyk** (21:24:32)

We can take the 1 factor out. If we factor out j-1, we get:

**rrusczyk** (21:24:40)

**rrusczyk** (21:24:46)

Why does this make us happy?

**rrusczyk** (21:26:13)

What can we do with that big expression on the right?

**rrusczyk** (21:26:53)

(I think y'all are just assuming what I'm driving at:

**rrusczyk** (21:27:01)

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.

**rrusczyk** (21:27:07)

So, we are investigating:

**rrusczyk** (21:27:12)

**rrusczyk** (21:27:43)

We now can do the same thing we tried before: try finding an interval that must
have a soluiton.

**rrusczyk** (21:27:47)

What is g(1)?

**Nukular** (21:28:09)

1 - (k-1)(2n-2) + 1

**JamesMatthews** (21:28:25)

2 - (k-1)(2n-2)

**rrusczyk** (21:29:19)

g(1) = 1 - (k-1)(2n-2) + 1 = 2 - (k-1)(2n-2).

**rrusczyk** (21:29:24)

What do we know about this?

**rrusczyk** (21:30:10)

Can we always make this negative?

**JamesMatthews** (21:30:23)

By taking n large?

**rrusczyk** (21:30:52)

Remember, we get to pick n! As long as k > 1, we can pick an n such that
g(1) < 0

**rrusczyk** (21:31:01)

So what's left to show?

**zfzf21** (21:31:31)

g(1/k) > 0

**hmmm** (21:31:15)

g(1/k)>0

**rrusczyk** (21:31:46)

We want to show that g(1/k) > 0.

**rrusczyk** (21:32:03)

Do we have to stick 1/k in that nasty expression, or is there a slick way we
can get around that?

**rrusczyk** (21:32:16)

(What have we already discovered about j = 1/k)

**zfzf21** (21:32:52)

f(1/k)<0

**JamesMatthews** (21:32:57)

g(1/k) = f(1/k)/(j-1) = negative/negative = positive

**rrusczyk** (21:33:28)

Right.

**rrusczyk** (21:33:50)

We know that f(1/k) < 0, and that f(j) = (j-1) g(j).

**rrusczyk** (21:34:16)

Hence, g(1/k) = f(1/k)/(1/k-1) > 0, since it is the ratio of negative numbers.

**rrusczyk** (21:34:35)

For those of you who wanted to evaluate g(1/k) explicitly:

**rrusczyk** (21:34:40)

**rrusczyk** (21:35:06)

g(1/k) > 0,

**rrusczyk** (21:35:09)

Are we happy?

**SuperNova** (21:35:15)

yes

**JamesMatthews** (21:35:17)

Yup

**rrusczyk** (21:35:25)

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.

**masamune2387** (21:35:24)

yay, we found a solution

**rrusczyk** (21:35:34)

We're happy, but not finished.

**rrusczyk** (21:36:29)

(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.)

**Nukular** (21:36:01)

We of course have to disprove k=1 from being a possibiility don't we.

**JamesMatthews** (21:36:25)

Might we need to prove that k <> 1?

**rrusczyk** (21:36:41)

Yep. How can we do that quickly?

**rrusczyk** (21:36:58)

What method that we've already used can we re-use to knock off that case.

**SuperNova** (21:36:55)

g(1/1) = g(1)

**rrusczyk** (21:37:27)

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.

**rrusczyk** (21:37:53)

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.

**rrusczyk** (21:38:12)

Think of how we knocked out other cases quickly: will any of those methods work?

**rrusczyk** (21:39:17)

(Things we did already: bounding argument, vertex counting, longest side)

**probability1.01** (21:39:35)

longest side

**rrusczyk** (21:39:55)

Explain.

**probability1.01** (21:40:19)

well 1 has to be the longest since the adjacent side of length 1 is partitioned.

**masamune2387** (21:40:34)

the longest sides are always AB and CD, so the parts are congruent!

**rrusczyk** (21:41:04)

If AB and CD aren't the longest side, then the longest side is part of both,
and we're done.

**rrusczyk** (21:41:10)

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.

**rrusczyk** (21:41:30)

When we got to the last case, we discovered that our hunch was wrong.

**rrusczyk** (21:41:37)

And there we found the solution.

**rrusczyk** (21:41:48)

Even working through the stepladder portion wasn't so hard.

**rrusczyk** (21:42:02)

Mostly, I want to stress that we didn't 'just see' this solution.

**rrusczyk** (21:42:06)

We reasoned our way to it.

**rrusczyk** (21:42:15)

The solution I 'just saw' was wrong.

**rrusczyk** (21:42:21)

I'll quickly summarize our solution:

**rrusczyk** (21:42:42)

First, we let k>1 since we could argue symmetry.

**rrusczyk** (21:43:19)

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.)

**rrusczyk** (21:43:43)

Next, we showed that CD could not map to something inside ABCD.

**rrusczyk** (21:43:53)

We deduced that it must map to something on the side of ABCD.

**rrusczyk** (21:44:37)

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.

**rrusczyk** (21:45:21)

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.

**rrusczyk** (21:45:36)

Then we dealt with the case of C mapping to B.

**rrusczyk** (21:45:53)

We used a bounding argument again to show that the only possibility there was
two rectangles.

**rrusczyk** (21:45:59)

Then we went to D mapping to B.

**rrusczyk** (21:46:34)

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.

**rrusczyk** (21:47:01)

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.

**rrusczyk** (21:47:47)

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.

**rrusczyk** (21:47:56)

Then we knocked out k = 1 with a longest side argument.

**rrusczyk** (21:48:01)

No magic.

**rrusczyk** (21:48:07)

No brilliant insights.

**rrusczyk** (21:48:16)

One deduction after another, and:

**Fermatprime** (21:48:10)

But lots and lots of work.

**masamune2387** (21:48:18)

it took a long time though

**JamesMatthews** (21:48:20)

But a looot of work

**rrusczyk** (21:48:25)

yep.

**rrusczyk** (21:48:36)

Curiously, your solution would only have to have the stepladder.

**rrusczyk** (21:48:47)

The rest turns out just to be scratch (and you knock out k =1)

**rrusczyk** (21:49:06)

All the rest was the work that goes that we could do if we didn't just see the
ladder.

**rrusczyk** (21:49:10)

(I sure didn't)