10402 - Triangle Covering

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

Moderator: Board moderators

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

10402 - Triangle Covering

Post by Ivan Golubev » Tue Nov 05, 2002 5:05 pm

I'm just puzzled with this problem, mainly with case T4.
Image
In my computations if P1 (and P2) is a point of intersections of three lines (for short, PITL) then constant == 2.312677596894 and P3 is not a PITL, otherwise if P3 is PITL then P1 and p2 cannot be PITL and constant == 2.3094010767585.

Looks like that second constant is closer to sample output but in this case how about "b) When three or more lines appear coincident they are actually coincident"?

Am I wrong or something else wrong?

Saiful Karim
New poster
Posts: 3
Joined: Mon May 06, 2002 7:38 pm

I don't know what's the problem also!!!

Post by Saiful Karim » Tue Nov 05, 2002 9:47 pm

I also faced the same problem & sending the two versions for T4 got
WA :( can any one help please?

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Tue Nov 05, 2002 11:30 pm

hello guys.

from the symmetry, we can deduce that P3 is the mid-point. now, let A and B be the end-points of the line of P3. so we have,

AP3 = r / sin(60 deg) ==> where r is the side of the squares

thus, AB = 2 * r / sin(60 deg)

hope i am correct, and hope this helps.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Wed Nov 06, 2002 4:55 pm

Adil wrote:thus, AB = 2 * r / sin(60 deg)
This is trivial, don't you think that 2.3094010767585 == 2 / sin(60) ? The problem in this case that points P1 & P2 won't be at the triangle border (at least, in my computations, may be I'm wrong but I don't think so).

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Thu Nov 07, 2002 1:49 am

hello there.

i think P1 and P2 are PITL. might it be that the middle square doesn't intersect the lower two squares on the border of the triangle? but in that case, the problem statement is partially-wrong i guess. :-?

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Sun Nov 10, 2002 8:57 am

In my opinion, p3 should be on the bottom side of the triangle, or the triangle will not be the largest. And p1 and p2 are not on the side of the triangle. But i got WA.
Wenyuan Dai, Shanghai Jiaotong University.

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

ATTN : PROBLEMSETTER

Post by Mahbub » Sun Nov 10, 2002 3:04 pm

There is no doubt that t4 = s*4/sqrt(3)...Becoz it is written by the

dicoverer of the problem!
The result for t2 is s* (4*root(6) - 6*root(2)) which is also as stated by

David Candrell...

So the prob is for t3 and t6..where he stated that t3 = 2.108+ and t6 =

3.168+..which do not hav analytic solutions. (He didnt wrote the equation

either...:(..).

But i was very hopeful when i succeeded to construct equations which

have the following results as constant :

2.1088402140624
3.1688842013610

which are both in agree with his approximate result. I think that its very

unlikely to get an erroneous equation and derive constants that are so

close to actual ones..Furthermore i didnt use any complex symmetry

property or something that i have doubt in.

So my opnion is that "THE PROBLEMSETTER NEEDS TO RECHECK HIS

SOLUTION AND THE PROBLEM DESCRIPTION"

Thanks
Light

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

ATTN : PROBLEMSETTER 10402 (TRIANGLE COVERING)

Post by Mahbub » Sun Nov 10, 2002 3:07 pm

There is no doubt that t4 = s*4/sqrt(3)...Becoz it is written by the

dicoverer of the problem!
The result for t2 is s* (4*root(6) - 6*root(2)) which is also as stated by

David Candrell...

So the prob is for t3 and t6..where he stated that t3 = 2.108+ and t6 =

3.168+..which do not hav analytic solutions. (He didnt wrote the equation

either...:(..).

But i was very hopeful when i succeeded to construct equations which

have the following results as constant :

2.1088402140624
3.1688842013610

which are both in agree with his approximate result. I think that its very

unlikely to get an erroneous equation and derive constants that are so

close to actual ones..Furthermore i didnt use any complex symmetry

property or something that i have doubt in.

So my opnion is that "THE PROBLEMSETTER NEEDS TO RECHECK HIS

SOLUTION AND THE PROBLEM DESCRIPTION"

Thanks
Light

hzickner
New poster
Posts: 1
Joined: Mon May 19, 2003 10:34 am

Re: ATTN : PROBLEMSETTER

Post by hzickner » Mon May 19, 2003 10:49 am

Mahbub wrote: But i was very hopeful when i succeeded to construct equations which

have the following results as constant :

2.1088402140624
3.1688842013610

Light
I found the same constants but got WA too. I have an analytic solution for T3, but needs a whole sheet of paper. for T6 I have only the numerical approximation (100 digits computed with MuPad). There must be something wrong with the correction software.

Holger

Cletus
New poster
Posts: 11
Joined: Tue May 13, 2003 5:15 am
Location: Up a tree, hatless.

Judge just plain wrong

Post by Cletus » Fri May 30, 2003 9:03 pm

"There is no doubt that ...Becoz it is written by the
dicoverer of the problem!"

Code: Select all


After many years of reading academic papers, I would not
take that as very strong evidence.

But in this case, it is undoubtedly right. I have come up with
exactly the same analytic results for t2 and t4, and exactly
the same numbers fot t2, t3, t4, and t6, by numeric methods,
to 14 or 15 digits of accuracy. We can not all have got the 
same numbers and got them wrong. I've done this with 
double self checking code to make sure all the intersections 
really are exact, and they are.

Except of course for the one at the bottom of the construction
for T4. If t4=4.0/sqrt(3.0), which it is, it is absolutely
impossible for the intersection of the two lowest squares to 
coincide with the base of the triangle. 

In fact, regardless of the value of t4 it is still impossible. 
If  those two squares met on the base of the triangle, we'd 
have a right-angled triangle with angles 30 and 60 degrees, 
one side = s, and the hypotenuse = t/2, giving t=2/cos(30).
   A similar but slightly less trivial construction on the left 
edge of the triangle gives t=(1+cos(15)+tan(15))/cos(15)
   Those two formulas are just not the same.

The two bottom squares of T4 must intersect approximately
0.00123 units of distance below the mid-point of the base of
the triangle.

So we have both a wrong problem description and a wrong
judge. We really have been honoured.


Zaheed
New poster
Posts: 6
Joined: Mon Jul 28, 2003 5:30 pm

10402

Post by Zaheed » Tue Sep 02, 2003 12:58 am

ohh my god... i've made it... :)

i've always been fond of geometrical problems... but this one is undoubtedly the best one i ever came across... it took me almost 3 hours to get accepted but at the end i was about to give up & it was my last attempt that reflected green...

after putting up so much effort when i got W/A i was really frustrated & for a moment i even thought the problemsetter must be some stupid person & he might have written a wrong solution cause i was really confident that my solution was correct... but you know we shouldn't think this way, its really unfair of us (or may be just me) to think this way... we should understand that this people (the genius problemsetters) really work hard to make it error-free & there is very little chance that their solution is incorrect... anyway, i could point out my mistake & now the corrected submission has been happiliy accepted my the judge... :D

i must admit shahriar manzoor is a real genius... plz DONT think therez anything wrong in this problem... it was a really nice problem.. & also i liked his problem, Flowers of a beautiful mind prob # 10540... it took me approx 36 mins to solve that in the last online contest... i was the one to solve it 1st but may be thats because i attempted it 1st... :D anyway, this kind of geometrical problems are really nice... i'm a newbie programmer & i'm yet to know all of those 1000 types of algoz properly :o so this kind of algo-free probs are really helpful... i don't mean algoz are bad cause those are also nice & i really find it interesting to learn new algoz every now n then but i need some more time to complete digesting all of the most commonly used algoz...

a friend of mine once told me the stuffs that are to be learned keeps on growing exponentially but we can only learn linearly... :( but still we don't give up & i guess thats where our real strength lies... :)

anyways... its really nice to solve a problem that stayed unsolved for quite some time... thanks to everyone for waiting for me to solve it first... :D


Sabur Zaheed (AIUB)
Last edited by Zaheed on Thu Sep 04, 2003 1:24 pm, edited 1 time in total.

Zaheed
New poster
Posts: 6
Joined: Mon Jul 28, 2003 5:30 pm

Post by Zaheed » Tue Sep 02, 2003 1:01 am

both the problem desrciption & its solution is quite ok!

regards

Sabur Zaheed

Zaheed
New poster
Posts: 6
Joined: Mon Jul 28, 2003 5:30 pm

Post by Zaheed » Tue Sep 02, 2003 1:05 am

Last edited by Zaheed on Sat Sep 06, 2003 11:25 am, edited 1 time in total.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Tue Sep 02, 2003 1:24 pm

Zaheed, the only reason of your accepted result is that you've been enough lucky to make the same mistake as the author of judge's test input/output. Nothing else.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm

Post by shahriar_manzoor » Tue Sep 02, 2003 2:03 pm

I myself also believe that this problem is wrong as I interpreted a figure wrongly. But somehow I don't find enough free time to fix this problem (may be reluctent to think down the same line again)

Post Reply

Return to “Volume 104 (10400-10499)”