Развитие с оглядкой на 9 колен назад, 11 класс

Рассмотрим девять чисел k₁,…,k₉, где k_i ϵ{0,1,2}. При этом хотя бы одно число k_i отлично от нуля. С помощью этих чисел вырабатывают последовательность u₁,u₂,…,u₂₀₁₉ по формулам: u₁=k₁,u₂=k₂,…,u₉=k₉,u_(i+9)=r₃ (u_i+u_(i+1) ),i=1,2,…,2010, где r₃ (a) – остаток от деления числа a на 3. Найдите такое наименьшее натуральное число l, что какие бы исходные числа k₁,…,k₉ мы ни взяли, в последовательности u₁,u₂,…,u_l каждое из чисел 0, 1 и 2 гарантированно встретится хотя бы один раз.

• Решение

Решение

Для каждого набора k=(k₁,…,k₉ ) укажем такое минимальное l, что в соответствующей последовательности u₁,u₂,…,u_l присутствует каждое из чисел 0, 1 и 2. Затем среди всех таких l останется выбрать наибольшее – это и будет ответом в задаче. 

1. В наборе k встречается каждое из чисел 0, 1 и 2. Тогда искомое l не превосходит 9; 

2. Набор k состоит только из 1. Тогда u₁₀=⋯=u₁₇=2 и u₁₈=0. Значит l=18; 

3. В наборе k присутствуют и 1, и 2, но нет 0. Значит среди чисел u₁,u₂,…,u₉ есть два соседних (u_s и u_(s+1)), одно из которых равно 1, а другое 2. Тогда u_(s+9)=0 и l≤17; 

4. Набор k состоит из 0 и 1. Число 2 впоследствии дадут только две рядом стоящие 1. Поэтому рассмотрим варианты: 

     4.1.в k есть рядом стоящие 1. Тогда l<19; 

     4.2.в k нет рядом стоящих 1. 

      Здесь возможны следующие случаи: 

4.2.1. Есть хоть одна 1 «не с краю». То есть найдется номер s такой, что 2≤s≤8 и k_s=1. 

Рядом стоящих 1 нет, поэтому k_(s-1)=k_(s+1)=0. Тогда u_(s+8)=u_(s+9)=1. Следовательно, u_(s+17)=2 и l≤25; 

4.2.2. 1 есть только «с краю». Пусть k=(1,0,…,0). В этом случае начало последовательности u₁,u₂,… можно вычислить непосредственно: {u_n }= {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0,…} и убедиться, что l=27. Пусть k=(1,0,…0,1). Тогда {u_n }={1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0…} и l=18. И, наконец, для k=(0,…0,1) находим {u_n }={0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, …}, l=26. 




Отметим, что случаи, «k состоит только из 2» и «k состоит только из 0 и 2» эквивалентны случаям 2 и 4 соответственно. Действительно, если в последовательности {u_n }, отвечающей набору 2∙k, заменить все 2 на 1, а 1 на 2, то получится последовательность, соответствующая набору k.
• Ответ

Ответ

l=27