Презентация "Олимпиадные задачи по математике для 10 и 11 классов"

Олимпиадные Олимпиадные задачи по задачи по математике математике Учитель математики Учитель математики Мехонцева Марина Григорьевна Мехонцева Марина Григорьевна

10 класс № 1 После  просмотра  фильма  зрители  по  очереди  оценивали фильм целым числом баллов от 0 до 10.  В  каждый  момент  времени  рейтинг  фильма  вычислялся  как  сумма  всех  выставленных  оценок,  делённая на их количество.  В  некоторый  момент  времени  T  рейтинг  оказался  целым  числом,  а  затем  с  каждым  новым  проголосовавшим  зрителем  он  уменьшался  на  единицу.  Какое  наибольшее  количество  зрителей  могло  проголосовать после момента T?

Решение.  Рассмотрим некоторый момент, когда рейтинг уменьшился на 1.  Пусть перед этим проголосовало n человек, и рейтинг был целым числом  x.  Значит,  сумма  баллов  стала  равна  nx.  Пусть  следующий  зритель  выставил  y  баллов.  Тогда  сумма  баллов  стала  равна  nx+y  =  (n+1)(x−1),  откуда  y  =  x−n−1.  Наибольшее  возможное  значение  x  равно  10,  а  наименьшее возможное значение n равно 1; значит, наибольшее значение y  (на первом таком шаге) равно 8. С каждым следующим шагом значение x  уменьшается  на  1,  а  значение  n  увеличивается  на  1.  Следовательно,  на  втором шаге значение y не превосходит 6, на третьем 4, и т.д. Поскольку  любая оценка не меньше 0, число шагов не превосходит 5.  Осталось показать, что пять шагов возможны. Пусть рейтинг в момент T  равен 10 (при одном проголосовавшем), затем второй зритель выставляет  8  баллов,  третий  6,  четвёртый  4,  пятый  2,  а  шестой  0.  Тогда  рейтинг  последовательно принимает значения 9, 8, 7, 6 и 5. Ответ: 5.

Комментарий.  Только ответ ­ 0 баллов. Только приведен пример, в котором проголосовало 5 зрителей ­ 2 балла. Доказано с полным обоснованием, что более 5 зрителей проголосовать  не могло (но пример отсутствует или неверен) ­ 5 баллов.

10 класс № 2 Дан  прямоугольный  треугольник  ABC  с  прямым  углом  C.  Пусть  BK    биссектриса  этого  треугольника.  Окружность,  описанная  около  треугольника  AKB,  пересекает  вторично  сторону  BC  в  точке  L.  Докажите,  что CB + CL = AB.

◦ ∠ Отложим на продолжении BC за точку C отрезок CN = LC. Тогда CB +  CL = NB, и нам надо доказать, что AB = NB. Так как четырёхугольник ABLK вписан, имеем  CKB = 180  −  AKB =  180  −  ALB =  ALC. С другой стороны, прямоугольные треугольники  ACL и ACN равны по двум катетам, так что  ANC =  ALC =  CKB =  ABN имеем ∠BAN = 180  −  B −  90  −  B/2. Тогда из треугольника  ∠ Из полученного равенства  ANB =  BAN и следует, что AB = NB. ◦ ∠ ANB = 180  −  B − (90  −  B/2) = 90  −  B/2 =  ANB.  ◦ ∠ ∠ ◦ ∠ ◦ ∠ ◦ ∠ ◦ ∠ ∠ ∠ ∠ ∠ Первое решение.  ∠ ∠ ∠ Замечание. Существует несколько вариаций вышеприведённого решения.  Например, из равенства  ABK =  CBK вытекает, что KA = KL = KN;  кроме того,  KAB =  KLC =  KNC. Отсюда нетрудно получить, что  ∠ AKB =  NKB, а значит, треугольники BKA и BKN равны. ∠ ∠ ∠ ∠ ∠ ∠

