Автор Тема: Задача Эйнштейна и другие...  (Прочитано 488593 раз)

0 Пользователей и 6 Гостей просматривают эту тему.

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1395 : 22 Декабрь 2016, 20:45:05 »
Похожую задачу я вроде когда-то здесь решил, применяя принцип Дирихле (“кролики в клетках”). :)
Рассмотрим вначале бесконечную последовательность 33333…
2017 - простое число (это будет важно в дальнейшем), и при делении фрагментов этой последовательности на 2017 число остатков конечно и равно 2016 (не считая нулевой остаток, то есть деление нацело). Значит, среди этих фрагментов наверняка найдутся два (а на самом деле - сколько угодно), которые при делении на 2017 дадут одинаковый остаток. Обозначим большее из этих чисел через M, а меньшее через N. Тогда число (M – N), которое можно представить в виде 3333…000…, будет нацело делиться на 2017. Эту разность можно представить в виде 3333… x 10 в степени n (n - число нулей). А поскольку 2017 и 10 в степени n являются взаимно простыми числами, то найденное число 3333… тоже будет делиться на 2017.
Аналогично можно доказать, что число типа mmmmm…, где m = 1, 2, 3, … 9, содержит фрагмент, который нацело делится на 2017.
Более того, если последовательность является дробной частью периодической дроби, то ее можно представить в виде RRRR…, где R - период дроби, после чего проходят те же рассуждения.
Осталось рассмотреть случай дробной части иррационального числа. Вообще-то, среди их фрагментов, на первый взгляд, можно найти любое число (как и в записи числа "пи" ), однако пример 12122122212222… вроде это опровергает, так что нужно подумать еще.

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1396 : 22 Декабрь 2016, 20:54:34 »
Попробуем так.
Среди фрагментов начальной последовательности найдется сколько угодно таких, которые при делении на 2017 дадут одинаковый остаток. Пусть наименьшее из таких чисел равно A.
Среди оставшегося бесконечного множества таких чисел, опять-таки по принципу Дирихле, найдется такое, “хвост” (то есть последние цифры) которого равен A. Обозначим его через B. Тогда разность (B – A) будет содержать число C, которое представляет собой разность (B – A) без нулей в конце и тоже делится на 2017.

Оффлайн Мефистошик

  • Создатель миров
  • ******
  • Сообщений: 20 602
  • Карма: +749/-0
  • Born-to-be-be-be
Re: Задача Эйнштейна и другие...
« Ответ #1397 : 22 Декабрь 2016, 21:54:01 »
Среди оставшегося бесконечного множества таких чисел, опять-таки по принципу Дирихле, найдется такое, “хвост” (то есть последние цифры) которого равен A. Обозначим его через B. Тогда разность (B – A) будет содержать число C, которое представляет собой разность (B – A) без нулей в конце и тоже делится на 2017.
Вот это слабый момент в решении. Тут принцип Дирихле не гарантирует существование такого числа.
Однако в целом принцип поиска решения верен.
Так что, думаю, Боб имеет приоритетное право "добить" эту задачу. :)
Nel mezzo del cammin di nostra vita
mi ritrovai per una selva oscura,
ché la diritta via era smarrita.

Оффлайн Сєм

  • Модератор
  • Создатель миров
  • *****
  • Сообщений: 8 706
  • Карма: +433/-0
Re: Задача Эйнштейна и другие...
« Ответ #1398 : 22 Декабрь 2016, 21:57:39 »
Пожалста, пожалста, тем паче, что я все равно к примеру взять, ни хрена не понял что вы тут понаписали...
пых!

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1399 : 23 Декабрь 2016, 11:57:24 »
Вот это слабый момент в решении.
Да, вчера по дороге домой я это сообразил. :)
Сегодня постараюсь подумать в свободное время, пара задумок есть.

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1400 : 23 Декабрь 2016, 11:57:50 »
Пожалста, пожалста, тем паче, что я все равно к примеру взять, ни хрена не понял что вы тут понаписали...
Шуткуешь?!)))

Оффлайн Сєм

  • Модератор
  • Создатель миров
  • *****
  • Сообщений: 8 706
  • Карма: +433/-0
