mersenneforum.org Project Euler
 Register FAQ Search Today's Posts Mark Forums Read

 2012-09-11, 21:36 #12 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts Would the solution not come from how to place n*n ants onto the number of crossable borders ? It appears the number of crossable borders is $2\sum_{i=1}^{n-1}i$ and yes I have a chessboard in front of me right now. edit: I realize now that no it's not that simple because you can't have 2 ants going in any direction from one box, so an amount of borders greater than 2 can't have ants on all of them. just realized the multiplier is 4 not 2. so the crossable borders is : $4\sum_{i=1}^{n-1}i$ Last fiddled with by science_man_88 on 2012-09-11 at 21:54
2013-11-16, 19:19   #13
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×797 Posts
Problems 445-447

Quote:
 Recent News Saturday 09 November 2013: Multiple release Saturday, November 16th, 10 pm server time we will release three problems simultaneously. The difficulty of those three problems will range from easy to hard. The problems will be centered around the same theme so they are related, whence the simultaneous release in one hard slot. Happy solving!
This is @ 2PM Pacific, 5PM Eastern time. (Not one of those brutal 2AM times.)

Last fiddled with by Batalov on 2013-11-16 at 19:41 Reason: server time is an obscure rendez-vous

 2014-06-15, 22:45 #14 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×3×797 Posts Project Euler was compromised Ouch! Attached Thumbnails
 2014-08-17, 08:07 #15 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100101010111002 Posts Project Euler is now restored (almost) fully.
 2016-06-12, 21:08 #16 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100101010111002 Posts PE 564 is rather nice...
2016-06-13, 09:10   #17
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

61×97 Posts

Quote:
 Originally Posted by Batalov PE 564 is rather nice...
Tough. Struggling to find a formula for working out the maximal area of a convex polygon given the length of all the sides. Can find a formula given the coordinates.
We know the sum of the interior angles. Am thinking that it may be possible to work out a possible set of coordinates for an odd number of sides by dividing up the angles according to the length of the opposite side. Not certain this would be maximal or even whether the area would change based upon the angles. Not sure how to extend this to even number of sides.

Found this which answers some of my questions. It looks like the formula for the area of a cyclic polygon is $\prod_{i=1}^{n}\sqrt{(\sum_{j=1}^{n}s_j/2) - s_i}$
The order of the sides doesn't matter.
Next problem is finding the maximal partition into side lengths.

2016-06-13, 12:20   #18
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

61×97 Posts

Quote:
 Originally Posted by henryzz Tough. Struggling to find a formula for working out the maximal area of a convex polygon given the length of all the sides. Can find a formula given the coordinates. We know the sum of the interior angles. Am thinking that it may be possible to work out a possible set of coordinates for an odd number of sides by dividing up the angles according to the length of the opposite side. Not certain this would be maximal or even whether the area would change based upon the angles. Not sure how to extend this to even number of sides. Found this which answers some of my questions. It looks like the formula for the area of a cyclic polygon is $\prod_{i=1}^{n}\sqrt{(\sum_{j=1}^{n}s_j/2) - s_i}$ The order of the sides doesn't matter. Next problem is finding the maximal partition into side lengths.
That formula is wrong. Still looking for a general formula.

2016-06-13, 12:52   #19
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by henryzz That formula is wrong. Still looking for a general formula.
why not something along the lines of:

$\sum_{i=1}^{sides} 1/2*(R_i*L_i)$

where R is the radius to a flat side and L is the length of that side this generates:

N/2*R*L for a regular N-gon

edit: okay technically this doesn't tell you the maximum but you have to start somewhere to get what's needed. these formulae can give area.

Last fiddled with by science_man_88 on 2016-06-13 at 13:06

2016-06-13, 17:20   #20
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·3·797 Posts

Quote:
 Originally Posted by henryzz That formula is wrong. Still looking for a general formula.
There is a general formula, but it only happens to lead to the semiperimeter formula for n=3 and n=4 only.
Interestingly, there was a researcher who produced the explicit formulae for n up to 8, but they are not useful for this PE problem.
Even more intriguingly, the formulae come in pairs (odd and next even n), so the fact that cases 3<=n<=4 look similar is not coincidental!

The initial realization about the polygons being [B]cyclic[/B] is a very good start.

 2016-06-14, 14:28 #21 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 171D16 Posts Needed to use bisection rather than Newton's method as it would sometimes diverge. Having trouble with the polygon with sides of length [3,1,1,1,1]. There doesn't seem to be a valid radius for this polygon. [2,1,1,1] is a bit of a nuisance as well due to it having a radius of 1 which is the minimum possible radius. I am beginning to think that I might need restrictions on which polygons are possible. However, there needs to be a solution for [3,1,1,1,1] based upon the value for S(5). I suspect that it must be impossible for the points to all be on the circle but a maximal polygon is possible. Not a clue how to find the area of that maximal polygon currently.
2016-06-14, 15:46   #22
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by henryzz Needed to use bisection rather than Newton's method as it would sometimes diverge. Having trouble with the polygon with sides of length [3,1,1,1,1]. There doesn't seem to be a valid radius for this polygon. [2,1,1,1] is a bit of a nuisance as well due to it having a radius of 1 which is the minimum possible radius. I am beginning to think that I might need restrictions on which polygons are possible. However, there needs to be a solution for [3,1,1,1,1] based upon the value for S(5). I suspect that it must be impossible for the points to all be on the circle but a maximal polygon is possible. Not a clue how to find the area of that maximal polygon currently.
as someone who tried to knit a regular pentagon my first thought turns to tan functions of the outer angles or at least saying okay the other side is 3 the rest of them total 4 what average angle can I have. If half go in and got connected together of the 1 segments it's like a 2,2,3 triangle but we want 5 true sides for [2,1,1,1] the first shape I can think of is a rhombus /__\ the outer segments being tilted to be roughly cos(theta)=1/2

 Similar Threads Thread Thread Starter Forum Replies Last Post lavalamp Puzzles 8 2015-02-04 14:28 lavalamp Puzzles 165 2012-05-24 16:40 Death Math 10 2011-08-03 13:49 Mini-Geek Lounge 2 2009-10-23 17:19 fivemack Factoring 4 2008-02-24 00:39

All times are UTC. The time now is 08:24.

Wed Oct 20 08:24:17 UTC 2021 up 89 days, 2:53, 0 users, load averages: 3.05, 3.21, 2.94