Project Euler - Page 2

science_man_88 · 2012-09-11, 21:36

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$

Batalov · 2013-11-16, 19:19

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.)

Batalov · 2014-06-15, 22:45

Ouch!

Batalov · 2014-08-17, 08:07

Project Euler is now restored (almost) fully.

Batalov · 2016-06-12, 21:08

PE 564 is rather nice...

henryzz · 2016-06-13, 09:10

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.

henryzz · 2016-06-13, 12:20

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.

science_man_88 · 2016-06-13, 12:52

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.

Batalov · 2016-06-13, 17:20

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.

henryzz · 2016-06-14, 14:28

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.

science_man_88 · 2016-06-14, 15:46

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

2012-09-11, 21:36	#12
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	Would the solution not come from how to place nn 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*

2014-06-15, 22:45	#14
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	Project Euler was compromised Ouch! Attached Thumbnails

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Project Euler 486	lavalamp	Puzzles	8	2015-02-04 14:28
Project Euler #372	lavalamp	Puzzles	165	2012-05-24 16:40
Euler (6,2,5) details.	Death	Math	10	2011-08-03 13:49
Project Euler	Mini-Geek	Lounge	2	2009-10-23 17:19
Bernoulli and Euler numbers (Sam Wagstaff project)	fivemack	Factoring	4	2008-02-24 00:39

2014-08-17, 08:07	#15
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	Project Euler is now restored (almost) fully.

2016-06-12, 21:08	#16
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2505₁₆ Posts	PE 564 is rather nice...

2016-06-14, 14:28	#21
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 1011011111000₂ 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.