Задача М554‍‍‍

Утверждение задачи сразу следует из двух лемм:

1. если число $n$‍‍ — хорошее, то и $2n+2$‍‍ — хорошее;
2. если число $n$‍‍ — хорошее, то и $2n+9$‍‍ — хорошее.

Докажем их.

Из равенств $$\begin{gather*} n=a_1+a_2+\ldots+a_k,\\ \dfrac1{a_1}+\dfrac1{a_2}+\ldots+\dfrac1{a_k}=1 \end{gather*}$$ следует $$\begin{gather*} 2n+2=2a_1+2a_2+\ldots+2a_k+2,\\ \dfrac1{2a_1}+\dfrac1{2a_2}+\ldots+\dfrac1{2a_k}+\dfrac12=1 \end{gather*}$$ ‍— тем самым доказано 1°; $$\begin{gather*} 2n+9=2a_1+2a_2+\ldots+2a_k+3+6,\\ \dfrac1{2a_1}+\dfrac1{2a_2}+\ldots+\dfrac1{2a_k}+\dfrac13+\dfrac16=1 \end{gather*}$$ ‍— тем самым доказано 2°.

Пользуясь 1° и 2°, очевидной индукцией (начинающейся с $2\cdot36+2=74$‍‍ для чётных $n$‍‍ и с $2\cdot33+9=75$‍‍ для нёчетных $n$‍)‍ доказываем, что любое число, большее 73, — хорошее.

Любопытно, однако, выяснить, какие числа, меньшие 73, хорошие, в частности — проверить правильность предпосылки, высказанной в условии. Без труда доказывается, что $k^2$‍‍ — всегда хорошее число и что если $m$‍‍ и $n$‍‍ — хорошие числа, то и $mn$‍‍ — хорошее. Кроме того, аналогично тому, как это сделано в 1° и 2°, проверяется, что если $n$‍‍ — хорошее, то хорошими будут также: $2n+8$‍‍ ($8=4+4$‍),‍ $2n+20$‍‍ ($20=4+8+8$‍),‍ $3n+6$‍‍ ($6=3+3$‍),‍ $3n+8$‍‍ ($8=2+6$‍),‍ $4n+6$‍‍ ($6=2+4$‍),‍ $4n+13$‍‍ ($13=3+4+6$‍),‍ $6n+5$‍‍ ($5=2+3$‍).‍

Пользуясь этим, а также подбирая представления для «недостающих» чисел, легко доказать, что хорошими будут числа 1, 4, 9, 10, 11, 16, 17, 18, 20, 22 и все числа от 24 до 73 (эти доказательства поясняют формулы на полях).

Подумайте, как проверить, будут ли хорошими числа 19, 21 и 23. Может быть, те, кто занимаются в нашей Заочной школе программирования, найдут более полезным составить программу, проверяющую, имеет ли система $$\left\{\begin{array}{l} x_1+\ldots+x_k=23,\\[6pt] \dfrac1{x_1}+\ldots+\dfrac1{x_k}=1, \end{array}\right.$$ решение в натуральных числах. (Если решение есть, то программа должна напечатать хотя бы одно решение, если нет — выдать «0».) Можете рассматривать это как дополнительную задачу к очередному уроку программирования; разумеется, полезно также дать оценку времени работы (числа тактов) и постараться, чтобы оно было как можно меньше.