mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-06-14, 19:50   #23
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×43×73 Posts
Arrow

Quote:
Originally Posted by henryzz View Post
...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!
Batalov is offline   Reply With Quote
Old 2016-06-16, 09:06   #24
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,869 Posts
Default

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).
henryzz is online now   Reply With Quote
Old 2016-06-16, 15:26   #25
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,869 Posts
Default

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.
henryzz is online now   Reply With Quote
Old 2016-06-16, 21:36   #26
WMHalsdorf
 
WMHalsdorf's Avatar
 
Feb 2005
Bristol, CT

33·19 Posts
Default

Wouldn't [2,1,2,1,1] for 5 sides produce the largest area since it is closest to a regular pentagon?
WMHalsdorf is offline   Reply With Quote
Old 2016-06-16, 23:35   #27
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×43×73 Posts
Default

The reordering of sides doesn't matter - ...by a very simple argument
Batalov is offline   Reply With Quote
Old 2016-06-17, 00:57   #28
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-06-17, 20:57   #29
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

586910 Posts
Default

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.
henryzz is online now   Reply With Quote
Old 2016-09-04, 17:05   #30
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

223118 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2021-01-18, 14:27   #31
Blackadder
 
Blackadder's Avatar
 
"Angelino Desmet"
Mar 2018
Belgium

72 Posts
Default

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.
Blackadder is offline   Reply With Quote
Old 2021-01-18, 14:31   #32
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

110318 Posts
Default

Quote:
Originally Posted by Blackadder View Post
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.
petrw1 is offline   Reply With Quote
Old 2021-01-19, 04:05   #33
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25×5×59 Posts
Default

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"...
LaurV is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.