Доказательство попарной взаимной простоты

[Ktina]

Правомерно ли применение "детского" арифмоста для решения следующей задачи?

======
Задача:

Пусть

а) $f(x)=x^2-x+1$

б) $f(x)=x^3-x+1$

(пункт б) возник в силу разнящихся версий - в одной книге так, а в другой иначе, хотя речь идёт об одной и той же олимпиаде, Всесоюзке-1978)

Доказать, что для любого натурального $m>1$ числа $m, f(m), f(f(m)), f(f(f(m))), \dots$ попарно взаимопросты.
======

Попытка:

Я применила арифмост для пятого класса (вроде, годится для обоих пунктов). Пусть среди чисел $m, f(m), f(f(m)), f(f(f(m))), \dots$ найдутся два числа, А и Б (причём А "левее" Б), имеющие общий натуральный делитель $n>1$. Тогда остаток при делении $f(A)$ на $n$ равен 1, как и остаток при делении чисел $f(f(A)), f(f(f(A))), \dots$ на $n$. Но среди упомянутых чисел должно встретиться Б, которое делится на $n$.
Противоречие.

Неужели авторами задачи подразумевалось столь элементарное решение?
Или это в моём решении баги?

[nnosipov]

Ktina в сообщении #561459 писал(а):

Неужели авторами задачи подразумевалось столь элементарное решение?

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

[Cash]

Решение правильное, авторское тоже несложное - использует тот факт, что у получаемых многочленов свободный член равен 1, а значит $f^k(m)$ взаимно прост с $m$ для целых $k>0$ и $m>1$
И, поскольку $f^{k+n}(m)=f^k(f^n(m))$, то $f^{k+n}(m)$ взаимно просто с $f^n(m)$
По мне - ваше нагляднее.
Задача - первая для 10 класса, потому несложная

[Ktina]

nnosipov в сообщении #561510 писал(а):

Ktina в сообщении #561459 писал(а):

Неужели авторами задачи подразумевалось столь элементарное решение?

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

В книге Васильева решение идентично тому, что Cash показал.
А в книге Купцова решение на целую страницу.

-- 18.04.2012, 16:25 --

Cash в сообщении #561513 писал(а):

Задача - первая для 10 класса, потому несложная

В те времена 10-й класс был последним.

[Cash]

(Оффтоп)

Цитата:

В книге Васильева решение идентично тому, что Cash показал.

Еще бы - оттуда и содрал

[nnosipov]

Целая страница --- это явно много.

(Оффтоп)

Кстати, уже на следующей неделе финал Всероссийской олимпиады.

[Cash]

Цитата:

В те времена 10-й класс был последним.

Кто-то говорил, что самые сложные задачи на всесоюзке - за 9-й класс. 8-й и 10-й на порядок легче. Не помню сейчас, чем обосновывали, но одна из причин - по результатам 9-го класса отбирали и готовили на Международную.

[Ktina]

Cash в сообщении #561521 писал(а):

Цитата:

В те времена 10-й класс был последним.

Кто-то говорил, что самые сложные задачи на всесоюзке - за 9-й класс. 8-й и 10-й на порядок легче. Не помню сейчас, чем обосновывали, но одна из причин - по результатам 9-го класса отбирали и готовили на Международную.

Сиречь, олимпиада для 9-го класса была чем-то вроде TST?

-- 18.04.2012, 16:48 --

Cash в сообщении #561513 писал(а):

...первая для 10 класса, потому несложная

Кстати, если верить книге Купцова, задача эта - третья для 10-го класса, а не первая. Ну и вместо квадрата там куб. А олимпиада, вроде, та же. Странные вещи происходят

[Cash]

(Оффтоп)

Не знаю, что такое TST, а google выдает
Tsim Sha Tsui (English pronunciation: /ˌtsɪm ˌʃɑː ˈtsuː.iː or ˌtʃɪm ˌʃɑː ˈtʃuː.iː/, often abbreviated as TST, is an urban area in southern Kowloon, Hong Kong. The area is administratively part of the Yau Tsim Mong District.

Я бы Васильеву верил, у него на обложке - Знак Качества нарисован

[Ktina]

Cash в сообщении #561534 писал(а):

(Оффтоп)

Не знаю, что такое TST, а google выдает
Tsim Sha Tsui (English pronunciation: /ˌtsɪm ˌʃɑː ˈtsuː.iː or ˌtʃɪm ˌʃɑː ˈtʃuː.iː/, often abbreviated as TST, is an urban area in southern Kowloon, Hong Kong. The area is administratively part of the Yau Tsim Mong District.

Я бы Васильеву верил, у него на обложке - Знак Качества нарисован

(Оффтоп)

TST - это Team Selection Test.

Коль уж задача оказалась тривиальной, давайте обобщим (но немножко переделаем)?

Пусть $P(x)$ - многочлен с целочисленными коэффициентами, принимающий взаимопростые значения при некоторых двух различных целочисленных аргументах.

Доказать, что существует бесконечное множество целых чисел, при которых $P(x)$ принимает попарно взаимопростые значения.

[nnosipov]

Ktina в сообщении #561540 писал(а):

Пусть $P(x)$ - многочлен с целочисленными коэффициентами, принимающий взаимопростые значения при некоторых двух различных целочисленных аргументах. Доказать, что существует бесконечное множество целых чисел, при которых $P(x)$ принимает попарно взаимопростые значения.

Можно считать, что $\gcd{(P(0),m)}=1$, где $m$ --- некоторое число. А дальше те же рассуждения относительно последовательности $m$, $P(m)$, $P(P(m))$, ...

[Cash]

(Оффтоп)

Цитата:

Сиречь, олимпиада для 9-го класса была чем-то вроде TST?

Тут разница принципиальная. Team Selection Test - окончательный этап в отборе, а всесоюзная олимпиада - только начало

[Ktina]

nnosipov в сообщении #561545 писал(а):

Ktina в сообщении #561540 писал(а):

Пусть $P(x)$ - многочлен с целочисленными коэффициентами, принимающий взаимопростые значения при некоторых двух различных целочисленных аргументах. Доказать, что существует бесконечное множество целых чисел, при которых $P(x)$ принимает попарно взаимопростые значения.

Можно считать, что $\gcd{(P(0),m)}=1$, где $m$ --- некоторое число. А дальше те же рассуждения относительно последовательности $m$, $P(m)$, $P(P(m))$, ...

В принципе, не намного сложнее получилось. Если не сказать "та же задача".

[Cash]

Цитата:

Можно считать, что $\gcd{(P(0),m)}=1$, где $m$ --- некоторое число. А дальше те же рассуждения относительно последовательности $m$, $P(m)$, $P(P(m))$, ...

А где в этом решении используется то, что НОД коэффициентов равен 1?

-- Ср апр 18, 2012 20:14:17 --

Или $m$ выбирается каким-то весьма специфическим образом? Все равно не пойму.
Пусть $P(x) = 2x^2+2$, $m=3$ и как пройдут рассуждения?

[nnosipov]

Cash в сообщении #561558 писал(а):

Пусть $P(x) = 2x^2+2$, $m=3$ и как пройдут рассуждения?

Но такой многочлен не удовлетворяет условию.