|
Сашуну спасибо за задачу - решать было интересно.
Но для начала давайте переведем задачу с псевдоматематического языка Сашуна на язык нормальной математики.
Дана бесконечная последовательность целых натуральных чисел от 1 до 6 такая, что сумма любых 7 чисел подряд не превосходит 12. Доказать, что в этой последовательности всегда найдется конечная подпоследовательность такая, что сумма чисел в ней равна 20, или построить контрпример.
Для удобства введем определение.
Окрестностью числа L будем называть конечную подпоследовательность из 13 чисел M1, M2…M6,L,M7…M12. При этом подпоследовательность M1, M2…M6,L будем называть левой полуокрестностью L, а L,M7…M12 – правой полуокрестностью L. Переформулируем задачу:
Дана бесконечная последовательность целых натуральных чисел от 1 до 6 такая, что сумма чисел как левой, так и правой полуокрестности любого числа L данной последовательности не превосходит 12. Доказать, что в этой последовательности всегда найдется конечная подпоследовательность такая, что сумма чисел в ней равна 20, или построить контрпример.
Основной идеи тут уже касались, но не сформулировали. Построение искомой последовательности, основано на факте, доказываемом ниже.
Лемма. Если такая последовательность существует, и максимальное число, встречающееся в ней, равно K (которое по условию меньше либо равно 6), то в данной последовательности встречается не более чем K-2 единиц подряд.
Доказательство – от противного. Пусть не так, то есть такая последовательность существут и в последовательности есть хотя бы K-1 единиц подряд. Рассматриваем первые N членов бесконечной подпоследовательности, начинающихся с этих единиц. Так как сумма этих членов при увеличении N на 1 монотонно увеличивается на сумму от 1 до K, то найдется N такое, что сумма этих N членов будет лежат в диапазоне от 19 до 20-K (назовем ее Сум(N)), а Сум(N+1) будет больше 20. Пусть она больше 20 на X. В этом случае X больше или равен K – иначе сумма подпоследовательности, начинающейся с числа, стоящего на месте X+1, равна 20, что противоречит условию. Но тогда у нас на N+1-м месте стоит число, большее K – иначе такую сумму не получить. Но мы сказали, что K – максимальное число в данной последовательности. Пришли к противоречию.
Теперь построение последовательности несложно. Если такая последовательность есть, то и любая ее бесконечная подпоследовательность тоже удовлетворяет условию задачи, поэтому, чтобы «обрубить» концевые условия, будем рассматривать какую-нибудь подпоследовательность начиная с не менее чем 7-го члена, то есть такую, все члены которой имеют окрестность в рамках исходной последовательности. Чему в ней равно K? K меньше 6 – так как в полуокрестности 6 должно быть 6 единиц подряд. K меньше 5 – так как в полуокрестности 5 должно быть минимум 4 единицы подряд. K меньше 4 – единственная полуокрестность, удовлетворяющая условию леммы, состоит из двух двоек и четырех единиц, но тогда сумма всей окрестности равна 20. K больше 2 – тогда в последовательности ноль единиц, то есть она состоит из одних двоек, но тогда сумма 10 членов равна 20. Остается K=3.. Тогда в любой полуокрестности тройки имеется ровно 3 единицы (если больше – то есть 2 единицы подряд, что противоречит лемме, а если меньше – то сумма полуокрестности заведомо больше 12), стоящих либо на четных, либо на нечетных местах, а оставшиеся места заполнены двойками. Сумма окрестности = 21, то есть с концов ее единиц быть не может (иначе сумма 12 последовательных чисел без этой единицы равна 20), а значит, единственно возможная окрестность выглядит так – 2,1,2,1,2,1,3,1,2,1,2,1,2. Но тогда следующее число в этой подпоследовательности – 3, а левая полуокрестность этой новой тройки не совпадает с только что установленной единственно возможной левой полуокрестностью тройки. Вывод: такой последовательности не существует.
|
