" Н а у к а м о л о д ы х " , 3 0 - 3 1 м а р т а 2 0 1 7 г . , А р з а м а с
П о с в я щ а е т с я 1 0 0 - л е т и ю Р о с т и с л а в а Е в г е н ь е в и ч а А л е к с е е в а
642
Определите, какой предмет, и в каком городе преподает каждая из
подруг.
Решение: В данной задаче выделим три множества элементов, а именно
множество учителей, множество учебных предметов и множество городов.
Каждое из множеств содержит по три элемента. Обозначим их точками и
подпишем соответственно первыми буквами слов. Эти точки – вершины графа.
В зависимости от условий задачи будем соединять точки отрезками, если имеет
место соответствие между данными элементами, или пунктирной линией, если
соответствия нет. Задача сводится к нахождению на графе трех треугольников с
вершинами в разных множествах, сторонами которых являются сплошные
линии.
Используя условие, что Елена работает не в Новосибирске, а Яна работает не в
Барнауле, проведем пунктирную линию, соединяющую соответственные
элементы. Зная, что житель Новосибирска преподает физику и что житель
Барнаула преподает математику, соединим сплошной линией данные элементы.
Зная, что Яна и Татьяна преподают не информатику, соединим данные
элементы пунктирной линией. Получаем следующий граф:
Из графа видно, что информатику преподает Елена. Соединяем эти
элементы сплошной линией. Далее определим, где живет преподаватель
информатики. Житель Барнаула преподает математику, житель Новосибирска
преподает физику, следовательно, житель Томска преподает информатику.
Обратим внимание, что получился треугольник Елена – Информатика – Томск с
двумя сплошными сторонами, значит, третью сторону также можно выделить
сплошной линией. Получаем граф следующего вида:
Е
Я
Т
Н
Т
Б
М
И
Ф
