Объясните ход решения задачи
В алфавите некоторого языка 22 согласные и 11 гласных букв. Словом в этом языке называется произвольное буквосочетание, в котором нет двух согласных подряд и ни одна буква не использована дважды. Каково наименьшее n такое, что при любом разбиении алфавита на n непустых групп из всех букв хотя бы одной из групп можно будет составить слово?
Голый ответ не нужен.
Вы идите от обратного - задайтесь вопросом, а каково максимальное m при котором условие задачи выполнить нельзя? Тогда искомое n=m+1
И вообще, когда его нельзя выполнить в конкретной группе букв? Если согласных в группе больше, чем гласных не менее, чем на 2. И только тогда. Это интуитивно понятно, но можно (и нужно, по идее) строго доказывать. Примем без доказательства.
Пусть при произвольном разбиении на m групп в каждой i-ой группе гласных букв хᵢ, а согласных (хᵢ+kᵢ), kᵢ⩾2
Просуммируем согласные по всем группам:
22=Σ(хᵢ+kᵢ)=Σхᵢ+Σkᵢ=11+Σkᵢ
Σkᵢ=22-11=11⩾2·m откуда m⩽11/2=5.5, и с учетом того, что m целое число, m⩽5
И в самом деле, к примеру, для m=5 легко построить пример разбиения, при котором не существует ни одной группы из всех букв которой можно было бы составить слово по данным правилам. Вот оно, в верхней строке согласные, в нижней гласные, в одном столбце буквы одной группы:
55444
32222
Поэтому ответ в задаче n=6
22 согласные + 11 гласных = 33 буквы
Слово: чередование гласная-согласная, без повторов
Найти минимальное n: алфавит -> n групп -> хотя бы 1 группа -> слово
Анализ:
Слово: ≥ 1 гласная + ≥ 1 согласная, чередование
Максимальная длина слова: k гласных + (k-1) согласных -> 2k-1; k гласных + k согласных -> 2k
n = 2:
Каждая группа: ≥ 1 гласная + ≥ 1 согласная
Максимальная длина слова зависит от количества гласных/согласных в группе
n = 3:
Возможна группа только с гласными/согласными -> слово невозможно
Минимизация риска:
n < 22 (число согласных), иначе возможна группа без гласных
Решение:
n = 12: даже если все гласные в разных группах, останется ≥ 1 согласная + ≥ 1 гласная -> слово
n > 12: возможна группа только с гласными/согласными -> слово невозможно
Ответ: n = 12
Для составления слова нужно максимум 23 буквы (11 гласных и 12 согласных). При разбиении алфавита на 12 групп, как минимум одна группа будет содержать 3 буквы, из которых можно составить слово. Поэтому наименьшее n=12n=12, чтобы в одной из групп можно было составить слово.
11+22=32
Ответ:32.
