MathDB

Let us call a figure on a sheet of squares an arbitrary finite set of connected squares, i.e. a set of squares in which it is possible to go from any square to any other by walking only on the squares of this figure. Prove that for every natural n there exists such a figure on the sheet of squares that it can be cut into "corners" (Fig. 1) exactly in

F_n

ways, where

F_n

s the

n

-th Fibonacci number (in the series of Fibonacci numbers

F_1 = F_2 = 1

and for each

i > 1

holds

F_{i+2} = F_{i+1} + F_i

). For example, a rectangle of

2 \times 3

squares can be cut at the corners in exactly two ways (Fig.

2

). https://cdn.artofproblemsolving.com/attachments/6/5/c82340623ff5f92a410bd73755ba8cbdc501ff.png

Problem Statement