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