Problem 393

[jmjoebar]

http://projecteuler.net/problem=393

this one is really challenging... as a brute force approach will take ages ! I strongly congratulate those who managed to solve it so rapidly.

[hk]

@ jmjoebar:
Please restrict yourself to meaningful posts.
Messages like the above probably fit in a tweet and could be better placed on Twitter.

[jmjoebar]

Sorry for that hk.

Let's try to be more constructive. I have an aglo written in Python that gives a quick answer for f(2) (trivial case=2), and f(4) as in the descriptoin f(4)=88.
However, it's damn too slow for having a result on f(10) within a minute.
Even f(6) takes couple of minutes... [I understand I shall not post my result for f(6) as it can be considered as a partial answer !]
So I think there is a more clever approach than brute force search. Can anybody confirm ?

JM

[hk]

@ jmjoebar:
Yes there is. Happy now?
In case you are phishing for that approach: this forum is not meant to discuss solution methods, and moreover it is moderated.
This forum is meant to give clarifications in case the wording of a problem isn't understood. It seems to me that you perfectly well understand the wording.
So could you please stop it now?

[mctrafik]

So f(3) = 0 because there's nowhere the center ant can move. Am I correct?

[unime]

So f(3) = 0 because there's nowhere the center ant can move.

Not precisely. All ants, including the center and, must move to an adjacent square.

The question is whether they can do so while meeting the conditions (no two end up in the same square, no crossing the same edge), and if so how many times. n=3 is small enough to brute force if you need to.

[mdean]

I think I see a way to show that f(3)=0 as well as a stronger statement, but I don't know what, if anything, it might give away.

[thundre]

I think I see a way to show that f(3)=0 as well as a stronger statement, but I don't know what, if anything, it might give away.

Having solved the problem, I will say that a proof that f(n)=0 for odd n has nothing to do with the problem of calculating it for even n.

[mdean]

All right, I'll take your word for it. If worse comes to worse, I can delete it later.

Start with any square. The ant from that square moves to an adjacent square. Another ant moves from that adjacent square to a third square. Due to the constraints of the problem, at some point this path needs to lead back to the original square to form a cycle (there are a finite number of squares and every other square in this path is already the destination square of one ant). Every time the path moves down, it must eventually move back up the same number of squares. Similarly with left and right. Therefore, the size of this cycle must be even.

So if n is odd, it is impossible for each of $n^2$ squares to be part of exactly one even cycle as each cycle contains an even number of squares so the total number of squares in such cycles is even while $n^2$ is odd. The conclusion follows that for odd n, f(n)=0.

[kevinsogo]

Another proof for odd n: Color the squares with black and white like a checkerboard. An ant in black goes to white, and an ant in white goes to black. Since number of black cells != number of white cells, it's impossible.

[lucaswerkmeister]

Is it allowed if I ask anyone who already solved the problem if he/she would verify my result for f(6)? I want to make sure my algorithm is right before spending hours of computation time on it (unless I find some clever shortcut).

[Marcus_Andrews]

Feel free to PM me and I'll let you know if your result is right or not.