Problem 1015

Let's show that mathematicians could choose the number $\alpha=\frac{\sqrt{29}-1}{2}-$ as a root of the equation $\alpha^{2}+\alpha=7$. It is clear that $\alpha > 2$. It is not difficult to see that for natural $m$, $(2 \alpha)^{m}=a_{m}+b_{m} \sqrt{29}$, where $a_{m}$ and $b_{m}$ are integers, and $a_{m} > 0 > b_{m}$ for even $m$. Therefore, the number $\alpha m$ is irrational.

It remains to show that for any natural number $n$, the sum of $n$ rubles can be collected in the required manner. Consider all ways to collect $n$ rubles using the issued coins (at least one such way exists: you can take $n$ one-ruble coins). Choose the way in which the smallest number of coins is used. Suppose that a coin of denomination $\alpha^{k} (k \geq 0)$ appears in this way at least 7 times. Then we can replace 7 coins of denomination $\alpha^{k}$ with coins of denominations $\alpha^{k+1}$ and $\alpha^{k+2}$. The total value of the coins will not change ($\alpha^{k+1}+\alpha^{k+2}=7 \alpha^{k}$), but their number will decrease. This contradicts the choice of our method.

## Answer

It could.

Author: Rigoryev M. A.

Prove that for any natural numbers $a_{1}, a_{2}, \ldots, a_{k}$ such that $\frac{1}{a_{1}}+\frac{1}{a_{2}}+\ldots+\frac{1}{a_{k}}>1$, the equation

![
where $[x]$ is the greatest integer not exceeding $x$.

## Solution

Let $S=\frac{1}{a_{1}}+\frac{1}{a_{2}}+\ldots+\frac{1}{a_{k}}$.

Suppose that the natural number $n$ is a solution to the equation in the problem's condition. Let $r_{i}$ be the remainder when $n$ is divided by $a_{i}$, i.e., $n=a_{i}\left[\frac{n}{a_{i}}\right]+r_{i}$. Then

$$\begin{aligned} n= & {\left[\frac{n}{a_{1}}\right]+\ldots+\left[\frac{n}{a_{k}}\right]=\frac{n-r_{1}}{a_{1}}+\ldots+\frac{n-r_{k}}{a_{k}}=} \\ & =n\left(\frac{1}{a_{1}}+\ldots+\frac{1}{a_{k}}\right)-\left(\frac{r_{1}}{a_{1}}+\ldots+\frac{r_{k}}{a_{k}}\right)=n S-\left(\frac{r_{1}}{a_{1}}+\ldots+\frac{r_{k}}{a_{k}}\right) \end{aligned}$$

from which $n=\frac{1}{S-1}\left(\frac{r_{1}}{a_{1}}+\ldots+\frac{r_{k}}{a_{k}}\right)$.

Thus, for a given set of numbers $(r_{1}, \ldots, r_{k})$ satisfying the conditions $0 \leq r_{i}<a_{i}$, there can be no more than one natural solution $n$ with such a set of remainders. There are exactly $a_{1} a_{2} \ldots a_{k}$ such sets, so the number of solutions to the equation $n=\left[\frac{n}{a_{1}}\right]+\ldots+\left[\frac{n}{a_{k}}\right]$ is no more than $a_{1} a_{2} \ldots a_{k}$.