Комбинаторные задачи Проект ученика 7 класса МОУ СОШ д. Быданово Белохолуницкого района Cкачкова Алексея Руководитель: Брезгина Л.Д. учитель математики 2008

Оглавление. Метод перебора. Дерево возможных вариантов. Таблица истинности. Метод Дирихле.

МЕТОД ПЕРЕБОРА

Космический корабль «Циклон» опустился на неизвестную планету X звезды Y созвездия Центавр. Планета оказалась обитаема и разделена океанами на 3 материка. Каждый материк выдвинул трёх представителей для того, чтобы лететь с кораблем на Землю.

Представителей первого материка зовут Ман,Зан,Сан; второго- Пын, Фын, Шын; третьего – Хыр, Кыр, Дыр. Но на «Циклоне» не хватит анабиозных ванн для 9 человек.

Сколько у инопланетян способов составить делегацию на Землю? Одного инопланетянина можно выбрать 9 способами, второго- 8, а третьего – 7. Получается 9х8х7=507 способов.

У инопланетян есть 507 способов составить делегацию на Землю.

ГРАФОВОЕ ДЕРЕВО

На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить он может кофе, соком или кефиром.

Сколько вариантов завтрака у Вовы? 1)Пряник кофе сок кефир 2) Плюшка кофе сок кефир

3) Бутерброд кофе кефир сок кофе 4) Кекс сок кефир У Вовы 12 вариантов завтрака.

АРТИСТЫ ЦИРКА

Виктор, Андрей, Борис и Михаил работают в цирке. У каждого из них есть свой номер. Один выступает со слоном, другой – с дрессированными собаками, третий из них показывает фокусы, а четвертый выступает клоуном.

Определите, какой номер на сцене показывает каждый из них? Михаил не работает с животными. Номер Андрея наиболее загадочен. Борис дружит с тем, кто выступает в номере со слоном.

Мы знаем, что Михаил не работает с животными ВикторАндрейБорисМихаил Клоун Фокус ник Собаки - Слон -

Мы знаем, что номер Андрея наиболее загадочен ВикторАндрейБорисМихаил Клоун - + Фокус ник + - Собаки - - Слон - -

Борис дружит с тем, кто выступает в номере со слоном ВикторАндрейБорисМихаил Клоун Фокус ник Собаки Слон - - -

Виктор выступает в номере со слоном ВикторАндрейБорисМихаил Клоун Фокус ник Собаки Слон

Михаил – клоун Андрей – фокусник Виктор выступает со слоном Борис дрессирует собачек

ТАБЛИЦА ИСТИННОСТИ

Четыре спортсмена бежали дистанцию. Когда к ним подошли после забега, чтобы узнать, кто и как пробежал, первый спортсмен ответил: «Я был не первым и не последним»; второй сказал: «Я не был первым»; третий ответил: «Я был первым»; четвертый сказал «Я был последним».

Кто из спортсменов говорит неправду и кто пришел первым, если известно, что только один из них врет?

1 спортсмен 1 место2 место3 место4 место

1 спортсмен говорит правду 1 место2 место3 место4 место

2 спортсмен 1 место2 место3 место4 место спортсмен говорит правду

3 спортсмен 3 спортсмен говорит правду 1 место2 место3 место4 место

4 спортсмен 4 спортсмен врёт 1 место2 место3 место4 место

МЕТОД ДИРИХЛЕ

В коробке 10 красных, 8 синих, 8 зелёных и 4 жёлтых карандаша. Берём карандаши из коробки не глядя. Каково наименьшее число карандашей, которое надо взять, чтобы наверняка было хотя бы:

А) 4 карандаша одного цвета Предположим, берём 1 карандаш, и вдруг он синий. Берём ещё 1 карандаш, а он зелёный. Синий и зелёный карандаш повторятся ещё 4 раза. 14-ый карандаш мы взять не сможем: нарушится условие задачи. Итак, чтобы было 4 карандаша одного цвета, мы можем взять только 13 карандашей.

Б) по карандашу каждого цвета Предположим, мы сначала выбрали все красные, синие и зелёные. Тогда берём 1 карандаш, и вдруг он жёлтый. Второй и третий карандаши тоже жёлтые. 28-ой карандаш мы взять не можем: нарушится условие задачи. Итак, чтобы взять по карандашу каждого цвета, мы можем взять только 27 карандашей.

В) 1 жёлтый карандаш Берём 1 карандаш, и вдруг он жёлтый. Второй и третий карандаши тоже жёлтые. 18-ый карандаш мы взять не можем: нарушится условие задачи. Итак, чтобы взять один жёлтый, мы можем взять только 17 карандашей.

Г) 6 синих карандашей Сначала мы берём все красные, зелёные и жёлтые. Берём 1 карандаш, пусть он синий. Если мы возьмём 29 карандашей, то нарушим условие. Итак, чтобы было 6 синих, мы можем взять только 28 карандашей.