Problems

Peter thought of a number between 1 to 200. What is the fewest number of questions for which you can guess the number if Peter answers

a) “yes ” or “no”;

b) “yes”, “no” or “I do not know”

for every question?

There are 4 coins. Of the four coins, one is fake (it differs in weight from the real ones, but it is not known if it is heavier or lighter). Find the fake coin using two weighings on scales without weights.

Prove the following formulae are true: $$\begin{array}{rl}{a}^{n+1}-b^{n+1}& =(a-b)(a^n+a^{n-1}b+\cdots +b^n);\\ a^{2n+1}+b^{2n+1}& =(a+b)(a^{2n}-a^{2n-1}b+a^{2n-2}{b}^2-\cdots +b^{2n}).\end{array}$$

Prove that $\sqrt{\frac{a^2+b^2}{2}}\ge \frac{a+b}{2}$.

Draw all of the stairs made from four bricks in descending order, starting with the steepest $(4,0,0,0)$ and ending with the shallowest $(1,1,1,1)$.

A frog jumps over the vertices of the triangle $ABC$, moving each time to one of the neighbouring vertices.

How many ways can it get from $A$ to $A$ in $n$ jumps?

Let $(1+\sqrt{2}+\sqrt{3}{)}^n=p_n+q_n\sqrt{2}+r_n\sqrt{3}+s_n\sqrt{6}$ for $n\ge 0$. Find:

a) $\underset{n\to \mathrm{\infty }}{lim}\frac{p_n}{q_n}$; b) $\underset{n\to \mathrm{\infty }}{lim}\frac{p_n}{r_n}$; c) $\underset{n\to \mathrm{\infty }}{lim}\frac{p_n}{s_n}$;

Find the generating functions of the sequences of Chebyshev polynomials of the first and second kind: $$F_T(x,z)=\sum _{n=0}^{\mathrm{\infty }}{T}_n(x)z^n;F_U(x,z)=\sum _{n=0}^{\mathrm{\infty }}{U}_n(X)z^n.$$

Definitions of Chebyshev polynomials can be found in the handbook.

We denote by $P_{k,l}(n)$ the number of partitions of the number $n$ into at most $k$ terms, each of which does not exceed $l$. Prove the equalities:

a) $P_{k,l}(n)-P_{k,l-1}(n)=P_{k-1,l}(n-l)$;

b) $P_{k,l}(n)-P_{k-1,l}(n)=P_{k,l-1}(n-k)$;

c) $P_{k,l}(n)=P_{l,k}(n)$;

d) $P_{k,l}(n)=P_{k,l}(kl-n)$.

Find the coefficient of $x$ for the polynomial $(x-a)(x-b)(x-c)\dots (x-z)$.