## Solutions for advanced problems "A" in March, 2002 |

In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.

**A.** **290.** Given a finite number of square sheets
of paper with a total area of 4 units, prove that it is possible to
cover a unit square with them. (*Allan Wilson,* England)

**Solution.** Let us reduce the size of the sheets so that they
should remain squares but the length of their sides should be of the
form \(\displaystyle \left({1\over2}\right)^n\). This can be done without reducing the
area to less that one fourth of the original value. Thus the total
area of the squares obtained is at least 1 unit.

Now repeat the following operation while it is possible: if there are four squares of the same size, put them together to form a square twice as large. As there are a finite number of sheets, this procedure will terminate in a finite number of steps.

At the end of the procedure, for any integer *k*, at most 3
squares of side 1/2^{k} and area 1/4^{k}
will remain. Hence the total area of the squares smaller than unity
is less than \(\displaystyle \sum_{k=1}^\infty3\cdot\left({1\over4}\right)^k=1\), that is, the
total area of the squares smaller than unity cannot be the total area
of all squares. Therefore, there will always be a square with sides
of at least one unit.

**A.** **291.** Solve the equation

\(\displaystyle x=\sqrt{2+\sqrt{2-\sqrt{2+x}}}.\)

**Solution.** Outside the interval [-2,2] one of 2+*x* and \(\displaystyle 2-\sqrt{2+x}\) is negative, and thus the right-hand side is undefined. The solution must lie in the interval [-2,2].

Let 0\(\displaystyle le\)*t\(\displaystyle le\)* be the number for which *x*=2cos*t*. Then

and

Thus the equation can be written in the form:

Hence and *x*=2cos40^{o}1,5321.

**A.** **292.** In a metropolis, there are *n*
underground lines (*n*>4). At most three lines meet at any
station, and for any two lines there is a third line such that one can
make a transfer to it from each of the two lines. Prove that there are
at least underground stations.

**Solution.** We are assuming that there are at least two
stations along each metro line.

First consider the case when there are at least three stations
along each line. The line-station pairs where line passes through
station can be counted in two ways. The number of lines is *n*,
each contains at least three stations, which makes at least 3*n*
pairs. On the other hand, there are at most three lines passing
through any station, which means at most three times as many pairs as
stations. Hence the number of stations is at least *n*, the
statement of the problem is true.

Now assume that there is a line that only has two stations. Let
*L* be such a line. There are at most 4 other lines passing
through the two stations of *L*; let these lines be defined
"close" lines and let all the other at least *n*-5 lines be
"distant" lines.

Colour the stations lying along close lines green, and colour the
rest of the stations red. Let *g* and *r* denote the number
of green and red stations, respectively.

Each distant metro line contains at least two stations. There are
at most two distant lines passing through any green station, and there
are at most three through passing through any red station. Thus
2(*n*-5)2*g*+3*r*.

For each distant line, there is a metro line that connects it to
*L*. Thus each distant line contains at least one green station.
As there are at most two distant lines through any green station,
*n*-52*g*.

It follows from the inequalities obtained that

Thus there are at least metro stations.

*Remark.* The constant in the problem cannot be
improved. If *n*=6*k*+1, the following diagram shows an
arrangement of the metro lines where the number of stations is .