НГУ

Форумы НГУ
Текущее время: Ср окт 23, 2019 7:43 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 09, 2007 8:44 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Да нет же.

Пусть P = \exists X: одновременно X, X+1 и X+2 не делятся на 3.

Твоё рассуждение выглядит так. Пусть P истинно, тогда предположим, что существует минимальный такой X, и придём к противоречию. Следовательно, не существует минимального X. То есть, в условиях истинности P количество таких троек бесконечно.

А исходный вопрос состоит как раз в том, истинно P или ложно.

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 09, 2007 10:19 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
fenster писал(а):
ConWor писал(а):
Пусть существуют некое минимальное X, такое, что X, X+1, X+2 не делятся на три. Тогда X-1 не делится на три (иначе X+2 делится на три). Ну а это противоречие с минимальностью X, так как X-1, X, X+1 не делятся ни три.

Это лишь доказывает, что если найдётся хотя бы одна тройка (x, x+1, x+2) такая, что все три числа не делятся на три, то существует бесконечное и неограниченное снизу множество таких троек (вспомним, что существуют отрицательные числа). Это несомненно полезное утверждение, но автору задачи требуется доказать несколько другое :)


Ну, если воспринимать задачу как задачу о натуральных числах, то неограниченного снизу множества троек быть не может и ConWor прав на все 100. А если считать, что задача поставлена для целых чисел, то доказательство ConWor'а будет верным, когда мы заменим

ConWor писал(а):
Пусть существуют некое минимальное X, такое, что X, X+1, X+2 не делятся на три. Тогда X-1 не делится на три (иначе X+2 делится на три). Ну а это противоречие с минимальностью X, так как X-1, X, X+1 не делятся ни три.


на

ConWor писал(а):
Пусть существуют некое X с минимальным модулем такое, что X, X+1, X+2 не делятся на три. Непосредственная проверка подтверждает, что X не равен 0 и -1. Если X < -1, то числа -(X+2), -(X+2)+1 = -(X+1) и -(X+2)+2 = -X не делятся на 3, чего не может быть, так как | -(X+2) | < | X |. Пусть, наконец, X > 0. Тогда X-1 не делится на три (иначе X+2 делится на три). Ну а это противоречие с минимальностью X, так как X-1, X, X+1 не делятся ни три.


Мою индукцию в этом случае тоже надо переписать. То есть сделать что-то вроде

----------------------

Теорема Для любого целого числа n одно из чисел n, n+1, n+2 делится на 3.

Доказательство Индукция по n.

База. При n = 0 число n делится на 3 и одновременно является элементом множества { n, n+1, n+2 } = { 0, 1, 2 }.

Шаг индукции. Пусть одно из чисел n, n+1, n+2 делится на 3.

Если n делится на 3, то n+3 также делится на 3. Если же n не делится на 3, то на 3 делится либо n+1, либо n+2. В обоих случаях одно из чисел n+1, (n+1)+1 = n+2, (n+1)+2 = n+3 делится на 3.

Если n+2 делится на 3, то n-1 также делится на 3. Если же n+2 не делится на 3, то на 3 делится либо n, либо n+1. В обоих случаях одно из чисел n-1, (n-1)+1 = n, (n-1)+2 = n+1 делится на 3.

Таким образом, если для какого-то n выполняется утверждение теоремы, то оно выполняется также для n+1 и n-1.

Конец доказательства.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Последний раз редактировалось Коба Пн апр 09, 2007 6:17 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 09, 2007 10:32 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт сен 02, 2005 12:59 pm
Сообщения: 1421
Откуда: Владимир
Какая трудная задача =)
А секвенцию кто-нить пробует доказать?

_________________
А мы гуляли, пели, шли своей тропой. Мы открывали двери, хоть вход был запрещен. Мы шли в огонь.
Знай, паскуда, вольных, знай!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 09, 2007 10:35 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт сен 02, 2005 12:59 pm
Сообщения: 1421
Откуда: Владимир
fenster писал(а):
Да нет же.

Пусть P = \exists X: одновременно X, X+1 и X+2 не делятся на 3.

Твоё рассуждение выглядит так. Пусть P истинно, тогда предположим, что существует минимальный такой X, и придём к противоречию. Следовательно, не существует минимального X. То есть, в условиях истинности P количество таких троек бесконечно.

А исходный вопрос состоит как раз в том, истинно P или ложно.

Если мы преполагаем, что P истинно, то нам не нужно предполагать существование минимального, оно следует из истинности P в той форме, в которой написал Коба, просто действительно нужно добавить рассуждения о модулях, но я это в неявной форме написал:
ConWor писал(а):
А то, что можно взять минимальный X (разумеется, положительный), понятно из двух причин: если есть отрицательная тройка чисел, неделящихся на три, то есть и положительная.

_________________
А мы гуляли, пели, шли своей тропой. Мы открывали двери, хоть вход был запрещен. Мы шли в огонь.
Знай, паскуда, вольных, знай!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 01, 2007 6:25 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
irchona писал(а):
Ну да в принципе, просто когда большие числа, как-то это подозрительно... :-?

Отнюдь. Теорема Дирихле гласит, что вероятность того, что два наугад выбранных натуральных числа окажутся взаимно-простыми, равна 6/pi^2 ~= 0.608...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт авг 02, 2007 2:29 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
maxal писал(а):
Теорема Дирихле гласит, что вероятность того, что два наугад выбранных натуральных числа окажутся взаимно-простыми, равна 6/pi^2 ~= 0.608...


А как вероятность считается? Для каждого n берётся количество пар взаимно простых, не превосходящих n, делится на n^2 и вычисляется предел при n стремящемся к бесконечности? Или как-то иначе?

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс авг 05, 2007 3:28 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Коба писал(а):
maxal писал(а):
Теорема Дирихле гласит, что вероятность того, что два наугад выбранных натуральных числа окажутся взаимно-простыми, равна 6/pi^2 ~= 0.608...


А как вероятность считается? Для каждого n берётся количество пар взаимно простых, не превосходящих n, делится на n^2 и вычисляется предел при n стремящемся к бесконечности?

Да. Детали можно посмотреть, например, в книжке
П.Ноден, К.Китте "Алгебраическая Алгоритмика"


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июн 11, 2008 11:04 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июн 11, 2008 10:27 pm
Сообщения: 1
irchona писал(а):
Как доказать, что из трех последовательных натуральных чисел одно делится на 3???


Как вариант.

Предположим, что ни одно из трех натуральных чисел: (n-1); n; (n+1) не делится на 3.
Тогда произведение (n-1)n(n+1) = n(n^2-1) также не должно делиться на 3.

Если n не делится на 3, то n^2 имеет остаток +1 по основанию 3 и, следовательно, выражение (n^2-1) кратно 3.
Противоречие.

p.s. Аналогично, рассматривая числа (n-2); n; (n+2), доказывается, что одно из трех последовательных натуральных четных (или нечетных) чисел делится на 3.
В общем случае, это справедливо для любых трех чисел, "отстоящих" друг от друга на равных расстояниях, не кратных 3.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB