На общем корпоративе в ИТ-компании, куда пригласили всех работников с семьями, четыре ребёнка нашли большие весы и решили устроить взвешивание. Каждый точно знал, сколько он весит, но не хотел никому говорить свой точный вес. В итоге сошлись на том, что будут взвешиваться по трое сразу во всех возможных комбинациях и записывать общий вес, чтобы никто не выяснил точный вес каждого
Получились такие значения: 63, 66, 69 и 72 килограмма. Но когда они показали родителям-программистам свои общие результаты, те быстро поняли, кто сколько весит.
Как они это сделали? Чтобы было проще, исходим из того, что все дети весят по-разному.
Сначала нам нужно понять, сколько всего было взвешиваний (и комбинаций). Для этого обозначим детей буквами: А, Б, В и Г, причём так как вес у всех разный, можно сразу составить неравенство, оно нам пригодится дальше.
A < Б < В < Г
Теперь к комбинациям. Всего у нас 4 ребёнка, по 3 на каждом взвешивании — и это значит, что таких комбинаций можно составить 4! / (3! × 1!) = 4. Если что, восклицательный знак — это факториал.
Дальше используем наше неравенство и упорядочим сразу возможные комбинации по возрастанию веса. Самая лёгкая — A + Б + В, потому что мы взяли первые три веса по возрастанию. Следующая за ней — А + Б + Г, когда мы берём два самых лёгких веса и добавляем последний по тяжести (Г > В). Затем оставляем значения А и Г и добавляем туда значение В, потому что В > Б, — получаем А + В + Г. Наконец, берём самые тяжёлые — Б + Г + Д.
Запишем эти комбинации по возрастанию веса:
A + Б + В
А + Б + Г
А + В + Г
Б + Г + Д
Это все возможные комбинации взвешивания: от того, что мы поменяем порядок слагаемых в каждой, общая сумма (и общий вес) не изменится.
По условию задачи мы знаем результаты взвешиваний, причём нам не говорят, кто при этом взвешивался. Но раз мы выяснили порядок комбинаций по возрастанию, то легко можем сопоставить эти данные:
A + Б + В = 63
А + Б + Г = 66
А + В + Г = 69
Б + Г + Д = 72
И вот тут появляется два варианта решения. С одной стороны, у нас есть четыре уравнения с четырьмя неизвестными — и это прям классика решения таких задач. Находим одно через другое, подставляем в третье и считаем чётвертое. Но есть способ гораздо проще.
Смотрите, если мы сложим все эти уравнения между собой, левые и правые части отдельно, то получим такое:
A + Б + В + А + Б + Г + А + В + Г + Б + Г + Д = 63 + 66 + 69 + 72
3А + 3Б + 3В + 3Г = 270
А + Б + В + Г = 90
А теперь сама хитрость: мы из этого уравнения будем вычитать по очереди каждое из наших и смотреть, что получается. Так как в каждом уравнении используются только три переменных из четырёх, каждое вычитание даст нам значение недостающей переменной. Смотрите сами.
Первое:
(А + Б + В + Г) − (A + Б + В) = 90 − 63
Г = 90 − 63 = 27
Второе:
(А + Б + В + Г) − (A + Б + Г) = 90 − 66
В = 90 − 66 = 24
Третье:
(А + Б + В + Г) − (A + Б + В) = 90 − 69
Б = 90 − 69 = 21
Четвёртое:
(А + Б + В + Г) − (A + Б + В) = 90 − 72
А = 90 − 72 = 18
Вот такое простое решение можно получить, если немного подумать и не начинать сразу решать 4 уравнения обычным способом.
