C6

[Новый гость]

Пожалуйста, помогите.
Задача из книги "Математика. Подготовка к ЕГЭ. Учебно-тренировочные тесты" (под редакцией Ф. Ф. Лысенко, С. Ю. Кулабухова):
`TZ`На доске написано число 2009. Каждый шаг мы стираем все числа с доски и на место каждого числа n пишем 2 числа: n^3+1 и Зn - 1. Будет ли шаг, когда все числа на доске станут взаимно просты с 3? Если станут, то на каком шаге?[[/TZ]]
Если эта задача уже обсуждалась, то дайте ссылку, или посоветуйте, как решать такие задачи.
Заранее спасибо.

@темы: Олимпиадные задачи, ЕГЭ, Теория чисел

Comments

[_ТошА_]

а вы знаете признак делимости на 3?

[Новый гость]

Число делится на 3, если сумма цифр числа делится на три.

[Диана Шипилова]

Подумайте, какие остатки при делении на 3 будут у полученных чисел.

[Новый гость]

От деления числа 2009 на 3 остаток будет 2. Если число Зn - 1 при n=2009 разделить на 3, остаток будет 2. А вот число n^3+1 - неужели 2009 и последующие огромные числа нужно будет возводить в куб?

[Диана Шипилова]

Новый гость
Не нужно, мы говорим только об остатках.

[Новый гость]

А есть специальный метод, позволяющий их найти, не проводя вычислений? Если есть, то какой?

[Диана Шипилова]

Новый гость
Да, есть раздел в математике, так называемая теория сравнений. Мы скажем: 2009 сравнимо с 2 по модулю 3, тогда 2009³ + 1 сравнимо с 2³ + 1, то есть с 0, по модулю 3.
Это все можно расписать и стандартным школьным способом, через остатки.

[Новый гость]

А что даёт знание остатков?

[Диана Шипилова]

Новый гость
Будут ли на шаге №1 все числа взаимно просты с 3?
А на шаге №2?
А дальше?

[Новый гость]

На первом шаге вроде бы да: 2009 не имеет с 3 никаких общих делителей, кроме 1 и -1

[Новый гость]

Однако в ответе сказано, что это не произойдёт ни на каком шаге...

[Новый гость]

Однако в ответе сказано, что это не произойдёт ни на каком шаге...

[_ТошА_]

Однако в ответе сказано, что это не произойдёт ни на каком шаге...

я так понимаю, что 1 шаг надо сделать как минимум. То, что 2009 взаимнопросто с 3 ничего не даёт

[Новый гость]

Первый шаг. При n=2009 число n^3+1 делится на 3, а Зn - 1 не делятся на 3.

[_ТошА_]

ну дальше делайте

[Новый гость]

Если бы я знал, как делать...

[_ТошА_]

Почитайте какую-нибудь литературу по т.ч. Можно ещё полной индукцией пройтись

[Новый гость]

То есть решение этой задачи можно найти в какой-нибудь книге? Эта задача - не изобретение Лысенко

[_ТошА_]

не знаю, стандартная ли она, но зная основы теории чисел она решается без проблем

[_ТошА_]

Вот смотрите. Давайте проведём полную индукцию. Любое число `n in Z` можно представить в виде: n = 3k, n = 3k + 1, n = 3k + 2
Мы смотрим делимость на 3.
Посмотрим на `n^3 + 1`
1) ] n = 3k
`(3k)^3 + 1` => ост. 1
2) ] n = 3k + 1
`(3k+1)^3 + 1` => ост. 2
3) ] n = 3k + 2
`(3k+2)^3 + 1` => ост. 0 (делится нацело)

Посмотрим на `3n - 1`
1) ] n = 3k
`9k - 1` => ост. 2
2) ] n = 3k+1
`9k + 2` => ост. 2
3) ] n = 3k + 2
`9k + 5` => ост. 2

и что мы видим? Какое бы число мы не засунули в 3n - 1, у нас всегда будет остаток от деления на 3 равен 2.

[Новый гость]

2009 относится к третьему типу, поэтому число n^3 + 1 будет делиться на 3. Значит, чтобы все числа были взаимно просты с 3, нужно, чтобы получающиеся числа n^3 + 1 относились к первому и второму типу. Но так как в ответе сказано, что это не произойдёт ни на каком шаге, значит, все числа вида n^3 + 1 должны относиться к третьему типу, т.е. (n^3 + 1)=3k + 2. Как это можно доказать? Нужно ли при этом учитывать, что самое первое n=2009?

[_ТошА_]

