Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
fkthat
Member

Откуда:
Сообщений: 3030
mayton
Закончим пятницу дуплетом.

Еще одна. Из Студенческих конкурсов
На плоскости нарисовано n точек. Игра состоит в том, что двое по очереди
соединяют какую-либо пару точек кривой линией на которой ставится новая точка.
При этом линии не должны пересекаться. И из каждой вершины должно исходить не
более трех линий. Выигрывает тот, кто проведет последнюю линию.

а) Доказать что игра кончиться
б) Найти оптимальную стратегию при n=2
в) Найти оптимальную стратегию для произвольного n.


То, что она закончится, доказать легко. При каждом ходе количество точек увеличивается на 1, а количество "исхождений" всех линий из точек увеличивается на 4. Рано или поздно (n + 4*x) / (n + x) => 1 + 3 * x / (n + x) станет больше трех, а значит игра закончится еще раньше этого.
18 июл 20, 21:00    [22169832]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
mayton
Это книжка 70х годов. Сборник олимпиад по математике.
Как думаешь там много говорят о Hex?
А я знаю? мне такие задачи не попадались.
Мож это по пограммированию, в 80-х начались.
Ну ОК, я уточнил, а то тут Усов мутит с битами, с делением на 7 ... Да, и как в 70-е надо было получать 365-е простое число?..

Другой вопрос. Подразумевается ли под разными делителями:
а) только простые
б) степень игнорируется?
в) "1" делитель ??
Потому что если не (а), то можно трактовать как всевозможные произведения простых делителей (ну, кроме себя и 1). Тогда множество всех сочетаний (но уже вкл. степень)=2^р-2, где р - кол-во простых. Учитывать наличие 1 среди делителей немного муторно.
И если 2^р-2=365,то делаем выводы. Только зачем в условии тогда единицы?
18 июл 20, 23:27    [22169852]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Да, сначала меня смутило количество 1. Показалось, что в битах.

А если смотреть, как обычное число, то:
делим на 111 (3*37) - получаем последовательность 1001001...01,
которая на 2 цифры меньше, чем первоначальная.
Правда, количество единиц - простое число (659).

А что дальше?

Сообщение было отредактировано: 19 июл 20, 07:44
19 июл 20, 07:47    [22169896]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
А если отнять от нового числа 1. то можно разделить полученное число сразу на 1000!
19 июл 20, 08:41    [22169899]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Gennadiy Usov,
автор
А что дальше?
В этом и загвоздка, всё это я уже проделал. 659 - простое, и больше нет набора единиц в кол-ве кратном 659. Поэтому при агрегировании (типа 100 1001 ...1001) всегда в начале будет другое число - остаток.
Например:
B=10^3, М1=111=3*37, А= (М1 М1 М1 ... М1)= Сум(B^k) k=0...658.
М2=М1*В+М1, А=(М1 М2 М2...М2)= М1+В*Сум(В^2k) k=0...329,
Если отбросить хедер, то остальное по основанию В^2k записывается (1111....111).
И так далее ... без всякой цели у меня ...

М.б. имеет смысл зацепиться за простоту 659 ? в варианте только простых делителей (а как быть с их кратностью?)

Сообщение было отредактировано: 19 июл 20, 12:24
19 июл 20, 12:20    [22169924]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Не то написал:
автор
М2=М1*В+М1, А=(М1 М2 М2...М2)= М1+В*Сум(В^2k) k=0...329,
Хотел так
...А= М1*В^xxx +Сум(В^2k *М2) k=0...329,

А вообще, какие чудесные наборы единиц известны? Здесь мы перечислили
111
111 111
1001
а ещё?

А к варианту моей первой задумки: кто помнит ряд Сум(1/р), где р - все простые, расходится? а если сходится, то к чему?

Сообщение было отредактировано: 19 июл 20, 12:36
19 июл 20, 12:39    [22169927]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Есть ещё один набор:

1111...111 - (679 единиц)
и
1000...0000100000....00001 (единица на 1-м, 679+1, и 2*679+1 местах)

Если второе число делить на 3, то получается:

3333....3333366666...666667
(679 троек и 678 шестёрок)

Сообщение было отредактировано: 19 июл 20, 13:30
19 июл 20, 13:31    [22169935]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Мне серия единиц напомнила школьные задачки на смекалку типа корень квадратный из 123454321 равно 11111 и так далее.

