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

Откуда:
Сообщений: 232
Добрый день
Скажите как вы понимаете условие задачи из топика?
Какое участие в решение принимает двойка?

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

Откуда:
Сообщений: 208
(2^x - 2^y) % 2019 = 0
Должна существовать только одна пара (x, y), для которой это условие выполняется

Сообщение было отредактировано: 14 июл 20, 19:32
14 июл 20, 19:34    [22167382]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019.  [new]
Сотрудник Главного Управления
Member

Откуда: Главное Управление
Сообщений: 44
SpringMan
Должна существовать только одна пара x, y, для которой это условие выполняется
неправда,
должна существовать хотя бы одна пара, для которой это выполняется
14 июл 20, 19:37    [22167384]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019.  [new]
Сотрудник Главного Управления
Member

Откуда: Главное Управление
Сообщений: 44
vi0
Скажите как вы понимаете условие задачи из топика?
Какое участие в решение принимает двойка?

вам, наверное, неясно что такое степень двойки?
это такое число, которое можно представить в виде 2^x где x - это натуральное число

Давно заметил, что многие российские олимпиадные задачки по математике грешат небрежностью формулировок, а иногда и неоднозначностью трактовок.
Явно не стараются объяснить суть задачи.
14 июл 20, 19:44    [22167388]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019.  [new]
Сотрудник Главного Управления
Member

Откуда: Главное Управление
Сообщений: 44
vi0,
кстати, вы что-нибудь слышали про принцип Дирихле?
14 июл 20, 19:47    [22167390]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Есть две степени числа 2: N и 0.

То есть, есть разность 2^N - 1

Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)

У нас М = 2019

Тогда 2^k - 1 делится на 2019

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

Откуда:
Сообщений: 208
Сотрудник Главного Управления
SpringMan
Должна существовать только одна пара x, y, для которой это условие выполняется
неправда,
должна существовать хотя бы одна пара, для которой это выполняется

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

Откуда:
Сообщений: 2204
Сотрудник Главного Управления
вам, наверное, неясно что такое степень двойки?
это такое число, которое можно представить в виде 2^x где x - это натуральное число
А ещё, если рассматривать общий вид, есть степени:
0 и отрицательные.
14 июл 20, 19:50    [22167394]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
SpringMan
(2^x - 2^y) % 2019 = 0
Должна существовать только одна пара (x, y), для которой это условие выполняется
Для степеней 2 по модулю есть элемент цикличности.

То есть, с определённым промежутком по показателям степени можно найти очередной показатель, где есть деление.
14 июл 20, 19:53    [22167396]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 12791
Сотрудник Главного Управления

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

Откуда: Москва
Сообщений: 12791
Можно задачу слегка упростить: коль скоро 2019 кратко 3-м, можно сгрупировать в разложении многочлена элементы попарно и искать кратное для 2019/3
14 июл 20, 20:15    [22167403]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Gennadiy Usov
Есть две степени числа 2: N и 0.

То есть, есть разность 2^N - 1

Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)

У нас М = 2019

Тогда 2^k - 1 делится на 2019
Кстати, k = 48
14 июл 20, 20:19    [22167404]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Совсем забыл.

В кольце вычетов по mod 2019 (да и любого N) существуют числа степени 2, такие, что они меньше 2019 (или N).
Таких чисел для 2019 будет 10.

Применяя 22167391, получаем 10 пар степеней числа 2, которые делятся на 2019:

(48,0), (49,1), (50,2),....,(57,10).

А также пары, для которых (47 + 48*k + j, j)
15 июл 20, 09:11    [22167540]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
fkthat
Member

Откуда:
Сообщений: 3030
Gennadiy Usov
Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)

Я совсем не помню уже теорчисел, но, по-моему, это только для взаимно простых чисел, т.е., в случае двойки, только если М нечетное.
15 июл 20, 12:42    [22167729]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
fkthat
Gennadiy Usov
Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)
Я совсем не помню уже теорчисел,
но, по-моему, это только для взаимно простых чисел, т.е., в случае двойки, только если М нечетное.
Пробел легко восполнить, если сделать маленькую программу умножения числа, начина с 1, на 2 по модулю n.

