2 Olympiad Geometry problems I like

[sirio11]

Problem #1:

Let P_1,P_2,P_3,.......,P_n points contained in a circle with radius = r with P_1 being the center of the circumference.
Let d_k = min{//P_j - P_k// j <> k } (This is the minimum of the distances from the other points to P_k)

Prove that: (d_1)^2+(d_2)^2+(d_3)^2+.......+(d_n)^2 <= 9(r^2)

Problem # 2 (Hard):

Let abcdef an hexagon with every pair of sides parallel. Any 3 vertices can be covered by a wide stripe of length = 1 (This is the length between the lines of the infinite strip).

Prove that the hexagon can be covered by a wide stripe of length = sqrt(2)

[furyshade]

here is another one that one of my brothers friends got when he did it, i liked it a lot and the solution is cool

what is the remainded of (1!+2!+3!...100!)/12

[blah_blah]

[ QUOTE ]
here is another one that one of my brothers friends got when he did it, i liked it a lot and the solution is cool

what is the remainded of (1!+2!+3!...100!)/12

[/ QUOTE ]

these problems have absolutely nothing in common at all. also, n! is divisible by 12 for n>3, so your problem is trivial (the answer is 1!+2!+3! = 9)

[furyshade]

[ QUOTE ]
[ QUOTE ]
here is another one that one of my brothers friends got when he did it, i liked it a lot and the solution is cool

what is the remainded of (1!+2!+3!...100!)/12

[/ QUOTE ]

these problems have absolutely nothing in common at all. also, n! is divisible by 12 for n>3, so your problem is trivial (the answer is 1!+2!+3! = 9)

[/ QUOTE ]

i never said they had anything to do with it, other than that they both were olympiad questions

[blah_blah]

pray tell which olympiad that was on?

[thylacine]

[ QUOTE ]
pray tell which olympiad that was on?

[/ QUOTE ]

The special olympiad.

[sirio11]

Meh, I don't have a problem with calling your question Olympiad, there all all kind of levels in the math Olympiad.
Probably for this forum easy problems are better, since we don't use too much time to post answers (Look at my problems, no answers yet).

A little variation I thought for your problem is:

For which k, 1+2+3+....+k divides 1!+2!+3!+....+k!

[Phil153]

#2 is tilting me. I can see it's true by drawing a diagram (since equal sides form the maximum ratio of hexagon width:strip length) but the proof is eluding me. It's something to do with the angles of the largest width internal triangle and how the points of that triangle relates to the lengths of ab,bc,and cd (and therefore the angles and therefore extra width required).

I'm missing something simple.

[jay_shark]

1) Are all the points on the circumference of the circle ?

The lhs of the inequality can be shown to be maximized when the n points form a regular polygon . Equality happens when there are 3 points equally spaced from each other .

Proof: Suppose we have n-1 points and we've determined d1,d2,d3,...,d(n-1). Now let the variable point Pn be between 2 random points . It's easy to see that if we select pn to be bisect the arc formed from the 2 points, then we've maximized dn . Now that dn has been chosen , we can continue this argument to prove that all the points must form a regular pentagon to maximize the lhs of the inequality .
Now use cosine law to prove that the sum of the squares of the sides cannot exceed 9r^2 .

Equality occurs when we have an equilateral triangle with sides of length sqrt3r .

[TomCowley]

Let ACE be the hardest set of vertices to cover. Now, the easiest way to cover these is to have two points on a line opposite the side of the triangle ACE with the largest angle. So the distance between the vertex with the largest angle and the opposite side will be 1. Now the shortest distance across the hexagon will be either AE, AC, or CE (since the sides are parallel). The shortest distance will be opposite the smallest angle in ACE, and by the definition of sine will be 1/sin(180-largest angle-angle).

Since the largest possible angle in ACE is approaching 90 degrees (can't be bigger in a standard no angle>180 hexagon), that leaves 90 degrees to divide among the smaller angles. So the largest possible smallest angle is approaching 45 degrees. So the value of 180-largest angle-angle will be approaching 45 from above. So the value of sin(180-largest angle-angle) will be approaching 1/sqrt(2) from above. So the value of 1/sin(180-largest angle-angle), which is our final answer, will be approaching sqrt(2) from below, so the upper bound of sqrt(2) is proven.

Edit: took the wrong complement, fixed.

[TomCowley]

I think you're forgetting that no distance can ever be greater than r, since all points are at most r from P_1. The hexagon gives 7r^2.

[jay_shark]

[ QUOTE ]
I think you're forgetting that no distance can ever be greater than r, since all points are at most r from P_1.

[/ QUOTE ]

P1 is center of the circle or circumference ?
I've heard of a point being a center or a hemisphere , but I've never heard of a point being the center of a circumference .

[TomCowley]

I assumed it was the center of the circle. I don't know what center of the circumference would even mean (it's on the circumference?). OP can clarify.

[TomCowley]

Ahh, the problem is a pain in the ass because it's actually <=7 (hexagon), but I guess it's really hard to prove that's optimal. Assuming that points are evenly spaced (tedious but not hard to show that non-evenly spaced points can never be optimal), we can treat this as a circle packing problem. Each circle will have radius R/n. Now, since the minicircles must be centered in the big circle, they can fill a maximum area of pi*(R+R/n)^2. Dividing areas of the circles means that there can be at most pi*(R+R/n)^2/(pi*(R/n)^2) = n^2 + 2n + 1 minicircles of radius R/n. Now the sum-of-squares metric that we're trying to compute states that we have at most n^2 + 2n +1 points at a distance of 2R/n apart, so the sum is at most (n^2 + 2n + 1)*4R^2/n^2 = 4R^2 (1 + 2/n + 1/n^2). Obviously the bigger n is, the smaller this expression is, so we want the minimum n. Since n<2 means there can only be one point (since we have a point at the middle of the circle, the center of the next minicircle would be outside the circle), which is trivially true, the smallest meaningful n is 2. Plugging that in gives 4R^2 (1 + 1 + 1/4) = 9r^2, which is an upper bound.

And, amazingly, the n=2 solution is the hexagon.

[thylacine]

[ QUOTE ]
Let ACE be the hardest set of vertices to cover. Now, the easiest way to cover these is to have two points on a line opposite the side of the triangle ACE with the largest angle. So the distance between the vertex with the largest angle and the opposite side will be 1. Now the shortest distance across the hexagon will be either AE, AC, or CE (since the sides are parallel). The shortest distance will be opposite the smallest angle in ACE, and by the definition of sine will be 1/sin(180-largest angle-angle).

Since the largest possible angle in ACE is approaching 90 degrees (can't be bigger in a standard no angle>180 hexagon), that leaves 90 degrees to divide among the smaller angles. So the largest possible smallest angle is approaching 45 degrees. So the value of 180-largest angle-angle will be approaching 45 from above. So the value of sin(180-largest angle-angle) will be approaching 1/sqrt(2) from above. So the value of 1/sin(180-largest angle-angle), which is our final answer, will be approaching sqrt(2) from below, so the upper bound of sqrt(2) is proven.

Edit: took the wrong complement, fixed.

[/ QUOTE ]

Good start. Actually AE, AC, CE (and BD, DF, FB) are upper bounds for hexagon width so you just need one being at most sqrt(2).

Also if ACE (or BDF) has no obtuse angle, I believe your argument does this case.

But you still have to the case where ACE and BDF both have an obtuse angle.

[jay_shark]

Tom , the sum of the squares of the sides of a hexagon inscribed in a circle of radius r is 6*r^2 .

An equilateral triangle works .

Let a be the side length of the equilateral inscribed in a circle of radius r .


a^2 = r^2+r^2-2*r^2cos120
a^2 = 3^r^2
a = r*sqrt3

So the sum of the squares is 9*r^2

--------------------------------------------------

The sum of the squares of the sides of a hexagon inscribed in a circle is 6*r^2 .

In general , the sum of the squares of the sides of a polygon should decrease as n increases .

[sirio11]

[ QUOTE ]
I think you're forgetting that no distance can ever be greater than r, since all points are at most r from P_1. The hexagon gives 7r^2.

[/ QUOTE ]

This is correct. P_1 is the center of the circle

[TomCowley]

You're forgetting the center point, which has distance r, so 6r^2 for the hexagon sides, + r^2 for the center point, =7r^2.

[jay_shark]

Right .

Good thing he cleared up that P1 is on the center of the circle .

[TomCowley]

Good catch. If ACE is obtuse, then it's tougher to cover ACF and/or BCF, where C/F are the obtuse angles, than it is to cover ACE, and the shortest distance across the hexagon is CF, not AC/CE/AE. Then the problem reduces to the parallelogram ACEF, and by similar analysis as for ACE in the other post, the CF distance is maximized to sqrt(2) as EFA reduces to 90 degrees from above.

[sirio11]

Tom, in my solution I used n mini circles with r_k = d_k / 2 and the big circle with R = (3/2)r.
So, A_k = pi (d_k^2/4) and using the areas:

pi (d_1^2/4)+pi (d_2^2/4)+......+pi (d_n^2/4) <= pi(9/4)r^2

Therefore d_1^2+d_2^2+......+d_n^2 <= 9r^2

And yes, my 1st thought was that the 9r^2 was way too high. It would be interesting to try to solve the problem for 7r^2, as soon as I have some time I'll try.

[sirio11]

[ QUOTE ]
Good catch. If ACE is obtuse, then it's tougher to cover ACF and/or BCF, where C/F are the obtuse angles, than it is to cover ACE, and the shortest distance across the hexagon is CF, not AC/CE/AE. Then the problem reduces to the parallelogram ACEF, and by similar analysis as for ACE in the other post, the CF distance is maximized to sqrt(2) as EFA reduces to 90 degrees from above.

[/ QUOTE ]

If ac,ce or ea is <= sqrt2 we're done; so wlog we assume ea >= ac>= ce> sqrt2
d(c,ae) <= 1 therefore angle ace must be > 90

Now, wlog let angle fce > 45, d(f,ce) = fc*sin(fce) >= sqrt2*sin45 > 1, similarly we obtain d(e,fc) > 1; therefore {a,c,e} can not be covered by a strip of width 1 contradicting the hypothesis.

[TomCowley]

Your solution for half-radius circles is the same as mine, but it doesn't explain why quarter-radius circles (or anything else) wouldn't be better.

[sirio11]

[ QUOTE ]
Your solution for half-radius circles is the same as mine, but it doesn't explain why quarter-radius circles (or anything else) wouldn't be better.

[/ QUOTE ]

You wrote:

[ QUOTE ]
Assuming that points are evenly spaced (tedious but not hard to show that non-evenly spaced points can never be optimal)

[/ QUOTE ]

My solution does not need this (and the tedious work to show it)

Explaining why quarter-radius (or anything else) wouldn't be better is quite trivial.

Edited to add: And probably you already meant that, but my solution is not about half-radius circles, using the d_k/2 as radius is quite different from R/2 and avoids several of the problems involved with using R/n. Not to mention the algebra is nicer, you don't need any limits .... /images/graemlins/smile.gif

[TomCowley]

Ahh, I see it now. I wan't reading your notation right. Nice.

[jay_shark]

I think we can do better for the first problem .
I conjecture that the lhs is <=7*r^2 .

Equality occurs when we have a regular hexagon inscribed in a circle .

[TomCowley]

I made the same observation. No clue how to prove it though.