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

 2012-06-02, 04:31 #1 jhs   Jun 2012 110 Posts 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.
 2012-06-03, 05:06 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2012-06-03, 10:57 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100101011002 Posts 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.
 2012-06-03, 20:30 #4 J.F.     Jun 2008 23×32 Posts 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...
 2012-06-03, 20:42 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×2,347 Posts 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.
 2012-09-01, 22:02 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×2,347 Posts PE 392 is the first one after the summer break! (already solved by 46)
2012-09-08, 16:10   #7
Batalov

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

22×2,347 Posts

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

 2012-09-09, 17:46 #8 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 3×1,951 Posts 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?
 2012-09-10, 13:01 #9 Volrac   Sep 2012 210 Posts 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} 1 & -1 & 1 & -1 & \\ -1 & 1 & -1 & 1 & \\ 1 & -1 & 1 & -1 & \\ -1 & 1 & -1 & 1 & \\ 1 & -1 & 1 & -1 & \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.
 2012-09-11, 13:43 #10 LaurV Romulan Interpreter     Jun 2011 Thailand 33·347 Posts Your matrix is 4x5 (for which there are solutions). But we got the idea. This problem seems not complicate to be solved recursively.
 2012-09-11, 14:03 #11 Volrac   Sep 2012 210 Posts 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.

 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 16:55.

Mon Apr 12 16:55:03 UTC 2021 up 4 days, 11:35, 1 user, load averages: 2.70, 2.18, 2.12