MathDB
Problems
Contests
National and Regional Contests
Latvia Contests
Latvia BW TST
2015 Latvia Baltic Way TST
11
11
Part of
2015 Latvia Baltic Way TST
Problems
(1)
figure on the sheet of squares cut into exactly in F_n$ ways
Source: 2015 Latvia BW TST P11
12/17/2022
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
F_n
F
n
ways, where
F
n
F_n
F
n
s the
n
n
n
-th Fibonacci number (in the series of Fibonacci numbers
F
1
=
F
2
=
1
F_1 = F_2 = 1
F
1
=
F
2
=
1
and for each
i
>
1
i > 1
i
>
1
holds
F
i
+
2
=
F
i
+
1
+
F
i
F_{i+2} = F_{i+1} + F_i
F
i
+
2
=
F
i
+
1
+
F
i
). For example, a rectangle of
2
×
3
2 \times 3
2
×
3
squares can be cut at the corners in exactly two ways (Fig.
2
2
2
). https://cdn.artofproblemsolving.com/attachments/6/5/c82340623ff5f92a410bd73755ba8cbdc501ff.png
combinatorics