Задачи из книги Канель-Белова Ковальджи

[Rasool]

Я сейчас решаю задачки из книги Канель-Белова Ковальджи "Как решают нестандартные задачи".
Приведу пример из книги из раздела "Причесывание задач":

Цитата:

Пример 1. Каждый ученик класса ходил хотя бы в один из двух походов. В каждом походе мальчиков было не больше 2/5. Докажите, что во всём классе мальчиков не больше 4/7.
Решение. «Лобовое» решение состоит в рассмотрении количеств мальчиков, ходивших только в первый поход, ходивших только во второй поход, ходивших в оба похода, то же для девочек, составлении и решении системы уравнений и неравенств. Этого делать не хочется, поэтому будем избавляться от лишних параметров, сводя задачу к её частному случаю. Мы проделаем это в несколько шагов. После каждого шага упрощения становится очевидным следующий шаг. Будем увеличивать число мальчиков в классе, не изменяя числа девочек и не нарушая условия задачи.
1 шаг. «Впишем» всех девочек в число участников обоих походов. От этого доля мальчиков в походах уменьшится, а в классе - не изменится. Итак, можно считать, что все девочки ходили в оба похода.
2 шаг. Если мальчик ходил в первый поход, то освободим его от посещения второго. Доля мальчиков в походе уменьшится. Итак, можно считать, что каждый мальчик ходил только в один поход.
3 шаг. Если в одном походе было меньше мальчиков, чем в другом, то добавим в класс мальчиков. Доля мальчиков в походах останется не больше 2/5, а доля мальчиков в классе увеличится. Можно считать, что мальчиков было в походах поровну.
4 шаг. Задача стала тривиальной: в обоих походах были все девочки и ровно половина мальчиков. Обозначим число девочек 3x, тогда мальчиков в походах было не больше 2x, а во всём классе - не больше 4x. Максимальное число мальчиков в классе 4x, а это 4/7 класса.

То есть по сути нужно рассмотреть "наихудший" случай, а потом от него отталкиваться.
У меня вызвала затруднение задача №7:

Цитата:

7. Алфавит некоторого языка состоит из $n$ букв. Известно, что ни одно слово не является началом другого. $a_k$ - число слов языка, состоящих из $k$ букв. Докажите, что

$$\sum\limits_{k=1}^{\infty} \frac{a^k}{n^k} \leqslant 1$$

Указание. Попробуйте заменить слова максимальной длины на меньшие слова.

Вот черновик моего решения:

Цитата:

Рассмотрим предельный случай, когда в языке только всевозможные слова из $k$ букв. Их $n^k$ штук. Условие задачи выполняется.
Добавим в язык $p$ различных слов из $l = k - m$ букв. Тогда придется вычеркнуть из $k$ - буквенных слов $p \cdot n^m$ слов, начинающихся с $l$ - буквенного слова.
Имеем:

$$\sum\limits_{k=1}^{\infty} \frac{a^k}{n^k} = \frac{n^k-p \cdot n^m}{n^k} + \frac{p}{n^l} = 1$$

Продолжая таким образом, можем прийти к искомому результату.

Теперь вопрос: как использовать указание к задаче "Попробуйте заменить слова максимальной длины на меньшие слова"? Допустим, язык состоит из слов "ooab", "oocd", "ab", "cd". Если разобьем первые два слова "ooab", "oocd" на слова из двух букв, получим такой язык: "oo", "oo", "ab", "cd", "ab", "cd". То есть налицо повторяемость. Как тут быть?

[svv]

Я не знаю, как тут использовать указание, но знаю, как сделать утверждение очевидным.
Пусть буквами языка являются цифры $0,1,...,m$ системы счисления с основанием $n=m+1$. Если в языке есть слово $s_1...s_k$, то закрасим промежуток $[a,b)\subset[0,1)$ вещественной оси, где
$a=\overline{0.s_1...s_k}$
$b=\overline{0.s_1...s_k(m)}=\overline{0.s_1...s_kmmmmm...}=a+n^{-k}$
Поскольку ни одно слово не является началом другого, промежутки не перекрываются.
Утверждение теперь можно переформулировать так: сумма длин неперекрывающихся закрашенных промежутков, соответствующих всевозможным словам, не превосходит $1$.

[Rasool]

svv в сообщении #1568528 писал(а):

Я не знаю, как тут использовать указание, но знаю, как сделать утверждение очевидным.
Пусть буквами языка являются цифры $0,1,...,m$ системы счисления с основанием $n=m+1$. Если в языке есть слово $s_1...s_k$, то закрасим промежуток $[a,b)\subset[0,1)$ вещественной оси, где
$a=\overline{0.s_1...s_k}$
$b=\overline{0.s_1...s_k(m)}=\overline{0.s_1...s_kmmmmm...}=a+n^{-k}$
Поскольку ни одно слово не является началом другого, промежутки не перекрываются.
Утверждение теперь можно переформулировать так: сумма длин неперекрывающихся закрашенных промежутков, соответствующих всевозможным словам, не превосходит $1$.

Оригинально.

[mihaild]

А вы заменяйте слова не по одному, а группами. Возьмите самое длинное слово, длины $k$, возьмите его префикс длины $k - 1$, замените все слова, начинающиеся на этот префикс (их не больше чем $n$) на это слово - сумма не уменьшилась (мы заменили не более чем $n$ слагаемых на одно в $n$ раз большее), а, например, суммарная длина всех слов уменьшилась.

[Rasool]

mihaild в сообщении #1568566 писал(а):

А вы заменяйте слова не по одному, а группами. Возьмите самое длинное слово, длины $k$, возьмите его префикс длины $k - 1$, замените все слова, начинающиеся на этот префикс (их не больше чем $n$) на это слово - сумма не уменьшилась (мы заменили не более чем $n$ слагаемых на одно в $n$ раз большее), а, например, суммарная длина всех слов уменьшилась.

Спасибо, жаль что я сам не догадался.