интересная комбинаторная задачка

stat3032681

Arranged in a circle are 2010 digits, each of them equal to 1, 2, or 3. For each positive integer k, it's known that in any block of 3k consecutive digits, each of the digits appears at most k+10 times. Prove that there is a block of several consecutive digits with the same number of 1s, 2s, and 3s.

iri3955

  Наметим начало.
Для к от 1 до 962 будем смотреть 3к чисел от начала. Для каждого ряда есть набор из 3х чисел (a1, a2, a3) означающих, насколько кол-во соответствующих цифр отличется от k. Тогда их сумма 0 и каждое не более 10 и не менее -20, тогда их не более 31^2 = 961. Значит, есть 2 одинаковые, разность между ними - искомая тройка. Если считать, что k должно быть меньше 2010/3, тогда, думаю, можно просто более точно оценить кол-во таких троек.
UPD. Да, троек, где
3 числа больше 0 - 0,
2 числа больше 0 - 300,
1 число больше 0 - 330,
0 чисел больше 0 - 1,
итого 631 < 2010 / 3

stat3032681

спасибо, очень красивое решение :)
Оставить комментарий
Имя или ник:
Комментарий: