В стране Бебрасии живут четыре племени: чекбоксы, лаптопы, смартфоны и двоичи.
У каждого из племён есть несколько деревень. Деревни одного племени обозначены на рисунке одинаково.
Однажды племена решили объединиться. Чтобы не создавать хаос, они решили делать это по очереди: сначала какие-то два племени объединяются в новое племя, потом из оставшихся трёх племён какие-то два опять объединяются, и, наконец, объединяются последние два племени.
Объединение двух племён занимает столько месяцев, сколько в этих племенах в сумме деревень.
За какое наименьшее количество месяцев могут объединиться все племена?
1 Ответ
Решение:
Правильный ответ: 24
Давайте пойдём с конца. Последнее объединение в любом случае включает в себя все 12 деревень и длится 12 месяцев.
На предпоследнем шаге у нас есть три племени. Поскольку на длительность последнего шага мы никак повлиять не можем (она всё равно будет составлять 12 месяцев), имеет смысл объединять два племени с наименьшим числом деревень.
С другой стороны, какие два племени мы бы ни объединили на первом шаге, получившееся племя станет самым большим. Значит, на первом шаге мы объединим какие-то два племени в одно, потратив X месяцев, а на втором (предпоследнем) шаге объединим другие два племени, потратив 12-X месяцев.
В итоге получаем X + (12-X) + 12 = 24.
Ответ 24 доступен при любом разбиения 12 деревень на 4 племени. Для этого разбиения он оптимален. Заметим, что при других разбиениях (если бы самое большое племя владело бы большим числом деревень, чем два самых маленьких) можно было бы объединить все племена за меньшее число месяцев.