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

2016-06-14, 19:50   #23
Batalov

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

3×43×73 Posts

Quote:
 Originally Posted by henryzz ...However, there needs to be a solution for [3,1,1,1,1] based upon the value for S(5).
You are retracing my steps :-)

Try to solve this particular sub-problem on the table using matchsticks (or Q-tips; 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!

 2016-06-16, 09:06 #24 henryzz 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).
 2016-06-16, 15:26 #25 henryzz 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.
 2016-06-16, 21:36 #26 WMHalsdorf     Feb 2005 Bristol, CT 33·19 Posts Wouldn't [2,1,2,1,1] for 5 sides produce the largest area since it is closest to a regular pentagon?
 2016-06-16, 23:35 #27 Batalov     "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
2016-06-17, 00:57   #28
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by science_man_88 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
you would think I would know a rhombus and a trapezoid aren't the same doh.

 2016-06-17, 20:57 #29 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 586910 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...iate-bisection 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.
 2016-09-04, 17:05 #30 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 223118 Posts Project Euler re-opened after the summer break with two related (moderate) problems: 567 and 568. Edit (September 10): pe 569 is also easy (brute force, run-time 40 minutes); but may be a bit harder to get run-time under 1 minute... Last fiddled with by Batalov on 2016-09-10 at 21:32
 2021-01-18, 14:27 #31 Blackadder     "Angelino Desmet" Mar 2018 Belgium 72 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.
2021-01-18, 14:31   #32
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

110318 Posts

Quote:
 Originally Posted by Blackadder 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.
They are pretty cool problems.
I did a couple hundred a dozen years ago.

 2021-01-19, 04:05 #33 LaurV Romulan Interpreter     Jun 2011 Thailand 25×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"...

 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 11:03.

Sat May 8 11:03:41 UTC 2021 up 30 days, 5:44, 0 users, load averages: 3.57, 3.32, 3.19