mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2012-06-02, 04:31   #1
jhs
 
Jun 2012

12 Posts
Default 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.
jhs is offline   Reply With Quote
Old 2012-06-03, 05:06   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Round these parts, you're not likely 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.)
Dubslow is offline   Reply With Quote
Old 2012-06-03, 10:57   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100011101002 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2012-06-03, 20:30   #4
J.F.
 
J.F.'s Avatar
 
Jun 2008

23·32 Posts
Default

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...
J.F. is offline   Reply With Quote
Old 2012-06-03, 20:42   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,333 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2012-09-01, 22:02   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

247416 Posts
Default

PE 392 is the first one after the summer break!
(already solved by 46)
Batalov is offline   Reply With Quote
Old 2012-09-08, 16:10   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,333 Posts
Default

Was anyone able to screenshot the formulation of PE 393?
(the site is down, the users are 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 n2 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).

Last fiddled with by Batalov on 2012-09-08 at 16:36
Batalov is offline   Reply With Quote
Old 2012-09-09, 17:46   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

132758 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2012-09-10, 13:01   #9
Volrac
 
Sep 2012

2 Posts
Default

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

\begin{bmatrix}<br />
1 & -1 & 1 & -1 & \\ <br />
-1 & 1 & -1 & 1 & \\ <br />
1 & -1 & 1 & -1 & \\ <br />
-1 & 1 & -1 & 1 & \\ <br />
1 & -1 & 1 & -1 & <br />
\end{bmatrix}

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.
Volrac is offline   Reply With Quote
Old 2012-09-11, 13:43   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×7×53 Posts
Default

Your matrix is 4x5 (for which there are solutions). But we got the idea. This problem seems not complicate to be solved recursively.
LaurV is offline   Reply With Quote
Old 2012-09-11, 14:03   #11
Volrac
 
Sep 2012

2 Posts
Default

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.
Volrac 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 02:24.

Sat Mar 6 02:24:19 UTC 2021 up 92 days, 22:35, 0 users, load averages: 2.03, 2.05, 1.65

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.