В стране Числонии 16 городов, названия которых – все двузначные числа, составленные из цифр 1, 2, 3, 4. Города соединены авиалинией в том и только в том случае, когда в их названиях есть одинаковые цифры. Все города так разбиты на N областей, что любая авиалиния соединяет города из разных областей. При каком наименьшем N такое возможно?
Давайте рассмотрим все возможные двузначные числа, составленные из цифр 1, 2, 3, 4. Всего таких чисел 4*4 = 16.
Названия городов в Числонии – это эти двузначные числа. Для удобства решения задачи пронумеруем города от 1 до 16.
Теперь рассмотрим возможные варианты городов для каждой области.
1. Область 1 – город 11.
В данном случае авиалиния из этого города должна соединяться только с городами, названия которых содержат цифру 1. Таких городов у нас 4 (11, 12, 13, 14). По условию, авиалиния должна соединять города из разных областей, поэтому в этой области должен быть еще хотя бы один город, название которого не содержит цифру 1.
2. Область 2 – городы 22, 21.
Авиалиния из города 22 должна соединяться только с городами, названия которых содержат цифру 2. Подходят города 12, 22, 42. Как и в предыдущем случае, в этой области должен быть еще хотя бы один город без цифры 2 в названии. Подходят города 13, 23, 33, 43.
Авиалиния из города 21 должна соединяться с городами, названия которых содержат цифру 1. Подходят города 11 и 21. В этой области также должен быть еще хотя бы один город без цифры 1 в названии. Подходят города 32, 42.
3. Область 3 – городы 33, 32, 31.
Авиалиния из города 33 должна соединяться только с городами, названия которых содержат цифру 3. Таких городов у нас 4 (13, 23, 33, 43). Нет необходимости в еще одном городе без цифры 3.
Авиалиния из города 32 должна соединяться только с городами, названия которых содержат цифру 2. Таких городов у нас 4 (12, 22, 32, 42). Нам нужен еще хотя бы один город без цифры 2. Подходят города 13, 23, 33 и 43.
Авиалиния из города 31 должна соединяться только с городами, названия которых содержат цифру 1. Таких городов у нас 4 (11, 21, 31, 41). Нам нужен еще хотя бы один город без цифры 1. Подходят города 42.
4. Область 4 – городы 44, 43, 42, 41.
Авиалиния из города 44 должна соединяться только с городами, названия которых содержат цифру 4. Таких городов у нас 4 (14, 24, 34, 44). Нет необходимости в еще одном городе без цифры 4.
Авиалиния из города 43 должна соединяться только с городами, названия которых содержат цифру 3. Таких городов у нас 4 (13, 23, 33, 43). Нам нужен еще хотя бы один город без цифры 3. Подходят города 14, 24, 34, 44.
Авиалиния из города 42 должна соединяться только с городами, названия которых содержат цифру 2. Таких городов у нас 4 (12, 22, 32, 42). Нам нужен еще хотя бы один город без цифры 2. Подходят города 13, 23, 33, 43.
Авиалиния из города 41 должна соединяться только с городами, названия которых содержат цифру 1. Таких городов у нас 4 (11, 21, 31, 41). Нам нужен еще хотя бы один город без цифры 1. Подходят города 32, 42.
Таким образом, мы рассмотрели все возможные варианты городов для каждой области и выяснили, что для каждой области нам нужно еще хотя бы одно число без соответствующей цифры (цифры 1, 2, 3 или 4).
Так как всего у нас 4 области, значит, нам в каждой области необходимо еще одно число без соответствующей цифры. Теперь рассмотрим, какие числа для этого подойдут.
Мы заметили, что все города разбиты на две группы: города, в названиях которых есть цифра 1 или 2 (это города 11, 12, ..., 42) и города, в названиях которых есть цифра 3 или 4 (это города 13, ..., 44).
В каждой группе чисел по 16, но в каждую область нужно взять только 4 числа. Поскольку в области должны быть разные числа, нужно взять по одному числу из каждой группы.
Таким образом, нам нужно взять 4 числа: одно число из группы чисел, в названиях которых есть цифра 1 или 2, и одно число из группы чисел, в названиях которых есть цифра 3 или 4.
Возможны такие комбинации:
Группа 1: города 11, 12, 21, 22
Группа 2: города 33, 34, 43, 44 (можно использовать любые 4 числа из группы)
Группа 1: города 11, 14, 41, 44
Группа 2: города 32, 34, 42, 44 (можно использовать любые 4 числа из группы)
Группа 1: города 12, 13, 22, 23
Группа 2: города 31, 33, 42, 44 (можно использовать любые 4 числа из группы)
Группа 1: города 12, 14, 21, 24
Группа 2: города 33, 34, 43, 44 (можно использовать любые 4 числа из группы)
Таким образом, мы получили 4 различных комбинации чисел, при которых условия задачи выполняются. Значит, наименьшее возможное значение N – это 4.