При этом будут получены вычеты.
Если эти вычеты отнимать от соответствующего 2^к, то получим число, кратное n.
15 июл 20, 12:48    [22167737]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
fkthat
Member

Откуда:
Сообщений: 3030
Gennadiy Usov
При этом будут получены вычеты.
Если эти вычеты отнимать от соответствующего 2^к, то получим число, кратное n.

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

Откуда:
Сообщений: 1027
у меня вопрос
2^k = 1(mod M) это тоже самое, что 2^k % M = 1
???
16 июл 20, 00:29    [22168271]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mini.weblab
у меня вопрос
2^k = 1(mod M) это тоже самое, что 2^k % M = 1
???
При определении 2^k = 1(mod M) применяется оператор 2^k % M = 1
16 июл 20, 05:29    [22168291]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
vi0
Member

Откуда:
Сообщений: 232
Сотрудник Главного Управления
vi0,
кстати, вы что-нибудь слышали про принцип Дирихле?
да, задача как раз оттуда
но по дороге, я вижу, приходится погружаться в сравнение по модулю
16 июл 20, 05:43    [22168292]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Из олимпиадных.

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

Откуда:
Сообщений: 2204
mayton
Из олимпиадных.
На шахматной доске размера n x n рисуется случайный прямоугольних, составленный
из нескольких квадратов. Найти вероятность того что прямоугольних является квадратом.
А какая вероятность того, что перемножаются одинаковые числа из всего перечня чисел?

Если чисел 100, то различных произведений 100 * 100 .
А количество квадратов - только 100.

Вот и вся вероятность: 1/100.

На шахматной доске (одна сторона) одинарных чисел 8, двойных чисел 7, тройных чисел 6, ...8-ти чисел 1.
Итого на одной стороне 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36.

Вероятность: 1/36

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

Откуда:
Сообщений: 2446
Gennadiy Usov
Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)...
Вот это просто замечательно. Зря я раньше пренебрегал вычетами и целочисленными опреациями.
Я чуть было не начал доказывать, что одно битовое разложение невозможно получить суммированием другого конкретного. Ну то есть по задаче
2^(a-b) - 1= (1111 ... 1111)
2019= 2^11-1-(2^4+2^3+2^2)= (111111 00011). И, что якобы, сколько ни суммируй последнее, никогда не избавиться от внутренних нулей т.е. якобы не получу (1111 ... 1111 00000).
А оказывается можно. Осознал. Был неправ.

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

Откуда:
Сообщений: 2446
Gennadiy Usov,
автор
прямоугольних, составленный из нескольких квадратов
X= (несколько <>1) ? true: false;
X== ????
16 июл 20, 13:54    [22168597]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
шахматная доска, у меня вывелось следующее




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

Откуда:
Сообщений: 2204
exp98
Gennadiy Usov,
автор
прямоугольних, составленный из нескольких квадратов
X= (несколько <>1) ? true: false;
X== ????
Не понял.

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

Откуда:
Сообщений: 2204
mini.weblab
шахматная доска, у меня вывелось следующее
В числителе должно быть 1/2 символов из знаменателя


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

Откуда:
Сообщений: 1027
Gennadiy Usov,

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

Откуда:
Сообщений: 2204
mini.weblab
Gennadiy Usov,
это еще почему и зачем?
чтобы у нас с вами ответы совпали?
Значит, один из нас прав.

Зачем в знаменателе 8-i+1, а в числителе i?
Доказывайте!
16 июл 20, 14:24    [22168631]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Gennadiy Usov,
а как же считать количество квадратов на шахматной доске?
8^2 + 7^2 + ... + 1^2
16 июл 20, 14:28    [22168636]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mini.weblab
Gennadiy Usov,
а как же считать количество квадратов на шахматной доске?
8^2 + 7^2 + ... + 1^2
Согласен.
Был не прав.
Понадеялся на цифры, а здесь отрезки.
16 июл 20, 14:36    [22168638]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Из олимпиадных.

На шахматной доске размера n x n рисуется случайный прямоугольних, составленный
из нескольких квадратов. Найти вероятность того что прямоугольних является квадратом.


Не бывает просто "случайных прямоугольников".

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

Откуда:
Сообщений: 654
Gennadiy Usov
Есть две степени числа 2: N и 0.

То есть, есть разность 2^N - 1

Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)

У нас М = 2019

Тогда 2^k - 1 делится на 2019
вот оно
https://ru.m.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)

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

Откуда:
Сообщений: 654
Aleksandr Sharahov
mayton
Из олимпиадных.

пропущено...


Не бывает просто "случайных прямоугольников".

Необходимо уточнить, что именно случайно в этой задаче и как именно оно случайно.
+1
Надо уточнить, как именно строится прямоугольник.
Либо это "все прямоугольники равновероятны", либо рандомно выбираются 4 величины (и даже тут есть варианты, например, можно ли правую границу выбрать левее, чём левую)
16 июл 20, 15:20    [22168675]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Замечание полезное. Но приобретя опыт со слчайной хордой в круге, не надо ждать, когда кто-то напишет варианты. Если, конечно, есть желание решить. Ставьте свой вариант и вперёд.
Вариант с правой вершиной влево ИМХО перебор.
16 июл 20, 19:06    [22168805]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
fkthat
Member

Откуда:
Сообщений: 3030
Имя пользователя1

https://ru.m.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)

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

Откуда:
Сообщений: 2204
fkthat
Имя пользователя1

https://ru.m.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)
Я же и говорил, что работает для взаимно простых чисел, но, меня, пользуясь моим невежеством, с толку сбили :))
При чём здесь "для взаимно простых чисел"?

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

Откуда: loopback
Сообщений: 48022
exp98
Замечание полезное. Но приобретя опыт со слчайной хордой в круге, не надо ждать, когда кто-то напишет варианты. Если, конечно, есть желание решить. Ставьте свой вариант и вперёд.
Вариант с правой вершиной влево ИМХО перебор.

Ответа я не знаю. Текст - из сборника олимпиадных задач. Текст - оригинальный.
16 июл 20, 19:54    [22168831]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
exp98
Замечание полезное. Но приобретя опыт со слчайной хордой в круге, не надо ждать, когда кто-то напишет варианты. Если, конечно, есть желание решить. Ставьте свой вариант и вперёд.
Вариант с правой вершиной влево ИМХО перебор.


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

Откуда:
Сообщений: 3030
Gennadiy Usov

В первом сообщении говорится о 3-х числах:
- два числа - разность степеней
- число 2019


Если 2^x - 2^y mod 2019 = 0, то 2^(x-y) mod 2019 = 1 и наоборот.

А еще легко проверить если двойку просто заменить на 2019 (т.е. не взаимно простое с 2019) - в какую степень его не возводи, по модулю 2019 всегда будет 0, а единицы никогда не будет.

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

Откуда:
Сообщений: 2204
fkthat
Если 2^x - 2^y mod 2019 = 0, то 2^(x-y) mod 2019 = 1 и наоборот.

А еще легко проверить если двойку просто заменить на 2019 (т.е. не взаимно простое с 2019) - в какую степень его не возводи, по модулю 2019 всегда будет 0, а единицы никогда не будет.
Наверное:

Если 2^x - 2^y mod 2019 = 0, то 2^(x-y)*(2^y - 1) mod 2019 = 0...
16 июл 20, 20:40    [22168856]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
fkthat
Member

Откуда:
Сообщений: 3030
Gennadiy Usov
fkthat
Если 2^x - 2^y mod 2019 = 0, то 2^(x-y) mod 2019 = 1 и наоборот.

А еще легко проверить если двойку просто заменить на 2019 (т.е. не взаимно простое с 2019) - в какую степень его не возводи, по модулю 2019 всегда будет 0, а единицы никогда не будет.
Наверное:

Если 2^x - 2^y mod 2019 = 0, то 2^(x-y)*(2^y - 1) mod 2019 = 0...

Под вечер торможу уже, да, импликация будет только в одну сторону. Т.е. если 2^(x-y) mod 2019 = 1 => (2^x - 2^y) mod 2019 = 0.
16 июл 20, 22:51    [22168895]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Сотрудник Главного Управления
Member

Откуда: Главное Управление
Сообщений: 44
mayton
рисуется случайный прямоугольних


