Problems

Prove that the following facts are true for any graph:

a) The sum of degrees of all vertices is equal to twice the number of edges (and therefore it is even);

b) The number of vertices of odd degree is even.

48 blacksmiths must shoe 60 horses. Each blacksmith spends 5 minutes on one horseshoe. What is the shortest time they should spend on the work? (Note that a horse can not stand on two legs.)

This problem is from Ancient Rome.

A rich senator died, leaving his wife pregnant. After the senator’s death it was found out that he left a property of 210 talents (an Ancient Roman currency) in his will as follows: “In the case of the birth of a son, give the boy two thirds of my property (i.e. 140 talents) and the other third (i.e. 70 talents) to the mother. In the case of the birth of a daughter, give the girl one third of my property (i.e. 70 talents) and the other two thirds (i.e. 140 talents) to the mother.”

The senator’s widow gave birth to twins: one boy and one girl. This possibility was not foreseen by the late senator. How can the property be divided between three inheritors so that it is as close as possible to the instructions of the will?

Prove that for every natural number $n>1$ the equality: $$\lfloor n^{1/2}\rfloor +\lfloor n^{1/3}\rfloor +\cdots +\lfloor n^{1/n}\rfloor =\lfloor {\log }_{2}n\rfloor +\lfloor {\log }_{3}n\rfloor +\cdots +\lfloor {\log }_{n}n\rfloor$$ is satisfied.

$a_1,a_2,a_3,\dots$ is an increasing sequence of natural numbers. It is known that $a_{a_k}=3k$ for any $k$. Find a) $a_{100}$; b) $a_{2022}$.

Given an endless piece of chequered paper with a cell side equal to one. The distance between two cells is the length of the shortest path parallel to cell lines from one cell to the other (it is considered the path of the center of a rook). What is the smallest number of colors to paint the board (each cell is painted with one color), so that two cells, located at a distance of 6, are always painted with different colors?

$f(x)$ is an increasing function defined on the interval $[0,1]$. It is known that the range of its values belongs to the interval $[0,1]$. Prove that, for any natural $N$, the graph of the function can be covered by $N$ rectangles whose sides are parallel to the coordinate axes so that the area of each is $1/N^2$. (In a rectangle we include its interior points and the points of its boundary).

A group of numbers $A_1,A_2,\dots ,A_{100}$ is created by somehow re-arranging the numbers $1,2,\dots ,100$.

100 numbers are created as follows: $$B_1=A_1,B_2=A_1+A_2,B_3=A_1+A_2+A_3,\dots ,B_{100}=A_1+A_2+A_3\cdots +A_{100}.$$

Prove that there will always be at least 11 different remainders when dividing the numbers $B_1,B_2,\dots ,B_{100}$ by 100.

a) Give an example of a positive number $a$ such that $\{a\}+\{1/a\}=1$.

b) Can such an $a$ be a rational number?

For which natural $n$ does the number $\frac{n^2}{{1.001}^n}$ reach its maximum value?