Второе решение.  ∠ ∠ Опустим  из  точки  K  перпендикуляр  KH  на  гипотенузу  AB.  Прямоугольные  треугольники  KCB  и  KHB  равны  по  гипотенузе  и  острому углу ( KBC =  KBH). Значит, CB = HB и KC = KH.  Далее,  в  окружности,  описанной  около  AKLB,  на  хорды  AK  и  KL  опираются  равные  углы,  поэтому  AK  =  KL.  Значит,  прямоугольные  треугольники  KHA  и  KCL  равны  по  катету  и  гипотенузе,  откуда  HA  =  CL. Итак, CB+CL = HB+HA = AB, что и требовалось доказать. Комментарий.  Выполнено  дополнительное  построение,  ведущих  к  решению  (например,  сторона  BC  продолжена  на  длину  CL,  или  рассмотрено  основание  перпендикуляра,  опущенного  из  K  на  AB)­1  балл.

10 класс № 3 Коэффициенты a, b, c квадратного трёхчлена f(x)  =  ax2  +  bx  +  c  натуральные  числа,  сумма  которых  равна 2000.  Паша  может  изменить  любой  коэффициент  на  1,  заплатив 1 рубль.  Докажите,  что  он  может  получить  квадратный  трёхчлен,  имеющий  хотя  бы  один  целый  корень,  заплатив не более 1050 рублей.

Решение.  Покажем, что можно из исходного трёхчлена получить новый, имеющий  хотя  бы  один  целый  корень,  изменив  коэффициенты  a,  b,  c  суммарно  даже  не  более,  чем  на  1022.  Если  коэффициент  c  не  больше  1022,  то,  сделав  его  равным  нулю,  мы  получим  искомый  трёхчлен  f1(x)  =  ax2+bx,  имеющий целый корень x = 0. Пусть теперь c > 1023; тогда из условия a + b ≤ 977.  Рассмотрим два последовательных квадрата, между которыми находится  c: m2 ≤ c < (m + 1)2. Поскольку c < 2000 < 452, имеем m ≤ 44. Тогда одна  из разностей c−m2 и (m+1)2−c не превосходит 12 ((m+1)2−m2) = ½*(2m+1),  то есть она не больше m ≤ 44.  Итак, найдётся натуральное k, для которого |c−k2| ≤ 44. Заменив теперь a  на  −1,  b  на  0,  а  c  на  k2,  мы  изменим  коэффициенты  суммарно  не более,  чем на (a+b+1)+|c−k2| ≤ 978+44 = 1022, и получим трёхчлен f2(x) = −x2 +  k2, имеющий целый корень x = k. Комментарий.  Отмечено,  что  при  не  очень  большом  значении  c  можно  получить многочлен, имеющий корень, заменив c на ноль ­1 балл.

10 класс № 4 Дано  натуральное  число  n  >  2.  Рассмотрим  все  покраски  клеток  доски  n  ×  n  в  k  цветов  такие,  что  каждая  клетка  покрашена  ровно  в  один  цвет,  и  все  k  цветов встречаются.  При  каком  наименьшем  k  в  любой  такой  покраске  найдутся  четыре  окрашенных  в  четыре  разных  цвета  клетки, расположенные в пересечении двух строк и двух  столбцов?

Первое решение.  Сначала покажем, как покрасить клетки в 2n − 1 цветов так, чтобы  не  было  ни  одной  четверки  клеток  разных  цветов,  лежащих  на  пересечении двух горизонталей и двух вертикалей. Занумеруем  горизонтальные  ряды  сверху  вниз  чётными  числами  0,  2, 4, . . . , 2n − 2, а вертикальные ряды слева направо нечетными числами  1, 3, . . . , 2n − 1. Покрасим последовательно 0­й ряд в цвет 0, 1­й ряд в  цвет  1,  .  .  .  ,  (2n  −  1)­й  ряд  в  цвет  2n  −  1.  При  этом  при  покраске  очередного  ряда  мы  перекрашиваем  все  клетки,  которые  были  покрашены  ранее.  В  конечной  раскраске  присутствуют  2n  −  1  цветов  (цвета 0 не останется). Убедимся,  что  она  удовлетворяет  условию.  Рассмотрим  четыре  клетки  на  пересечении  двух  горизонталей  и  двух  вертикалей.  Один  из  этих  четырёх  рядов  (вертикалей  или  горизонталей)  был  покрашен  последним; тогда две его клетки останутся окрашенными в этот цвет и,  следовательно, будут одноцветными.

