Problems

How many integers are there from 1 to 1,000,000, which are neither full squares, nor full cubes, nor numbers to the fourth power?

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.

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 the number $\sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{7}+\sqrt{11}+\sqrt{13}+\sqrt{17}$ is irrational.

a) One person had a basement illuminated by three electric bulbs. Switches of these bulbs are located outside the basement, so that having switched on any of the switches, the owner has to go down to the basement to see which lamp switches on. One day he came up with a way to determine for each switch which bulb it switched on, descending into the basement exactly once. What is the method?

b) If he goes down to the basement exactly twice, how many bulbs can he identify the switches for?