Количество единиц 1977 подозрительно похоже на дату в 20м веке. Возможно это подсказка. И количество делителей
подозрительно похоже на число дней в году.
19 июл 20, 13:48    [22169940]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
А вообще мне всё больше кажется, что это не для школьников, вариант условия, когда рассматривать только простые делители. Это всё равно, как известную задачу по муху между 2-мя поездами решать через дифуры.

У меня растёт уверенность, что условие было про любые делители, кроме быть может 1 и самого А. Хотя в этом варианте последняя оговорка и не требуется.
Вчера я прикидывал эскиз решения через сумму всех сочетаний. Но можно проще, по-школьному.

Каждый делитель имеет пару, если А не точный квадрат. Тогда кол-во делителей чётно. Но 365 нечётное.
Остаётся доказать, что А не есть квадрат, что скорее всего. Но я на неск. дней отлучаюсь, так что все патенты вам.
19 июл 20, 13:52    [22169942]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Если к этой колбасе из единиц прибавить 9 то получиться число кратное десятичной системе.
Возможно это облегчит расчеты.

x = 11111....1 = (x + 9) - 9 = 10^1978 - 9
19 июл 20, 14:00    [22169947]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
А нет. Прошу прощения. Тупанул. Всё таки глаза замыливаются этой чортовой двоичной.
19 июл 20, 14:01    [22169948]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Gennadiy Usov
А если смотреть, как обычное число, то:
делим на 111 (3*37) - получаем последовательность 1001001...01,
которая на 2 цифры меньше, чем первоначальная.
Правда, количество единиц - простое число (659).
А что дальше?
Геометрическая прогрессия для 1001001...01 !

= (10^1978 - 1) / (10^3 - 1) = (10^989 - 1) * (10^989 + 1) / (10^3 - 1)

989 = 23 * 43

Сообщение было отредактировано: 19 июл 20, 16:16
19 июл 20, 16:15    [22169986]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Так случилось, я вернулся. Простое док-во, что А не есть точный квадрат целого.
А состоит из 1977 "1". А/9 не целое. А/3 нацело. ==> А/3 не делится на 3. А не квадрат.
Вариант любых делителей. Песец.
19 июл 20, 21:37    [22170066]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
1) exp98, я не понял. Нам надо доказать что в числе A/3 не более чем 365 - 1 делитель.
1 мы уже нашли по признаку делимости на 3. Поэтому осталось найти 364.

2) Остаток можно еще дальше разлагать по признакам делимости но надо понимать
что это олимпиадка и мы ищем решение на уровне смекалки. Тоесть без факторизаций
на вычислительны станциях. А просто так... "глаз пристрелявши.."
19 июл 20, 22:06    [22170076]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
24 - тоже не точный квадрат целого но тем не менее имеет делители.
19 июл 20, 22:08    [22170077]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
mayton
24 - тоже не точный квадрат целого но тем не менее имеет делители.
Вот и сосчитай по определению делителя, сколько их у 24. Чётное кол-во или нет.
1 24 2 12 3 8 4 6 все различные.
Я полагаю, что их чётное, след-но не 365.
19 июл 20, 23:00    [22170098]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Для остальных, кто в танке. Почему 24 не квадрат?
Потому что множитель 3 единичной кратности (24 на 9 не делится).
20 июл 20, 00:22    [22170125]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
exp98
Так случилось, я вернулся. Простое док-во, что А не есть точный квадрат целого.
А состоит из 1977 "1". А/9 не целое. А/3 нацело. ==> А/3 не делится на 3. А не квадрат.
Вариант любых делителей. Песец.
А как быть с тем, что А делится ещё на 37?
20 июл 20, 06:40    [22170163]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Gennadiy Usov, а зачем?
Давайте повторюсь, выше отписывался уже.
Сначала я тоже был во власти простых множителей (даже без учёта их кратности). По инерции последних лет задачу так и понимал.
Потом возникло подозрение, вызванное простой формулировкой "разных делителей", что не надо мудрствовать, а тупо выполнять написанное.
Поэтому от начальной интерпретации я отказался. Я сдался. Решил задачу в другой интерпретации.
Я решил задачу в постановке "любое число, к-рое делит А нацело", не только простое.

И поэтому вопрос ваш вызывает недоумение. А представимо в виде произведения степеней простых мн-лей. Для квадрата необходимое условие, чтобы степень каждого простого мн-ля была чётной. В частности для "3" это 9 81 ..... Но А не делится на 9.
Если B^2= A= 3^1 * 37^x * p1^y *...pk^z....... где все р простые , то очевидно, что В не целое. Снимите шоры инерции!
Или вы думаете, что типа Корень(3) * Корень(37) даст целое число?
20 июл 20, 12:48    [22170351]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
exp98
Для остальных, кто в танке. Почему 24 не квадрат?
Потому что множитель 3 единичной кратности (24 на 9 не делится).

