Xreferat.com » Рефераты по математике » Логические задачи и методы их решения

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

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

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

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

- Но ведь это очень трудно, - печально вздохнула Леночка.

- Совсем не трудно, - утешил её дедушка. – К тому же я помогу тебе – вот послушай:

1) ни один шарик не лежит в коробочке того же цвета, что и он сам;

2) ы красной коробочке нет синих шариков;

3) в коробочке нейтрального цвета лежат один красный и один зелёный шарик. (Тут Леночка, не выдержав, спросила, что такое нейтральный цвет. Дедушка объяснил, что так принято называть белый или чёрный цвет);

4) в чёрной коробочке лежат шарики холодных тонов (Леночка уже знала, что холодными называют зеленые и синие тона);

5) в одной коробочке лежат белый и один синий шарик;

6) в синей коробочке находится один черный шарик. Помогите Леночке решить дедушкину задачу!

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

Первый способ решения (рис.7).


Коробочка Белая Черная Синяя Зеленая Красная
Шарик




Белый - - - -





Черный - - - - +




Синий - -

- -

- -
Зеленый + -



- -

Красный + - - -



- -

Рис.7.


Из утверждений 1, 2, 3 ,4 следует, что в белой коробочке лежат один зеленый и один красный шарики. Тогда в черной коробочке лежат либо два синих, либо синий и зеленый; но из утверждения 5 следует, что два синих шарика лежать в черной коробочке не могут. Один зеленый шарик лежит в белой коробочке, второй в черной, значит зеленых шариков нет в синей и красной коробочках (рис. 8).

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


Коробочка Белая Черная Синяя Зеленая Красная
Шарик




Белый - - - -





Черный - - - - +




Синий - - + - - -

- -
Зеленый + - + - - - - - - -
Красный + - - -



- -

Рис.8.


Красный шарик может лежать только в синей коробочке, а значит белый и черный – в красной (рис.9).


Коробочка Белая Черная Синяя Зеленая Красная
Шарик




Белый - - - - - - + - + -
Черный - - - - + - - - + -
Синий - - + - - - + - - -
Зеленый + - + - - - - - - -
Красный + - - - + - - - - -

Рис.9.


Второй способ решения (рис.10).


Черная белая зеленая красная синяя


Черный


Черный белый зеленый красный синий


Красный и зеленый шарики, по условию 3, образуют пару одной коробочки. Так как в синей коробочке одно «место» занято, то эта пара может лежать только в белой. Сузим информацию. По условию 5, синий и белый шарики образуют пару. Эта пара может лежать только в зеленой коробочке (рис.11).


Черная зеленая красная синяя


Черный


Черный белый белый зеленый красный синий синий


Рис. 11.


Ещё «сузив» информацию, получим окончательное решение этой задачи (рис. 12).


Черная красная синяя


Черный


Синий белый белый черный красный


Рис. 12.


в) Сопоставление трех множеств

следующая задача «трехмерна», т.е. для ее решения нужно сопоставить три множества. Рассмотрим способ решения этой задачи при помощи таблиц.

Задача 6. «Трамвай в часы «пик».

Один психолог решил заняться изучением того, как влияет на нервную систему человека поездка в переполненном трамвае, в часы «пик». Для этого опросил по одному пассажиру с каждого из четырех маршрутов трамвая; 55, 15, 25 и 33. среди опрошенных, которых звали Андрей (А), Петр (П), Владимир (В), Леонид (Л), оказалось по одному представителю четырех профессий :слесарь(с), электромонтер (э), маляр (м), фрезеровщик (ф). К сожалению, поездки в набитых трамваях основательно истрепали нервы самому психологу. Не удивительно, что он забыл, у кого из опрошенных какая профессия. Впрочем, такая забывчивость сама по себе достаточно красноречиво говорит о том, как влияет на нервную систему человека поездка в переполненном трамвае! В памяти нашего психолога сохранились лишь бессвязные отрывки из того, что рассказывал каждый из опрошенных о своем маршруте. Разумеется, полагаться на память было нельзя, и психилог решил проверить все самым тщательным образом. Ну и, конечно, нужно было выяснить, у кого какая профессия. Вот что удалось выяснить;

  1. Номер трамвайного маршрута, которым следовал Владимир, начинается не с единицы.

  2. О тридцать третьем маршруте рассказывал кто-то из рабочих- металлистов.

  3. Номер трамвайного маршрута, которым следовал фрезеровщик, составлен из таких цифр, что их сумма равна числу букв в имени фрезеровщика.

  4. Леонид рассказал о трамвайном маршруте, номер которого состоит из двух одинаковых цифр.

  5. Имя электромонтера начинается не с буквы В.

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

  7. В памяти психолога вдруг отчетливо всплыла фраза, сказанная Леонидом кому-то из пассажиров: «Вы сели не на тот трамвай, вам нужно пересесть на пятьдесят пятый».

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

Решение. Чтобы отразить соответствие между двумя любыми множествами, необходимо составить три таблицы. Разложив, условия задачи на элементарные запреты, отметив их в таблице, затемнив соответствующую клетку (рис. 13).

В таблице 1 (рис. 13) сразу находится частичное решение: Леонид ехал в трамвае с номером 33. Значит, что ни электромонтер, ни маляр не были пассажирами трамвая 33, и то, что Леонид не фрезеровщик, делаем вывод, что Леонид – слесарь.

На самом деле мы воспользовались «правилом треугольника». Треугольником, в данном случае, называются фигуры из трех клеток, соединенных линиями соответствия (рис. 14).

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

а) во всех вершинах расположены элементарные запреты;

б) в двух вершинах расположены элементарные запреты, а в третьей – знак соответствия (кружок);

в) во всех трех вершинах расположены знаки соответствия (кружки);

Доказательство этого правила аналогично приведенному в задаче 2. пользуясь правилом, получим окончательное решение.

Леонид - слесарь, 33-й маршрут трамвая;

Андрей - фрезеровщик, 15-й маршрут;

Владимир - маляр, 25-й маршрут;

Петр - электромонтер, 55-й маршрут трамвая.

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


Задача 7. Решите представленную на рисунке 16 задачу.



Рис. 16.


Как видно из рисунка, нельзя найти ни одного частичного решения задачи. Однако, рассмотрим на рис. 16 первую строку таблицы I. Кружок, разрешающий соответствие между элементами, может стоять либо в первой, либо во второй клетках. Предположим, что кружок стоит во 2-й клетке. Тогда клетка А-а и А-в в таблице II, по правилу треугольника, должны быть заняты элементами запрета. Первая строка в таблице II оказалась «запрещенной», но, если задача имеет решение, этого быть не может. Таким образом, кружок в таблице I, в первой строке, стоит в клетке А-б. Если посмотреть на строки А (II) и γ(III), - видно, что элементарные запреты дополняют друг друга до полной строки. Такие строки назовем дополняющими друг друга поперечными строками.

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

Теперь можно сформулировать правило переноса клеток, или правило дополнительности:

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

По этому правилу, поперечные, дополняющие друг друга строки А-П и γ-III пересекаются в клетке А-γ-I. Значит, в этой клетке расположен элементарный запрет, (Тот же результат был получен при помощи рассуждений). Дальше задача уже легко решается при помощи правил, известных ранее. На рисунке 17 показана клетка пересечения двух дополняющих строк.

Трехмерная задача может решаться и в системе координат. Вот как выглядит такая система для данной задачи (рис.19). Все правила решения для трехмерной задачи остаются справедливыми.




г)


Многомерные задачи.


Задача 8. «Преступление в гостинице». Когда в 11 часов утра служащие гостиницы в Пиэри Поуч открыли, наконец, дверь четвертого номера, расположенного на первом этаже (до этого они долго, но безуспешно пытались достучаться, но им никто не открывал), глазам их предстало ужасное зрелище: знаменитая кинозвезда, обворожительная мисс Вамп лежала на паркете в глубоком обмороке, все вещи были разбросаны в беспорядке, а бесценное бриллиантовое ожерелье кинозвезды исчезло. Правда, мисс Вамп вскоре пришла в себя, но ничего вспомнить так и не смогла. Пришлось обратиться за помощью к знаменитому сыщику Сэму Силли и его ловкому помощнику Джонни Вуду. Сыщик и его помощник тотчас же принялись за работу. Вскоре им удалось выяснить следующее:

1.На первом этаже гостиницы расположено всего 6 номеров: от первого до шестого.

2. Мисс Вамп в последний раз видели в ресторане гостиницы в 18 часов вечера, накануне похищения бриллиантов. Ожерелье было тогда на ней.

3. С 18 часов вечера до 10 часов утра никто из служащих гостиницы не входил в коридор перед номерами, расположенными на первом этаже, и ничего, кроме стука в дверь, не слышали.

4. Между 18 часами вечера и полуночью в гостинице побывало всего 6 посторонних: мистер Браун, мистер Грин, мистер Хилл, мистер Смит, мистер Тейлор и мистер Уайт. Все они приходили к постояльцам, занимавшим номера на первом этаже. Портье, которому из-за его стойки прекрасно виден весь коридор первого этажа, отчетливо запомнил, что каждый из них заходил лишь в один номер, причем ни какие два посетителя не заходили в один и тот же номер. К сожалению, портье не записал, в какой номер заходил каждый из посетителей и до которого часа оставался в гостинице. К тому же, все посетители заходили в гостиницу в различное время: один побывал в ней между 18 и 19 часами, другой между 19 и 20 и т.д. Последний посетитель заходил в гостиницу между 23 к 24 часам. Сэм Силли навестил каждого из шести подозреваемых и выяснил следующее:

5. Достоверно известно, что с 20 до 24 часов мистер Браун принимал у себя дома гостей. Будучи образцовым хозяином мистер Браун от начала до конца своего приема ни на минуту не покидал гостей.

6. Столь же неопровержимо установлено, что с 21 часа до 24 часов мистер Грин находился среди гостей мистера Брауна.

7. Допросить мистера Хилла не удалось, но это не помешало Джони Вуду собрать подробнейшие сведения о подозреваемых и их окружении, снять отпечатки пальцев, следов обуви и т.д. (Попутно, выяснилось одно странное обстоятельство: на мистере Смитте оказались те же ботинки, которые накануне с 18 до 24 часов носил мистер Хилл).

8. Мистер Тейлор с 19 часов 45 минут до 21 часа довольно громко выяснял отношения со своей женой, что могут подтвердить его соседи.

9. Мистер Уайт с 19 до 22 часов находился в театре, а с 23 часов до полуночи присутствовал на заключительной части приема, устроенного мистером Брауном.

Вернувшись в гостиницу, Сэм Силли и Джонни Вуд тщательно осмотрели все номера, расположенные на первом этаже, и установили, что:

10. Все окна плотно закрыты и через них снаружи в гостиницу никто не проникал.

Затем они сравнили все обнаруженные в номерах следы (отпечатки обуви, пальцев, отдельные волоски и т.д.) с теми данными, которые им удалось собрать о подозреваемых. Выяснилось следующее:

11. В номер 5 не заходили ни мистер Смит, ни мистер Тейлор, ни мистер Уайт.

12. Мистер Смит не заходил в номера 1, 3, 6.

13. Мистер Грин не мог быть посетителем номера 3 и номера 6.

Наконец, допросили портье. Приводим выдержку из протокола допроса:

14. Сэм Силли: Вы утверждаете, что незадолго до 20 часов на несколько минут задремали за своей стойкой. Не мог ли кто-нибудь за это время незаметно проникнуть в гостиницу или пробраться из одного номера в другой?

Портье: Входная дверь была заперта, сэр. Я сплю очень чутко, а двери номеров слегка скрипят. Стоило уходившему посетителю хлопнуть дверью, как я бы сразу проснулся. А ведь скрип был очень тихий: так скрипят двери лишь в 1 и 4-м номерах. Затем портье припомнил, что:

15. До 19 часов никто не входил ни в 5-й, ни в 6-й номера.

16. В 20 часов 10 минут в 1 или 3 или 6 номерапришел посетитель, а также, что:

17.Между 22 и 23 часами двери 2, 3 и 6-го номеров не открывались: в эти номера никто не входил и никто не выходил.

Собранные данные позволили сыщикам напасть на след преступника. Из условий 10, 4, 3 и 2 напрашивается почти неопровержимый вывод: бриллиантовое ожерелье похитил один из шести посетителей, а именно тот, который либо вечером, либо ночью заходил в 4-й номер. Можно ли найти преступника, пользуясь всеми данными, собранными Сэмом Силли и Джоном Вудом?

Решение. Одни лишь материалы следствия не позволяют получитьоднознаяного решения ни в одной из таблиц. Но стоит воспользоваться правилом дополнительности, как появляются сразу 5 элементарных запретов (рис. 20).




Эти запреты позволяют найти первое частичное решение: мистер Хилл заходил в номер 5.

Далее задача решается методом треугольника. Уже 10-е частичное решение позволяет установить виновность мистера Брауна, который заходил в номер 4 между 19 и 20 часами. После частичного решения 13 в таблицах I и II остается по 4 пустых клетки, которые не удается заполнить (рис. 21). Но, поскольку мистер Смит заходил в гостиницу раньше или позже мистера Тейлора, что не вызывает противоречия, задача имеет два окончательных решения.

Рассмотрим еще одну задачу, где требуется установить соответствие между множествами, но этих множеств уже 5 (может быть и 6, и 7). Автоматически, пользуясь правилами, решить такую задачу уже не удается. Однако она не менее привлекательна и интересна.


Задача 9. «Укого живет сорока». На одной из улиц дачного поселка только 5 домов. Они окрашены в разные цвета, и занимают их семьи поэта, писателя, критика, журналиста и редактора. В доме каждой семьи живет любимая птичка. Глава семьи получает на завтрак любимый им напиток, после чего отправляется а город, пользуясь любимым способом передвижения. Известно, что:

  1. поэт пользуется велосипедом;

  2. редактор живет в красном доме;

  3. критик живет в крайнем доме слева, а рядом расположен голубой дом;

  4. тот, кто ездит на мотоцикле, живет в среднем доме;

  5. тот, кто живет в зеленом доме, всегда отправляется в город пешком;

  6. зеленый дом расположен справа от белого;

  7. в доме, где живет снегирь, на завтрак всегда бывает молоко;

  8. тот, кто на завтрак получает какао, живет в доме, соседнем с тем домом, где живет синица;

  9. в желтом доме на завтрак подают чай;

  10. живущий рядом с любителем канареек утром пьет чай;

  11. писатель пьет только кофе;

  12. тот, кто ездит на своем автомобиле, любит пить томатный сок;

  13. в доме журналиста живет попугайчик.

А у кого живет сорока?

Решение. Для решения задачи сразу составим основную таблицу, которую будем заполнять по ходу решения (рис. 22). Воспользуемся условиями 3 и 4. По условию 6 имеем две возможности: 31 – зеленый дом №4, 32 – зеленный дом №5. Продолжим заполнять основную таблицу, если за истину принять предложение 31 (рис. 22, подчеркнуто одной чертой). Из 6 следует, дом №3 – белый; (2,3) – дом №5 красный, тогда дом №1 – жёлтый. Учтем условия 5 и 9; (9; 10) – в голубом доме живут канарейки; 1 в голубом доме живет поэт, который пользуется велосипедом. Из условия 12 следует, что редактор ездит на автомобиле и любит томатный сок.

Где живет писатель? Имеем две возможности:

- П1: писатель живет в белом доме;

- П2: писатель живет в зеленом доме.

Продолжим рассуждения, считая верным утверждение П1 (рис. 22, курсив). Тогда в зеленом доме живет журналист. Из условия 11 следует , что в среднем доме пьют кофе. Из 13 – следует, в доме №4 живет попугайчик.

Рассмотрим условие 7. Молоко на завтрак может быть либо в доме №2, либо в доме №4. Но там не может жить снегирь. Получив противоречивые данные, возвращаемся к гипотезе П2. Снова условие приводят к противоречию (рис. 23).

Рис 22.

Цвет дома

желтый

голубой

белый

зеленый

красный

Глава семьи критик

поэт

писатель

журналист

редактор

Напиток

чай



кофе

сок

Способ передвижения

велосипед

мотоцикл

пешком

автомобиль

Птичка

канарейки

попугайчик




Цвет дома

желтый

голубой

белый

зеленый

красный

Глава семьи критик

поэт

писатель журналист

редактор

Напиток

чай



кофе

сок

Способ передвижения

велосипед

мотоцикл

пешком

автомобиль

Птичка

канарейки

попугайчик

Рис. 23.


Возвращаемся к гипотезе 32. Тогда из 2 следует: дом №1 желтый, а следовательно, в голубом доме живут канарейки. Попробуйте ответить на вопрос: «Где живет поэт?». Два варианта ответа (так как по условию 1, поэт пользуется велосипедом):

- ПТ1 – поэт живет в голубом доме;

- ПТ2 – поэт живет в белом доме.

Предположим, что вариант ПТ1 верен (рис. 24, курсив). Из 12 следует: сок пьют в белом доме. Из 11 следует, что писатель живет в зеленом доме и пьет кофе; в белом доме живет журналист, у которого есть попугайчик (условие 13). По условию 8, какао на завтрак могут получать поэт и редактор. Но у редактора нет соседа, который держит синицу. Значит какао любит поэт, а синица живет у критика.

Условие 7: молоко на завтрак может быть только у редактора. Получаем

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: