Project Euler
 

Hi

I find 384 to be a tough one. In the sense that I get a system overflow error when I create an array to store the s(n) values. Can anyone suggest a better approach?

Thanks.

Round these parts, you're [URL="http://www.mersenneforum.org/showthread.php?p=301094#post301094"]not likely[/URL] to get an answer for such a question. You might get an answer if you post what you think might be a viable alternative. (I'd help you myself, but I'm not yet up to snuff on such mathematical things.)

The worst challenge for 387 was to wait until 3am for it to show up and then hack something fast with eyes already shutting involuntarily.

#39, even then.

Believe it or not, I made the #1 spot years ago on (back then) mathschallenge.net. Then, there were only ~110 problems and I could handle the competition at a particular problem, probably because they were all asleep like you Batalov ;). Now the competition is much much heavier and I'm afraid this new #1 badge is out of my league...

They cleverly shift the posting times (and they should - to level the playing field; fair is fair). Too bad that sometimes (not this time) their site freezes after (or even before?) posting.

PE 392 is the first one after the summer break!
(already solved by 46)

Was anyone able to screenshot the formulation of PE 393?
(the site is down, the users are down :down:)

EDIT: there are signs of life: an empty page with the project banners came up... reloading... there it is.
[quotE]An n x n grid of squares contains n[SUP]2 [/SUP] ants, one ant per square.

All ants decide to move simultaneously to an adjacent square (usually 4 possibilities, except for ants on the edge of the grid or at the corners).
We define f(n) to be the number of ways this can happen without any ants ending on the same square and without any two ants crossing the same edge between two squares.

You are given that f(4) = 88.

Find f(10).[/quotE]

For my solutions I find it easiest to think in loops multiplying by 2^n to account for direction with n being the number of loops.

2x2 has 2 solutions. Both effectively a loop with 2 directions.
2x3 has 2 solutions. Both are again loops around the outside with 2 directions.
2x4 can be:
(1 2x4 loop) *2 because of 2 directions.
(2 2x2 loops) * 4 because of 2 directions.
2x4 has 6 solutions total.
3x3 is impossible.
3x4 can be:
(2 2x3 loops) *4 because of direction of movement
(1 loop, 2 2x3 loops joined at one end) *4 because of 2 sides and 2 directions
3x4 has 8 solutions total.
4x4 can be:
(4 2x2 loops) *2^4=16 because of 4 loops each having 2 directions
(3 loops, a 2x4 loop on one side and 2 2x2 loops) * 32 because of 4 arrangements
(2 2x4 loops) *8 because of 2 directions and 2 arrangements.
(2 loops, 1 around the outside of the 4x4 and 1 2x2 loop in the centre) * 4 because of 2 directions
(2 loops, a 2x2 in a corner and a L shaped loop) *16 because of 4 arrangements and 2 directions.
(1 loop, 2 2x4 loops joined at one end forming a U) *8 because of 4 arrangements and 2 directions.
(1 loop, 2 2x4 loops joined in the middle forming a H) * 4 because of 2 arrangements and 2 directions.
It is possible to divide the 4x4 into 2 2x4s and use that for 56 of the solutions but you get 16 extra solutions because of duplicates when the 2x4s are reduced to 2x2 loops.
16+32+8+4+16+8+4=88 solutions total.

3x3 is certainly impossible as it forms an unbreakable chain around the outside. Is any area with an odd number of squares impossible? Can anyone prove it?

Hai i just dropped in, had troubles with this one as well, still have. But i couldnt leave this page without giving some proof.

For the an informal proof of the above: a grid graph is bipartite, since we can split up diagonals.
Look at this 5x5 graph to tell a bit why

[TEX]\begin{bmatrix}
1 & -1 & 1 & -1 & \\
-1 & 1 & -1 & 1 & \\
1 & -1 & 1 & -1 & \\
-1 & 1 & -1 & 1 & \\
1 & -1 & 1 & -1 &
\end{bmatrix}[/TEX]

If we want to make cycles in this, every 1 needs to go to a -1 and every -1 to a 1. So if we start a cycle in a 1, then closing a loop always takes an even amount of turns. same for cycles starting at a -1 square.

What can we say about this, well if both sides are uneven, we can do two things:
1) make a cycle that fills the whole grid, but this isnt possible, since a cycle needs to have an even amount of squares

2) make a small cycle inside it and then move on making more cycles with the remaining squares. But since cycles are always even, we get that the remaining squares are still uneven. So if we keep doing this for a certain amount of times. we can never get the uneven part filled with a full cycle since cycles must be even.

So thereby a square having 2 unequal sides gives 0 as outcome. And also to make it more general, its for every unequal numbered grid.

But yea i now have a method to calculate f(6), but i dont really get it fast enough for f(8) and f(10) those numbers will be huge.

Your matrix is 4x5 (for which there are solutions). But we got the idea. This problem seems not complicate to be solved recursively.

Oh yea oops, 4x5 indeed, but yea its about the idea of the proof ;D. And I have a recursive algorithm, but it already takes a few minutes for f(6). I guess i just missed something crucial in my algorithm. Have tried other methods, but no success in those at all.

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 [TEX]2\sum_{i=1}^{n-1}i[/TEX] 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 : [TEX]4\sum_{i=1}^{n-1}i[/TEX]

Problems 445-447
 

[QUOTE][URL="http://projecteuler.net/problems"]Recent News[/URL][B]

Saturday 09 November 2013: Multiple release[/B]

Saturday, November 16th, 10 pm server time we will release [U]three problems simultaneously[/U].
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![/QUOTE]
This is @ 2PM Pacific, 5PM Eastern time. (Not one of those brutal 2AM times.)

Project Euler was compromised
 

Ouch!

[URL="http://projecteuler.net/news"]Project Euler[/URL] is now restored (almost) fully.

[URL="https://projecteuler.net/problem=564"]PE 564[/URL] is rather nice...

[QUOTE=Batalov;436105][URL="https://projecteuler.net/problem=564"]PE 564[/URL] is rather nice...[/QUOTE]

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 [URL="http://www.drking.org.uk/hexagons/misc/polymax.html"]this [/URL]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.

[QUOTE=henryzz;436129]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 [URL="http://www.drking.org.uk/hexagons/misc/polymax.html"]this [/URL]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.[/QUOTE]

That formula is wrong. Still looking for a general formula.

[QUOTE=henryzz;436135]That formula is wrong. Still looking for a general formula.[/QUOTE]

why not something along the lines of:

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


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.

[QUOTE=henryzz;436135]That formula is wrong. Still looking for a general formula.[/QUOTE]
There is a general formula, [SPOILER]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![/SPOILER]

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

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.

[QUOTE=henryzz;436211]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.[/QUOTE]

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

[QUOTE=henryzz;436211]...However, there needs to be a solution for [3,1,1,1,1] based upon the value for S(5). [/QUOTE]
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 --> [SPOILER]the circle's center _[I]can[/I]_ be outside of the polygon, but the (maximal) polygon is still cyclic![/SPOILER]

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

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.

Wouldn't [2,1,2,1,1] for 5 sides produce the largest area since it is closest to a regular pentagon?

The reordering of sides doesn't matter [SPOILER]- ...by a very simple argument[/SPOILER]

[QUOTE=science_man_88;436219]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[/QUOTE]

you would think I would know a rhombus and a trapezoid aren't the same doh.

I found a paper which includes the method I have been using for solving the majority of cases. [URL]http://www.sciencedirect.com/science/article/pii/S0022314X07001126[/URL]
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.
[URL]http://mathoverflow.net/questions/35987/multivariate-bisection[/URL] 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.

[URL="https://projecteuler.net/news"]Project Euler re-opened[/URL] 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...

I discovered [I]Project Euler[/I] only recently and decided to take up programming again because of it. Have done the three first problems. This is cool.

[QUOTE=Blackadder;569593]I discovered [I]Project Euler[/I] only recently and decided to take up programming again because of it. Have done the three first problems. This is cool.[/QUOTE]

They are pretty cool problems.
I did a couple hundred a dozen years ago.

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"... :smile: