Логические задачи, решаемые с помощью графов.

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

Графом называется любое множество точек, некоторые из которых соединены линиями или стрелками. Точки, изображающие элементы множества, называют вершинами графа, соединяющие их отрезки – рёбрами графа. Точки пересечения рёбер графа не являются его вершинами. Во избежание путаницы вершины графа часто изображают не точками, а маленькими кружочками. Рёбра иногда удобнее изображать не прямолинейными отрезками, а дугами

Задача 1. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

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

Задачи- игры, стратегии.

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

Стратегия наз выигрышной если независимо от ходов одного из игроков второй при выбранной стратегии выигрывает

В задачах-играх имеет место понятие выигрышной или проигрышной позиции.

 «Правильной игрой» в задачах этого класса называется выигрышная — стратегия, придерживаясь которой игрок выиграет при любых ответных действиях противника.

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

1. инвариант — один из игроков каждым своим ходом приводит состояние игры в некоторое состояние (например, сумма оставшихся незанятыми полей) и такое состояние является выигрышным.

2. выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным.

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

Пример:

Имеется прямоугольный стол каждый из двух игроков по очереди кладет на стол манету. Проигрывает тот, кому некуда положить монету (кол-во монет не ограничено, все монеты равные).

Решение: 1-ый кладет монету в центр прямоугольника, тогда при любом выборе 2-го игрока 1-ый всегда найдет место куда положить монету. Выигрывает при такой игре 1-ый.

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

При решении задач на док-ва часто пользуются принципом дирихле. в самой простой форме его можно сформулировать так:"нельзя посадить 3 кролика в 2 клетки так, чтобы в каждой клетке находилось не более 1 кролика".

В общем виде:"Если в n клетках сидят не меньше n+1 кроликов, то найдется клетка в которой сидит не меньше двух кроликов. Если же в 3-х клетках сидят 2 кролика, то хотя бы 1 клетка пуста".

 Роль клеток и кроликов могут выполнять разные объекты. Главное понять что в задаче кролики, а что клетки.

Общий принцип Дирихле

Если в n-клетках сидит не менее kn+1 – кроликов, найдется клетка в которой  сидят хотя бы k+1 кроликов.

Задача 1. В мешке лежат шарики 2-х разных цветов (много белых и много черных). Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.

Решение: 3 шарика. Это - просто применение принципа Дирихле: кроликами будут взятые шарики, а клетками - черный и белый цвета. Клеток две, поэтому если кроликов хотя бы три, то какие-то два попадут в одну клетку (будет 2 одноцветных шарика). С другой стороны, взять два шарика мало, потому что они могут быть двух разных цветов.

Олимпиадные задачи. Взвешивания. Переливания. 

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

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

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

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

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

-Инварианты

-игры

-стратегии

-графы

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

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

Пример

Имеются чашечные весы без гирь и три одинаковые по внешнему виду монеты, одна из которых фальшивая и легче других. Сколько надо взвешиваний чтобы определить фальшивую монету.(ответ: 1)

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

Пример:

Как имея 5 литровую банку и 9 литровое ведро, набрать из рики 3 литра воды

Решение 0 9

             5 4

0 4

4 0

4 9

5 8

0 8

5 3