Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
 Докажите, что среди степеней двойки есть две, разность которых делится на 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]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить