A...Question :P (1 Viewer)

[Riviet]

Agh! I read it as n >= 4 so I was trying to solve it for a quadrilateral, I suppose it isnt true for a quadrilateral otherwise surely the question would have been restated.

Yeah i sought of stumbled when i saw n>4, I reckon it's more clear if it had said n>5 so there's no way of misreading it as starting with n=4. Good luck with proving it guys.

 

[airie]

My current take on the question would be to prove it through induction, but it might not yield any result.

It would be best to train yourself for the AMO not by doing past questions straight away if you are not familiar with it. AMT does offer several books on how to tackle olympiad style questions, whether they are effective I am not sure.

Have you done the AMOC Correspondence Program 4 last year? It is used to give people some practice at solving olympiad style questions, by providing hints to guide you. Certainly easier than the AMO, but it is something to start with.

As for your PM, I'll answer it here just in case there is anyone else that is after the same information.

The 2006 AMO will be held on the 7th and 8th Feb. Each day consists of 4 questions, with 4 hours to do them. Like standard international olympiads each question is marked out of 7, and the marks are gained exponentially (ie relatively easy to get 1 mark, harder to get the next mark etc).

There isn't much specific advice I can give you beyond what AMT recommends, since the questions can cover quite a wide range of topics. The most important thing is to realise that you do have all those time, and it's not uncommon to be stuck on a question and not realise any possible ways to solve it until later. Keep on thinking about them.

A useful tip is to draw large sized, proper scaled diagram for geometric questions. It might not give you the answer (or the answer but no working), but can provide you insights into how to solve it. Or in the case of giving you the answer, you can work from both ends to meet in the middle, or know what you're looking out for when writing out your working.

Write every idea you have on the question down and try to justify everything. You never know what you might be given a mark for.

If this question seems very different, don't stress out, because it is certainly one of the harder ones. However, even if you do find the questions in the AMO intimidating, don't worry either, you're already within an elite group of people in Australia to participate in the AMO (roughly 100 or so a year).

That's pretty much all I can think of at the moment. SeDaTeD did the AMO in 2003 and got a bronze, so he might have some inputs of his own.

Hmmm...OK think I got all that Ooh working from both ends...I never really make use of that...I always either do it from one way or another, seeing that I really get dizzy if I have 'RTP' written all over the place And yep I did do that Programme 4 last year, do you mean the actual questions they gave were easier than the AMO, or that they were just easier cos hints were provided? Seeing that although I did get a couple of 7's for that programme, I solved them using more than an hour on average for each question

 

[icycloud]

OK, I have what I think is a proof for n=5.

Important: New proof in a later post. The proof below is flawed (see replies below).

Consider the pentagon with sides r₁, r₂, ..., r₅ and diagonals d₁, d₂, ..., d₅.
Each of the diagonals d_n can be shown to have a limiting minimum length in two of the sides r_n and _m. {please see the attachment diagram}
That is to say, d_n >= r_n and d_n >= r_m.

Thusly, we form a system of inequalities:

d₁ >= r₁
d₁ >= r₂
...
d₅ >= r₅
d₅ >= r₁

We can show that each diagonal is represented twice, and each side is represented twice.
Hence, we have:

2 (d₁ + d₂ + d₃ + d₄ + d₅) >= 2 (r₁ + r₂ + r₃ + r₄ + r₅)

Dividing 10 on both sides, we have:

(r₁ + r₂ + r₃ + r₄ + r₅) /5 <= (d₁ + d₂ + d₃ + d₄ + d₅) /5

This is the result we wanted (AM_r <= AM_d).

This is really an application of the triangle inequality (as I mentioned earlier in this thread).
Consider the triangle with sides r_1, r_5, d_1 (see diagram for this).

Now, by the triangle inequality:

r_1 + r_5 >= d_1

However, consider:

Lim {r_5 --> 0} then r_1 --> d_1
That means r_1 = d_1 when r_5 = 0 {this is the limiting length}.

<Addendum: see posts below> (The fact that a diagonal can form a triangle with another diagonal and a side instead of two sides. Two such triangles can be formed and a unique set of inequalities can then be constructed once again.)

Does this make sense guys? Now I'm going to try to generalise this for all n>4. Please reply with any criticisms/comments.

p.s. I also got very close to solving for n>4 using complex numbers, this alternative method seems quite promising. Maybe that's the way to go instead?

 

[Templar]

AMOC Correspondence Program 4 is both easier in the general ability required for the questions, as well as hints provided.

What if the angle between two sides is less than 60? It is possible to have the diagonal less than any of the two sides it is subtended on.

 

[icycloud]

What if the angle between two sides is less than 60? It is possible to have the diagonal less than any of the two sides it is subtended on.

Can you further expand on that? Do you mean like this? (see diagram) If so, there are combinations to get around that fact? (Note that there can only be a maximum of two angles less that 60 degrees) The diagonal can form triangles with another diagonal! (see the bottom diagram) {The fact that a diagonal can form a triangle with another diagonal and a side instead of two sides. Two such triangles can be formed and a unique set of inequalities can then be constructed once again.}

 

[Templar]

Suppose a cyclic pentagon with the diameter as one side. There is no diagonal greater than that side, and your inequality will not contain that side (apart from the trivial inequality that the side is greater than anything you've got). How do you bring that into the equations?

 

[icycloud]

True, very true. There should be a way to resolve that, BUT I have another proof! Please spot the flaw in this one .

Here it is: (for n=5 once again)

The general convex pentagon with diagonals are shown in the diagram.
Again, let the sides be r₁, r₂, r₃, r₄, r₅ and the diagonals d₁, d₂, d₃, d₄, d₅.

As shown in the diagram, the diagonals can be cut as shown, with fractions 1/a, 1/b, 1/c, etc... of the lengths of the diagonals forming triangles with the sides.

Now, using the triangle inequality, we get the set of inequalities:

(1/a) d₁ + (1/b) d₂ >= r₂
(1/c) d₃ + (1/d) d₁ >= r₃
(1/e) d₄ + (1/f) d₃ >= r₄
(1/g) d₅ + (1/h) d₄ >= r₅
(1/i) d₂ + (1/j) d₅ >= r₁

Adding, we have:

r₁ + r₂ + r₃ + r₄ + r₅ <= (1/a + 1/d) d₁ + (1/b + 1/i) d₂ + (1/c + 1/f) d₃ + (1/e + 1/h) d₄ + (1/g + 1/j) d₅

BUT we also have:

(1/a + 1/d) d₁ <= d₁
(1/b + 1/i) d₂ <= d₂
etc....

SO we get:

r₁ + r₂ + r₃ + r₄ + r₅ <= (1/a + 1/d) d₁ + (1/b + 1/i) d₂ + (1/c + 1/f) d₃ + (1/e + 1/h) d₄ + (1/g + 1/j) d₅ <= d₁ + d₂ + d₃ + d₄ + d₅

Thusly!

r₁ + r₂ + r₃ + r₄ + r₅ <= d₁ + d₂ + d₃ + d₄ + d₅

Dividing both sides by 5, we have our result.

Again, I'm sure there's some kind of flaw in this. Well Templer?

If it's not flawed, then I believe a variation of this method can be used to prove the inequality for all n-gons n>4.

 

[Templar]

Perfectly valid. No flaws that I can see.

With that, I might have a solution to the problem, since you solved both of the pre requisites I required to base a proof on. But let's hear your n-gon solution.

 

[SeDaTeD]

Well, I haven't done Olympiad styles questions for a while and plus I've never had any sorta training, bar those 3 days at the thing Templar also attended.

I don't think I've got anywhere substantial but I had a few digs from different approaches. I'll skim through my writing and see if I can discern what I was thnking.

Ideas:

Starting from a point and going around the polygon, an obtuse angle will guarantee that a 2-step diagonal will be longer than the side, which you started from. An acute angle may result in a diagonal being shorter, equal or longer than the side it came from.

I tried to make rules for associating diagonals with sides. (Going counterclockwise, take a point and all diagonals starting from that and endng on a vertex which is closer by goin counterclockwise than clockwise belong to the side whihc starts from that point) This doesn't really work for even n though. Then I tried to make a function, for each point being: sum of diagonal lengths - no. of diags*side length. The summing them up for each point and seeing if it's >0. Haven't got any further on that thing bar a sketchy idea.

There can be a max of 3 acute angles in the polygon.

Um... Kinda thinking of extreme cases, making sides much longer than the diagonals, but this usually cause other sides to be shorter and also longer diagonals elsewhere. This is forced by convexity somehow.

Could use the property that sum of external angles in convex poly is 360 degrees. Perhaps some dot-product thing between adjacent edges, bu that'd lead to cos's and it kinda looks messy.

Oh yeah, triangle inequality appears to be paramount.

Drawing a poly and constructing circles centred on the vertices and haing the radius equal to the length of the side going counterclockwise (or clockwise). Then with the diagonals, corresponding to the vertex (see above), colour in the bit that is outside the circle, or colour the difference if it's shorter in another colour. Then sum these coloured bits. (Don't ask me how, I'm throwing ideas).

Possible induction, given a poly of n sides with the statement true, place the next vertex, keeping the whole thing convex, and then join up the sides nd diagopnals. Then somehow relate this to the assumed property and properties of the new lines. (Again don't ask me how)

Hmm, well I haven't got anywhere. I'm not a fan of geometry questions though.

 

[SeDaTeD]

Nice work icycloud. I always go, "now why didn't I think of that?" when i see a solution that seems so simple.

 

[Templar]

Nice work icycloud. I always go, "now why didn't I think of that?" when i see a solution that seems so simple.

So typical of us who have been in the olympiad program to say when seeing a simple solution. Especially IMO ones that you write 10 pages and still couldn't get it out, and the official solution is 10 lines.

Basic inductive proof:
1. The argument holds for a pentagon (see icycloud's working)
2a. The sum of diagonals subtended by two sides is always greater than the sum of the sides (extension on icycloud's proof for pentagon)
2b. By dissecting a n-gon into n-1 gon, we can prove that if the argument holds for a n-1 gon, it will hold for an n-gon (exercise!)
3. By the principle of mathematical induction...

 

[airie]

Good work icycloud! Yep your proof looks alright to me too

However, I find it pretty difficult to prove the n-gon case, assuming that the (n-1)-gon case stands >.< I mean, I think icycloud's proof stands largely because of the fact that there is an equal number of sides and diagonals in a pentagon (both 5), seeing how in the end he divides both sides of the inequality by the same number to obtain the required inequality. But this would not be true for n>=6 though, as there is only one solution for n = n(n-3)/2 where n is a positive integer and that is 5. How would we overcome this then?

Also, this may or may not be significant, but I find that any diagonal of an n-gon is divided into n-1 segments at most, (see diagram attached) seeing that only the yellow diagonals connecting points other than the endpoints of the green diagonal would intersect with it and hence divide it. Would this assist in any way?

 

[Templar]

There are two ways to solve this that I can see.

1. Use icycloud's method, to show that the sum of diagonals spanning m sides is greater than the sum of the sides, for m=2 to floor[n/2]. Might be messy logically.

2. Use induction, construct diagonals spanning 2 sides and divide n-gon into various n-1 gons. Modify algebraic equations and done.

 

[airie]

There are two ways to solve this that I can see.
1. Use icycloud's method, to show that the sum of diagonals spanning m sides is greater than the sum of the sides, for m=2 to floor[n/2]. Might be messy logically.
2. Use induction, construct diagonals spanning 2 sides and divide n-gon into various n-1 gons. Modify algebraic equations and done.

Sorry, but could you please prove this rigourously? I find difficulties when trying to prove the n+1 case assuming the n case is true by icycloud's methods, for reason I've already mentioned in my previous post. And I really don't know how to divide an n-gon into (n-1)-gons, seeing that we'd have to take care of the diagonals too, which would be different in an (n-1)-gon from those in an n-gon. Could you expand the 'modigy algebraic equations and done' bit?

 

[who_loves_maths]

wow, good to see such refereshing mathematics being discussed during school breaks... and a nice surprise for me after a 3-month sabbatical from maths in an exceptional problem here

before reading my take on the problem, here's an explanation of most of the notations i've used in the proof for reference:

okay, here's my two-cents, separated into 3 main stages:

STEP 1

This result will be important for the subsequent induction process, but more evidently it represents itself as an immediate graphical solution for the pentagon case - since a pentagon has as many sides as diagonals, and so all its diagonals are of this 'D-set' nature.
simply divide the last inequality throughout by 5 and you've got the inequality case for n=5.

EDIT: sorry, i didn't see icycloud's solution for the case n=5 and Templar's urging of the general result that has come to be shown here in my proof before i made this post.
icycloud's solution for n=5 is of course equivalent (but in a more algebraically complex fashion) to my proof of the same result above; the method above, however, is more graphical and generalises to all convex polygons n > 4 , which is the case Templar has sought.


STEP 2

it seems like all who have posted thus far in this thread have, for some reason, forgotten about the very simple case of the quadrilateral. it is, as one can see, much simpler to prove the case for n=4 than for the pentagon, both graphically and algebraically.
in order to prove the generalinequality, one clearly cannot start an inductive proof with n=5 when the n=4 case is also true (unless you're planning to do backward-induction as well).


STEP 3 [a bit lengthy, sorry]

Q.E.D
okay i admit this last step can be long-winded and off-putting to ppl, but plz bear with me and take a carefully read through it. i can guarantee there's no "fudging" or the likes, but can't promise there won't be mistakes. so plz report and post up an errors that i've made in the proof if spotted thx.


I hope this resolves some issues

 

[buchanan]

[SIZE=-1]

[/SIZE]Prove that for any integer n>=5 and for any convex n-gon, the arithmetic mean of its sidelengths is no greater than the arithmetic mean of its diagonals.

How would you attack such problems? I only got up to...uhh...there are n sides and n(n-3)/2 diagonals in an n-gon...pretty pathetic Can anyone please help?
[SIZE=-1]

No.That's not pathetic at all. Your question (except for the n>=5 bit, which really should be n>=4) is equivalent to the first part of the 1984 IMO Q5:

[/SIZE] Let d be the sum of the lengths of all the diagonals of a plane convex polygon with n > 3 vertices. Let p be its perimeter. Prove that n - 3 < 2d/p.

Why is this equivalent? Because it means p/n < d/(n(n-3)/2), which is precisely your question.


No fancy induction is required:


Given any diagonal AX, let B be the next vertex counterclockwise from A, and Y the next vertex counterclockwise from X. Then the diagonals AX and BY intersect at K. AK + KB > AB and XK + KY > XY, so AX + BY > AB + XY. Keeping A fixed and summing over X gives n - 3 cases. So if we then sum over A we get every diagonal appearing four times on the lhs and every side appearing 2(n-3) times on the rhs, giving 4d > 2(n-3)p.

 

[buchanan]

It is not true for n=4

Be more careful please. It does hold for n=4.

Let the quadrilateral be ABCD, and the diagonals intersect at K.

Then

AK+BK > AB

BK+CK > BC

CK+DK > CD

DK+AK > DA

Adding, we get 2(AK+BK+CK+DK) > AB+BC+CD+DA

so with d=sum of diagonals, p=perimeter, 2d > p and p/4 < d/2, hence it is true for n=4.

 

[noah]

yeah realised that just after i posted it.

hence the deletion

 

[airie]

Wow, well done who_loves_maths and buchanan!

Nice proof who_loves_maths, thanks a lot for your detailed explanation I was pretty baffled as of how to do the induction bit but now I get it Now why did I keep thinking that the diagonals would be changed beyond recognition if I split an (n+1)-gon into a triangle and an n-gon??

That's a really ingenious solution you have there buchanan, and wow, didn't know that this question would have some connections with an IMO question o.0 Your proof sure is short and elegant, but the dumb old me stared at it for like 5 whole minutes before I could finally see the reasons and went 'ooh right!'

lol the question had actually asked for n-gons where n>4, which was what I originally put in the first post of this thread. So I guess that a proof for a quadrilateral wasn't needed for this particular question? And because that there were some people who pointed out that it was easily mistaken for n>=4 which was why they started proving for a quadrilateral first, I figured that I'd just change n>4 to n>=5 just to clarify

Thanks to everyone who has posted in this thread you guys were a great help

 

[SoulSearcher]

That's a really ingenious solution you have there buchanan, and wow, didn't know that this question would have some connections with an IMO question o.0 Your proof sure is short and elegant, but the dumb old me stared at it for like 5 whole minutes before I could finally see the reasons and went 'ooh right!'

sure, if you mean by 'dumb old me' as a girl who is going to participate in the AMO, and is probably on her way to killing the HSC maths exams when she does them.