# Optimal number of moves in "magnetism" puzzle? [duplicate]

Once, I saw a puzzle on Puzzlopia (now a Chinese website, just put a .com in the bold text). I call this "Magnetism", where the board and rules are:

(recreation)

## Rules:

1) There is an electron (denoted by a negative sign) at the most bottom-left, and a proton (denoted by a positive sign) at the most top-right.
2) They split such that the electron splits one step north and east, and the proton splits one step south and west. (diagram above)
3) They can only split if they are not blocked by the same particle in either direction.
4) When a particle splits and it meets its opposite particle, they are destroyed.
5) Destroy every particle to win.

What is the optimal number of moves for this board? (which is $$8\times8$$)

• Numberphile has a video on this topic. You may want to go and have a look youtube.com/watch?v=lFQGSGsXbXE&t=183s Feb 22, 2020 at 6:39
• @AniketGupta Interesting topic, but I think it doesn't answer the question? Feb 22, 2020 at 15:07

## 1 Answer

Many thanks to Amorydai and u_ndefined who pointed out that I messed up below for the 4x4 and larger grids...

...so the numbers of moves below are all upper limits.

consider a 2x2 board.

There will be 2 moves. The electron move and the proton moves and all split particles are eliminated

consider a 3x3 board.

After 2 move of the electron and proton we will have effectively two 2x2 boards with an electron and proton in SE / NW corners - so it will take 2 moves to split the original electron and proton and then twice the number of moves for a 2x2 board. Thus the total moves are$$2 + 2\times(moves for~ 2\times2 ~board) = 2+ 2\times2=6 ~moves$$

consider an $$n \times n$$ board.

After 2 move of the electron and proton we will have effectively two $$(n-1)\times(n-1)$$ boards with an electron and proton in SE / NW corners - so it will take 2 moves to split the original electron and proton and then twice the number of moves for an $$(n-1)\times(n-1)$$ board. Thus the total moves are$$moves for ~ n\times n~board = 2 + 2\times(moves for~ (n-1)\times(n-1) ~board)$$

Thus in for 2x2, 3x3.... up to 8x8 board we have

2x2 2 move ; 3x3 6 moves ; 4x4 14 moves ; 5x5 30 moves ; 6x6 62 moves ; 7x7 126 moves ; 8x8 254 moves

and in general

for nxn we have $$moves for ~n\times n = 2^n - 2$$

• Formula is okay until 4x4, where you can get 12 moves. Feb 22, 2020 at 15:05
• tip: move the electron in a zigzag direction Feb 22, 2020 at 15:43
• @tom If you label the 4x4 board 1 to 4 on first row, 2 to 8 on second, etc. I will put the number of cell where a split needs to happen, obviously electron splits up and right and the proton down and left: 13, 4, 14, 3, 7, 11, 9, 10, 5, 2, 11, 8. This is 12 moves. Feb 22, 2020 at 17:53
• @Amorydai - ok, so many thanks for the explanation... ok so I got it wrong...
– tom
Feb 22, 2020 at 21:29