# The second frog concerto

(This puzzle continues the puzzle "The frog concerto".)

There is another pond that contains $39$ waterlilies that are arranged in a rectangular $3\times13$ grid. One saturday evening $39$ frogs give a croaking concerto for the residents of the pond.

At the beginning of the concert, the $k$th frog is sitting on the $k$th lily pad (where $1\le k\le39$). There is a short break in the middle of the concert, and after this break none of the frogs returns to its old lily pad. It turns out that after the break each of the $39$ lily pads again carries one frog, and that every frog is now sitting on some new pad that is horizontally or vertically adjacent to its old pad from before the break.

Question: How many different seating arrangements are there after the break that match the above description.

(The answer to this question will be a square number. A good solution will clearly explain the reason why a square number shows up here.)

• There are no solutions to the question as stated, because if you set up the 3*13 board in a checkerboard pattern, there are 20 black squares and 19 white squares. Every black square frog must move to a white square, and vice versa. But there are 20 black square frogs and only 19 white squares, so its impossible – astralfenix Mar 16 '16 at 12:32
• @astralfenix 0 is a square number. I would put that as an answer if I were you. – hexomino Mar 16 '16 at 12:37
• Because there is no solution maybe it's interesting to see what the result is when moving to a new pad is optional for each frog – Ivo Beckers Mar 16 '16 at 13:11

Hence the answer is $0$ (which indeed is a square number).
If you set up the $3\times13$ board in a checkerboard pattern, there are $20$ black squares and $19$ white squares.
Every black square frog must move to a white square, and vice versa. But as there are $20$ black square frogs and only $19$ white squares, you'll end up with at least one white square with two or more frogs on it.