Олимпиадные задачи. Раскраски.

Как правило, к олимпиадным задачам относятся так называемые «нестандартные» задачи, т.е. такие алгоритмы решения, которых явно не определены. К таким задачам относятся:

1. Стандартные по фабуле задачи школьной математики, но нестандартные по формам решения.

2. Нестандартные по фабуле и содержанию задачи, требующие анадиза предложенных ситуаций.

3. Олимпиадные и тематические задачи. Это задачи на определенную тему, не содержащуюся в программе школьного курса математики, но обязательно присутствующие в программе подготовки школьников к олимпиадам:

-Принцип Дирихле

-Инварианты

-игры

-стратегии

-графы

-процессы и операции и т.д.

Раскраскиявл. частью решения задачи с инвариантами.

Инвариантом называется некоторое преобразование величина или свойство не изменяется.

Для построения инвариантов иногда используют вспомогательные раскраски, т.е. разбиение рассматриваемых объектов на несколько групп.

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

Пример 1. Из шахматной доски вырезали две противоположные угловые клетки. Докажите, что оставшуюся фигуру нельзя разрезать на «домино» из двух клеток

Решение. Каждая фигура «домино» содержит одну белую и одну чёрную клетку. Но в нашей фигуре 32 чёрных и 30 белых клеток (или наоборот).

Пример 2. Можно ли все клетки доски 9 × 9 обойти конем по одному разу и вер-нуться в исходную клетку?

Решение. Каждым ходом конь меняет цвет клетки, поэтому, если существует обход, то число чёрных клеток равно числу белых, что неверно.

Олимпиадные задачи. Инварианты.

Как правило, к олимпиадным задачам относятся так называемые «нестандартные» задачи, т.е. такие алгоритмы решения, которых явно не определены. К таким задачам относятся:

1. Стандартные по фабуле задачи школьной математики, но нестандартные по формам решения.

2. Нестандартные по фабуле и содержанию задачи, требующие анадиза предложенных ситуаций.

3. Олимпиадные и тематические задачи. Это задачи на определенную тему, не содержащуюся в программе школьного курса математики, но обязательно присутствующие в программе подготовки школьников к олимпиадам:

-Принцип Дирихле

-Инварианты

-игры

-стратегии

-графы

-процессы и операции и т.д.

Инвариант это некая величина или свойства которая при определенном преобразовании не изменяется.

2 вида задач:

· Задачи в которых нужно докозать, что некая величина или свойство является инвариантом

· Задачи в решении которых используется ивариант

Стандартные инварианты: четность – нечетность, раскраска , перестановки, остаток от деления и тд.

Пример

Учитель написал на листке бумаге число 20, листок передоется по классу и каждый ученик либо прибавляет 1 , либо отнимает 1. В классе 33 ученика. Возможно ли получить в конце число 26? (нет, в конце получится не четное число)

Логические задачи, приёмы и методы их решения.

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

Логические задачи можно решать такими методами:

-метод рассуждений - самый примитивный способ. Этим способом решаются самые простые логич.задачи. Идея: проводим рассуждения, используя последовательно все условия задачи и приходим к выводу, кот.будет явл.решением задачи.

-метод таблиц. Позволяет наглядно представить условие задачи и помогают делать правильные логич. выводы в ходе решении задачи.

-метод графов

-метод блок-схем. Последовательность решения оформляется в виде схем

-метод кругов эйлера

Принцип «крайнего» при решении олимпиадных задач.

Под понятием «крайний» понимается рассмотрение какого-либо особого (наибольшего, наименьшего, середин) случая в рассмотренной ситуации.

Пример.

На плоскости расположено несколько точек, все попарные расстояния между которыми различны. Каждую из этих точек соединяют с ближней. Может ли при этом получиться замкнутая ломаная?

Решение:

►

Поскольку все расстояния различны, рассмотрим крайний случай: самое большое расстояние. Пусть это будет АВ, и рассмотрим соединение точек с ними: Д и С. Т.К. АВ ­макс.-но, то по условию точка А не ближайшая к В, поэтому соединяется с С или D. Также и точка В, а это значит что точка В и А остаются не соединенными.◄

Пример.

На плоскости расположенно n-точек, причем S любого треугольника с вершинами в этих точках не превосходит едениц. Докажите, что все эти точки можно поместить в четырехугольник S=4.

Решение:

►

Используя метод крайнего, выберем из всех ∆ наибольшей площади. Пусть это будет ∆АВС.

Проведем через точку В прямую BL||AC, тогда если какая-то точка Х из рассматриваемых расположена по другую сторону от прямой BLчем сторона AC, то S_∆AXC>S_∆ABC, и значит по другуб сторону от прямой BL нет точек (аналогично доказывается что по другую сторону от прямой ||AB и проходящую через вершину С нет точек, и также нет точек, проходящих через вершину А параллельно ВС).

Треугольник, образованный при пересечении прямых BL, CL, AL имеет плащадь в 4 больше чем S_∆ABC, но не больше чем 4.