Это первая задача, по традиции, она является самой простой, возможно, чтобы разогреть участников, возможно, чтобы дать шанс слабым командам.
P.S. Она простая только с точки зрения людей, которые готовились каждый день начиная с 4-го класса.
3n - является решением кто-то уже писал.
3n+2 - не являются решением так как после них в последовательности точно не будет квадравтов.
1 - очевидное решение.
4 - не решение (непосредственно проверяется 4,2,3k+2)
Возьмем минимальное число n>1 такое что 3n+1 - решение. В последовательности с таким первым числом все числа имеют вид 3k+1 и нет чисел меньше него так как иначе это не было бы минимальным числом. А это значит что нет полных квадратов больших 3n+1 и меньших (3n+1)^2. То есть (3n-2)^2<3n+1, а это возможно только при n=1. Противоречие, а значит решиний вида 3k+1 кроме 1 нет.
Это можно объяснить и проще. По условию если число нецелое, то следующее будет нецелое + 3. А нецелое + 3 всегда будет давать нецелое. То есть алгоритм зависнет на нецелых числах навсегда.
(программистские навыки дают о себе знать)
Я тоже сначала прочитал так же неверно условия как и вы. А потом перечитал и понял, что я не так понял.
Вероятно, я опоздал, но ошибка в том, что ты подумал, что речь идет о нецелости самого a_n, тогда как в задаче проверяется корень из a_n.
Лига математиков
572 поста2.4K подписчиков