Программа спецкурсов

Темы спецкурсов, требования к слушателям, содержание программ и некоторые задачи

Лектор: Шаповалов Александр Васильевич

Тема спецкурса: Разрезания клетчатых досок и геометрических фигур

Требования к слушателям: знание геометрии в объеме 7 класса

Содержание курса: 

• Разрезания по клеткам.
• Можно или нельзя?
• Принцип Дирихле.
• Узкие места и их подсчёт.
• Соответствие.
• Чередование и двудольные графы.
• Как доказать невозможность разрезания? Инвариант.
• Перекройка фигур. Теорема Бояйи-Гервина.
• Счет углов и формула Эйлера.
• Разрезания и рациональные числа.

Примеры задач 

• Какое наибольшее число пятиклеточных прямоугольников можно вырезать из шахматной доски?
• Из шахматной доски вырезаны две клетки разного цвета. Докажите, что оставшуюся часть  можно разрезать на двуклеточные прямоугольники.
• Из шахматной доски вырезана одна клетка (любая). Всегда ли можно оставшуюся часть разрезать на трехклеточные уголки?
• Можно ли клетчатую доску 10×10 разрезать на прямугольники 1×4?
• Можно ли какой-нибудь квадрат разрезать на равные треугольники и сложить из них два меньших не равных квадрата?
• Из шахматной доски вырезана одна угловая клетка. На какое наибольшее число равновеликих треугольников можно разрезать оставшуюся часть доски?
• Из копий прямоугольника A можно сложить прямоугольник B. Докажите, что из копий прямоугольника B можно сложить прямоугольник, подобный прямоугольнику A. 
• Можно ли разрезать квадрат на треугольники так, чтобы каждый треугольник имел отрезок границы (ненулевой длины) ровно с четырьмя другими треугольниками?

Лектор: Волченков Сергей Геннадьевич

Тема спецкурса: Графы. Алгоритмы.

Требования к слушателям: начальные знания не требуются

Содержание курса: 

• Графовые модели ситуаций, помогающие исследовать задачу.
• Графы. Определения. Примеры.
• Избранные свойства графов.
• Обходы графов. Пути. Циклы. Деревья.
• Эйлеровы обходы. Алгоритм Флёри.
• Плоские графы.
• Турниры.
• Избранные алгоритмы на графах.
• Алгоритмы с неполной или отсутствующей обратной связью («слепые» алгоритмы).

Примеры задач 

• Обойти Кёнигсбергские мосты.
• Расставить различные натуральные числа, не превышающие N, в таблице 3×3 чтобы в соседних клетках одно число делилось на другое при наименьшем возможном N.
• На шахматной доске стоит несколько ладей. Описать алгоритм их правильной окраски в наименьшее количество цветов.
• Составить расписание туров однокругового футбольного турнира для N команд.
• Вдоль дороги стоят несколько столбов, окрашенных каждый в один из трёх цветов. Начальная окраска неизвестна. Разрешается называть пару номеров столбов, и маляр красит эти столбы по следующему правилу: если столбы окрашены в разные цвета, он перекрашивает их в третий цвет, иначе он ничего не делает. Можно ли все столбы окрасить одинаково? Обратной связи с маляром нет.

Лектор: Емельянов Лев Александрович

Тема спецкурса: Отрезки касательных

Требования к слушателям: знание геометрии в объеме 7 класса

Содержание курса: 

• Неравенство треугольника.
• Параметризация треугольника.
• Вписанная, описанная, вневписанные окружности треугольника.
• Описанные четырёхугольники.
• Касательные к сфере. Полувписанная сфера тетраэдра.
• Точка Содди треугольника.

  Примеры задач 

• Даны 5 отрезков, из которых можно составить пятиугольник. Таких пятиугольников бесконечно много (если существует хотя бы один). Существует ли среди них описанный пятиугольник?
• Тот же вопрос для шестиугольника.
• Можно ли сформулировать критерий существования вписанной окружности многоугольника? Есть ли принципиальная разница между чётно- и нечётноугольниками?

Лектор: Кузнецов Дмитрий Юрьевич

Тема спецкурса: Комбинаторные задачи экстремального типа

Требования к слушателям: начальные знания не требуются

Содержание курса: 

• Задачи типа «Оценка+пример».
• Построение оптимальных конструкций с помощью метода «пропеллера».
• Методы доказательства  оценки: разбиение на части, метод узелков, метод стенок, метод перегородок, метод «якорей».
• Метод раскраски (шахматная, полосатая, диагональная и другие). Связь раскраски с координатами.
• Метод уточнения оценки через построение примера.
• Таблица-доска - двудольный граф. Минимальная связность. Деревья.
• Кодирование при доказательстве оценки.

 Примеры задач 

• Какое наибольшее количество не бьющих друг друга ладей (королей, слонов, коней, ферзей) можно разместить на шахматной доске? 
• Какое наибольшее количество ладей (королей, слонов, коней, ферзей) можно разместить на шахматной доске так, чтобы каждая фигура била ровно 1 (ровно 2, не более 1, не более 2 и т.д.) других фигур?
• Какое наибольшее количество несоприкасающихся между собой кораблей 1×1 (1×2, 1×3, 1×4) можно разместить на поле 10×10?
• Какое наибольшее количество прямоугольников 1×4 можно вырезать по линиям сетки из квадрата 10×10?
• На шахматную доску 8х8 положили 8 доминошек  так, что каждая покрывает ровно две соседние клетки. Доказать, что на доске найдется квадрат, состоящий из четырех клеток, ни одна из которых не накрыта доминошкой.
• Имеется множество билетов с номерами от 1 до 30 (номера могут повторяться). Каждый из учеников вытянул один билет (учеников не обязательно 30). Учитель может произвести следующую операцию: прочитать список из нескольких (возможно одного) номеров и попросить их владельцев поднять руки. Какое минимальное число раз ему надо проделать такую операцию, чтобы узнать номер билета у каждого ученика? 

Лектор: Агаханов Сергей Назарович

Тема спецкурса: Теория чисел. Делимость.

Требования к слушателям: начальные знания не требуются

Содержание курса: 

• Признаки делимости. Разложение числа на простые множители
• Комбинаторные задачи на делимость
• Разбиение числа на цифры
• Деление с остатком.
• Сравнение по модулю. Свойства сравнений.
• НОД и НОК, алгоритм Евклида.

Примеры задач 

• Какое наибольшее число можно составить из цифр 1, 2, ... 9, используя каждую не более одного раза так, чтобы это число делилось на каждую свою цифру?
• Произведением каких четырех последовательных натуральных чисел является число 3024?
• Докажите, что если в трехзначном числе две последние цифры одинаковы и сумма его цифр делится на 7, то и само число делится на 7.
• Докажите, что сумма двух последовательных четных натуральных чисел не может быть квадратом натурального числа.
• Между городами A и B проложена железная дорога длиной 2011 км. На первом километровом столбе написали 1 и 2010, на втором – 2 и 2009, на третьем – 3 и 2008 и т.д. Докажите, что числа на каждом столбе взаимно простые.