Логические задачи графы

Разработка урока «Решение логических задач с помощью графов»

Цель: научиться решать логические задачи способом графа и способом Эйлера.

Тип урока:

Форма организации познавательной деятельности: фронтальная, парная, групповая.

Уч-ся раздаются карточки с 10 задачами,

Учитель: Что-то объединяет эти задачи? Какой тип задач перед вами.

Логический

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

  1. Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

  1. Решение логических задач с помощью таблиц

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

Давайте попробуем решить эти задачи. Для решения мы разделимся на группы, по выбору карточек. Решение задач по времени- 5 минут.

Обсуждение решения каждой группы.

Учитель: Сколько задач вы решили. Разбор одной задачи у доски.

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

Каким способом можно решить?

Назовите цель нашего урока.

научиться решать логические задачи способом графа.

Объяснение задачи учителем

Решение логических задач с помощью графов

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

№1. При составлении расписания на понедельник в IX классе преподаватели высказали просьбу завучу.

Учитель математики: «Желаю иметь первый или второй урок».

Учитель истории: «Желаю иметь первый или третий урок».

Учитель литературы: «Желаю иметь второй или третий урок».

Какое расписание будет составлено, если по каждому предмету может быть только один урок?

Вершины графа – обозначения уроков и их порядковые номера в расписании.

Рёбра графа – высказывания преподавателей:

просьба учителя математики – красные линии (М1 и М2);

просьба учителя истории – зелёные линии – (И1 и И3);

просьба учителя литературы – синие линии (Л2 и Л3).

М

И

Л

1

2

3

№2. На соревнованиях по легкой атлетике Андрей, Боря, Сережа и Володя заняли первые четыре места. Мнения девочек разошлись, как места распределились между победителями.

Даша. Андрей был первым, Володя – вторым

Галя. Андрей был вторым, Борис – третьим

Лена. Боря был четвертым, Сережа – вторым.

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

Эту задачу решим с помощью графа. Метод графов применяет тогда, когда между объектами существует много связей.

Андрей – 1 место,Сергей – 2 место, Борис – 3 место, Володя – 4 место

Марина, Лариса, Жанна и Катя умеют играть на разных инструментах( пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий и испанский), но каждая только один. Известно:

  1. Девушка, которая играет на гитаре говорит по испански.

  2. Лариса не играет ни на скрипке ни на виолончели и не знает английского языка.

  3. Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского.

  4. Девушка, которая говорит по — немецки, не играет на виолончели.

  5. Жанна знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Решение:

Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и рассматривая первое условие она играет на гитаре. Из условия N2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки.

Т.к. Жанна не играет на скрипке, то остается один инструмент, на котором она может играть это виолончель. Тогда Катя играет на скрипке, и знает английский язык.

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

№3. с помощью диаграмм Эйлера-Венна на основе теории множеств

В классе 36 человек. Ученики посещают математический, физический и химический кружки. Математический посещают 18 человек, физический – 14, химический – 10.

Кроме того, 2 человека посещают все 3 кружка, 8 – и математический и физический, 5 – и математический и химический,

3 — и физический и химический. Сколько учеников не посещают никаких кружков?

На изображение последовательно наносим круги, обозначающие множество учеников,

посещающих различные кружки (М 18 – 18 учеников посещают математический кружок и т.д.). В центре диаграммы область МФХ иллюстрирует посещаемость двумя учениками 3 кружков. Вместе с вами заполним остальные области (МФ, ХФ, МХ). Сколько учеников не посещают никаких кружков?

Ответ: 36-(7+6+5+3+2+1+4)=8 8 учеников не посещают кружки.

№2. Пятеро одноклассников – Ирена, Тимур, Камилла, Эльдар и Залим стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии. Известно, что победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере; Камилла и Эльдар тоже заинтересовались информатикой; Тимур всегда побаивался физики; Камилла, Тимур и победитель олимпиады по литературе занимаются плаванием; Тимур и Камилла поздравили победителя олимпиады по математике; Ирена сожалеет о том, что у нее остается мало времени на литературу. Победителем какой олимпиады стал каждый из этих ребят?

Решение.

  1. Рассмотрим множество школьников (И, Т, К, Э, З) и множество предметов, по которым проводятся олимпиады (Ф, И, М, Л, Г). По условию задачи между элементами множеств существует взаимно-однозначное соответствие. Если в ходе задачи выясняется, что X выиграл олимпиаду по предмету Y, то точки X и Y соединяются сплошным отрезком, в противном случае – пунктирным.

  2. Согласно условиям 1, 2 и 3 ни Ирена, ни Камилла, ни Тимур, ни Эльдар не могут быть победителем олимпиады по информатике. Следовательно, Залим – победитель олимпиады по информатике. Соединим вершины графа «З» и «И» сплошным отрезком, а все остальные вершины, обозначающие название предметов, соединяем с вершиной «З» пунктиром.

  1. Отобразим сведения, содержащиеся в высказываниях 3, 4 и 5 на графе.

  1. Из графа видно, что Тимур – победитель олимпиады по географии. Следовательно, соединим вершины графа «Т» и «Г» сплошным отрезком, а все остальные вершины, обозначающие имена ребят, соединяем с вершиной «Г» пунктиром.

  1. Из графа видно, что Камилла является победителем олимпиады по физике. Соединим вершины графа «К» и «Ф» сплошным отрезком, а все остальные вершины, обозначающие имена школьников, соединяем с вершиной «Ф» пунктиром. По условию 6 выясняется, что Ирена не является победителем олимпиады по литературе.

  1. Из графа видно, что победителем олимпиады по математике является Ирена, то есть соединим вершины графа «И» и «М» сплошным отрезком.

  1. Тогда Эльдар – победитель олимпиады по литературе. Имеем конечный граф.

Ответ. Ирена – победитель олимпиады по математике; Тимур – победитель олимпиады по географии; Камилла – победитель олимпиады по физике; Эльдар – победитель олимпиады по литературе; Залим – победитель олимпиады по информатике.

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

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

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

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

Решение задач с помощью графа

1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе — семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках — проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.

Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.

Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.

Виды графов:

1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

2. Неориентированный граф — это граф, в котором нет направления линий.

3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).

Решение задач с помощью графов:

Задача 1.

Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.

Задача 2.

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Решение:

Вершины графа — это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Решение:

Ниже представлен разбор задач.

Применение теории графов при решении логических задач

Введение

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

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

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

Предметом исследования в данной работе является решение логических задач при помощи графов.

Цель исследования: применить графовый аппарат для решения логических задач.

Гипотеза: На наш взгляд решение многих логических задач будет менее трудоемким, мы будем использовать для этого теорию графов.

Задачи исследования:

  1. рассмотреть решение задач при помощи графов;

  2. научиться переводить задачи на язык графов;

  3. сравнить традиционные методы решения задач с методами теории графов.

В 1736 году великий математик Леонард Эйлер нашел решение головоломки, носящей название «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом) омывает два острова (рис. Рисунок 1Рисунок 1). Берега реки с островами были во времена Эйлера связаны мостами так, как это показано на рисунке. В головоломке требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать.

Рисунок 1

Л. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок. Владея материалом вводной части курса «Знакомство с графами», нетрудно воспроизвести идею рассуждения Л. Эйлера. Для этого нужно предварительно заменить Рисунок 1 схемой, приведенной на рисунке 2, где острова и берега изображаются точками.

Рисунок 2

Схема, приведенная на рисунке Рисунок 2 не является, строго говоря графом: на ней имеются кратные ребра. Тем не менее 1736 год, когда эта головоломка была решена, принято считать годом рождения теории графов.

Спустя сто с лишним лет, в 1874 году немецкий ученый Г. Кирхгоф разработал эффективную методику определения значения силы тока в электрической цепи, используя методы и понятия, получившие позднее права гражданства в теории графов. Еще 10 лет спустя английский математик А. Кели (мать его была русской, он владел русским языком и следил за русской математической литературой; он оказался среди тех немногих математиков, которые с самого начала поняли и поддержали идеи Н.И. Лобачевского) разработал теорию деревьев для подсчета числа изомеров насыщенных углеводородов с данным числом n атомов углерода.

Графом в математике называется конечная совокупность точек, называемых вершинами; которые из них соединены друг с другом линиями называемыми ребрами графа .

Графом называется множество точек, изображенных на плоскости (листе бумаги, доске), некоторые пары из которых соединены линиями. Точки называются вершинами графа, линии – ребрами. Степенью вершины называется число ребер, выходящих из вершины.

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

Рисунок 3

Граф на рис.Рисунок 3 изображает схему дорог между селами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф, на котором легко увидеть возможные маршруты. Вершина М вверху- начало маршрутов. Из нее можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4321  24 способа.

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

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G1 (рис.Рисунок 4).

Рисунок 4

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

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

Решение многих логических задач с помощью графов вполне доступно уже младшим школьникам. Для этого им достаточно иметь лишь интуитивные представления о графах и самых очевидных их свойствах.

Рассмотрим примеры использования графов при решении некоторых известных задач. При этом объекты будем изображать точками, а отношения между ними – отрезками (положения точек и длины отрезков произвольны).

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

Задача 1. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас белокурый, другой брюнет, третий рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

Приведем подробное решение. Построим граф отношения, заданного в условии задачи. Для этого, прежде всего, выделим множество фамилий М и множество цветов волос К, элементы которых будем обозначать точками. Точки множества М назовем буквами Б, Ч, Р (Белокуров, Чернов и Рыжов); точки второго множества – б, бр, р (белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы их соединим сплошной линией, а если не соответствует – штриховой. Условие задачи указывает лишь на несоответствия, поэтому вначале должен возникнуть граф, изображенный на рисунке Рисунок 5.

Рисунок 5

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

Принцип решения задачи прост. Если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с его третьей точкой ее необходимо соединить сплошной линией. Поэтому граф на рисунке Рисунок 5 дополняется сплошными линиями, соединяющими точки Б и р, Р и бр (рис. Рисунок 6).

Рисунок 6

Далее остается соединить сплошной линией точку Ч и точку б, так как точка Ч соединена с точкой бр штриховой ли­нией, а точка р уже «занята» (рис. 7).

Рисунок 7

Таким образом, на графе этого рисунка автоматически прочитываем ответ: Белокуров — рыжий, Чернов — белокурый, Ры­жов – брюнет. Таким же приемом решаются, например, задачи 2 и 3.

Задача 2. Для Вани, Коли и Миши испечены пи­роги: один с капустой, другой с рисом, третий – с яблоками. Миша не любит пирог с яблоками и не ест с капустой. Ваня не любит пирог с капустой. Кто какой пирог ест?

Задача 3. На одном заводе работают три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Ива­нов и Семенов. У слесаря нет ни братьев, ни сестер, он самый младший из друзей. Семенов, женатый на сестре Борисова, старше токаря. Назовите фамилии сле­саря, токаря и сварщика.

Приведенные задачи можно успешно решать и с ис­пользованием таблиц. Такой способ или его модифика­ции рекомендуется и разбирается во многих научно-по­пулярных книгах и педагогических пособиях. Можно, однако, указать классы задач, в которых применение графов, изображенных точками и отрезками, оказывает­ся более удобным и оправданным. Использование же в решениях метода таблиц типа турнирных таблиц или их обобщений вынуждает важную часть рассуждений проводить «устно». При этом неоднократно приходится возвращаться к условию задачи, к промежуточным ре­зультатам, многое помнить и в нужный момент поль­зоваться полученной информацией. К такому типу задач относятся задачи с тремя или большим числом множеств рассматриваемых объектов.

Задача 4. Три товарища – Иван, Дмитрий и Степан – преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде;

2. Москвич преподает не физику;

3. Тот, кто работает в Ленинграде, преподает химию;

4. Дмитрий преподает не биологию.

Какой предмет и в каком городе преподает каждый из товарищей?

Решение. Выделим три множества: множество имен, множество предметов и множество городов. Эле­мент каждого из множеств на рисунке 4 задан своей точкой (буквы на этом рисунке — первые буквы соот­ветствующих слов). Если две точки из разных множеств характеризуют признаки разных людей, то будем сое­динять такие точки штриховой линией. Если же две точки из разных множеств соответствуют признакам одного человека, то такие точки будем соединять попар­но сплошными линиями. Существенно, что по условию задачи для каждой точки любого множества в каждом из остальных множеств найдется одна и только одна точка, ей соответствующая.

Рисунок 8

Таким образом, граф на рисунке 8 содержит все заданные в условии элементы множеств и отношения между ними. Задача на языке графов сводится к нахождению трех «сплошных» тре­угольников с вершинами в разных множествах.

Рассмотрим граф на рисунке 8. Напрашивается штри­ховой отрезок ХД, Действительно, Л соответствует X и, одновременно, Л не соответствует Д, т. е. X не может соответствовать Д. Итак, используется типичная для такого рода задач операция на графе: если у тре­угольника с вершинами в трех разных множествах одна сторона сплошная, вторая — штриховая, то третья должна быть штриховой. Из условия задачи следует равномерность еще одной операции на графе: если какая-то точка соединена штриховыми отрезками с двумя точками во втором множестве, то ее следует со­единить с третьей точкой этого множества сплош­ным отрезком. Так проводится сплошной отрезок ДФ. Далее проводится штриховой отрезок ДМ (в тре­угольнике ДФМ сторона ДФ сплошная, а ФМ — штри­ховая), ДК сплошным (ДМ и ДЛ штриховые), Теперь соединим точки Ф и К сплошным отрезком. Если в треугольнике с вершинами в разных множествах две стороны сплошные, то третья тоже будет сплошной. Найден первый «сплошной» треугольник ДФК. Так, не возвращаясь к тексту задачи, руководствуясь лишь естественными операциями на графе, описанными выше, мы находим решение (рис. 9).

Рисунок 9

Отметим последователь­ность, в которой проводились отрезки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершины каждого из трех полученных «сплошных» треугольников определяют ответ задачи: Иван преподает химию в Ленинграде, Дмитрий — физику в Киеве и Степан — биологию в Москве.

В следующей задаче применение графов помогает обнаружить наличие двух решений.

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, француз­ским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 10

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 11

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечи­вают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

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

Задача 6. В шахматном турнире принимали уча­стие 6 партнеров разных профессий: токарь, слесарь, инженер, учитель, врач и шофер. Известно:

1. в первом туре Андреев играл с врачом, учитель с Борисовым, а Григорьев с Евдокимовым;

2. во втором туре Дмитриев играл с токарем, а врач с Борисовым;

3. в третьем туре Евдокимов играл с инженером;

4. по окончании турнира места распределились так — Борисов I место, Григорьев и инженер поделили II и III места, Дмитриев занял IV Место, а Золотарев и слесарь поделили пятое и шестое места.

Какие профессии имели Григорьев, Дмитриев и Евдо­кимов?

Теория графов при решении различных видов задач

Муниципальное бюджетное образовательное учреждение

Октябрьская средняя общеобразовательная школа

Исследовательская работа по математике

по теме

«Теория графов при решении различных

видов задач»

Выполнил:
ученик 7 б класса
Макшун Алексей

Руководитель:

учитель математики

Мошково 2011 год

1. Введение.

1. 1. Актуальность выбранной темы.

Однажды мне встретилась задача, описанная Льюсом Кэрроллом. «Три человека жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались».

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

Цель:

Показать применение теории графов для решения различных видов задач.

Задачи :

· Изучить элементы теории графов для решения интересующих меня задач.

· Разобрать решение различных видов задач.

· Повысить математическую культуру.

1.2. История возникновения теории графов.

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах. Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз. Это им не удавалось, а Эйлер доказал, что это принципиально невозможно. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.

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

Примерами графов могут служить схемы авиалиний, метро, дорог, электросхемы, чертежи многоугольников.

Схема Новосибирского метрополитена.

Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.

Генеалогическое дерево .

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

2. Основная часть.

2.1. Основные понятия теории графов. Применение ее при решении логических задач.

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст. А. На рисунке : Ст. А = 1, Ст. Б = 2, Ст. В = 3, Ст. Г= 2, Ст. Д= 0.

рис.5

Задача №1.

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

Решение:

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

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

Задача №2.

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

По вечерам Андрей и токарь играют в домино против Сергея и электрика.

Определите профессию каждого из друзей.

Решение.

Составим граф из 4 друзей и 4 профессий. Пунктирными линиями отметим невозможные связи, а сплошной — соответствие имени и профессии. Если от каждой вершины выходить 3 пунктирных линии, то четвертая линия должна быть сплошной.

В С Н А

Ш С Т Э

Задача №3.

В небольшом городке живут пять друзей: Иванов, Петренко, Сидорчук, Гришин и Капустин. Профессии у них разные: один из них маляр, другой — мельник, третий- плотник, четвертый-почтальон, а пятый — парикмахер.

Петренко и Гришин никогда не держали в руках малярной кисти.

Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном.

Сидорчук был недавно в ЗАГСе одним из свидетелей, когда Петренко и дочь парикмахера сочетались законным браком. Иванов и Петренко каждое воскресенье играют в городки с плотником и маляром.

Гришин и Капустин по субботам обязательно встречаются в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто?

Решение.

Иванов Петренко Сидорчук Гришин Капустин

маляр мельник плотник почтальон парикмахер

2.2. Эйлеровы пути. Построение фигуры одним росчерком.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Доказательство:

Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро, что и требовалось доказать.

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Доказательство:

Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R — число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать.

Теорема.

Число нечетных вершин любого графа четно. Доказательство:

Что и требовалось доказать.

Задача №4.

Можно ли 25 приборов соединить проводами так, чтобы каждый прибор был соединен ровно с пятью другими?

Решение.

Невозможно. В таком графе было бы нечетное число вершин нечетной степени.

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2. Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

Задача №5.

В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Решение:

Построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).

Эйлеровы графы.

Эйлеров путь — путь в графе, проходящий через каждое ребро ровно один раз.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6) Такими графы названы в честь учёного Леонарда Эйлера.

рис.6 (эйлеровы графы)

Закономерность 3 (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4.

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 5.

Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 6.

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

Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

Задача № 6 о кенигсбергских мостах.

Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз.

Решение.

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

Задача № 7.

Четыре острова соединены между собой и с берегами реки 14 мостами так, как это показано на рисунке. Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз?

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

Задача №8.

Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение:

1) Можно, т. к. только 2 нечетные вершины.

2) Нельзя, т. к. 4 нечетные вершины.

Задача №9.

Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?

Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.

Задача №10. Муха в банке.

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

Решение.

Ребра и вершины образуют граф, все 8 вершин которого имеют 3 степень, и, следовательно, требуемый обход невозможен.

Задача № 11.

Попробуйте построить данные фигуры одним росчерком.

2.3. Плоские графы.

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

Эйлер доказал теорему, которая даёт отрицательный ответ на вопрос этой задачи.

Теорема Эйлера.

Если граф, имеющий n вершин и m ребер,- плоский, тогда справедливо равенство n-m+p=2, где p количество непересекающихся частей (их называют гранями), на которые этот граф разбивает плоскость.

Доказательство.

Граф «три дома и три колодца» имеет шесть вершин и девять рёбер. Если он плоский, количество граней p должно быть равно p = n – m + 2 = 9 — 6 + 2 = 5. Но так как никакие два дома или два колодца не соединены между собой, каждая грань имеет, по меньшей мере, четыре ребра. Получим неравенство 2n ≥ 4p(каждое ребро считается два раза), откуда получаем ложное неравенство 18 ≥ 20. Аналогично доказывается, что полный пятивершинный граф также не может быть плоским.

Теорема Понтрягина – Куратовского.

Граф является плоским тогда и только тогда, когда он не содержит графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.

3. Заключение.

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

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

4. Литература.

1. , Макеева работа по математике. – Саратов: «Лицей», 2002 г.

2. Башмаков в кармане «Кенгуру». — М.: Дрофа, 2010г.

3. Игнатьев смекалка. — М.: «Омега», 1994г.

4. Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.

5. «Математика» — приложение к газете «Первое сентября» №7,2005г

5.Физико-математический журнал «Квант», №6, 1994г.

6. Энциклопедический словарь юного математика / Сост. А.П. Савин.- М.: Педагогика, 1989.

Так же использовались данные со следующих сайтов:

http://www. /index. php? cnt=4

http:infometronovosibirsk_metro_map. htm

Энциклопедический словарь юного математика / Сост. А.П. Савин.- М.: Педагогика, 1989.

Башмаков в кармане «Кенгуру». — М.: Дрофа, 2010г.

http:infometronovosibirsk_metro_map. htm

http://www. /index. php? cnt=4

Физико-математический журнал «Квант», №6, 1994г.

Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.

, Макеева работа по математике. – Саратов: «Лицей», 2002 г.

«Математика»- приложение к газете «Первое сентября» №7,2005г

Физико-математический журнал «Квант», №6, 1994г.

Башмаков в кармане «Кенгуру». — М.: Дрофа, 2010г.

Физико-математический журнал «Квант», №6, 1994г.

Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.

Физико-математический журнал «Квант», №6, 1994г.

Башмаков в кармане «Кенгуру». — М.: Дрофа, 2010г.

, Макеева работа по математике. – Саратов: «Лицей», 2002 г.

, Макеева работа по математике. – Саратов: «Лицей», 2002 г.

Игнатьев смекалка. — М.: «Омега», 1994г.

, Макеева работа по математике. – Саратов: «Лицей», 2002 г.

Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.

Башмаков в кармане «Кенгуру». — М.: Дрофа, 2010г.

Применение графов к решению логических задач

Государственное автономное профессиональное образовательное учреждение Чувашской Республики «Алатырский технологический колледж» Министерства образования и молодежной политики Чувашской Республики

Исследовательская работа:

«Применение графов к решению логических задач»

Автор работы: Шугурова Ольга

II курс, специальности 38.02.01

Руководитель: Фирсова Н.А.

Алатырь – 2019 г.

План

Введение………………………………………………………………………………3

  1. Понятие логической задачи ……………………………………………………. 4

2. Применение графов к решению логических задач…………………………….5

2.1 Основные понятия и теоремы теории графов……………………………….5

2.2 Примеры решения задач с помощью графов…………………………………6

Заключение………………………………………………………………………………13

Литература…………………………………………………………………………………14

Введение

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

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

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

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

Предметом исследования в данной работе является решение логических задач при помощи графов.

Цель исследования: применить графовый аппарат для решения логических задач.

Гипотеза: На наш взгляд решение многих логических задач будет менее трудоемким, мы будем использовать для этого теорию графов.

Задачи исследования:

  • изучить литературу по данной теме;
  • научиться переводить задачи на язык графов.
  • рассмотреть решение задач при помощи графов;
  • определить преимущества данного метода при решении логических задач.

1. Понятие логической задачи.

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

При этом часть утверждений условия задачи может выступать с различной истинной оценкой (быть истиной или ложной).

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

В учебно-методической литературе используются и такие классификации логических задач:

· по содержанию мыслительной операции, задействованной в процессе решения (это задачи на: аналогию; сравнение; умозаключение.классификацию; анализ и синтез; абстрагирование; обобщение);

· по характеру требований (нахождение искомого, построение или преобразование, отыскание процесса);

· по приемам, задействованным в процессе решения (с помощью рассуждений, таблиц, графов, блок-схем, и др.)

Известно несколько различных приемов решения логических задач:

· словесное рассуждение;

· построение графов;

· построение блок-схем;

· построение таблицы;

Каждый из этих способов обладает своими достоинствами.

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

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

Метод графов применяется тогда, когда между объектами, о которых идет речь в задаче, существует много связей. Граф позволяет наглядно представить эти связи и определить, какие из них не противоречат.

Решение многих логических задач с помощью графов вполне доступно уже младшим школьникам. Для этого им достаточно иметь лишь интуитивные представления о графах и самых очевидных их свойствах.

2 Применение графов к решению логических задач.

2.1 Основные понятия и теоремы теории графов.

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

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Примерами графов могут служить схемы авиалиний, метро, дорог, электросхемы, чертежи многоугольников.

Рисунок 1

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

Теорема: Любой граф содержит четное число нечетных вершин.

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Эйлеров граф

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

Рисунок 3.

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

Рисунок 4.

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

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

2.2 Примеры решения задач с помощью графов.

Рассмотрим примеры использования графов при решении некоторых известных задач. При этом объекты будем изображать точками, а отношения между ними – отрезками (положения точек и длины отрезков произвольны).

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

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

Задача 1. На рисунке изображен интересный пример лабиринта в саду Хемптон Корт:

Рисунок 5. Рисунок 6.

Построим соответствующий ему граф. Коридоры лабиринта – это ребра графа, а перекрестки, тупики, входы и выходы – это вершины. (Рисунок 6.)

И, соответственно, выйти из центра лабиринта по маршруту:

13 — 12 — 11 — 9 — 10 — 7 — 4 — 1.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.

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

Рисунок 7.

Решение: Занумеруем последовательно клетки доски:

Рисунок 8.

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии,

возможен. Рисунок 9.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным. Ответ. Соединить телефоны таким образом невозможно.

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Рисунок 10.

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

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G1 (рис.11).

Рисунок 11. Рисунок 12.

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

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

Задача №5 » Задачи на перебор вариантов или задачи про рыцарей и лжецов»

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

Задача 7. Четыре спортсменки Аня, Валя, Галя и Даша заняли первые четыре места в соревнованиях по гимнастике, причем никакие две из них не делили между собой эти места. На вопрос, какое место заняла каждая из них, трое болельщиков высказали предположения:

1. Аня — II место, Даша — III место;

2. Аня — I место, Валя — II место;

3. Галя — II место, Даша — IV место.

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

Решение. На рисунке 14 точки «верхнего» множества соответствуют именам спортсменок, а «нижнего» — занятым местам.

Рисунок 13

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

Предположим, например, что Валя заняла II место, тогда неверными должны быть высказывания; «Аня заняла I место», «Аня заняла II место», «Галя заняла II место». Отрезки, соответствующие ложному высказыванию, будем перечеркивать

Рисунок 14

В таком случае Даша займет III и IV места, что по условию задачи невозможно. Следовательно, предположение, что Валя заняла II место, неверно; верным будет высказывание

«Аня заняла I место» (рис. 15). Но тогда зачеркиваем отрезки АН и ВП, оставляя ДIII. Далее зачеркнем отрезок Д IV.

Рисунок 15

Итак, Аня заняла I место, Даша — III, Галя —II , Валя —IV.

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

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

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, французским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 16

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 17

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечивают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

Заключение

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

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

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

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

Литература

Интернет ресурсы

Графы. Решение задач с помощью графов

Теория графов позволяет решать наиболее легким способом, наглядно многие логические задачи, которые способствуют развитию мышления и интеллекта.
Теория графов является частью комбинаторики. А удобство формулировок комбинаторных задач в терминах графов привела к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики. С 2006 года раздел математики комбинаторику ввели в школьный курс. Многие задачи по комбинаторики можно просто решить, используя понятие граф. Однако пока отсутствуют наглядные электронные пособия, по формированию практических навыков по данной теме. Поэтому тема актуальна и интересна.
Цель работы:
Изучить понятие граф и его элементы, создать электронное пособие, знакомящего школьников с задачами и вариантами их решений по данной теме.
Задачи:
1. Исследовать литературу по теме.
2. Подобрать и решить задачи с использованием понятия графа.
3. Разработать комплект задач по данной теме с ответами.
4. Изучить возможности программы PowerPoint.
5. Создание электронного пособия.
Проблемный вопрос: «В чём заключается особенность задач, которые удобно решать с помощью графов?»
Объект исследования: логические задачи по математике и информатике
Предмет исследования: многообразие задач, методы и приёмы их решения.
Методы исследования: моделирование, сравнение, обобщение, аналогии, изучение литературных и Интернет-ресурсов, анализ и классификация информации.

Файлы:

Исследовательская работа: Исследовательская работа «В мире графов»

2.2. Применение графов при решении задач

Задачи на вычерчивание фигур одним росчерком

Задача 1. О Кенигсбергских мостах. Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу.
Вопрос: можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту. Благодаря этой задаче была создана теория графов.
Мосты через реку Прегель расположены как на рисунке.
(приложение 2 рис.1).

Рассмотрим граф, соответствующий схеме мостов

Проблема семи мостов Кёнигсберга.
Суть: можно ли пройти по 7 мостам города Кёнигсберга, не ступив на каждый более одного раза.

Решение: было найдено русско-немецким математиком Леонардом Эйлером(1736 год).

Его рассуждения заключались в следующем:

1) Число нечётных вершин графа должно быть чётно (теорема 2).
2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
4) Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Задача 2. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля–Меркурий, Плутон–Венера, Земля–Плутон, Плутон–Меркурий, Меркурий–Венера, Уран–Нептун, Нептун–Сатурн, Сатурн–Юпитер, Юпитер–Марс и Марс–Уран. Можно ли добраться с Земли до Марса?

Решение: Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршруты – не пересекающиеся между собой линии.

Ответ: с Земли до Марса добраться нельзя.

Логические задачи.

Задача 3. В соревнованиях по борьбе, проходящих по олимпийской системе, участвуют 20 борцов. За какое минимальное время можно провести соревнование, если в спортивном зале есть только три борцовских ковра, и на каждую схватку, включая разминку и отдых, отводится час? Изобразите схему соревнований с помощью корневого дерева.

Решение: одна из возможных схем приведена на рисунке.

(приложение 2 рис.2)

Ответ: На соревнование уйдет 7 часов.

Задача 4. Среди девяти монет есть одна фальшивая, которая легче других. Определите ее с помощью двух взвешиваний на рычажных весах.

Решение: Разобьем монеты на три группы по три монеты. Положим монеты двух групп на разные чашки весов.

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

Если чашки придут в равновесие, то фальшивая — третья монета. Если чашки не придут в равновесии, то фальшивая — более легкая монета.

Решение этой задачи легко изобразить в виде графа-дерева, похожего на алгоритм. (приложение 2, рис.3)

Задачи на группу знакомств
Задача 5. Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Решение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д.

Это первые буквы имён.

Соединим те точки, которые соответствуют именам созвонившихся ребят.

(приложение 2, рис.4)

Задача 6. В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Решение: Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).

Логическая задача на переливание. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами (приложение рис.16).

В результате получаем два решения:

одно в 7 ходов, другое в 8 ходов.

(приложение 2, рис.5)
Задача 7. Имеется шахматная доска 3×3, в верхних двух углах стоят два чёрных коня, в нижних – два белых (рисунок ниже). За 16 ходов поставьте белых коней на место чёрных, а чёрных на место белых и докажите, что за меньшее число ходов это сделать невозможно.

Решение: Развернув граф возможных ходов коней в круг, получим, что в начале кони стояли так, как на рисунке ниже. А в конце кони должны поменяться местами, при этом каждый конь должен сделать 4 хода, а меньшим числом ходов обойтись не удастся, т. к. кони не могут перепрыгивать через друг друга.

Тогда, передвигая коней в графе, каждый раз перемещая всех коней, как показано на рисунках 1-4, мы получим за 16 ходов белых коней на месте чёрных, а чёрных на месте белых (рис.5). (приложение 2, рис.6)
Примеры задач, решаемых методом графов в приложении 3.

Перейти к разделу 2.3. Генеалогическое древо – один из способов применения теории графов

Журнал Педагог

Конспект занятия по внеурочной деятельности для учащихся 6 класса по математике по теме «Решение логических задач с помощью графов» Описание: данная работа направлена на использование предметных навыков и умений учащихся решать логические задачи с использованием графов. Такие виды задач не вызывают негативного отношения у учащихся с разной математической подготовкой, так как каждый из них может не зная таблицы умножения или математических правил принять участие в решении задач. И как показывает практика, учащиеся с большим интересом решают подобные задачи.
Планируемые учебные результаты:
Предметные
: развитие представления о графах как вспомогательных средствах при решении задач;
Метапредметные
: формирование умения выделять существенные признаки объекта и отношения между объектами; умение строить схемы;
Личностные
: формирование способности увязать учебное содержание с собственным жизненным опытом, понять значение информационного моделирования как метода познания окружающей действительности. В ходе занятия у учащихся могут быть сформированы универсальные учебные действия:
Регулятивные УУД.
Обнаружить и сформулировать учебную проблему, составить план выполнения работы
Познавательные
УУД.
Общеучебные действия: поиск и выделение необходимой информации, самостоятельное создание алгоритмов деятельности. Логические действия: построение логической цепи рассуждений.
Коммуникативные
УУД.
Умение с достаточной полнотой и точностью выражать свои мысли, владение монологической и диалогической формами речи в соответствии с грамматическими и синтаксическими нормами родного языка. Ход занятия. В Википедии можно найти следующее определение графа. В общем смысле
граф
представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара
м н о ж е с т в . Те о р и я г р а ф о в н а ход и т п р и м е н е н и е , н ап р и м е р , в геоинформационных системах ( Г И С ) . Су щ е с т ву ю щ и е и л и в н о в ь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез. Но с помощью графов можно решать логические задачи различной тематики. Рассмотрим некоторые из них.
№ 1.
В первенстве класса по шашкам было 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Каждый участник должен сыграть по одной партии друг с другом. К настоящему моменту некоторые партии уже сыграны: Андрей сыграл с Борисом, Галиной и Еленой; Борис с Андреем, Галиной; Виктор — с Галиной, Дмитрием и Елена – с Андреем и Виктором. Сколько игр проведено и сколько осталось провести? Решение: 1. Изобразим точки с начальными буквами имен всех участников. 2. Соединим отрезками те точки – игроков, которые уже сыграли (голубые). 3. Посчитаем количество получившихся отрезков – игр. (7) 4. Соединим другим цветом тех игроков, которые еще не играли.(красные) 5. Посчитаем количество получившихся отрезков – несыгранных игр. (8)
№ 2
Пятеро ребят — Андрей, Володя, Даша, Борис и Галя договорились пойти в кино. Было решено, что если с кем — то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе. Володя звонил Борису и Даше. Борис звонил Андрею и Даше. Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Нужно выяснить, почему не все собрались у кинотеатра. Решение: 1. Изобразим точки с начальными буквами имен всех ребят. 2. Соединим отрезками те точки – ребят, которые позвонили другим (голубые). Из рисунка видно, что две точки А и Г не соединены отрезком, значит Галя и Даша не дозвонились друг другу и поэтому не пришли к кинотеатру.
№ 3.
Однажды, рано утром, кто – то принес букет и поставил его в вазу на учительском столе. Когда ребята пришли в класс, учитель спросила: «А, знаете ли вы, кто принес цветы?». Ребята стали гадать. Были высказаны различные предположения – цветы принесли Андрей и Борис, Андрей и Даша, Андрей и Сергей, Борис и Даша, Борис и Володя, Володя и Галя, Галя и Даша. Учитель сказала, что в одном из этих предположений одно имя названо правильно, а другое – нет. Во всех же остальных предположениях оба имени названы неправильно. Кто принес цветы? Решение: 1. Изобразим точки с начальными буквами имен всех ребят. 2. Соединим отрезками точки – имена, которые были названы в предположениях.
3. Заметим, что из всех сделанных предположений только одно заслуживает внимания – т.е. только в одном одно имя названо правильно. Значит, надо найти такой отрезок, конец которого не имеет общего с другими точками. Это отрезок АС и точка С. 4. Вывод: цветы принес Сергей.
№4
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Определить самое высокое и самое низкое дерево. Решение: Вершины графа (точки) — это деревья, обозначенный первой буквой названия дерева. В данной задаче два отношения: “ ниже” и “выше”. Рассмотрим отношение “ниже” и проведем стрелки от более высокого дерева к более низкому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от рябины к лиственнице и т.д.
Получили граф, на котором видно, что самое низкое дерево – клен, а самое высокое — тополь.
Итог занятия
Итак, кроме приведенных задач, графы широко используются в строительстве, электротехнике, менеджменте, логистике, географии, машиностроении, социологии, программировании, автоматизации технологических процессов и производств, психологии, рекламе. Из всего этого следует практическая ценность теории графов. В любой области науки и техники встречаешься с графами. Графы — это замечательные математические объекты, с помощью которых можно решать математические, экономические и логические задачи, различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Многие математические факты удобно формулировать на языке графов. Теория графов является частью многих наук. Теория графов — одна из самых красивых и наглядных математических теорий. В последнее время теория графов находит всё больше применений и в прикладных вопросах. Возникла даже компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов.
Домашнее задание.
Подготовить задачи, решаемые с помощью графа.

Методы решения логических задач

Методы решения логических задач

Логические задачи являются оптимальным средством развития творческого мышления и эвристической деятельности школьников. Существуют разные способы формализации, как условий задачи, так и процесса ее решения: алгебраический, табличный, графический и др. Каждый из этих способов обладает своими достоинствами.

Логические задачи встречаются в текстах олимпиад по математике, а также в КИМах ЕГЭ базового уровня по математике. Как правило, задачу можно решить несколькими способами (методами). Чтобы выбрать наиболее простой и эффективный способ для каждой конкретной задачи, необходимо знать все эти способы.

Прием моделирования на полупрямой

Если в задаче имеется множество объектов и требуется установить взаимоотношение между элементами этого множества, то задачу можно решать на полупрямой.

Задача 1. На вечеринку собрались четверо друзей: Аня, Вика, Миша и Коля. Коля пришел раньше Ани, но не был первым. Определите, в какой последовательности друзья приходили к месту встречи, если Вика пришла последней.

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

а) Коля пришел раньше Ани:

б) Коля не был первым, то есть кто-то из друзей опередил Колю:

в) Вика пришла последней:

г) Значит, Миша пришел раньше всех:

Ответ: Миша, Коля, Аня, Вика.

Решение.

а) Вика стоит впереди Сони, но после Аллы

б) Денис не находится рядом ни с Аллой, ни с Викой, значит он – крайний слева

в) Боря и Алла не стоят рядом, Борис не находится рядом с Денисом, значит место Бориса – после Вики

Ответ: Алла, Вика, Борис, Соня, Денис.

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

1) Рысь тяжелее буйвола.

2) Буйвол самый тяжелый из всех этих животных.

3) Медведь тяжелее буйвола.

Решение. Отметим данные задачи на полупрямой, причем с одной стороны полупрямой отметим однозначные данные, с другой стороны – неоднозначные.

М

М

М

Ответ: 24.

Прием моделирования с помощью таблицы

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

Задача 4. Перед соревнованиями по плаванию каждого из четырех участников А, Б, В, Г спросили, на какое место он рассчитывает. А сказал: «Я буду первым», Б сказал: «Я не буду последним», В сказал: «Я не буду ни первым, ни последним» и Г сказал: «Я буду последним». После заплыва оказалось, что только один из них ошибочно предсказал результат. Кто из пловцов ошибся? (Задачи повышенной трудности в курсе алгебры 7-9 классов: Кн. для учителя / Н.П. Кострикина. – М.: Просвещение, 1991; задача № 50)

Решение. Составим таблицу, в которой знаком «плюс» укажем предполагаемые результаты.

Пловец

Места

А

+

Б

+

+

+

В

+

+

Г

+

Предположим, что ошибся А, тогда он мог занять 2-е или 3-е место (4-е место занял пловец Г, который, если ошибся А, правильно предсказал свой результат, так как по условию ошибся только один пловец). В этом случае возможны следующие варианты распределения мест:

а) А – 2, Б – 1, В – 3, Г – 4;

б) А – 3, Б – 1, В – 2, Г – 4.

Докажем, что действительно ошибся пловец А. Если бы ошибся Б, т.е. занял 4-е место, то ошибся бы и пловец Г, что противоречит условию задачи. Если бы ошибся В, тогда он должен быть или первым или последним. В таком случае ошибся бы еще один пловец – А или Г. Если бы ошибся Г, то ошибся бы еще один пловец, в противном случае последнее место не занял бы никто. Так как по условию задачи мог ошибиться только один пловец, то Г не ошибся.

Ответ: ошибся пловец А.

Задача 5. В летний лагерь приехали отдыхать три друга: Миша, Володя и Петя. Известно, что каждый из них имеет одну из следующих фамилий: Иванов, Семенов, Герасимов. Миша – не Герасимов. Отец Володи – инженер. Володя учится в 6 классе, Герасимов учится в 5 классе. Отец Иванова – учитель. Какая фамилия у каждого из трех друзей? (Математические олимпиады в школе. 5-11 классы / А.В. Фарков – М.: Айрис-пресс, 2008; 6 класс, вариант 4, задача № 5)

Решение. Начертим таблицу и заполним последний столбец таблицы, исходя из условий: Миша – не Герасимов, Володя учится в 6 классе, Герасимов – в 5 классе. Значит, Володя – не Герасимов.

Имя

Фамилия

Иванов

Семенов

Герасимов

Миша

Володя

Петя

Следовательно, Герасимов – Петя. Поэтому ставим плюс на пересечении строки «Петя» со столбцом «Герасимов» и минусы – в остальных клетках строки «Петя».

Имя

Фамилия

Иванов

Семенов

Герасимов

Миша

Володя

Петя

+

По условию отец Володи – инженер, отец Иванова – учитель. Значит Володя – не Иванов. Поставим минус в соответствующей клетке, увидим, что Володя – Семенов. Тогда Миша – Иванов.

Имя

Фамилия

Иванов

Семенов

Герасимов

Миша

+

Володя

+

Петя

+

Ответ: Миша – Иванов, Володя – Семенов, Петя – Герасимов.

Задача 6. После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них — математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью:

1) Иван живет не в Минске;

2) Андрей – не в Витебске;

3) житель Минска преподает не математику;

4) Андрей преподает не физику;

5) повезло только жителю Витебска: он преподает любимую им химию.

Можно ли по этим данным определить, кто где живет и что преподает?

Решение. По условиям задачи имеем:

Имя

Город

Дисциплина

Минск

Витебск

Харьков

Математика

Физика

химия

Иван

Андрей

Борис

Значит, Андрей преподает математику. Но математику не может преподавать житель Минска. Таким образом, Андрей – житель Харькова. Но тогда, ни Иван, ни Борис в Харькове не живут.

Отобразим наши рассуждения в таблице:

Имя

Город

Дисциплина

Минск

Витебск

Харьков

Математика

Физика

химия

Иван

Андрей

+

+

Борис

Из таблицы видно, что Иван не живет ни в Минске, ни в Харькове. Следовательно, Иван – житель Витебска и преподает химию:

Имя

Город

Дисциплина

Минск

Витебск

Харьков

Математика

Физика

химия

Иван

+

+

Андрей

+

+

Борис

Значит, Борис – житель Минска и преподает физику. Окончательно получим:

Имя

Город

Дисциплина

Минск

Витебск

Харьков

Математика

Физика

химия

Иван

+

+

Андрей

+

+

Борис

+

+

Ответ: Андрей преподает математику и живет в Харькове, Борис – физику и живет в Минске, Иван – химию и является жителем Витебска.

Прием моделирования с помощью графов

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

Задача 7. Три товарища – Иван, Дмитрий и Степан преподают различные предметы (химию, биологию и физику) в школах Москвы, Тулы и Новгорода. О них известно следующее:

  1. Иван работает не в Москве, а Дмитрий – не в Новгороде;

  2. москвич преподает физику;

  3. тот, кто работает в Новгороде, преподает химию;

  4. Дмитрий и Степан преподают не биологию.

Какой предмет, и в каком городе преподает каждый? (Журнал «Математика в школе», № 3, 2005, стр. 32))

Решение.

В задаче можно выделить три множества: учебных предметов, городов, учителей. Каждое множество содержит по три элемента. Обозначим их точками – вершинами графа.

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

Так, используя условие 1), проведем пунктирную линию, соединяющую объекты Иван и Москва, Дмитрий и Новгород. В соответствии с условием 2) соединим сплошной линией вершины Москва и физика, а условие 3) выразим сплошной линией от точки Новгород до точки химия. По условию 4) Дмитрий и Степан преподают не биологию, соединим соответствующие вершины пунктирными линиями.

Получается, что биологию преподает Иван. Известно, что химик живет в Новгороде, а физик – в Москве, значит, биолог живет в Туле. Проведем соответствующие сплошные линии.

Обратим внимание на треугольник, образованный вершинами Иван, Тула, биология: в нем есть две сплошные стороны, значит, третью сторону (Иван – Тула) также можно выделить сплошной линией. В самом деле, если Иван преподает биологию, а биолог живет в Туле, то Иван живет в Туле.

Что известно про Дмитрия? Дмитрий не живет в Новгороде (по условию) и не живет в Туле (там живет Иван), значит, Дмитрий живет в Москве – проведем соответствующую сплошную линию. Но москвич преподает физику – эта линия тоже сплошная. В треугольнике с вершинами в точках Дмитрий, Москва и физика две стороны сплошные, следовательно, третью сторону тоже можно выделить сплошной линией.

Что же известно про Степана? Степан не живет в Туле (там живет Иван) и не живет в Москве (там живет Дмитрий), следовательно, Степан живет в Новгороде – проведем сплошную линию. Но тот, кто живет в Новгороде, преподает химию – эта линия тоже сплошная. Так появляется третий треугольник из сплошных линий.

Ответ: Иван преподает биологию и живет в Туле, Дмитрий – физику и живет в Москве, Степан – химию и является жителем Новгорода.

Задача 8. Однажды в туристическом лагере оказались вместе пять ребят. Их имена: Леонид, Сергей, Николай, Олег и Петр. Их фамилии: Антонов, Борисов, Васильев, Дроздов и Иванов. Кроме того, известно, что Петр знаком со всеми, кроме одного. Борисов знаком только с двумя. Леонид знает только одного из всех. Дроздов и Сергей не знакомы. Николай и Иванов хорошо знают друг друга. Сергей, Николай и Олег давно знакомы между собой. Антонов знаком только с Петром.

Попробуйте по этим сведениям узнать имена и фамилии всех мальчиков.

Решение. Будем соединять отрезками объекты (ребят), которые знакомы между собой. По условию, что Сергей, Николай и Олег давно знакомы между собой, имеем:

Из условия: Антонов знаком только с Петром делаем вывод, что Леонид – Антонов и соединяем линией Леонида и Петра.

По условию задачи Дроздов и Сергей не знакомы. Следовательно, Петр – Дроздов.

Петр знаком со всеми, кроме одного. Выше сказано, что с Сергеем он не знаком, значит знаком с Леонидом, Николаем и Олегом.

Так как Борисов знаком только с двумя, делаем вывод: Сергей – Борисов. По условию Николай и Иванов хорошо знают друг друга, значит Олег – Иванов, Николай — Васильев.

Борисов

Васильев

Иванов

Ответ: Антонов Леонид, Борисов Сергей, Васильев Николай, Дроздов Петр, Иванов Олег.

Задача 9. 5 школьников приехали из 5 различных городов в Архангельск на областную математическую олимпиаду. «Откуда вы, ребята?» — спросили их хозяева. Вот что ответил каждый из них.

Андреев: «Я приехал из Онеги, а Григорьев живет в Каргополе».

Борисов: «В Каргополе живет Васильев. Я же прибыл из Коряжмы».

Васильев: «Я прибыл из Онеги, а Борисов – из Котласа».

Григорьев: «Я прибыл из Каргополя, а Данилов из Вельска».

Данилов: «Да, я действительно из Вельска, Андреев же живет в Коряжме».

Хозяева очень удивились противоречивости ответов приехавших гостей. Ребята объяснили им, что каждый из них высказал одно утверждение правильное, а другое ложное. Но по их ответам вполне можно установить, кто откуда приехал. Откуда приехал каждый школьник? (Математические олимпиады в школе. 5-11 классы / А.В. Фарков – М. : Айрис-пресс, 2008; 7 класс, вариант 1, задача № 6)

Решение.

Решим задачу, представив ее условие в виде графа.

Вершины графа – фамилии мальчиков и названия городов, откуда они приехали. Ребра графа – высказывания школьников:

мнение Андреева – жирные линии;

мнение Борисова – тонкие линии;

мнение Васильева – жирные пунктирные линии;

мнение Григорьева – тонкие пунктирные линии;

мнение Данилова – штрихпунктирные линии.

Так как каждый из мальчиков сделал только одно правильное заявление, то надо оставить только по одной линии каждого типа. Всего в графе должно остаться 5 линий разных типов.

Предположим, что у Андреева верно первое утверждение, то есть он из Онеги. Тогда надо удалить из графа ребра Григорьев – Каргополь (только одно утверждение Андреева верное), Андреев – Коряжма (он из Онеги), Васильев – Онега (из Онеги – Андреев). Значит, верно первое утверждение Данилова, что он из Вельска и ложно первое утверждение Григорьева, поэтому удаляем из графа ребро Григорьев – Каргополь, а также ребро Борисов – Коряжма (он из Котласа).

Итак, получилось, что Андреев из Онеги, Борисов из Котласа, Васильев из Каргополя, Данилов из Вельска, значит Григорьев из Коряжмы.

Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение правильное, тогда Григорьев приехал из Каргополя. Значит, Данилов приехал не из Вельска (ложное второе утверждение Григорьева), а Андреев не из Онеги. Тогда у Борисова первое утверждение ложное (в Каргополе живет Григорьев), значит, Борисов прибыл из Коряжмы.

Поэтому Андреев не из Коряжмы (в Коряжме живет Борисов) и получается, что верно первое высказывание Данилова – я из Вельска. Получили противоречие: Данилов из Вельска и не из Вельска. Значит, второй вариант невозможен.

Ответ: Андреев из Онеги, Борисов из Котласа, Васильев из Каргополя, Григорьев из Коряжмы, Данилов из Вельска.

Прием моделирования с помощью диаграмм (кругов) Эйлера-Венна

Данный метод позволяет графически решать математические задачи на основе применения теории множеств.

Задача 10. В классе 36 человек. Ученики этого класса посещают математический, физический и химический кружки, причем математический кружок посещают 18 человек, физический – 14, химический – 10. Кроме того, известно, что 2 человека посещают все три кружка, 8 человек – и математический и физический, 5 – и математический и химический, 3 – и физический и химический.

Сколько учеников класса не посещают никаких кружков?

Решение. На рисунке самый большой круг изображает множество всех учеников класса. Внутри этого круга расположены три пересекающихся круга меньшего диаметра: эти круги изображают членов математического, физического и химического кружков и обозначены буквами М, Ф, Х.

Пусть МФХ – множество ребят, каждый из которых посещает все 3 кружка. Дадим аналогичные имена и другим множествам: МФ – множество занимающихся и в математическом, и в физическом кружке (и, возможно, также в химическом), МФ — и в математическом, и в физическом, но не в химическом и т.д.

Впишем нужные имена множеств в области, изображенные на рисунке:

Х

Обратимся к числовым данным. В область МФХ впишем число 2, так как все три кружка посещают 2 ученика. Далее известно, что ребят, посещающих и математический, и физический кружок, — 8. Значит, множество МФ состоит из 8 человек. Но это множество является объединением множеств МФХ и МФ, причем в МФХ входят 2 человека. Значит, на долю МФ остается 6 человек.

Теперь рассмотрим множество МХ, состоящее из 5 человек. Оно также состоит из двух частей: на МФХ приходится 2 человека. Значит, на МХ – 3.

Множество ФХ состоит из 3 человек. На ФХ приходится 1 человек.

Рассмотрим теперь множество М, в которое входит 18 учеников. Оно состоит из четырех частей. Количественный состав трех подмножеств мы уже нашли: это 2, 6 и 3. Значит, в четвертое подмножество, а именно в М, входит 18 – (2 + 3 + 6) = 7 человек.

Аналогично определим количество учащихся в множествах и :
14 – (6 + 2 + 1) = 5, 10 – (3 + 2 + 1) = 4.

Три пересекающихся круга образуют 7 непересекающихся областей, изображающих непересекающиеся подмножества учеников, каждый из которых посещает хотя бы 1 кружок. Просуммируем цифры в этих областях: 6 + 5 + 7 + 3 + 2 + 1 + 4 = 28 человек посещает кружки.

Значит, 36 – 28 = 8 ребят не посещают никаких кружков.

Ответ: в классе 8 учеников, не посещающих кружки.

Задача 11. Среди 150 школьников марки собирают только мальчики. 67 человек собирают марки СССР, 48 человек – Африки и 32 человека – Америки, 11 человек – только СССР, 7 человек – только Африки, 4 человека – только Америки и только Иванов собирал марки СССР, Африки, Америки. Найдите максимальное число девочек. (Задачи повышенной трудности в курсе алгебры 7-9 классов: Кн. для учителя / Н.П. Кострикина. – М.: Просвещение, 1991, задача № 176)

Решение. Изобразим с помощью кругов Эйлера условие задачи

Имеем систему трех уравнений:

(56 = 67 – 11),

(41 = 48 – 7),

(28 = 32 – 4),

откуда 2 (x + y + z) = 122, т.е. x + y + z = 61.

Следовательно, марки собирают 61 + 11 + 7 + 4 + 1 = 84 мальчика, максимальное число девочек: 150 – 84 = 66.

Ответ: 66 девочек.

Задача 12. После зимних каникул классный руководитель спросил, кто из ребят ходил в театр, кино или цирк. Оказалось, что из 36 учеников класса двое не были ни в кино, ни в театре, ни в цирке. В кино побывало 25 человек, в театре – 11, в цирке – 17; и в кино, и в театре – 6; и в кино, и в цирке – 10; и в театре, и в цирке – 4.

Сколько человек побывало и в кино, и в театре, и в цирке?

Решение. Изобразим с помощью кругов Эйлера условие задачи.

В область КТЦ впишем х. Известно, что в кино и в театре побывала 6 человек, значит, на долю КТ остается (6 –х) человек. Аналогично на КЦ приходится (10 – х) человек, на ТЦ – (4 – х) человек.

Рассмотрим множество К, в которое входит 25 человек. Оно состоит из четырех частей. Количественный состав трех подмножеств мы уже нашли: это х, 6-х и 10-х. Значит, в четвертое подмножество, содержащее ребят, которые побывали только в кино входит
25 – (х + 6 – х + 10 – х) = 9 + х человек.

Просуммируем выражения в 7 непересекающихся областях, изображающих подмножества учеников, каждый из которых посетил хотя бы одно культурное заведение:

(9+х)+(6-х)+(1+х)+(10-х)+х+(4-х)+(3+х)=33+х.

По условию из 36 учеников класса 2 ученика нигде не были. Значит,

33 + х = 34, х = 1

Ответ: один человек побывал и в кино, и в театре, и в цирке.

Прием моделирования с помощью блок-схемы

При применении данного метода каждый шаг в рассуждении выделяется отдельным изображением (прямоугольником).

Задача 13. На некотором острове отдельными селениями живут правдолюбы и шутники. Правдолюбы всегда говорят только правду, а шутники постоянно шутят, а поэтому всегда лгут. Жители одного племени бывают в селении другого, и наоборот. В одно из селений попал путешественник, но не знает, в какие именно. Доказать, что путешественнику достаточно первому встречному задать вопрос: «Вы местный?», чтобы по ответу определить, в селении какого племени он находится.

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

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

Прием моделирования с помощью алгебры высказываний

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

Задача 14. В одном королевстве были незамужние принцессы, голодные тигры и приговоренный к казни узник. Но король всякому узнику, осужденному на смерть, давал последний шанс спастись. Ему предлагалось угадать, в какой из двух комнат находится тигр, а в какой принцесса. Хотя вполне могло быть, что король в обеих комнатах разместил принцесс или, что хуже, в обеих тигров. Выбор надо было сделать на основании табличек на дверях комнат. Причем, узнику было известно, что утверждения на табличках либо оба истинны, либо оба ложны. Надписи гласили:

Первая комната: Вторая комната:

По крайней мере, в одной из этих комнат находится принцесса

Тигр
в другой комнате

Какую дверь должен выбрать узник?

Решение.

Введем обозначения:

П1 = В первой комнате находится принцесса.

= В первой комнате находится тигр.

П2 = Во второй комнате находится принцесса.

= Во второй комнате находится тигр.

А – утверждение на первой двери: А = П1  П2

В – утверждение на второй двери: В =

Условие задачи о том, что утверждения на табличках либо одновременно истинные, либо одновременно ложные, записывается так:

А & B  = 1.

Подставим вместо А и В соответствующие формулы и упростим:

А & B  = ((П1  П2) & )  ((

= .

Итак, = 1. Значит, в первой комнате находится тигр, во второй – принцесса.

Ответ: в первой комнате – тигр, во второй – принцесса.

Литература

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *