4-RMMS, №4

[MrDindows]

Дано натуральное $n=\prod\limits_{i=1}^s p_i^{a_i}$, ($p_i$ - различные простые делители) обозначим $g(n)=\sum\limits_{i=1}^s a_i$. $f(n)=(-1)^{g(n)}$.
Например $f(12)=f(2^2\cdot3^1)=(-1)^{2+1}=-1$
Доказать:
1) Существует бесконечно много таких $n$, что $f(n)=f(n+1)=1$
2) Существует бесконечно много таких $n$, что $f(n)=f(n+1)=-1$

Задача с "THE 4th ROMANIAN MASTER OF MATHEMATICS COMPETITION", №4.
Оригинал

(Моё решение)

Во первых $f(ab)=f(a)\cdot f(b)$
1) Предположим что таких $n$ - ограниченое число, тогда для всех $k$, которые больше чем наибольшее $n$, должно выполняться условие: $f(k^2-1)=-1$, $f(k^2+1)=-1$, так как$ f(k^2)=1$ для всех $ k$. Но тогда $f((k^2-1)(k^2+1))=f(k^4-1)=-1 \cdot(-1)=1$, А значит пара $(k^4, k^4-1)$ удовлетворяет условие, что противоречит выбору $k$ и нашему предположению. Значит оно не верно, что и требовалось доказать.
2) Предположим что таких $n$ - ограниченное число, тогда выберем наибольшее $n$, такое что $f(n)=f(n-1)=-1$ . Рассмотрим пару $n^3, \ n^3-1$ . $f(n^3)=-1$. Значит из предположения $f(n^3-1)=1$.
Тоесть $f(n^3-1)=f((n-1)(n^2+n+1))=-1\cdot f(n^2+n+1)=1$ . Значит $f(n^2+n+1)=-1$.
Но $f(n^2+n)=f(n(n+1))=-1\cdot 1=-1$. Значит пара чисел $(n^2+n, \ n^2+n+1)$ удовлетворяет условие, но ,так как она очевидно больше выбранной, это противоречит нашему предположению. Значит оно не верно,что и требовалось доказать.

Всё верно?)

[Equinoxe]

Мне непонятно, почему должно быть $f(k^2 - 1) = -1$.
Ведь мы не против случая двух подряд идущих -1, а у них $f(k^2-1)=1$.

И проверьте $(3^4, 3^4 - 1)$ — ведь получается $4$ и $f(2^4*5) = 5$
Мне непонятно даже, почему $f(n^3)=-1$, это по-моему противоречит здравому смыслу, ведь $f(n^2)=1$, тогда это утверждение аналогично тому, что у всех чисел нечетное g(n)

[Sonic86]

По-моему, правильно...

[staric]

К чему огород городить?

(Оффтоп)

Для -1 достаточно рассмотреть простые и соседние четные (при необходимости - поделить их на 2),
для 1 числа вида 3р и соседние четные...

[Equinoxe]

staric, это почему? Мне совершенно неочевидно, что у соседних 3p и вообще p будет какое-то конкретное g(n)
MrDindows, а насчет 1-ого извините, всё верно, может быть и во втором я ошибаюсь, сейчас проверю

-- Вс мар 06, 2011 15:12:08 --

И во втором тоже всё верно :)

[staric]

Equinoxe, не понял - есть сомнения в разложимости на множители 3р+1, 3р-1, или в f(3р)=1?
Или вообще суть не ясна?

(Оффтоп)

Если f(3p-1)=1 или f(3p+1)=1, имеем пару, если обе -1, то f((3p-1)/2)= f((3p+1)/2)=1.

[Equinoxe]

staric, да, была неясна сама идея, оффтоп всё объяснил, красиво :)

[MrDindows]

staric в сообщении #419913 писал(а):

Equinoxe, не понял - есть сомнения в разложимости на множители 3р+1, 3р-1, или в f(3р)=1?
Или вообще суть не ясна?

(Оффтоп)

Если f(3p-1)=1 или f(3p+1)=1, имеем пару, если обе -1, то f((3p-1)/2)= f((3p+1)/2)=1.

Прикольно. Но только у меня ни чуть не сложнее, имхо. Вместо $3p$ взял $k^2$ и расписал по-подробнее.

[staric]

Согласен, суть та же, просто Equinoxe так напугали ваши разложения... Я решил, делить на 2 проще.