The frog concerto

Question

A pond contains $24$ waterlilies that are arranged in a rectangular $2\times12$ grid (that is, two rows with twelve waterlilies). One evening $24$ 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\le24$). 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 $24$ 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.)

Answer 1

The answer is

$54289$, or $233^2$

This is because

If we label the frogs 01-12 on the top and 24-13 on the bottom
01 02 03 04 05 06 07 08 09 10 11 12
24 23 22 21 20 19 18 17 16 15 14 13

We see that every odd frog must end on an even position and every even frog must end on an odd position. So the positioning of the even and odd frogs are independent of each other. They are also symmetrical to each other, so the total number of even positions equals the total number of odd positions. Therefore, we can consider only the odd frogs and square the answer to get the total number of seating arrangements.

Now, to calculate the position for 24 frogs, I broke it up into 2 parts:

Part 1: Frog 01 moves to position 24. In this case, the number of positions is the same as calculating the positions for the remaining 11 odd frogs in a 2 x 11 rectangle.

Part 2: Frog 01 moves to position 02. This forces frog 23 to position 24. In this case, the number of positions is the same as calculating the positions for the remaining 10 odd frogs in a 2 x 10 rectangle.

Therefore

$F(x) = F(x-1) + F(x-2)$, so we have a Fibonacci sequence.
$F(1) = 1$
$F(2) = 2$
$F(12) = 233$, so there are 233 positions for 12 odd frogs. Square this to give the total positions for 24 frogs, and we arrive at our answer, $54289$.

Answer 2

I think the answer is:

$$384199201$$ or $$19601^{2}$$

Lets consider nx2 chessboard. Frog is checker. Checkers move from black to white and vice-versa.

Let w(i) be the number of possible rearrangement of checkers from black to white on ix2 chessboard. Final answer will be w(12)^2 because case is symmetrical and independent.

Now obviously: $$w(0) = 1$$ $$w(1) = 1$$ $$w(2) = w(1) + 2*w(0)$$ And: $$w(i) = w(i-1) + 2*w(i-2)+2*w(i-3)+...+2*2(0)$$ $$w(i) = w(i-1) + 2*[w(i-2) + w(i-3) + … + w(0)]$$

Because either:

• checker on first row changes it place and checkers on other (i-1) chessboard have all the possibilities in the world
• checker on first m row jump places in cycle in either direction (2 possibilities) and checkers on 2x(i-m) chessboard have all the possibilities in the world

Now calculating all elements directly, answer to w(12) and w(12)^2.

No case is duplicated because for every element summed there is further checker horizontal position change forbidden in further sum elements.

Answer 3

Let's assume they were initially arranged like this:

_1__2__3__4__5__6__7__8__9_10_11_12
13_14_15_16_17_18_19_20_21_22_23_24

Let $x_n$be the number of arrangements for $n$ columns, and $x_{m,m+1}$ the one for two aligned rows with one being one unit longer. If we start from the upper left corner, then go down and rinse and repeat to place our numbers we'll get something like:

$13-1......................................x_{11}$ (13 top left, 1 bottom left etc.)
$2-14......................................x_{10}$

$13-14....................................x_{10,11}$
$13-14-1-2.........................x_{10}$
$13-14-1-15-2.................x_{9,10}$

$2-1.........................................$(equivalent to 13-14, 90-degree rotation)

$x_0 = 1$
$x_1 = 1$
$x_2 = 1 + 1 + 2*1=4$
$x_{0,1} = 1$
$x_3 = 9$

Induction time:

$x_n = x_{n-1} + x_{n-2} + 2*x_{n-2,n-1}$

$x_{m,m+1} = x_{m} + x_{m-1,m}$

$2*x_{n-2,n-1} = 2*x_{n-2} + 2*x_{n-3,n-2}$

$2*x_{n-2,n-1} = 2*x_{n-2} + 2*x_{n-3} + ... + 2*x_1 + 2*x_{0,1}$

$x_n = x_{n-1} + 3*x_{n-2} + 2*x_{n-3} + ... + 2*x_1 + 2$ $x_{n-1} = x_{n-2} + 3*x_{n-3} + 2*x_{n-4} + ... + 2*x_1 + 2$

$x_n = 2*x_{n-1} + 2*x_{n-2} - x_{n-3}$

$x_0 = 1$
$x_4 = 25$

So far, $x_k = F(k)^2$. If every value before $x_n$ follows this rule, $x_{n-2} = a^2$ and $x_{n-3}=b^2$, then $x_{n-1} = (a+b)^2$. $x_n = 2a^2+2b^2+4ab + 2a^2 - b^2 = (2a+b)^2 = [a+(a+b)]^2$, so our formula is always true and $x_{12} = 54289$.

Answer 4

This is Joel Rondeau's solution. I just thought I would try to make it easier to follow:

When the frogs first arrive, they are pleased to find that their lillypads have been tastefully decorated in a black and white checkerboard pattern. As they leave for the break, each white frog anticipates returning to one of the 2 or 3 black pads adjacent to its white one, and similarly for the black frogs. But when they return, they are surprised to find that some scallawag has swapped the color scheme on every lillypad. The ones that were white before are now black, and vice versa. Each frog is somewhat disconcerted to see that their new pad is the same color as their old.

But the surprises are not over, for after they move in place, they realize there is a now a mirror above them, angled so that from the audience, the top row appears on the bottom, and the bottom row on top. Indeed, in the mirror, the color scheme appears unchanged. But those frogs who had chosen to move down or up appear in the mirror as to have not moved at all. Those whose chose to move right or left appear in the mirror to have moved diagonally right or left instead, staying on their same color.

From this view, the white frogs rearranged themselves on the white pads, and the black frogs rearranged themselves independently on the black pads. The two colors are symmetrically treated, so the number of arrangements on each is the same.

Now assuming that there are $n$ rows, let $F_n$ be the number of allowable arrangements of the $n$ white frogs. The leftmost frog has only two choices (as viewed by mirror): stay still, or move to the pad in column 2. If it stays in place, then the remaining $n-1$ frogs can arrange themselves in the remaining places in $F_{n-1}$ ways. If the frog moves, then the column 2 frog is the only one that can reach the column 1 position, which it must do if each frog is to sit on its own pad. So white frogs 1 and 2 swap places. The remaining $n-2$ frogs can arrange themselves in $F_{n-2}$ ways. Therefore $$F_n = F_{n-1} + F_{n-2}$$. Now if $n=1$, there is only one column, and so the frog has only one choice: stay put. $F_1 = 1$. If $n=2$, then the two frogs can either stay put or swap places. $F_2 = 2$. This is the pattern for the Fibonacci numbers. The recursion fomula can be used to calculate $F_{12} = 233$. There are 233 ways the white frogs can rearrange, and 233 ways the black frogs can rearrange, giving $233^2 = 54289$ total ways the frogs can rearrange.