Re: Задача Эйнштейна и другие...
« Ответ #1401 : 23 Декабрь 2016, 14:07:14 »
Шуткуешь?!)))
в том и проблема, что нет.
пых!

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1402 : 23 Декабрь 2016, 17:58:05 »
Среди фрагментов начальной последовательности найдется сколько угодно таких, которые при делении на 2017 дадут одинаковый остаток.
Среди этих чисел, опять-таки по принципу Дирихле, будут сколько угодно таких, у которых n последних цифр будут совпадать (n = 1, 2, 3, …). Обозначим все разности таких чисел при одинаковом n через Nn1, Nn2, Nn3, … Все эти разности (без нулей в конце) тоже будут делиться на 2017. То же можно сказать о разностях этих разностей, разностях разностей этих разностей и т.д.
Хотя бы один член получившегося бесконечного ряда (а на самом деле - бесконечно много членов) совпадет с одним из фрагментов в записи бесконечной непериодической дроби (в которой, кстати, нет нулей). Это интуитивное утверждение, кажется, можно доказать “от противного”.
Возможно, проходит и вероятностное доказательство. Поскольку начальная последовательность состоит из случайных чисел, то она будет содержать по крайней мере один фрагмент (а на самом деле - сколько угодно), совпадающий с неким членом последовательности, общий член которой выражается формулой 2017n.

Оффлайн Мефистошик

  • Создатель миров
  • ******
  • Сообщений: 20 602
  • Карма: +749/-0
  • Born-to-be-be-be
Re: Задача Эйнштейна и другие...
« Ответ #1403 : 23 Декабрь 2016, 18:10:38 »
Вероятностное доказательство точно не проходит. Не тот тип задачи.
А в остальном - опять же доказательство неполно, к сожалению. Интуитивное утверждение, возможно, и верно, но доказательства нет.
Дам небольшую подсказку: нам не нужно рассматривать все подрядки, достаточно взять строго определенное их количество. И главная задача - найти правило их выбора. Дальше - фактически задача тобой доказана.
Nel mezzo del cammin di nostra vita
mi ritrovai per una selva oscura,
ché la diritta via era smarrita.

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1404 : 23 Декабрь 2016, 19:40:05 »
По-видимому, стоит вначале попробовать решить задачу, взяв 7 вместо 2017, после чего можно будет действовать по аналогии.
В случае 3 решение нетрудно: если однозначное число N в последовательности само не делится на 3, то его можно представить в виде (3n + 1 ) или (3n + 2). В первом случае следующее за ним однозначное число M должно быть равно (3m + 1), чтобы двузначное число NM не делилось на 3 (само число M тоже не должно делиться на 3). Но тогда при любом третьем по порядку числу P доказываемое утверждение верно:
1) P делится на 3, тогда нечего доказывать;
2) P = 3p + 1, тогда число NMP делится на 3, поскольку сумма его цифр равна 3(n + m + p) + 3, то есть делится на 3;
3) P = 3p + 2, тогда делится на 3 число MP, поскольку сумма его цифр равна 3(m + p) + 3, то есть делится на 3.
Случай 5 (вместо 2017) вроде рассматривать не следует, поскольку 5 и 10 (в любой степени) не являются взаимно простыми числами.
А следующее простое число - как раз 7,

Оффлайн Мефистошик

  • Создатель миров
  • ******
  • Сообщений: 20 602
  • Карма: +749/-0
  • Born-to-be-be-be
Re: Задача Эйнштейна и другие...
« Ответ #1405 : 24 Декабрь 2016, 10:28:10 »
Я так понимаю, будет продолжение? :)
Nel mezzo del cammin di nostra vita
mi ritrovai per una selva oscura,
ché la diritta via era smarrita.

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1406 : 24 Декабрь 2016, 13:01:28 »
Я так понимаю, будет продолжение? :)
С числом 7 строго доказанного способа пока не нашел.
Предполагаю, что идея должна быть такой.
Рассмотрим фрагмент записи вида n1n2n3...n7. Предполагаем, что ни одно чисел, выраженных этими цифрами, не делится на 7 (иначе утверждение будет доказано априори). Остатки от их деления на 7 обозначим через p1, p2, p3, ..., p7.
Точно так же не должны делиться на 7 любые двузначные, трехзначные, ... шестизначные и семизначное число, образованные последовательными цифрами в этой записи.
Легко видеть, что при переходе цифр n из единичного в более высший разряд остаток от деления на 7 меняется. Например, 2 при делении на 7 дает остаток 2, 20 - остаток 6, 200 - остаток 4 и т.д. Поэтому по крайней мере одно из чисел, начинающееся с одной из цифр p в этой записи, должно попасть в "яблочко", то есть дать нулевой остаток. Здесь важно также то, что число 7 при умножении на другие числа в произведении может дать в конце любую цифру.
Если эта гипотеза верна, то для заданного числа 2017. нужно рассмотреть фрагмент записи n1n2n3...n2017 и провести те же рассуждения.
Для строгого доказательства этой гипотезы требуется рассуждать не в уме (как я поступаю), а сесть на достаточное время с ручкой и бумагой, а на это, к сожалению, сейчас времени нет. Поэтому пусть загадку "добьет" любой желающий.

