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$ $pi$ be the number for which x=2cost. Then

$\sqrt{2+x}=2\cos{t\over2},$

$\sqrt{2-\sqrt{2+x}}=2\sin{t\over4}=2\cos\left({\pi\over2}-{t\over4}\right)$

and

$\sqrt{2+\sqrt{2-\sqrt{2+x}}}=2\cos\left({\pi\over4}-{t\over8}\right).$

Thus the equation can be written in the form:

$\cos t=\cos\left({\pi\over4}-{t\over8}\right).$

Hence $t={2\pi\over9}$ and x=2cos40^o $approx$ 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 ${5\over6}(n-5)$ 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 3n 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) $le$ 2g+3r.

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-5 $le$ 2g.

It follows from the inequalities obtained that

$g+r={1\over3}\cdot(2g+3r)+{1\over6}\cdot2g\ge{1\over3}\cdot2(n-5)+{1\over6}\cdot(n-5)={5\over6}(n-5).$

Thus there are at least ${5\over6}(n-5)$ metro stations.

Remark. The constant ${5\over6}$ in the problem cannot be improved. If n=6k+1, the following diagram shows an arrangement of the metro lines where the number of stations is $5k={5\over6}(n-1)$ .

Already signed up?
New to KöMaL?