Заметим, что когда мы используем 3k - 1, у нас всегда остаток равен двум. А значит число, получившееся, представимо в виде n = 3k+2. А значит `n^3 + 1` от этого числа всегда будет делиться на 3 (показано выше).
А так как по условию Каждый шаг мы стираем все числа с доски и на место каждого числа n пишем 2 числа: n^3+1 и Зn - 1. , то заместо числа, полученного из 3n - 1 мы всегда будем получать 2 числа, одно из которых делится на 3.

[Новый гость]

Всё-таки не могу до конца понять решение. Как доказать, что при замене числа n на числа n^3+1 и Зn - 1 мы обязательно получим число вида 3k+2?

[_ТошА_]

Подставляя абсолютно любое число в 3n - 1, мы получим число 3k + 2
Но число вида 3k + 2, подставляя в n^3 + 1 делится на 3 нацело, отсюда всегда будет вылезать хотя бы одно число, невзаимнопростое с 3

[Новый гость]

Ладно, попробую начать сначала.
1. Самое первое и единственное n равно 2009. 2009 при делении на 3 даёт остаток 2. Поэтому число 2009 имеет вид 3k + 2.
2. Первый шаг: число 3k + 2 заменяю двумя числами:
2.1. (3k+2)^3 + 1. Число (3k+2)^3 + 1, если раскрыть скобки и привести подобные слагаемые, будет иметь вид 3k.
2.2. 3(3k+2)-1. Число 3(3k+2)-1 , если раскрыть скобки и привести подобные слагаемые, будет иметь вид 3k + 2.
На первом шаге невозможно получить, все числа, взаимно простые с 3. Вывод: при замене числа вида 3k + 2 в соответствии с условиями мы не получим нужного нам результата (т.е. чтобы все числа не делились на 3).
Замена числа 3k + 2 - тупиковая ветвь.
3. У нас ещё есть число вида 3k. Если заменять его, то мы получим числа:
3.1. (3k)^3 + 1=27k^3+1. Это число при делении на 3 даст остаток 1. Т.е. число (3k)^3 + 1 имеет вид 3k + 1.
3.2. 9k-1. Данное число имеет вид 3k + 2. (как это можно объяснить?)
4. Возможный путь получения нужного результата (когда все числа на доске станут взаимно просты с 3) таков:
Итак, после первого шага мы записали числа вида: 3k и 3k + 2.
На втором шаге заменяем число 3k на числа вида 3k + 1 и 3k + 2.
Таким образом, на доске будут три числа, взаимно простые с 3: 3k + 1, 3k + 2 (полученные после второго шага) и 3k + 2 (которое осталось ещё с первого шага).
Учитывая вышеизложенное, ответим на вопросы задачи:
Будет ли шаг, когда все числа на доске станут взаимно просты с 3?
Да, будет.
Если станут, то на каком шаге?
На втором.
Открываю книгу "Математика. Подготовка к ЕГЭ-2010. Учебно-тренировочные тесты под редакцией Лысенко, Кулабухова", убеждаюсь, что данная задача С6 переписана правильно из 3-го варианта, смотрю в ответ и вижу: "Такого шага не будет".
В чём же ошибка? Помогите, пожалуйста, разобраться с этой задачей.

[Диана Шипилова]

3.2. 9k-1. Данное число имеет вид 3k + 2. (как это можно объяснить?)

`9k - 1 = 3*3k - 1 = 3*(3k - 1) + 2`

[Диана Шипилова]

На втором шаге заменяем число 3k на числа вида 3k + 1 и 3k + 2.

По условию на каждом шаге мы заменяем все числа.

[_ТошА_]

как у вас такое получилось то?
Значит изначально на доске:
1) 3k + 2
Стираем, пишем:
2) 3k (из `n^3 + 1`) и 3k + 2 (из 3n - 1) далее буду писать жирным числа, что получились после `n^3 + 1` и курсивным после `3n - 1`
Стираем, на месте каждого получаем ещё 2 пары:
3) 3k + 1, 3k + 2 (из первого числа, что стрли). 3k , 3k + 2 (из второго числа, что стёрли)

[_ТошА_]

Диана Шипилова спасибо

[Новый гость]

А, ясно!
То есть в каждом шаге обязательно будут появляться числа 3k (не взаимно простое с 3) и 3k + 2, из которого в следующем шаге получатся числа такого же вида, одно из которых будет делиться на 3. Следовательно, мы ни на каком шаге не получим нужный результат.
Огромное спасибо всем, кто объяснял, как решать.