Гость
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Докажите, что среди степеней двойки есть две, разность которых делится на 2019 / 25 сообщений из 115, страница 1 из 5
14.07.2020, 19:02
    #39979608
vi0
vi0
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Добрый день
Скажите как вы понимаете условие задачи из топика?
Какое участие в решение принимает двойка?
...
Рейтинг: 0 / 0
14.07.2020, 19:34
    #39979616
SpringMan
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
(2^x - 2^y) % 2019 = 0
Должна существовать только одна пара (x, y), для которой это условие выполняется
...
Рейтинг: 0 / 0
14.07.2020, 19:37
    #39979617
Сотрудник Главного Управления
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
SpringMan
Должна существовать только одна пара x, y, для которой это условие выполняется
неправда,
должна существовать хотя бы одна пара, для которой это выполняется
...
Рейтинг: 0 / 0
14.07.2020, 19:44
    #39979620
Сотрудник Главного Управления
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
vi0
Скажите как вы понимаете условие задачи из топика?
Какое участие в решение принимает двойка?

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

Давно заметил, что многие российские олимпиадные задачки по математике грешат небрежностью формулировок, а иногда и неоднозначностью трактовок.
Явно не стараются объяснить суть задачи.
...
Рейтинг: 0 / 0
14.07.2020, 19:47
    #39979622
Сотрудник Главного Управления
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
vi0,
кстати, вы что-нибудь слышали про принцип Дирихле?
...
Рейтинг: 0 / 0
14.07.2020, 19:48
    #39979623
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Есть две степени числа 2: N и 0.

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

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

У нас М = 2019

Тогда 2^k - 1 делится на 2019
...
Рейтинг: 0 / 0
14.07.2020, 19:50
    #39979625
SpringMan
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Сотрудник Главного Управления
SpringMan
Должна существовать только одна пара x, y, для которой это условие выполняется
неправда,
должна существовать хотя бы одна пара, для которой это выполняется

Да, конечно, затупил
...
Рейтинг: 0 / 0
14.07.2020, 19:50
    #39979626
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Сотрудник Главного Управления
вам, наверное, неясно что такое степень двойки?
это такое число, которое можно представить в виде 2^x где x - это натуральное число
А ещё, если рассматривать общий вид, есть степени:
0 и отрицательные.
...
Рейтинг: 0 / 0
14.07.2020, 19:53
    #39979627
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
SpringMan
(2^x - 2^y) % 2019 = 0
Должна существовать только одна пара (x, y), для которой это условие выполняется
Для степеней 2 по модулю есть элемент цикличности.

То есть, с определённым промежутком по показателям степени можно найти очередной показатель, где есть деление.
...
Рейтинг: 0 / 0
14.07.2020, 20:10
    #39979630
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Сотрудник Главного Управления

должна существовать хотя бы одна пара, для которой это выполняется
Если существует хотя бы одна, то их бесконечность, остальные получатся умножением операндов в левой части на любую натуральную степень двойки.
...
Рейтинг: 0 / 0
14.07.2020, 20:15
    #39979632
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Можно задачу слегка упростить: коль скоро 2019 кратко 3-м, можно сгрупировать в разложении многочлена элементы попарно и искать кратное для 2019/3
...
Рейтинг: 0 / 0
14.07.2020, 20:19
    #39979633
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Gennadiy Usov
Есть две степени числа 2: N и 0.

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

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

У нас М = 2019

Тогда 2^k - 1 делится на 2019
Кстати, k = 48
...
Рейтинг: 0 / 0
15.07.2020, 09:11
    #39979725
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Совсем забыл.

В кольце вычетов по 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)
...
Рейтинг: 0 / 0
15.07.2020, 12:42
    #39979867
fkthat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Gennadiy Usov
Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)

Я совсем не помню уже теорчисел, но, по-моему, это только для взаимно простых чисел, т.е., в случае двойки, только если М нечетное.
...
Рейтинг: 0 / 0
15.07.2020, 12:48
    #39979872
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
fkthat
Gennadiy Usov
Для любого числа M можно найти число k (и не одно), что
2^k = 1(mod M)
Я совсем не помню уже теорчисел,
но, по-моему, это только для взаимно простых чисел, т.е., в случае двойки, только если М нечетное.
Пробел легко восполнить, если сделать маленькую программу умножения числа, начина с 1, на 2 по модулю n.

При этом будут получены вычеты.
Если эти вычеты отнимать от соответствующего 2^к, то получим число, кратное n.
...
Рейтинг: 0 / 0
15.07.2020, 15:48
    #39979993
fkthat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Gennadiy Usov
При этом будут получены вычеты.
Если эти вычеты отнимать от соответствующего 2^к, то получим число, кратное n.

Поверю на слово, неохота сейчас посреди рабочего дня вникать.
...
Рейтинг: 0 / 0
16.07.2020, 00:29
    #39980206
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
у меня вопрос
2^k = 1(mod M) это тоже самое, что 2^k % M = 1
???
...
Рейтинг: 0 / 0
16.07.2020, 05:29
    #39980219
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
mini.weblab
у меня вопрос
2^k = 1(mod M) это тоже самое, что 2^k % M = 1
???
При определении 2^k = 1(mod M) применяется оператор 2^k % M = 1
...
Рейтинг: 0 / 0
16.07.2020, 05:43
    #39980220
vi0
vi0
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Сотрудник Главного Управления
vi0,
кстати, вы что-нибудь слышали про принцип Дирихле?
да, задача как раз оттуда
но по дороге, я вижу, приходится погружаться в сравнение по модулю
...
Рейтинг: 0 / 0
16.07.2020, 12:07
    #39980366
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Из олимпиадных.

На шахматной доске размера n x n рисуется случайный прямоугольних, составленный
из нескольких квадратов. Найти вероятность того что прямоугольних является квадратом.
...
Рейтинг: 0 / 0
16.07.2020, 12:49
    #39980396
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
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
...
Рейтинг: 0 / 0
16.07.2020, 13:49
    #39980441
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
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).
А оказывается можно. Осознал. Был неправ.
...
Рейтинг: 0 / 0
16.07.2020, 13:54
    #39980449
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
Gennadiy Usov,
авторпрямоугольних, составленный из нескольких квадратов X= (несколько <>1) ? true: false;
X== ????
...
Рейтинг: 0 / 0
16.07.2020, 13:59
    #39980455
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
шахматная доска, у меня вывелось следующее
...
Рейтинг: 0 / 0
16.07.2020, 14:15
    #39980466
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Докажите, что среди степеней двойки есть две, разность которых делится на 2019
exp98
Gennadiy Usov,
авторпрямоугольних, составленный из нескольких квадратов
X= (несколько <>1) ? true: false;
X== ????Не понял.

Лучше конкретный пример
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Докажите, что среди степеней двойки есть две, разность которых делится на 2019 / 25 сообщений из 115, страница 1 из 5
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]