найдётся.  Рассмотрим раскраску клеток в k или более цветов.  Переформулируем задачу следующим образом.  Рассмотрим  двудольный  граф,  вершины  которого  соответствуют  горизонталям  и  вертикалям  доски  (всего  2n  вершин).  Если  клетка  на  пересечении некоторых горизонтали и вертикали покрашена в цвет c, то  соединим  вершины,  соответствующие  этим  горизонтали  и  вертикали,  ребром цвета c.  Осталось доказать, что при k > 2n требуемая четвёрка обязательно  Разноцветным  циклом  будем  называть  цикл,  в  котором  нет  двух  рёбер  одного  цвета.  Нам  требуется  доказать,  что  в  построенном  графе  найдется разноцветный цикл из 4 рёбер. 1.  Докажем,  что  найдется  хотя  бы  один  разноцветный  цикл  (возможно,  более,  чем  из  4  рёбер).  Выберем  по  одному  ребру  каждого  цвета всего не менее 2n рёбер попарно разных цветов. Остальные рёбра  временно  сотрем.  В  полученном  графе  количество  рёбер  не  меньше  количества вершин; как известно, в таком графе найдется цикл.

2.  Теперь  найдем  в  исходном  графе  кратчайший  разноцветный  цикл.  Пусть  это  цикл  a1b1a2b2  .  .  .  asbsa1  из  2s  ребер,  где  ai  вершины,  соответствующие  горизонталям  доски,  а  bj  вершины,  соответствующие  вертикалям.  Докажем, что этот цикл состоит из 4 ребер, то есть s = 2.  Пусть  напротив,  s  >  2.  Рассмотрим  ребро  b2a1.  Если  его  цвет  отличен  от  цвета  каждого  из  ребер  a1b1,  b1a2  и  a2b2,  то  a1b1a2b2a1  разноцветный цикл из 4 ребер; противоречие.  Иначе цвет ребра b2a1 отличен от цвета каждого из ребер b2a3, a3b3, .  . . , akbk, bka1, тем самым цикл a1b2a3b3 . . . akbka1 из 2k − 2 ребер является  разноцветным; противоречие. Ответ. k = 2n.

Сначала мы предъявим пример покраски клеток в 2n − 1 цветов так,  чтобы не было ни одной требуемой разноцветной четверки клеток. Второе решение.  Покрасим все клетки первой горизонтали H и первой вертикали V в  2n − 1 различный цвет, причём клетку на их пересечении покрасим в цвет  c; затем покрасим все оставшиеся клетки также в цвет c.  Тогда нетрудно понять, что из четырёх клеток на пересечении любых  двух столбцов и двух строк максимум две будут иметь цвет, отличный от  c. Значит, требуемой четвёрки клеток не найдётся.  Осталось доказать, что при k ≥ 2n требуемые четыре клетки всегда  найдутся.  Мы  докажем  более  общее  утверждение:  если  клетки  прямоугольника  m  ×  n  окрашены  в  k  ≥  m  +  n  цветов,  причём  все  цвета  присутствуют,  то  найдутся  4  разноцветных  клетки  на  пересечении  двух  строк и двух столбцов. Индукция по m+n. Заметим сразу, что при m = 1 утверждение верно,  ибо  раскрасок  n  клеток  в  n+1  цвет  не  существует;  в  частности,  это  доказывает базу индукции при m+ n = 2.  Предположим теперь, что m, n ≥ 2, и совершим переход индукции.

Рассмотрим  произвольную  раскраску  клеток  прямоугольника  m×n  в  k  цветов.  Назовём  цвет  c  уникальным  для  столбца  V,  если  цвет  c  встречается  только  в  столбце  V;  аналогично  определим  цвет,  уникальный для строки. Пусть существует столбец, для которого есть не  более  одного  уникального  цвета.  Тогда  выбросим  его;  в  оставшемся  прямоугольнике  будет  встречаться  не  менее  k  −  1  ≥  m  +  n  −  1  цветов,  значит,  по  предположению  индукции  в  нём  найдётся  нужная  четвёрка  клеток. Итак, осталось разобрать случай, когда в каждом столбце (и,  аналогично,  в  каждой  строке)  хотя  бы  по  два  уникальных  цвета.  Рассмотрим любой столбец V1; пусть в нём два уникальных цвета p и q, и  какие­то клетки этих цветов стоят в строках H1 и H2 соответственно. В  H1 есть два уникальных цвета; один из них отличен от p. Пусть этот цвет   r, и в H1 клетка этого цвета стоит в столбце V2 ≠ V1. Тогда построенные  два столбца и две строки требуемые. Действительно, на их пересечении в  V1  стоят  два  разных  цвета,  уникальных  для  V1;  значит,  они  не  встречаются в V2. Цвет r ≠ p уникален для H1, значит, он не встречается  в H2. Итого, в нашем пересечении есть различные цвета p, q, r, а также  клетка цвета, отличного от них. Это и требовалось.

Комментарий.  Только верный ответ ­ 0 баллов. Приведён  пример  покраски  в  2n  −  1  цветов,  в  который  нет  четырех  клеток разных цветов на пересечении двух строк и двух столбцов ­ 2  балла. Доказано,  что  для  любой  покраски  в  2n  цветов  найдутся  четыре  клетки разных цветов на пересечении двух строк и двух столбцов ­ 5  баллов. За использование без доказательства утверждения о том, что в графе с  t  вершинами  и  не  менее,  чем  t  ребрами,  есть  цикл,  баллы  не  снижаются.

11 класс № 1 Квадратный трехчлен f(x) имеет два различных  корня. Оказалось, что для любых чисел a и b верно  неравенство f(a2 +b2) ≥ f(2ab).  Докажите, что хотя бы один из корней этого  трёхчлена отрицательный.

Первое решение.  Подставим в условие b = 0 и получим, что f(a2) ≥ f(0) при всех a. Следовательно,  f(t)  ≥  f(0)  при  любом  положительном  t.  Из  этого  и  свойств графика квадратичной функции следует, в частности, что ветви  параболы направлены вверх.  Предположим,  что  оба  корня  трёхчлена  неотрицательны.  Тогда  вершина  параболы  имеет  положительную  абсциссу,  назовём  ее  t0.  Но  трёхчлен  в  точке  t0  принимает  единственное  минимальное  значение,  то  есть f(0) > f(t0).  Противоречие.

Второе решение.  Предположим, что оба корня трёхчлена неотрицательны.  Тогда вершина параболы имеет положительную абсциссу, назовем ее  t0.  Пусть  ветви  параболы  направлены  вверх.  Тогда  наименьшее  значение  трёхчлена равно f(t0).  Подставим в условие b = −a и получим, что f(2a2) ≥ f(−2a2) при всех  a.  Следовательно,  f(t)  ≥  f(−t)  при  любом  положительном  t;  в  частности,  f(t0) ≥ f(−t0), что невозможно. Пусть ветви параболы направлены вниз.  Тогда  наибольшее  значение  трёхчлена  равно  f(t0).  Подставим  в  условие b = 2a и получим, что f(5a2) ≥ f(4a2) при всех a.  Следовательно,  f(5t/4)  ≥  f(t)  при  любом  положительном  t;  в  частности, f(5t0/4) ≥ f(t0), что невозможно.  В обоих случаях мы пришли к противоречию.  Значит наше предположение неверно.

Третье решение.  Заметим,  что  для  любых  чисел  0  ≤  p  ≤  q  можно  подобрать  такие  неотрицательные числа a и b, что p = 2ab и q = a2 + b2.  Действительно, достаточно взять  a = ½ *(√p + q + √q − p) и b = ½ *(√p + q − √q − p).  Следовательно, для любых чисел 0 ≤ p ≤ q имеем неравенство  f(p) ≤ f(q).  Таким  образом,  на  положительной  полуоси  трёхчлен  возрастает.  Поэтому ветви его графика направлены вверх.  Но тогда он не может иметь два неотрицательных корня, поскольку это  противоречит возрастанию.

Четвёртое решение.  Пусть f(x) = kx2+?x+m. Подставим в условие b = −a.  Тогда 4ka4 + 2?a2 + m = f(2a2) = f(a2 + (−a)2) ≥ f(2a  ?  (−a)) = = f(−2a2) = 4ka4 − 2?a2 + m.  Поэтому 4?a2 ≥ 0 при любом a. Следовательно, ? ≥ 0.  Если при этом k > 0, то сумма корней равна −?/k ≤ 0 и, значит, у  трёхчлена есть отрицательный корень.  Если же k < 0, то подставим в условие b = 0 и получим, что ka4 +  ?a2 + m = f(a2) ≥ f(0) = m. Следовательно, a2(ka2 + ?) = ka4 + ?a2 ≥ 0 при  всех a.  Но это невозможно при a > p−?/k.  Комментарий. Доказано, что у f(x) есть неположительный корень ­   4 балла.  В решении пропущен существенный случай (например, когда ветви  параболы направлены вниз) не более 2 баллов.

11 класс № 2 По кругу расставлено 300 положительных чисел.  Могло ли случиться так, что каждое из этих чисел,  кроме одного, равно разности своих соседей?

Решение.  Предположим, что требуемая расстановка существует.  Ясно,  что  наибольшее  из  чисел  не  может  равняться  разности  соседей;  значит, каждое из остальных чисел равно разности соседей.  В частности, наибольшее число встречается ровно один раз; обозначим  его через m. Пусть d одно из наименьших чисел в круге. Рассмотрим любую из двух  дуг между d и m; пусть на ней стоят подряд числа d = a0, a1, . . . , ak = m.  Докажем индукцией по i = 0, 1, . . . , k − 1, что ai+1 ≥ ai. В базовом случае  i = 0 утверждение верно, ибо d наименьшее число.  Для  перехода  от  i  −  1  к  i  предположим,  что  i  <  k  и  ai−1  ≤  ai.  Тогда  равенство ai = ai−1 − ai+1 невозможно, ибо ai+1 > 0, и поэтому ai = ai+1 − ai−1.  Значит,  ai+1  >  ai,  что  и  доказывает  переход  индукции.  Мы  заодно  показали, что ai+1 = ai + ai−1 при всех i = 1, . . . , k − 1.

Аналогично, если на другой дуге между d и m стоят подряд числа d  = b0, b1, . . . , bℓ = m, то b0 ≤ b1 ≤ . . . ≤ bℓ и bi+1 = bi +bi−1 при всех i = 1, 2, . . .  , ?−1.  Наконец,  для  числа  a0  =  b0  =  d  условие  задачи  также  должно  выполняться, так что d = |a1−b1|.  Без ограничения общности можно считать, что d = b1−a1; тогда a2 = a0  + a1 = b1 > a1.  Продолжим  теперь  последовательности  a0,  a1,  .  .  .  и  b0,  b1,  .  .  .  согласно формулам ai+1 = ai +ai−1 и bi+1 = bi +bi−1.  Докажем индукцией по i = 1, 2, . . ., что ai < bi ≤ ai+1. При i = 1 это уже  доказано выше. При i = 2 из соотношений b0 = a0 ≤ a1 < b1 = a2 получаем a2  = a1 + a0 < b1 + b0 = b2 ≤ a2 + a1 = a3.  Для  перехода  индукции  предположим  теперь,  что  i  ≥  3,  и  утверждение уже доказано для меньших значений I.  По предположению индукции, имеем ai−2 < bi−2 ≤ ai−1 < bi−1 ≤ ai, откуда  ai = ai−1 + ai−2 < bi−1 + bi−2 = bi ≤ ai + ai−1 = ai+1, что и требовалось.

Итак, мы получили, что a0 = b0 ≤ a1 < b1 ≤ a2 < b2 ≤ . . .. Значит,  равенство  bℓ  =  ak  возможно  лишь  при  k  =  ?  +  1;  но  тогда  общее  количество  чисел  в  круге  равно  k  +  ?  =  2?  +  1,  что  не  может  равняться 300.  Противоречие. Замечание.  Если  число  300  заменить  на  любое  нечётное  число,  то  требуемая  конфигурация будет существовать (в ней два равных минимальных числа  будут  стоять  рядом).  Таким  образом,  в  любом  верном  решении  должен  использоваться  тот  факт,  что  300  чётно  (в  приведённом  решении  он  используется  в  последнем  абзаце,  чтобы  исключить  случай  k  =  ?  +  1).  Условие положительности чисел также важно, иначе бы подошёл пример  0, 0, 0, . . . или 0, 1, 1, 0, 1, 1, . . . , 0, 1, 1.  Комментарий.  Верный  ответ  без  обоснования  ­  0  баллов.  Доказано,  что последовательность чисел на каждой из двух дуг между наименьшим  и наибольшим числом удовлетворяет рекуррентному уравнению an+2 = an+1  + an ­ 2 балла.

11 класс № 3 Петя  хочет  выписать  возможные  последовательности из 100 натуральных чисел, в каждой  из  которых  хотя  бы  раз  встречается  число  4  или  5,  а  любые два соседних члена различаются не больше, чем на  2. Сколько последовательностей ему придётся выписать? все

Первое решение.  Обозначим n = 100. Назовём последовательность из n натуральных чисел,  любые  два  соседних  члена  которой  различаются  не  больше,  чем  на  2,  интересной.  Каждой  интересной  последовательности  a1,  a2,  .  .  .  ,  an  сопоставим  разностную последовательность bi = ai+1 − ai (i = 1, 2, . . . , n − 1).  Все  члены  разностной  последовательности  равны  0,  ±1  или  ±2,  так  что  количество всевозможных разностных последовательностей равно 5n−1.  Посчитаем сначала количество S всех интересных последовательностей,  минимальный член которых не превосходит 5. Рассмотрим произвольную  разностную  последовательность  b1,  b2,  .  .  .  ,  b99.  Любые  две  интересные  последовательности,  соответствующие  ей,  отличаются  прибавлением  одного  и  того  же  числа  к  каждому  члену.  Значит,  среди  них  ровно  по  одной последовательности с минимальным членом, равным 1, 2, 3, 4 или  5. Таким образом, S = 5  ?  5n−1 = 5n.

В  S  учтены  все  последовательности,  выписываемые  Петей,  и  несколько лишних тех, в которых не встречается ни 4, ни 5.  Ясно,  что,  если  в  интересной  последовательности  встречаются  как  числа, большие 5, так и меньшие 4, то 4 или 5 также встретится.  Но  минимальный  член  каждой  лишней  последовательности  не  больше 3, значит, и все их члены не превосходят 3.  количество равно S − 3n = 5n − 3n. Ответ. 5100 − 3100. Итак, все лишние последовательности состоят из чисел 1, 2 и 3.  С  другой  стороны,  каждая  последовательность  из  чисел  1,  2  и  3  является интересной, и, стало быть, лишней.  Итого,  лишних  последовательностей  ровно  3n,  а  значит,  искомое

