А.В.Шаповалов -->Занятия и кружки-->Летняя школа Малого мехмата, 2017

Летняя школа Малого мехмата, Болгария, Приморско
1-18 июля 2017 г.
Группа 10-1

Руководители: Ивлев Фёдор Алексеевич, Кузин Михаил Сергеевич

Артемьев Ярослав, Волкова Мария, Ерицян Эдуард, Запольский Дмитрий, Катаев Матвей, Махирева Алена, Николаев Арсений, Шагурин Иван

Программа зачёта
1. Моделирование с помощью точек и отрезков на прямой и окружности. Задача о разрезании сыра и раскладывании на кучи равного веса и с равным числом кусков.
2. Сдвиги и сжатия групп точек. Задача об отмеривании теплой воды.
3. Доказательство нехватки данных для однозначного ответа путем предъявления неразличимых примеров с разными ответами. Задача об определении цвета клетки.
4. Доказательство невозможности гарантированного алгоритма выигрыша путём построения контрпримера «задним числом». Задача о невидимой точке и квадрате.
5. Упорядочение конечных наборов непрерывных весов. Задача о разложении яблок в пакеты по 4.
6. Многовариантность выбора большей части. Задача о выборе 51 ящика из 100 с бананами и апельсинами.
7. Доказательство без разглашения. Вероятностное доказательство умения установить изоморфизм графов.
8. Обмен секретной незашифрованной информацией по открытому каналу. «Русская карточная задача» о Грише и Лёше.
9. Теорема о пересечении ломаных формулировка и набросок доказательства.
10. Следствия из теоремы о пересечении ломаных: пересечение путей короя и ладьи, проверка связности подграфа решетки 3×3.

Непрерывная комбинаторика-1: точки и сыр

8 июля

Листок:
doc    pdf

В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Хорошей моделью в таких задачах служат наборы точек на прямой и окружности.

Неоднозначные данные

9 июля

Листок:
doc    pdf

Чтобы доказать, что информации недостаточно для получения однозначного ответа, можно построить два примера, которые удовлетворяют всем условиям, но дают разные ответы. Неразличимые примеры и контрпримеры могут строится после того, как испытания уже проведены и ответы даны, с использованием уже полученной информации. Этот метод часто применяется, чтобы опровергнуть предположение о наличие «гарантированного» алгоритма. В частности, в задачах на взвешивание можно доказать наличие монет с одинаковой «судьбой».

Непрерывная комбинаторика-2: порядок

10 июля

Листок:
doc    pdf

В некоторых задачах возникают комбинации из конечного числа объектов нецелого веса. Важным приемом является упорядочение объектов. Предположив противное, мы получим некоторое утверждение, верное для всех наборов. Умело выбирая нужные наборы, придем к противоречию.

Доказательства без разглашения

11 июля

Листок:
doc    pdf

Ты доказываешь банку онлайн, что имеешь право снимать свои деньги. А хакер, скопировав доказательство, не должен этого права получить! Как так сделать?

Пересечение ломаных

12 июля

Листок:
doc    pdf

Теорема. Если внутри квадрата ABCD проходят две ломаные: одна с концами A и C, другая с концами B и D, то эти ломаные пересекаются.
Доказательство сводится к рассмотрению простых случаев с двумя-тремя точками и отрезками. Есть немало олимпиадных задач, где нужна ссылка на эту теорему.