20160614, 19:50  #23  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×43×73 Posts 
Quote:
Try to solve this particular subproblem on the table using matchsticks (or Qtips; 4 "1/3"s and one "1")... and you will see what is going on! Only if completely stuck, watch this spoiler > the circle's center _[I]can[/I]_ be outside of the polygon, but the (maximal) polygon is still cyclic! 

20160616, 09:06  #24 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,869 Posts 
There are two sizes of angles the angles between sides of length 1 and the two angles between sides of length 1 and 3. All of the vertices are the opposite side of the longest line to the centre of the circle.
Not sure where to go from here. Need to check whether the only problem cases are the ones with a load of 1s and a longer side. If so it should be possible to work it out as a special case(calculate the distance between the endpoints of the curve generated from the sides of length 1 with certain angles and solve for the larger size). 
20160616, 15:26  #25 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,869 Posts 
I implemented the special case(one long side and a load of 1s). This wasn't enough. Now stuck with [6,2,1,1,1,1,1,1,1]. There has got to be something I am missing with my standard optimization. My standard optimization presumably assumes that the polygon is facing the other way around.

20160616, 21:36  #26 
Feb 2005
Bristol, CT
3^{3}·19 Posts 
Wouldn't [2,1,2,1,1] for 5 sides produce the largest area since it is closest to a regular pentagon?

20160616, 23:35  #27 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×43×73 Posts 
The reordering of sides doesn't matter  ...by a very simple argument

20160617, 00:57  #28  
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
Quote:


20160617, 20:57  #29 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5869_{10} Posts 
I found a paper which includes the method I have been using for solving the majority of cases. http://www.sciencedirect.com/science...22314X07001126
Unfortunately the formula is reliant on the centre of the circle being inside the polygon. I have not a clue how to go about cases such as [6,2,1,1,1,1,1,1,1] other than increasingly complex optimization problems. For one large side and a load of 1s I just needed to vary one angle until the length of the long side was correct. For more than one large side there are two angles to vary. This is possible but this solution is not necessarily unique which means it may not be maximal(if it converges given it is not unique). This means I am trying to maximize the area at the same time as solving for side length. http://mathoverflow.net/questions/35...iatebisection should hopefully give me the means to do this. Am I barking up the wrong tree here? Will I have to go beyond 2d optimization for future cases n<=50? I am hoping that there are few enough cases that speed won't be an issue. 
20160904, 17:05  #30 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22311_{8} Posts 
Project Euler reopened after the summer break with two related (moderate) problems: 567 and 568.
Edit (September 10): pe 569 is also easy (brute force, runtime 40 minutes); but may be a bit harder to get runtime under 1 minute... Last fiddled with by Batalov on 20160910 at 21:32 
20210118, 14:27  #31 
"Angelino Desmet"
Mar 2018
Belgium
7^{2} Posts 
I discovered Project Euler only recently and decided to take up programming again because of it. Have done the three first problems. This is cool.

20210118, 14:31  #32 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
11031_{8} Posts 

20210119, 04:05  #33 
Romulan Interpreter
Jun 2011
Thailand
2^{5}×5×59 Posts 
We also did few, at the time. As we remember, for some of them, you don't need a computer, you can just do them with a pencil on paper if you think a bit. On the other hand, some were difficult and we gave up, due to limited time, knowledge, and "guts"...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Project Euler 486  lavalamp  Puzzles  8  20150204 14:28 
Project Euler #372  lavalamp  Puzzles  165  20120524 16:40 
Euler (6,2,5) details.  Death  Math  10  20110803 13:49 
Project Euler  MiniGeek  Lounge  2  20091023 17:19 
Bernoulli and Euler numbers (Sam Wagstaff project)  fivemack  Factoring  4  20080224 00:39 