Нет квадратам!

[Xenia1996]

Существует ли

а)2011
б)бесконечное множество

попарно различных натуральных чисел, таких что никакая сумма нескольких (конечного непустого подмножества) из этих чисел не является полным квадратом?

Мне показалось, что множество всех степеней двойки с нечётным натуральным показателем отвечает на оба пункта задачи. Действительно, сумма нескольких (возможно, одной) "нечётных" степеней двойки делится на самую маленькую из них (которая имеет нечётный показатель), но не делится на удвоенную эту же самую маленькую.

Я точно знаю, что ошиблась, потому что "в книжке" совсем другое решение, намного более сложное. Если бы моё было верно, "они" бы быстрее додумались до моего, чем до опубликованного там.

[ИСН]

Нет, тамошнее как раз проще, но зато оно не обобщаемо на бесконечный случай.

[TOTAL]

$a_1=2, a_{n+1}=1+(a_1 + \cdots + a_n)^2$

[Xenia1996]

ИСН в сообщении #416607 писал(а):

Нет, тамошнее как раз проще, но зато оно не обобщаемо на бесконечный случай.

(Проще?)

Не соблаговолите ли уточнить, чем именно?

Мало того, что существует бесконечное множество требуемых чисел, так ещё и существует бесконечное множество таких непересекающихся бесконечных множеств ("нечётные" степени тройки, пятёрки, семёрки ...)!

-- Чт фев 24, 2011 14:34:15 --

TOTAL в сообщении #416611 писал(а):

$1+4^n$

При любом n?

[ИСН]

Xenia1996 в сообщении #416612 писал(а):

Не соблаговолите ли уточнить, чем именно?

Извольте. Понятие "я делюсь на p один раз, потому я не квадрат" проще, чем понятие "я делюсь на кого-то там в нечётной степени..." (которое является его обобщением).
Мелочь, конечно.
Или, если угодно - тот вариант потому проще, что в нём задействованы меньшие числа (порядка $2011^3$, а не $4^{2011}$).
Но Ваш вариант зато лучше тем, что вот да, бесконечность.

[Xenia1996]

ИСН в сообщении #416615 писал(а):

Xenia1996 в сообщении #416612 писал(а):

Не соблаговолите ли уточнить, чем именно?

Извольте. Понятие "я делюсь на p один раз, потому я не квадрат" проще, чем понятие "я делюсь на кого-то там в нечётной степени..." (которое является его обобщением).
Мелочь, конечно.
Или, если угодно - тот вариант потому проще, что в нём задействованы меньшие числа (порядка $2011^3$, а не $4^{2011}$).
Но Ваш вариант зато лучше тем, что вот да, бесконечность.

(Оффтоп)

Теоретически у нас 30 тыс. долларов Вы правы, а практически - полный дом куртизанок моё решение поймёт любой пятиклассник (точнее, любой, кто знает, что такое степень)

[ИСН]

(Оффтоп)

Ну, наверное, да.

[svv]

Могу добавить, что Ваше решение понравится программерам: у сумм будут единицы только в битах с нечетными номерами (считая с 0).

[Xenia1996]

svv в сообщении #416622 писал(а):

Могу добавить, что Ваше решение понравится программерам: у сумм будут единицы только в битах с нечетными номерами (считая с 0).

(Оффтоп)

Я так понимаю, мы одним махом две задачи решили.
Выходит, любой квадрат натурального числа обязан иметь хотя бы одно несоответствие между чётностью бита и чётностью его номера?

[svv]

Да. Если имеется хотя бы два бита, и четность бита равна четности его номера, то двоичная запись заканчивается на ...10. Тогда остаток от деления на 4 равен 2 -- значит, не квадрат.

Двоичная запись квадратов последовательных натуральных чисел попеременно заканчивается на ...00 и ...01. Как видите, вариант ...11 тоже исключается.
Иначе говоря, остаток от деления квадрата на 4 может быть только 0 (квадрат четного числа) и 1 (нечетного).
Стало быть, у квадрата в первом бите всегда 0.

[Xenia1996]

svv в сообщении #416662 писал(а):

Да. Если имеется хотя бы два бита, и четность бита равна четности его номера, то двоичная запись заканчивается на ...10. Тогда остаток от деления на 4 равен 2 -- значит, не квадрат.

Двоичная запись квадратов последовательных натуральных чисел попеременно заканчивается на ...00 и ...01. Как видите, вариант ...11 тоже исключается.
Иначе говоря, остаток от деления квадрата на 4 может быть только 0 (квадрат четного числа) и 1 (нечетного).
Стало быть, у квадрата в первом бите всегда 0.

С точки зрения арифметики, это элементарно. Просто никогда не смотрела на эти вещи "под углом информатики".

[svv]

svv писал(а):

остаток от деления квадрата на 4 может быть только 0 (квадрат четного числа) и 1 (нечетного)

Xenia1996, посмотрите, как это наблюдение позволило элементарно решить проблему $n!-1=N^2$ в соседней теме.