Let us consider a set *C_N* of character strings with length of
*N* characters each (*N* <= 20), satisfying the following
properties:

a) every string contains no more than two different characters: A
and B.

b) every string does not contain two adjacent characters A.

**Example**: If *N*=4, strings were ABBA, BABA, BBBB, but AABA,
ABAA and AAAB are not belonging to *C*_4, because of not satisfying
the condition b).

Write a program, that solves the following problems:

**Problem 1**. For any integer *N* compute the number of elements
of set *C_N* without generating the elements themselves.

**Example**. If *N*=20, the number of elements of *C_N* is
17711.

**Problem 2**. Output some arbitrary *K* different elements
of *C_N*. The integer *K* should be entered by the keyboard.

**Problem 3**. Output the strings of *C_N* (1 <= *N* <=
10) which are symmetric relatively to its centre.

**Example**. For N=4: ABBA, BBBB; For N=5: ABBBA, BABAB, ABABA, BBABB.

Let us consider a set *P* containing points with integer coordinates
(*x*,*y*) for which 0 < *x* < *a*, 0 < *y*
< *b*, for some integers *a* and *b*. Write a program,
that solves the following problems:

**Problem 1**. Input the data from text file `PTS.TXT` containing
the coordinates of the points of *P*. The file has the following structure:

row 1: | a b |

row 2: | x_1 x_2 |

... | ... |

Last (k+1)-th row |
x_k y_k |

The number of points is not known before reading the data from the file.

Your program should render on the computer screen the points of *P*.

**Problem 2**. Every point of *P* should be colored in
blue or red, so that the difference of numbers of blue and red points located
on any straight line, which is parallel to one of the coordinate lines,
should not be greater then 1. Your program should render on the computer
screen no more than two coloring of points of *P*.

**Problem 3**. Construct a rectangle, which satisfies simultaneousely
the following two conditions:

a) Its vertices have integer coordinates and its sides are parallel
to the coordinate lines;

b) The number of points of *P*, which are within the rectangle
are equal to the number of points, which are outside the rectangle.

Remark: The points located on the sides of the rectangle are neither inner,
nor outer to the rectangle.

Source: Matematika i informatika, journal published by Bulgarian Ministry of Education, n. 3, 1994, pp. 68-69.

© The text is translated from Bulgarian by Emil Kelevedzhiev.

Return to the Home Page of Bulgarian Mathematics and Informatics Competitions.