Оффлайн Мефистошик

  • Создатель миров
  • ******
  • Сообщений: 20 602
  • Карма: +749/-0
  • Born-to-be-be-be
Re: Задача Эйнштейна и другие...
« Ответ #1407 : 24 Декабрь 2016, 13:17:43 »
Здесь важно также то, что число 7 при умножении на другие числа в произведении может дать в конце любую цифру.
Это справедливо для всех взаимнопростых с 10 чисел. :)
Если эта гипотеза верна, то для заданного числа 2017. нужно рассмотреть фрагмент записи n1n2n3...n2017 и провести те же рассуждения.
Для строгого доказательства этой гипотезы требуется рассуждать не в уме (как я поступаю), а сесть на достаточное время с ручкой и бумагой, а на это, к сожалению, сейчас времени нет. Поэтому пусть загадку "добьет" любой желающий.
Да нет нужды. ;)
Ты почти уже все сделал.
И даже правильно назвал фрагмент, который надо рассмотреть. Просто взял из этого фрагмента слишком много чисел. :)

На самом деле идея с том, что нужно рассматривать числа n1n2n3...n2017, n2n3...n2017, n3...n2017, ..., n2017. Если среди них будет такое, что делится на 2017, задача доказана. Если нет, то среди них найдется два, которые при делении на 2017 будут давать одинаковые остатки. Их разность будет начинаться с подрядка последовательности, который переходит в определенное количество нулей. Ну и поскольку 2017 и 10 - взаимнопростые числа, то указанный подрядок также будет делиться на 2017.

Считаю, что Боб вполне заслужил эти 5 баллов. :)
Nel mezzo del cammin di nostra vita
mi ritrovai per una selva oscura,
ché la diritta via era smarrita.

Оффлайн Мефистошик

  • Создатель миров
  • ******
  • Сообщений: 20 602
  • Карма: +749/-0
  • Born-to-be-be-be
Re: Задача Эйнштейна и другие...
« Ответ #1408 : 24 Декабрь 2016, 13:18:34 »

Мефистошик - 78
Bob-Domon - 55
lionel - 29
Шарин Налхара - 20
Сєм - 19
Пингвинчег - 12
Леди с Севера - 9
Симмах - 8
G8 - 5
Никта - 2
Луан - 2
Тереза - 2
Нана - 2
Селин -1
Nel mezzo del cammin di nostra vita
mi ritrovai per una selva oscura,
ché la diritta via era smarrita.

Оффлайн Bob-Domon

  • Создатель миров
  • ******
  • Сообщений: 13 014
  • Карма: +698/-0
Re: Задача Эйнштейна и другие...
« Ответ #1409 : 24 Декабрь 2016, 15:18:20 »
На самом деле идея с том, что нужно рассматривать числа n1n2n3...n2017, n2n3...n2017, n3...n2017, ..., n2017.
Оказывается, мне нужно было пойти немножко дальше от этого:
Точно так же не должны делиться на 7 любые двузначные, трехзначные, ... шестизначные и семизначное число, образованные последовательными цифрами в этой записи.
А именно - взять одно семизначное, одно шестизначное (начиная от второй цифры фрагмента), одно пятизначное (начиная от третьей цифры фрагмента) и т.д, Я все пытался получить нули в конце с сохранением порядка до нулей, а ларчик просто открывался. :)
Насколько понимаю, найденный мной способ доказательства для периодических дробей является частным случаем этого способа.