10885 - Martin the Gardener

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Aug 20, 2005 8:31 pm

The points are on the same circle. But your approach is not the way to go.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Sat Aug 20, 2005 10:01 pm

Cho wrote:The points are on the same circle. But your approach is not the way to go.
Any hints?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Aug 21, 2005 4:52 am

I got the idea from misof's second reference. You don't need to understand the paper completely. From the middle of the second page to the end of the second page is enough for solving this problem. i.e. just half a page.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

..?

Post by wook » Sun Aug 21, 2005 3:53 pm

i think that misof's papper is TOO DIFFICULT to understand

and that i don't need it (because i can't make an understanding :) )


my idea is following :

1. all points are on a circle.
2. if coords are rational, multiplying appropriate large number, we can make them integer.
3. we can express some distances between two points on a circle with an arbitrary angle.
Sorry For My Poor English.. :)

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Sun Aug 21, 2005 8:55 pm

Thanks 2 all!

I got AC.

I used idea of Maehara's proof (linked by misof), just
like Cho advised :)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 21, 2005 11:30 pm

There's really a much simpler solution than that described in misof's reference. Here's my method:

First, I'm looking for points with rational coordinates and rational distances between any two of them, of the form:
(x_i, y_i) = (cos t_i, sin t_i), for i=1..13 (i.e. all points are lying on the unit circle.)

The distance between the i-th and j-th points is given by (after trig simplifications):
2 sin(t_i/2) cos(t_j/2) - 2 cos(t_i/2) sin(t_j/2).
Now, if I demand that all sin(t_i/2), cos(t_i/2) are rationals, then all distances and coordinates will become rational, too.

Let sin(t_i/2)=p_i/q_i (for p_i,q_i \in Z.) Then cos(t_i/2)=sqrt(q_i^2 - p_i^2)/q_i.
For cos(t_i/2) to be rational, q_i^2 - p_i^2 must be a square.
The integers p_i, q_i can be found by checking first few pythagorean triples.
The coordinates then can be easily computed by trig formulas.

To get integer coordinates and distances, I multiply each x_i, y_i by the lcm of denominators of all x_i, y_i, and then shift all points such that all coordinates become non-negative.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Aug 26, 2005 1:09 am

Many thanks, mf.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Aug 26, 2005 11:54 am

I just realized, I outputted negative numbers and the special corrector program still accepts this.

Is this a bug? :o
Well, not much of a bug anyways.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Aug 29, 2005 6:03 pm

Well according to the previous posts "The points are on the same circle".

Therefore the circle is
(x-2)^2 + (y-3/2)^2 = (5/2)^2

But i haven't realized how that is possible because there aren

Post Reply

Return to “Volume 108 (10800-10899)”