Регион 2023

Подсказка 1:

Для удобства расстояние между соседними столбами примем за единичное. Также пронумеруем их от 1 до n. Пусть nᵢ — количество столбов i-го цвета. Сколько всего будет искомых пар?

Подсказка 2:

Несложно догадаться, что для одного цвета таких пар nᵢ − 1 (количество промежутков). Значит, всего n₁ − 1 + ... + nₖ − 1 = n − k. Задача на оценку + пример, однако по условию нам дана только различность всех расстояний. Для примера, как мы можем оценить сумму 2-ух различных натуральных чисел, зная, что они от 1 до 5?

Подсказка 3:

Очевидно, что она ≥ 1 + 2 и ≤ 4 + 5. Применим аналогичную идею, только сумму чего будем оценивать?

Подсказка 4:

Кажется, хорошей идеей будет оценить сумму всех расстояний S. S ≥ 1 + 2 + ... + (n − k) = (n − k)(n − k − 1)/2. Да, мы получили какое-то неравенство, но оценку на количество из него пока что не вывести. Какое неравенство мы хотим получить для итоговой оценки?

Подсказка 5:

То, где с обеих сторон участвуют только переменные n и k. С правой частью мы справились, что же делать с левой?

Подсказка 6:

Необходимо выразить или оценить сверху S с помощью n и k (идея двойного подсчёта). Зайдём из далека. Как можно посчитать (не оценить) сумму расстояний для конкретного цвета?

Подсказка 7:

Попробуем сначала самым честным и пробивным способом. Пусть d₁, ..., dₚ — номера столбов первого цвета (НУО). Тогда искомая величина равна d₂ − d₁ + d₃ − d₂ + ... + dₚ − dₚ₋₁. А если покороче?

Подсказка 8:

Сумма расстояний для первого цвета = dₚ − d₁ (в целом, это интуитивно). Может обобщим эту идею?

Подсказка 9:

Пусть aᵢ — номер первого столбца i-го цвета, bᵢ — последнего. Тогда чему же равно S?

Подсказка 10:

S = b₁ − a₁ + ... + bₖ − aₖ = b₁ + ... + bₖ − (a₁ + ... + aₖ). Однако переменных k и n мы пока что не наблюдаем. Как бы их привязать к этому выражению?

Подсказка 11:

Разумеется, в явном виде выразить через n и k мы не сможем (ибо сумма может быть разной), значит, нужно вновь оценить сверху (чтоб нам на руку сыграла транзитивность в неравенствах). Посмотрим, что мы имеем: две суммы различных чисел. Кажется, мы где-то это уже видели...

Подсказка 12:

Поскольку мы хотим получить оценку сверху на S, то сумму b₁ + ... + bₖ нужно оценить снизу, а a₁ + ... + aₖ сверху. Метод нам известен, а что же получается в итоге?

Подсказка 13:

S ≤ k(n − k) (получите данный вид самостоятельно). Что же мы имеем? (n − k)(n − k − 1)/2 ≤ S ≤ k(n − k). Какая оценка на n у нас получилась?

Подсказка 14:

n ≤ 3k − 1. Осталось придумать пример. Он строится из оценки, всего лишь необходимо гарантировать равенства во всех выше написанных неравенствах. Успехов!