Олимпиада школьная

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 26 янв 2022, 13:22

final_11_klass.pdf
(125.52 KiB) Загружено 351 раз

Я думаю про задачу 6. Поставим в каждом узле сетки (n-1)x(n-1) нолик, если этот узел центр квадрата, иначе крестик. Условие означает, что для любого нолика на соседних 8 узлах есть три крестика подряд уголком (то есть между ними клетка покрыта только одним квадратиком) Назовем такие крестики дружественными этому нолику (их может оказаться и 3, и 5. и 6, и больше.)Рассмотрим двудольный граф показывающий отношения дружественности между крестиками и ноликами. Из каждого нолика идет не менее трех ребер в крестики. Но если рассмотреть любой крестик, дружественный нолику, то получаем , что у него может найтись еще не более двух дружественных ноликов, отсюда (двойным подсчетом ребер графа) - асимптотически ноликов не более, чем крестиков (на бесконечной доске). Оптимальная констукция это две диагонали из ноликов, рядом две диагонали из крестиков, и так чередуются
Но здесь не учтено, что фактически решетку (n-1)x(n-1) окружает кайма из крестиков (по краю исходной доски nxn), то есть для нолика на расстоянии клетки от края- дружественными может оказаться один настоящий крестик и два фиктивных. Поэтому хотя мы доказали что C ( отношение числа ноликов к [math]) асимптотически 1/2, для не очень больших досок оно может оказаться и больше 1/2, и максимум из таких С будет ответом задачи, надо просчитывать.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 26 янв 2022, 14:40

Ian писал(а):Source of the post для не очень больших досок оно может оказаться и больше 1/2
Это не важно, нужно же найти нижнюю границу C.
Если при больших n будет меньшее C, то оно и определяет.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 26 янв 2022, 14:49

Вот предположим, что при n=10 удалось f(n)=51, значит С=0,5 не катит. Как раз максимум по n максимума числа квадратиков, деленного на [math] ищем. А почему бы 51 не оказаться? Если ноликов меньше чем крестиков но считая 40 фиктивных крестиков, тут пока только знаем f(n)<60

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 26 янв 2022, 16:04

При маленьких n должно быть меньше 0.5 из-за границы.
Вот возьмём n=2. Тут только один квадрат будет. Выходит [math].

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 26 янв 2022, 19:45

zykov писал(а):При маленьких n должно быть меньше 0.5 из-за границы.

Да действительно я могу модифицировать свое доказательство. Раньше было; число крестиков k, число ноликов (центров квадратиков2х2) z, число ребер графа R. По доказанному (с ошибкой) [math]. отсюда [math]
Теперь есть [math], а другого неравенства нет так как ребра могут идти еще в 4 угловых фиктивных (не более чем по одному ребру) и в 4n-4 фиктивных крестика напротив сторон (не более трех ребер в каждые два соседних), получается неравенство [math]
[math]
[math] и из этого следует [math] , [math] совершенно для всех натуральных n. Не такая уж страшная задача, за что тут больше всех баллов

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 26 янв 2022, 23:24

По 5й задаче. У нас n элементов 1,2,3...n , и m множеств из них. Пусть [math]- число множеств , которым принадлежит элемент i.Конечно [math]-только за этим количество множеств и нужно Тогда, что удивительно, сумма слева -это просто сумма кубов введенных чисел [math], столько раз элемент i будет в ней посчитан. Свелось к неравенству
[math] -среднее кубическое не меньше среднего арифметического.
Тут отдельно надо подумать как это доказывать школьнику. Я бы попробовал из интуитивной выпуклости кубической параболы, что всякая хорда выше параболы.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 27 янв 2022, 08:11

Задача 2. Из тождеств [math] и [math]
уравнение упрощается до
[math]
В этой сумме n слагаемых, каждое не меньше 1, а последнее не меньше n - равенство тогда и только тогда, когда n простое

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 27 янв 2022, 09:29

В задаче 1- может быть решение (2t,2t,-t,-t,-t,-t) и соответственно 12 уравнений - одна переменная из первых двух, две переменные из последних четырех. Сутки понадобилось чтобы догадаться. и все это время думал будет наоборот

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 27 янв 2022, 10:09

В задаче 4 я думаю ответ 4020, это максимальное число корней уравнения [math] , но опять проблема как это объяснить со школьной точки зрения

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 31 янв 2022, 15:21

4-6.jpg
4-6.jpg (150.38 KiB) 11500 просмотра
сегодня во 2-м туре предлагались. 6я крутая, видимо связана с идеей что даже у случайной последовательности половина совпадений, а если не у нее так у ей противоположной, и значит можно одним битом сообщить какая из двух. И значит, можно заранее сформировать [math] сильно попарно непохожих последовательностей и n битами сообщить какая из них ближе к нужной. Но чему же все таки равно С, как хотя бы добиться С=45

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 31 янв 2022, 19:36

Не знаю, чего от школьников хотели.
Видимо имели ввиду Hamming code, а именно Hamming(15,11).
Отсюда 44=11*4 и 60=15*4.

(Хотя наверно Hamming(63,57) лучше будет.)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 31 янв 2022, 19:58

Имеется ввиду, что код из 15 битов может восстановить ошибку в любом одном из битов.
[math]
Т.е. разбиваем 60 на 4 группы по 15. "Корректируем" ошибку в одном бите, если есть. Получаем 11 битов данных. Всего 44 бита.
Фокусник по этим 11 битам считат сам код из 15 битов, который отличается от исходного значения не более чем на 1 бит.

В итоге будет не более 4 ошибочных битов.
Т.е. C выходит 56.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 31 янв 2022, 20:37

57 уже не подходит для C, т.к.
[math]

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Олимпиада школьная

Сообщение Ian » 31 янв 2022, 21:29

zykov писал(а):Не знаю, чего от школьников хотели.
Видимо имели ввиду Hamming code
А подробнее. Если, для простоты, сообщение 15 битное, какие 11 бит вы будете передавать? Как фокусник по вашим битам восстановит то что он должен назвать? Почему это будет отличаться от исходного не более чем на бит?
Потому что код Хэмминга я изучал как более длинный, чем передаваемая информация, но позволяющий в случае сбоя (замены) не более чем одного бита узнать, где была ошибка, и значит исправить ее. Он базируется на расстоянии Хэмминга между словами (число различных битов, если слова написаны одно под другим). И , как Вы упоминали, есть информационное соотношение - для слова длины 60 есть [math] слов, отличающееся от него не более чем на 3 бит. Соответственно каждое слово ассистента может дать менее чем [math] вариантов успеха, и при не более чем [math] возможных словах ассистента число вариантов успеха фокусника не может достичь [math]- значит, отличия на не более чем 3 бита гарантировать невозможно.
Но где гарантия, что на каждое из [math] слов ассистента существует слово фокусника, отличающееся от заданного не более чем на 4 бита? В этом и нужен Хэмминг.
Таким образом, школьникам нужно было это переоткрыть, не ссылаясь на Хэмминга. 100 баллов (около 3х задач из 6ти) на этой дистанционной олимпиаде дают студ. билет в вшэ.
Последний раз редактировалось Ian 01 фев 2022, 07:03, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 01 фев 2022, 06:43

Там на вики всё подробно расписано.
Вот про Hamming(7,4) всё совсем в деталях. Hamming(15,11) будет так же, только вместо 3 битов чётности будет 4.
Прочитайте там Goal, Hamming matrices.

Идея такая, что из [math] слов выбираем [math] кодовых слов, так что любые два слова отличаются минимум 3 битами. Все остальные слова - ошибочные. Каждое ошибочное отличается от какого-то одного кодового ровно на 1 бит. Это позволяет ошибку в одном бите исправить. Само кодовое слово и 15 его ошибочных с ошибкой в одном бите дают набор слов, и таких наборов [math].
Последний раз редактировалось zykov 01 фев 2022, 07:06, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 01 фев 2022, 06:53

Если посмотреть на столбцы матрицы H, то видно, что это двоичные числа от 1 до 7. Т.е. если мы умножаем матрицу H на вектор длины 7 в котором только 1 единица, то получим вектор длины 3 с двоичным кодом позиции этой единицы.
Ошибка в одном бите означает прибавление к слову такого вектора с 1 единицей. Само кодовое слово при умножении на H даёт нули. Значит слово с ошибкой в одном бите при умножении на H даст позицию этой ошибки.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 01 фев 2022, 07:04

Ian писал(а):Source of the post Если, для простоты, сообщение 15 битное, какие 11 бит вы будете передавать? Как фокусник по вашим битам восстановит то что он должен назвать?
Либо эти 15 бит - код без ошибки, либо с ошибкой в 1 бите. Если ошибка, то исправляем. Берём только 11 бит данных и даём их фокуснику. Фокусник обратно считает 15 бит кодового слова по данным. Эти 15 либо совпадают с исходными, либо отличаются ровно на 1 бит.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Олимпиада школьная

Сообщение zykov » 01 фев 2022, 07:10

Ian писал(а):Source of the post Таким образом, школьникам нужно было это переоткрыть, не ссылаясь на Хэмминга
Ну, любознательный школьник вполне мог бы знать про коды Хэмминга.
Эта задача явно с компьютерным уклоном. Чистому математику наверно трудно по-быстрому её решить. Если с нуля делать, то повозиться надо.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 11 гостей