Количество составных чисел в последовательности

[Xenia1996]

Даны числа:

$11, 101, 1001, 10001, \dots , 10^k+1, \dots , 10^{2011}+1$

Доказать, что среди этих чисел

а) не менее 300 составных
б) не менее 2000 составных

Пункт а) мне понятен. Каждое шестое число указанного вида делится на 7. Это следует из арифметики остатков, получаемых при делении степеней десятки на 7: $3, 2, 6, 4, 5, 1$.

В пункте б) если воспользоваться суммой кубов (например, $1001=10^3+1^3$, следовательно, делится на 10+1=11), можно получить 670 составных чисел, но до 2000 всё равно не дотягивает. Нужна нестандартная идея, или я просто о чём-то забыла?

[zhekas]

каждое второе делится на 11

[Xenia1996]

zhekas в сообщении #429593 писал(а):

каждое второе делится на 11

И что? Всё равно не 2000.

[zhekas]

ну уже и не 670

[ИСН]

Тут надо подумать о простых числах Ферма и о том, почему их стали искать в таком виде.
В сущности, все экземпляры, у которых показатель не степень двойки, на что-нибудь да делятся.

[Xenia1996]

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

Тут надо подумать о простых числах Ферма и о том, почему их стали искать в таком виде.
В сущности, все экземпляры, у которых показатель не степень двойки, на что-нибудь да делятся.

Числа Ферма - это степени двойки плюс единичка, а не степени десятки. Или есть связь?

[ИСН]

Не то чтобы связь, но аналогия прямая.

[Xenia1996]

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

Не то чтобы связь, но аналогия прямая.

А то, что $a^{2k+1}+b^{2k+1}$ делится на a+b, это надо доказывать? Если нет, то я догадалась, как решить.

[ИСН]

Вот-вот.

[Xenia1996]

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

Вот-вот.

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

[ИСН]

Ой, ну если есть лишнее время, можете доказать по индукции, там просто.

[MrDindows]

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

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

Не то чтобы связь, но аналогия прямая.

А то, что $a^{2k+1}+b^{2k+1}$ делится на a+b, это надо доказывать? Если нет, то я догадалась, как решить.

Имхо, доказывать это не надо, достаточно только показать, что это следует из того, что:
$a^{2k+1}+b^{2k+1}=(a+b)(a^{2k}-a^{2k-1}b+...-ab^{2k-1}+b^{2k})$