Это было грубо.
20 июл 20, 13:20    [22170368]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
exp98
Gennadiy Usov, а зачем?
Давайте повторюсь, выше отписывался уже.
Сначала я тоже был во власти простых множителей (даже без учёта их кратности). По инерции последних лет задачу так и понимал.
Потом возникло подозрение, вызванное простой формулировкой "разных делителей", что не надо мудрствовать, а тупо выполнять написанное.
Поэтому от начальной интерпретации я отказался. Я сдался. Решил задачу в другой интерпретации.
Я решил задачу в постановке "любое число, к-рое делит А нацело", не только простое.

И поэтому вопрос ваш вызывает недоумение. А представимо в виде произведения степеней простых мн-лей. Для квадрата необходимое условие, чтобы степень каждого простого мн-ля была чётной. В частности для "3" это 9 81 ..... Но А не делится на 9.
Если B^2= A= 3^1 * 37^x * p1^y *...pk^z....... где все р простые , то очевидно, что В не целое. Снимите шоры инерции!
Или вы думаете, что типа Корень(3) * Корень(37) даст целое число?
Мысль хорошая, а формулировка ужасная, много недосказанности, потом переход на очевидность (молча).

Попробую сформулировать ответ проще.

Вместо А = 1111....111 можно было бы написать любое число, имеющее "гладкий" множитель, меньший корня из А.
Число интересное, что создаёт определённую путанность.
В нашем случае есть множитель - это 3 (и ещё 37, чтобы больше запутать).

Допустим есть число А.
У него М делителей, включая 1 и А.
Применяя
exp98
mayton
24 - тоже не точный квадрат целого но тем не менее имеет делители.
Вот и сосчитай по определению делителя, сколько их у 24. Чётное кол-во или нет.
1 24 2 12 3 8 4 6 все различные.
Я полагаю, что их чётное, след-но не 365.
получаем, что число делителей будет чётным,
за исключением одного случая: А - квадрат некоторого числа В.
А если А квадрат числа В, то у числа А должен быть ещё один множитель 3.
Но число А/3 не делится на 3 (по сумме цифр - 659)
Следовательно, для числа А количество множителей будет чётным.

Прошу прощения у exp98, если что не так.
20 июл 20, 14:08    [22170419]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Простите меня все, кого я ненароком задел или обидел.
mayton
Это было грубо.
Но это было именно для остальных. Намеренно следующим постом. Для тех других потенциально, кто к этому моменту ещё не понял, я немного перефразировал рассуждение. Ну и немного иронии - не все же на олимпиады ходили, да и я не верх совершенства.
И я предполагал, что про танк давно уже не более обидно, чем фраза типа "записать в склерозничек". Не ожидал.
Но вот же (в разделе С++ чаще всего) пишут "какие проблемы?". А ведь это эквивалент "ты что - дурак?". И это не смущает авторов как и "блин" как заменитель похожего восклицания. Но все привыкли.
20 июл 20, 20:14    [22170670]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Там откуда я родом - говорили "для тех кто в танке" - синоним "для тех кто тупой" (или глухой).

Ну да ладно. Проехали.

И про определение делителя я тоже не понял.
20 июл 20, 20:20    [22170675]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Gennadiy Usov
Попробую сформулировать ответ проще.
...
Прошу прощения у exp98, если что не так.
Всё так. Только я думаю, что сразу сказал проще (доходчивей):
автор
Каждый делитель имеет пару, если А не точный квадрат. Тогда кол-во делителей чётно. Но 365 нечётное. Остаётся доказать, что А не есть квадрат,
автор
А представимо в виде произведения степеней простых мн-лей. Для квадрата необходимое условие, чтобы степень каждого простого мн-ля была чётной. В частности для "3" это 9 81 ..... Но А не делится на 9.
Причём достаточно того, что 1977 единиц не делится на 9, но вроде об этом уже давно было сказано, а с "37" мы придумали сами себе трудность.

А "необходимое условие" - это термин, как и слово "делитель", и "представимость в виде произведения степеней простых мн-лей. ". Зачем их пояснять?

Сообщение было отредактировано: 20 июл 20, 20:23
20 июл 20, 20:24    [22170678]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Согласен.

Однако не могу найти фразу в перечне сообщений на топике:
exp98
автор
.......Остаётся доказать, что А не есть квадрат,
20 июл 20, 20:38    [22170688]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
Все форумы / Программирование Ответить