Поиск взаимно простых (или нечто в этом роде)

[Xenia1996]

Найдите наибольшее k такое, что для любого натурального n найдётся по крайней мере k чисел, являющихся элементами множества \{n+1, n+2, \dots , n+16\}, взаимно простых с n(n+17)

(Попыталась попытаться)

Может, я условие задачи не поняла, но у меня в ответе вышла единичка.
При n=15015=3\cdot5\cdot7\cdot11\cdot13 только 15016 будет взаимно простым с 15015\cdot15032

Нуль получить, по-моему, невозможно.
Действительно, n+1 обязано быть взаимно простым с n, следовательно должно иметь общий делитель с n+17 (и делитель этот должен быть чётным), значит n+17 - чётное число.
С другой стороны, n+16 обязано быть взаимно простым с n+17, следовательно должно иметь общий делитель с n (и делитель этот должен быть чётным), значит n - чётное число.

Но n+17 и n могут быть оба чётными только в сказке.
Противоречие.

Но меня по-прежнему не оставляет ощущение того, что я неправильно поняла условие задачи.

[MrDindows]

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

Найдите наибольшее k такое, что для любого натурального n найдётся по крайней мере k чисел, являющихся элементами множества \{n+1, n+2, \dots , n+16\}, взаимно простых с n(n+17)

(Попыталась попытаться)

Может, я условие задачи не поняла, но у меня в ответе вышла единичка.
При n=15015=3\cdot5\cdot7\cdot11\cdot13 только 15016 будет взаимно простым с 15015\cdot15032

Нуль получить, по-моему, невозможно.
Действительно, n+1 обязано быть взаимно простым с n, следовательно должно иметь общий делитель с n+17 (и делитель этот должен быть чётным), значит n+17 - чётное число.
С другой стороны, n+16 обязано быть взаимно простым с n+17, следовательно должно иметь общий делитель с n (и делитель этот должен быть чётным), значит n - чётное число.

Но n+17 и n могут быть оба чётными только в сказке.
Противоречие.

Но меня по-прежнему не оставляет ощущение того, что я неправильно поняла условие задачи.

Разве $15016$ взаимно просто с 15015\cdot15032:??
Помоему $15017, 15019, 15023, 15031$ взаимнопросты с 15015\cdot15032
Так что условие вы поняли правильно, а вот решение - не верное)

[venco]

В принципе правильно, только пример плохой - в нём 4 взаимно-простых.

[Xenia1996]

MrDindows в сообщении #408427 писал(а):

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

Найдите наибольшее k такое, что для любого натурального n найдётся по крайней мере k чисел, являющихся элементами множества \{n+1, n+2, \dots , n+16\}, взаимно простых с n(n+17)

(Попыталась попытаться)

Может, я условие задачи не поняла, но у меня в ответе вышла единичка.
При n=15015=3\cdot5\cdot7\cdot11\cdot13 только 15016 будет взаимно простым с 15015\cdot15032

Нуль получить, по-моему, невозможно.
Действительно, n+1 обязано быть взаимно простым с n, следовательно должно иметь общий делитель с n+17 (и делитель этот должен быть чётным), значит n+17 - чётное число.
С другой стороны, n+16 обязано быть взаимно простым с n+17, следовательно должно иметь общий делитель с n (и делитель этот должен быть чётным), значит n - чётное число.

Но n+17 и n могут быть оба чётными только в сказке.
Противоречие.

Но меня по-прежнему не оставляет ощущение того, что я неправильно поняла условие задачи.

Разве $15016$ взаимно просто с 15015\cdot15032:??
Помоему $15017, 15019, 15023, 15031$ взаимнопросты с 15015\cdot15032
Так что условие вы поняли правильно, а вот решение - не верное)

Ой, ч#рт!
Ну тогда вообще нуль получается...

-- Ср фев 02, 2011 23:14:29 --

Нет, не нуль. Правильный ответ - единичка, только надо было мне взять 30030, а я перепутала.

[MrDindows]

Нет не нуль=)
И $30030$ тоже не прокатывает.
Ибо $30041$ и $30031$ взаимо просты с $30030*30047$

-- Ср фев 02, 2011 23:29:45 --

И всё-таки нет=) Ответ $k=1.$
Для этого возьмём число, которое даёт остатки:
$1 \ mod \ 2, \ 9 \ mod \ 13, \ 5 \ mod \ 11, \ 1 \ mod \ 9, \ 4 \ mod \ 7, \ 3 \ mod \ 5. $
Согласно Китайской теореме об остатках( если я не ошибаюсь), такое число существовать будет.
И несложно убедиться, что только $n+16$ будет взаимопросто с $n(n+17)$

[MrDindows]

Ошибся, $30030 $подходит =)
Ну будем считать что я рассмотрел случай нечётного $n$

[Simba]

у меня вопрос: мы ищем ведь максимум, тогда почему ответ ,скажем, не 2?

[Xenia1996]

Simba в сообщении #408558 писал(а):

у меня вопрос: мы ищем ведь максимум, тогда почему ответ ,скажем, не 2?

Максимум какой именно величины?
Вы условие задачи внимательно прочли?

[Simba]

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

Максимум какой именно величины?Вы условие задачи внимательно прочли?

Ах да, все ясно, с этим примером не сразу разобрался, простите за мою глупость, обещаю, я буду стараться делаться умней

[Xenia1996]

Simba в сообщении #411069 писал(а):

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

Максимум какой именно величины?Вы условие задачи внимательно прочли?

Ах да, все ясно, с этим примером не сразу разобрался, простите за мою глупость, обещаю, я буду стараться делаться умней

А Вы думаете, я условие сразу поняла? Это они спецом намеренно нас запутывают