Второе решение.  Назовём хорошей последовательность из n натуральных чисел, в которой хотя бы  раз  встречается  число  4  или  5,  а  любые  два  соседних  члена  различаются  не  больше,  чем  на 2.  Обозначим через Sn  количество хороших  последовательностей  длины n. Мы докажем индукцией по n, что Sn = 5n − 3n. База  индукции  при  n  =  1  очевидна.  Сделаем  переход  от  n  к  n  +  1.  Рассмотрим  произвольную  n­членную  хорошую  последовательность;  пусть  она  оканчивается  числом k.  Тогда  к  ней  можно  приписать  любое  число  от  k−2  до  k  +  2;  полученная  последовательность будет хорошей, если приписываемое число натуральное. Если  же оно неположительно (то есть равно 0 или −1), то после приписывания прибавим  ко всем числам последовательности по 5. Полученная последовательность будет  оканчиваться числом 4 или 5, а значит, будет хорошей. Заметим,  Для  последовательностей,  полученных  без  прибавления  5,  это  очевидно;  при  этом  таким образом получаются ровно все хорошие последовательности, среди первых  n членов которых есть 4 или 5. Последовательности же, полученные прибавлением  5, тоже попарно различны; при этом это ровно все хорошие последовательности,  первые n членов которых больше 5, и при этом среди них встречается 9 или 10. В  частности, эти последовательности отличны от описанных ранее. Итого, мы пока  что построили 5Sn хороших (n + 1)­членных последовательностей. последовательности  разные.  что  все  полученные

Осталось подсчитать число ещё неучтённых последовательностей. В  каждой  неучтённой  последовательности  среди  первых  n  членов  нет  чисел 4, 5, 9 и 10, а последний член равен 4 или 5.  Значит, либо первые n её членов единицы, двойки и тройки, либо все  они шестёрки, семёрки или восьмёрки.  Посчитаем  количество  первых;  количество  вторых  считается  аналогично. Рассмотрим любую последовательность из n единиц, двоек и  троек (её соседние члены автоматически отличаются максимум на 2). Если она оканчивается числом 3, то к ней можно приписать 4 или 5,  получив неучтённую последовательность.  Если она оканчивается числом 2, то можно приписать лишь 4; если  же  её  последнее  число  1,  то  хорошую  последовательность  из  неё  получить нельзя.  Значит,  количество  полученных  неучтённых  последовательностей  равно  2  3n−1  +3n−1  =  3n  (и  ещё  столько  же  получаются  из  последовательностей  с  числами  6,  7  и  8).  Итого,  мы  получаем  Sn+1  =  5Sn+2 ? 3n = 5(5n−3n)+2 ? 3n = 5n+1 − 3n+1, что и требовалось. ?

Комментарий.  Только ответ ­ 1 балл. Если  задача  решается  для  последовательностей  из  n  чисел,  но  разобраны  лишь  случаи  небольших  значений  n  (скажем,  n  ≤  6)  ­  0  баллов. При  подходе,  аналогичном  первому  решению,  неверно  подсчитано  количество лишних последовательностей снять 3 балла. При  индуктивном  подходе,  аналогичном  второму  решению,  неверно  произведён  учёт  последовательностей,  в  которых  числа  4  и  5  стоят  только на последнем месте ставится не более 3 баллов.

Использованные источники Использованные источники 1. Материалы для проведения регионального этапа XLI ВСЕРОССИЙСКОЙ МАТЕМАТИЧЕСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ 2014–2015 учебный год  Второй день. Сборник . 2–3 февраля 2015 г. Москва, 2014 2. Макет презентации: Малыгина  Ирина  Николаевна