Сотрудник Главного Управления
Давно заметил, что многие российские олимпиадные задачки по математике грешат небрежностью формулировок, а иногда и неоднозначностью трактовок.
Явно не стараются объяснить суть задачи.

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

Откуда:
Сообщений: 2204
Сотрудник Главного Управления
Сотрудник Главного Управления
Давно заметил, что многие российские олимпиадные задачки по математике грешат небрежностью формулировок, а иногда и неоднозначностью трактовок.
Явно не стараются объяснить суть задачи.
Вот хороший пример к тому, что я писал выше.
Давно замечено, что так нам хочется покритиковать.

А самому слабо представить "правильную формулировку".

Ваше слово товарищ Сотрудник Главного Управления
17 июл 20, 09:03    [22169006]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Gennadiy Usov,

случайными могут быть:
центр,
одна сторона,
2 стороны,
диагонали,
периметр,
площадь,
угол с осями координат,
их комбинации в различном порядке.

Различным может быть распределение вероятности.

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

Откуда:
Сообщений: 2204
Надо понять, как выбираются стороны прямоугольников: 1 из 36?

Сообщение было отредактировано: 17 июл 20, 11:03
17 июл 20, 10:57    [22169098]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
удалено

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

Откуда: loopback
Сообщений: 48022
Хм... как-бы я пытался делать.

В подобного рода задачах на теор-вер если говорят о случайности - то имеют в виду линейное распеделение вероятностей.
Тоесть то что бросает игральная кость или функция random() в языках программирования.

Шахматная доска n x n - дискретна. На ней n^2 клеток. Сколько клеточных квадратов мы можем сделать на доске 3х3 ?

1) Большой квадрат - сама доска (+1)
2) Маленькие квадраты - клетки (+9)
3) Квадраты состоящие из 4 соседних клеточек 2х2. Таковых будет ... эээ 4 штуки кажется. (+4)

Итого для доски 3x3 мы можем выбросить максимум 1 + 9 + 4 = 14 случайных квадратов из .... неизвестного числа
произвольных прямоугольников. Из возможно мы посчитаем как перебор всех возможных пар клеток левого
верхнего и правого нижнего угла прямоугольника. Тут - формулы сочетаний и размещений нам в помошь.

Вот как-то так. Дальше эту формулу надо обобщить на n x n.
17 июл 20, 15:00    [22169312]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
Шахматная доска n x n - дискретна. На ней n^2 клеток.
... для доски 3x3 мы можем выбросить максимум 1 + 9 + 4 = 14 случайных квадратов из .... неизвестного числа
произвольных прямоугольников. Из возможно мы посчитаем как перебор всех возможных пар клеток левого
верхнего и правого нижнего угла прямоугольника. Тут - формулы сочетаний и размещений нам в помошь.

Вот как-то так. Дальше эту формулу надо обобщить на n x n.
Так mini.weblab уже это сделал:
mini.weblab
как же считать количество квадратов на шахматной доске?
8^2 + 7^2 + ... + 1^2
mini.weblab
шахматная доска, у меня вывелось следующее


Осталось вместо 8 "поставить" N (в отличие от n в формуле).

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

Откуда: loopback
Сообщений: 48022
Кто протестирует это?
17 июл 20, 16:21    [22169373]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
Кто протестирует это?
Тестировать можно только то, что можно с чем-нибудь сравнивать.

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

Откуда: loopback
Сообщений: 48022
Как вариант. У нас есть формула. И мы напишем софт который симулирует генерацию прямоугольников
и считает соотношение успехов и неуспехов. Сходимость - будет.
17 июл 20, 16:57    [22169405]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
mini.weblab
поправила формулу (для софта)

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

Откуда:
Сообщений: 2446
mini.weblab,
в общем-то правильно, но непрозрачно.
"Прозрачный" знаменатель имеет вид СУМ((8-j+1)*(8-k+1)). Но да, легко преобразуется к твоему виду.
Конкретно для 8х8 Р= 17/36. Если фраза "несколько" исключает 1х1, то в верхней формуле вычесть по 1 ввеху и внизу.

Соответственно модель вероятности такова.
Прям-ки чертить только по границам клеток. Соответственно длины натуральные.
Дробь считать не как деление суммарных площадей, а как кол-во всевозможных прям-ков по границам клеток.

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

Откуда:
Сообщений: 2446
mayton
Кто протестирует это?
Я тестировал независимо.
17 июл 20, 19:33    [22169484]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Еще одна пятничная олимпиадная.

Доказать что у числа 11111111111111....1 (1977 единиц) не может быть 365 различных делителей.
17 июл 20, 19:44    [22169489]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

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

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

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

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

б) Найти оптимальную стратегию при n=2
Допустим, есть точки 1 и 2.
Будем следить за количеством чисел (не более 3-х)

Строится третья точка и первая линия : 1,2,3,3
Допустим следующая линия 2,3,4,4 (вычеркнули 3)
Далее 4,1,5,5. (вычеркнули 4)
Далее 1,2,6,6 (вычеркнули 1, 2)
Остались только 5 и 6 (каждая уже по 2).

Что-то должно быть такое...

А далее перебор вариантов
Пока получается, что побеждает 1-ый - 5-я линия (3 варианта).

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

Откуда:
Сообщений: 2204
Всё намного проще.

Есть массив (n,3), который "забивается" по строчкам n 4-мя числами.
До тех пор, пока не будет заполнена целиком строка из 3-х чисел.
При этом должно остаться только 1 ячейка.
То есть:

4 * к = 3 * р - 1.

Ответ: к = 5 (количество линий!), р = 6

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

Откуда:
Сообщений: 2446
Снова чио-нибудь на теорчисел. Я пасс.
Могу только сказать, что 800! ~7,71*10^1976.
Исходное число А= 1/9*(10^1977 -1).
365=5*73.
автор
Закончим пятницу
В каком году закончим?
17 июл 20, 21:40    [22169519]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
Еще одна пятничная олимпиадная.
Доказать что у числа 11111111111111....1 (1977 единиц) не может быть 365 различных делителей.
Число 1977 делится на 3.
Следовательно, имеем 659 раза по 3 единички.
То есть, начальное число делится на 7.
17 июл 20, 21:59    [22169523]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Есть соображение. А не делится на 2 4 6 8 10 12.....
Если бы делители были поряд от 1 до 365, то А=2,5*10^778.
Половина из них чётные, значит последний делитель >= 365+182+91+45+22+11+ .... =724
724!~ 7*10^1757

А не делится на 9, ещё сколько-то добавить.
ПОтом ещё на что-то. Вот так перебором м.б. наскребём на огромный последний делитель. И вдруг тогда их произведение станет >А, а их кол-во вдруг даже меньше 365. Как-то так.
Но я использовал калькулятор, что вряд ли положено было на олимпиаде.))
17 июл 20, 22:06    [22169524]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
exp98
Есть соображение. А не делится на 2 4 6 8 10 12.....
Если бы делители были поряд от 1 до 365, то А=2,5*10^778.
Половина из них чётные, значит последний делитель >= 365+182+91+45+22+11+ .... =724
724!~ 7*10^1757

А не делится на 9, ещё сколько-то добавить.
ПОтом ещё на что-то. Вот так перебором м.б. наскребём на огромный последний делитель. И вдруг тогда их произведение станет >А, а их кол-во вдруг даже меньше 365. Как-то так.
Но я использовал калькулятор, что вряд ли положено было на олимпиаде.))


можно сразу длину вдвое уменьшить, т.к. 9*1111...1111=9999..9999=10^1978-1=(10^989-1)*(10^989+1)
18 июл 20, 00:44    [22169575]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mini.weblab
Member

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

а) Доказать что игра кончиться

можно использовать аналогию модели роста популяции
1) начальное конечное количество точек - N; точку, поставленную на линию, соединяющую точки, будем называть потомок;
точка у которой 3 потомка - деактивируется.
2) максимальное количество точек (потомков) в первом поколении N * 3/2
3) во-втором, N*3/4; в третьем - N*3/8; ... ; в n-нном N*3*/(2^n)
4) последовательность (количество активных точек) сходится к 0, значит игра конечна.

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

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

б) Найти оптимальную стратегию при n=2
Получилась формула для n чисел (без учета пересечений!)
(две формулы)

Есть две последовательности:
q1 = n +(n-1)*n + 4*k
и
q2 = (n +(n-1)*n/2 + k)*3

При увеличении k разность q1 и q2 будет равна :
q2 - q1 = 2
Тогда только одна линия остаётся.
18 июл 20, 07:06    [22169608]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Простое разделение двух точек:

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

Откуда:
Сообщений: 2204
Скорее всего, такими петлями разделяется множество точек.

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

Откуда: loopback
Сообщений: 48022
В теории графов есть формула, которая связывает вершины и ребра.

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

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

Доказать что у числа 11111111111111....1 (1977 единиц) не может быть 365 различных делителей.
Можно ещё по другому доказать.

Допустим есть 365 делителей.
Они нечётные.
Допустим они есть числа от 3 до 721.
Среднее число из них 360.
Длина в битах у этого числа 8 (уменьшаем на 1, что важно при умножении).
Если умножить 365 на 8, получим более 2920 бит.
А это намного больше, чем 1977.

А если принять во внимание, что 365 простым числом будет 2423, что намного больше, чем 721.

Следовательно, у числа с 1977 единиц не может быть 365 делителей.
18 июл 20, 08:59    [22169624]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
В теории графов есть формула, которая связывает вершины и ребра.

А у нас есть ограничение - мощность вершины не более 3.
А это ограничение выполняется:
q2 из22169608 , где k - количество линий, а 3 - количество ребер у вершины.

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

Откуда:
Сообщений: 2446
mayton
Еще одна пятничная олимпиадная.
В какой системе счисления число 1111111..... ?? в Hex? octal? ....
18 июл 20, 12:35    [22169683]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Это книжка 70х годов. Сборник олимпиад по математике.

Как думаешь там много говорят о Hex?
18 июл 20, 13:00    [22169691]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Имя пользователя1
Member

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

а) Доказать что игра кончиться

можно использовать аналогию модели роста популяции
1) начальное конечное количество точек - N; точку, поставленную на линию, соединяющую точки, будем называть потомок;
точка у которой 3 потомка - деактивируется.
2) максимальное количество точек (потомков) в первом поколении N * 3/2
3) во-втором, N*3/4; в третьем - N*3/8; ... ; в n-нном N*3*/(2^n)
4) последовательность (количество активных точек) сходится к 0, значит игра конечна.
можно ещё так: изначально есть 3n неиспользованных подключений. Каждый ход использует пару подключений, и добавляет точку с одним неиспользованным подключением, то есть количество оных уменьшается на единицу
18 июл 20, 13:42    [22169699]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Имя пользователя1
Member

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

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

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

https://ru.m.wikipedia.org/wiki/Рассада_(игра)
18 июл 20, 13:49    [22169700]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Сотрудник Главного Управления
Member

Откуда: Главное Управление
Сообщений: 44
mayton
Доказать что игра кончиться

Вряд ли вы сможете доказать, что игра закончится, если так и не смогли осилить простейшее правило.
18 июл 20, 19:04    [22169802]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Сотрудник Главного Управления,

Grammar nazi?
18 июл 20, 19:30    [22169814]     Ответить | Цитировать Сообщить модератору
 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]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
exp98
Member

Откуда:
Сообщений: 2446
Gennadiy Usov, вот же зануда. Почему у меня получается?
Попробуйте контекстным поиском в браузере. 4-я страница топика.
Поисковая фраза "Остаётся доказать, что А не есть квадрат".
Можно и с зпт на конце - я же копи-вставкой работал.
20 июл 20, 20:51    [22170694]     Ответить | Цитировать Сообщить модератору
 Re: Докажите, что среди степеней двойки есть две, разность которых делится на 2019  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 654
Доказать, что забор из единиц - не квадрат, проще простого.
Если у квадрата последняя цифра единица, то предпоследняя должна быть четной, можете легко увидеть для обоих подходящих вариантов: (10k + 1)2 и (10k - 1)2

Так что если суть задачи в том, что у нашего забора не может быть ровно 365 разных делителей, то легко решается. Я почему-то подумал, что разговор о том, что их не менее 365

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

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

Сообщение было отредактировано: 22 июл 20, 12:36
22 июл 20, 12:36    [22171627]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
Все форумы / Программирование Ответить