## Exercises and problems in Informatics |

## Please read The Conditions of the Problem Solving Competition.

**I. 25.** According to Zeckendorf's
theorem, every natural number *n* can uniquely be expressed as a
sum of Fibonacci numbers
*n*=*F*_{k1}+*F*_{k2}+...+*F*_{kr}
such that *k*_{i}\(\displaystyle \ge\)*k*_{i+1}+2 and
*k*_{r}\(\displaystyle \ge\)2 hold for all *i* (1*i*<*r*), where, as usual, Fibonacci numbers
satisfy *F*_{0}=0, *F*_{1}=1 and
*F*_{k}=*F*_{k-1}+*F*_{k-2}
(*k*>1).

Given a natural number *n* (1*n* 10^{7}),
your program (I25.pas,...) should decompose it into a sum of Fibonacci
numbers. (Efficiency of your solution will also be taken into
account.) (*10 points*)

**I. 26**. Let us consider a square. The
Sierpinski carpet is obtained by recursively taking off smaller and
smaller squares: at the first level the middle square with side being
one-third of the original one is removed. Then, in the second level,
divide the remaining area into 8 smaller squares and repeat the
previous process again. The remaining 8^{
}

**.**8 squares (with area being one-ninth
of the previous squares each) are handled in the same way in the third
level, and so on.

level 1 | level 2 | level 3 | level 4 |

Prepare your program (I26.pas,...) which reads the
number of the level, and draws the corresponding Sierpinski
carpet. (Parts that have not been removed should be coloured grey.)
(*10 points*)

**I. 27**. The *French flag* problem
is the following control problem. *N* adjacent cells (operating
in the same way) should be equipped with and appropriate
state-transition function (that is a formula to be written into the
cell) such that the cells form a French flag pattern as a result
(*i.e.* *N*/3 cells become red, *N*/3 cells become
white and *N*/3 cells become blue).

In the initial state, on disturbing the leftmost
cell, 3 waves (*i*,*j*,*k*) emerge from it. The
*i*-wave stays for 1 time step in each cell before moving to its
right neighbour. The *j*-wave stays for 2, while the
*k*-wave stays for 5 time steps in a cell before moving to the
next one. The *i*-wave is reflected from the rightmost cell and
annihilates each of the waves it encounters.

The original grey colour of a cell changes
according to the type of the wave: *i*-waves give blue,
*j*-waves give white and *k*-waves give red colour to the
cells they pass over. If a cell meets a reflected *i*-wave, its
colour is unchanged in the future.

Figure 1 | Figure 2 | Figure 3 |

If the leftmost cell is disturbed once more, then
it initiates *i*-, *j*- and *k*-waves, and the pattern
is formed again (see Figure 2). Finally, if the row of cells is
pulled apart (that is an empty column is inserted), then the pattern
will appear in both parts (see Figure 3). (Figures are on the
bottom page of this paper.) Prepare an Excel sheet (I27.XLS) that
solves the French flag problem. (*10 points*)