19
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Yeah I've made some mistakes (general method is ok). I'll fix them tommorow. $\endgroup$ – user20217 Mar 16 '16 at 17:47
27
$\begingroup$

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$.

$\endgroup$
  • 3
    $\begingroup$ I believe something should be said about how, in each case, what is leftover is also a rectangular formation -- either $2 \times (x-1)$ or $2 \times (x-2)$ -- so that indeed recursion is alright. Also, of note is how, if we define $F(x)$ to be the number of arragements for a single parity of frogs in a $2 \times x$ grid, then by inspection $F(1) = 1$ and $F(2) = 2$. In particular, $F$ is shifted by a term relative to the usual Fibonacci sequence. In any case, great answer and reasoning overall! $\endgroup$ – Fimpellizieri Mar 14 '16 at 20:48
  • 1
    $\begingroup$ If two frogs try to jump onto eachother's waterlilies, they'll bump into eachother in mid-air. $\endgroup$ – Darrel Hoffman Mar 14 '16 at 21:50
  • 4
    $\begingroup$ They took a break. Got up, stretched their legs. Didn't say they immediately went from one lilly pad to the other. $\endgroup$ – Joel Rondeau Mar 14 '16 at 21:52
  • $\begingroup$ @DarrelHoffman The pads are big enough such that multiple frogs can be on each pad. $\endgroup$ – corsiKa Mar 14 '16 at 22:35
  • $\begingroup$ @Fimpellizieri I took your advice and updated the answer. Thank you. $\endgroup$ – Joel Rondeau Mar 16 '16 at 19:17
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $w(i) = w(i-1) + 3 * w(i-2) + 2 * (w(i-3) + w(i-4) + ...)$, as there are 3 possible rearrangements of a square (rotate CW, rotate CCW, or swap top pair and swap bottom pair). Only 2x2 squares have the third possibility, though. $\endgroup$ – Paul Sinclair Mar 16 '16 at 16:28
  • $\begingroup$ "Final answer will be $w(12)^2$ because case is symmetrical and independent." - could you explain what this means? What "cases" are you referring to?. I can think of no justification at all for squaring this. $\endgroup$ – Paul Sinclair Mar 16 '16 at 16:33
  • $\begingroup$ When the first m rows rotate, one of the rotation directions involves the first checker staying in its row. You are counting this case twice. $\endgroup$ – f'' Mar 16 '16 at 18:16
  • $\begingroup$ This is wrong and Joel is right. #include <cstdio> bool T[2][12]; inline bool ch(const int x, const int y) { return (x >= 0) && (x < 2) && (y >= 0) && (y < 12) && !T[x][y]; } int f(int n) { if(n == 24) return 1; int x = n%2; int y = n/2; int r = 0; if (ch(x+1,y)) { T[x+1][y] = true; r += f(n+1); T[x+1][y] = false; } if (ch(x-1,y)) { T[x-1][y] = true; r += f(n+1); T[x-1][y] = false; } if (ch(x,y+1)) { T[x][y+1] = true; r += f(n+1); T[x][y+1] = false; } if (ch(x,y-1)) { T[x][y-1] = true; r += f(n+1); T[x][y-1] = false; } return r; } void main() { printf("%d\n", f(0)); } $\endgroup$ – Pawel Dobrzycki Mar 17 '16 at 8:07
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.