Это первая задача, по традиции, она является самой простой, возможно, чтобы разогреть участников, возможно, чтобы дать шанс слабым командам.
P.S. Она простая только с точки зрения людей, которые готовились каждый день начиная с 4-го класса.
Все числа, представимые в виде 3n или в виде 3n+1.
С числами вида 3n всё понятно. Рано или поздно в ряду попадётся квадрат, после чего корень из него также будет иметь вид 3n, а значит либо он снова будет квадратом, либо, прибавляя 3-ку мы дойдём до первого встреченного квадрата. Если он снова квадрат, то повторяем операцию.
Если число не представимо в виде 3n, то это либо 3n+1, либо 3n+2. В первом случае опять же рано или поздно, добавляя 3-ки мы доходим до квадрата числа. При извлечении корня мы получим число, представимое в виде 3n+1.
Во втором случае до квадрата мы никогда не доходим и последовательность бесконечно увеличивается. Это происходит, поскольку оба вида при возведении в квадрат будут представимы в 3n+1
(3n+1)^2 = 9n^2 + 6n + 1
(3n+2)^2 = 9n^2 + 12n + 3 + 1
Дополню:
Надо из ответа вырезать числа вида 3n+1 между (3n+1)^2 и (3n+2)^2, второе включительно, поскольку они при такой последовательности будут приводить именно на бесконечную последовательность, попадая при взятии корня на 3n+2.
Например, решением не будут числа 19, 22 и 25; 52, 55, 58, 61 и 64; и т.д.
Очевидно, что в последовательности 3n+1 квадраты, приводящие к 3n+1 и к 3n+2 чередуются.
Расстояние между квадратами меньше расстояния между числом и его квадратом начиная с a>4
Таким образом, ближайший квадрат перенесет либо к 3n+2, либо ближе к началу (...->4 ->2 ->inf)
В итоге остаются только числа, кратные трем.
А также придется исключить квадраты этих чисел а также эти числа возведенные в степень степени двойки и числа приводящие к таковым.
Не очень похоже на решение получается.
А почему решением не будут ваши числа? Для обоих случаев есть решения:
19, 22, 25, 5, 8, 4, 7, 10, 13, 16, 4, 7...
в этом случаи существует определённое А (целых даже несколько)
так же как и во втором варианте
52, 55, 58, 61, 64, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65... 121, 11 и тут он совпадает
значит тут тоже есть такое А, которое выполняет условия.
Наверное это просто расхождения в понимании условия задачи, потому как у нас спрашивают буквально "при каких начальных значениях первого члена последовательности она зацикливается"
Сейчас вот посчитал немного точнее, так ведь неправильная последовательность выходит. Так что не смотрите сюда, тут таки не правильно.
Как уже сказал человек выше, верным ответом будут числа, которые не входят в множество 3n + 2, так как все квадраты представляются в виде 3n и 3n+1
Поэтому окончательным решением будут все простые числа, исключая числа вида 3n+2
Не должно еще существовать некоторого натурального С, что С^2 принадлежит интервалу (А,А^2) и C=3k+2 для любого натурального k и k=0.
P.S. Не, это не решение, так, мысля в слух.
И это все, к слову, размышления на тему того, каким должно быть A, а не a нулевое
То, что вы написали, не полное решение. Насчет чисел вида 3n: почему не попадется раньше, чем 9n^2 какой-то другой квадрат, отчего получится цепочка неповторяющихся чисел.
Насчет чисел вида 3n+1: опять же, почему будут повторы?
рассмотрим три вида чисел 3n, 3n+1 и 3n+2
(остаток от деления квадрата целого числа на 3 всегда либо 0 либо 1)
2) 3n+1 можно заметить, что для таких чисел остаток от деления на три инвариантен отн-но возвезедения в квадрат/извлечения корня, еще можно заметить что четные степени 2ки как раз имеют вид 3к+1, поэтому рано или похдно мы в них упремся и попадем в число "2", которое согласно предыдущему пункту -точно не решение
мне кажется тут можно показать более формально, но на пальцах как-то так (буду благодарен за аккуратный вывод, времени нет)
3) 3n интуитивно понятно. Если мы начали с некого 3m то либо дойдем итерациями до (3m)^2 либо до (3n )^2 где n<m, теперь меняем m на n и переходим в начало этого предложения)
Не все, просто бесконечно много. Бесконечность - она такая, может быть разной :)
Например, если взять все натуральные числа, то их количество бесконечно. При этом количество чётных чисел тоже бесконечно. И с точки зрения обывателя количество чётных числе в два раза меньше, чем количество всех натуральных. Хотя в действительности эти бесконечности равны по мощности.
Тут так же - часть членов последовательности равна числу A, но не обязательно все.
Моё решение не слишком удачно. Наверное, сейчас я решала бы по-другому :)
Но конкретно в этом примере мы выйдем на круг 3n+2. Я там дополняла решение, исключая ряд значений. Это, конечно, тоже надо исключать.
Общее правило я выше писала. А это просто отдельный частный случай. Он не попал под правило, потому что разница между числом и квадратом меньше 3
Вообще, можете забыть, что я сейчас сказала :)
Пока ехала до работы спокойно подумала над задачей. Так что корректным решением можно считать, например, такое:
Разделим все числа по делимости на 3: 3n, 3n+1, 3n+2.
Числа вида 3n очевидно удовлетворяют условию задачи, поскольку (3n)^(1/2), если такая операция возможна, так же имеет вид 3n.
Числа 3n+2 очевидно не удовлетворяют, поскольку не может быть квадрата вида 3n+2.
Теперь рассмотрим числа вида 3n+1. Предположим, что в нашей последовательности мы наткнулись на число, квадратный корень из которого имеет вид 3n+1. Сможем ли мы зациклить эту последовательность, т.е. снова добраться до исходного числа? Это будет зависеть от того, нет ли в последовательности чисел, являющихся квадратами чисел вида 3n+2.
Для проверки этого факта решим неравенство (3n-1)^2 > 3n+1.
(3n-1)^2 - ближайший к исходному числу квадрат числа вида 3n+2; 3n+1 - корень квадратный из исходного числа.
Несложно обнаружить, что решениями неравенства будут числа: (-беск.; 0) U (1; +беск.)
Т.е. для всех n >= 2 очевидно, что последовательность не зацикливается, "натыкаясь" на квадрат вида (3n+2)^2.
Отдельно рассмотрим 2 числа, не попавших в решение неравенства:
0: 3*0+1 = 1. Число 1, очевидно, удовлетворяет задаче
1: 3*1+1 = 4. Число 4, очевидно, не удовлетворяет, поскольку является полным квадратом само по себе и в результате сводит к последовательности, начинающейся с 2, т.е. числа вида 3n+2.
Таким образом, ответом будет: все числа вида 3n и число 1
Региональная - это весьма здорово, учитывая, что я в этом году только начинаю участвовать в олимпиадах :)
Лига математиков
572 поста2.4K подписчиков