Problems

Consider a chess board of size $n\times n$. It is required to move a rook from the bottom left corner to the upper right corner. You can move only up and to the right, without going into the cells of the main diagonal and the one below it. (The rook is on the main diagonal only initially and in the final moment in time.) How many possible routes does the rook have?

Tickets cost 50 cents, and $2n$ buyers stand in line at a cash register. Half of them have one dollar, the rest – 50 cents. The cashier starts selling tickets without having any money. How many different orders of people can there be in the queue, such that the cashier can always give change?

Prove that the Catalan numbers satisfy the recurrence relationship $C_n=C_0{C}_{n-1}+C_1{C}_{n-2}+\cdots +C_{n-1}{C}_0$. The definition of the Catalan numbers $C_n$ is given in the handbook.

Determine all prime numbers $p$ and $q$ such that $p^2-2q^2=1$ holds.

Suppose that there are 15 prime numbers forming an arithmetic progression with a difference of $d$. Prove that $d>30,000$.

Could it be that a) $\sigma (n)>3n$; b) $\sigma (n)>100n$?

Prove that for a real positive $\alpha$ and a positive integer $d$, $\lfloor \alpha /d\rfloor =\lfloor \lfloor \alpha \rfloor /d\rfloor$ is always satisfied.

Prove that if $p$ is a prime number and $1\le k\le p-1$, then $(\genfrac{}{}{0ex}{}{p}{k})$ is divisible by $p$.

Prove that if $p$ is a prime number, then $(a+b{)}^p-a^p-b^p$ is divisible by $p$ for any integers $a$ and $b$.

Prove that in any infinite decimal fraction you can rearrange the numbers so that the resulting fraction becomes a rational number.