Три в ряд

А давайте отвлечемся от учебы и поговорим об играх! Знаете, какая игра-головоломка наиболее популярна? На самом деле, наиболее популярен целый жанр игр-головоломок, который называется «Три в ряд» – для простой, в общем-то, головоломки, создаются все новые и новые геймплеи, и игра полностью оправдывает такую экономическую ставку: этот жанр игр принес разработчикам более 5 млрд долларов всего за полгода!

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

Давайте попросим наших гостей показать свои сундуки: известно, что ровно у 13 авантюристов есть рубины, ровно у 9 – изумруды, ровно у 15 – сапфиры, ровно у 6 – бриллианты. А еще нам рассказали по секрету: если у авантюриста есть сапфиры, то у него обязательно есть еще и изумруды или бриллианты, но никогда и то, и другое вместе. А если у него есть изумруды – то в сундуке должны быть еще или рубины, или сапфиры. Сможем ли мы с такими вводными определить, какое минимальное количество авантюристов может быть у нас в гостях?

Итак, задача поставлена, принимаемся за решение! В описанной ситуации каждая группа авантюристов представляет собой множества, некоторые из которых пересекаются. На что нужно обратить внимание в первую очередь? Давайте рассмотрим два последних факта – они как раз про пересечение.

Мы знаем, что если у авантюриста есть сапфиры, то у него есть еще и изумруды или бриллианты. То есть множества (сапфиры и изумруды) и (сапфиры и бриллианты) не пересекаются, но в сумме дают ровно множество (сапфиры). Вернемся к первой части условия: здесь нам даны мощности множеств для каждого камня отдельно. И вот тут важно заметить! Число авантюристов с сапфирами точно ровно сумме тех, у кого есть изумруды, и тех, у кого есть бриллианты: 9 + 6 = 15. Что нам это дает? Внимание на формулировки: у каждого авантюриста с изумрудами или бриллиантами есть еще и сапфиры, то есть (сапфиры и изумруды) = (изумруды) = 9 и (сапфиры и бриллианты) = (бриллианты) = 6!

А вот теперь рассмотрим второе условие про пересечение: у каждого авантюриста с изумрудами есть или сапфиры, или рубины. Но мы уже выяснили: во всех сундуках с изумрудами окажутся еще и сапфиры, а это значит, что (изумруды и рубины) = 0, так как в условии прописано «исключающее или».

Итак, мы выяснили, что группы авантюристов с изумрудами и рубинами не пересекаются. Отсюда напрямую следует, что у нас с вами в гостях не менее (изумруды) + (рубины) = 9 + 13 = 22 авантюристов. Мы получили оценку снизу. Достигается ли она?

Последний этап решения задачи – привести пример, чтобы доказать, что 22 и правда минимальное число авантюристов. Мы уже точно знаем, что из 22 человек 9 имеют сапфиры и изумруды. Тогда среди оставшихся тринадцати у 6 есть сапфиры, бриллианты и рубины, а у 7 человек только рубины. Попробуйте сами проверить, что при таком распределении выполняются все условия задачи.

Отлично! Мы с вами выяснили, что у нас в гостях никак не меньше 22 авантюристов, фанатов игры-головоломки «три в ряд». И если домашнее задание уже готово, статья прочитана и задача решена – самое время присоединиться к ним в игре!