Олимпиадные задачи по теме «Последовательности» - сложность 4 с решениями
Последовательности
НазадДве команды шахматистов одинаковой численности сыграли матч: каждый сыграл по одному разу с каждым из другой команды. В каждой партии давали 1 очко за победу, ½ – за ничью и 0 – за поражение. В итоге команды набрали поровну очков. Докажите, что какие-то два участника матча тоже набрали поровну очков, если в обеих командах было:
а) по 5 шахматистов;
б) произвольное равное число шахматистов.
По кругу стоят2009целых неотрицательных чисел, не превышающих 100. Разрешается прибавить по1к двум соседним числам, причем с любыми двумя соседними числами эту операцию можно проделать не более<i> k </i> раз. При каком наименьшем<i> k </i>все числа гарантированно можно сделать равными?
Последовательность<i> a<sub>1</sub>,a<sub>2</sub>,.. </i>такова, что<i> a<sub>1</sub><img align="absmiddle" src="/storage/problem-media/115397/problem_115397_img_2.gif"></i>(1<i>,</i>2)и<i> a<sub>k+</sub></i>1<i>=a<sub>k</sub>+<img align="absmiddle" src="/storage/problem-media/115397/problem_115397_img_3.gif"> </i>при любом натуральном <i> k </i>. Докажите, что в ней не может существовать более одной пары членов с целой суммой.
Последовательности(<i>a<sub>n</sub></i>)и(<i>b<sub>n</sub></i>)заданы условиями<i> a<sub>1</sub>=</i>1,<i> b<sub>1</sub>=</i>2,<i> a<sub>n+</sub></i>1<i>=<img src="/storage/problem-media/111872/problem_111872_img_2.gif"> </i>и<i> b<sub>n+</sub></i>1<i>=<img src="/storage/problem-media/111872/problem_111872_img_3.gif"> </i>. Докажите, что<i> a</i>2008<i><</i>5.
В бесконечной последовательности <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, <i>a</i><sub>3</sub>, ... число <i>a</i><sub>1</sub> равно 1, а каждое следующее число <i>a<sub>n</sub></i> строится из предыдущего <i>a</i><sub><i>n</i>–1</sub> по правилу: если у числа <i>n</i> наибольший нечётный делитель имеет остаток 1 от деления на 4, то <i>a<sub>n</sub> = a</i><sub><i>n</i>–1</sub> + 1, если же остаток равен 3, то <i>a<sub>n</sub> = a</i><sub><i>n</i>–1</sub> – 1. Докажите, что в этой последовательности
а) число 1 встреч...
Саша написал на доске ненулевую цифру и приписывает к ней справа по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите, что на доске не более 100 раз был написан точный квадрат.
В последовательности натуральных чисел {<i>a<sub>n</sub></i>}, <i>n</i> = 1, 2, ..., каждое натуральное число встречается хотя бы один раз, и для любых различных <i>n</i> и <i>m</i> выполнено неравенство <img align="absmiddle" src="/storage/problem-media/109941/problem_109941_img_2.gif"> Докажите, что тогда |<i>a<sub>n</sub> – n</i>| < 2000000 для всех натуральных <i>n</i>.
В прямоугольной таблице 9 строк и 2004 столбца. В её клетках расставлены числа от 1 до 2004, каждое – по 9 раз. При этом в каждом столбце числа различаются не более чем на 3. Найдите минимальную возможную сумму чисел в первой строке.
Последовательность {<i>a<sub>n</sub></i>} строится следующим образом: <i>a</i><sub>1</sub> = <i>p</i> – простое число, имеющее ровно 300 ненулевых цифр, <i>a</i><sub><i>n</i>+1</sub> – период десятичной дроби <sup>1</sup>/<sub><i>a<sub>n</sub></i></sub>, умноженный на 2. Найдите число <i>a</i><sub>2003</sub>.
Докажите, что существует бесконечно много натуральных <i>n</i>, для которых числитель несократимой дроби, равной 1 + ½ + ... + <sup>1</sup>/<sub><i>n</i></sub>, не является степенью простого числа с натуральным показателем.
Пусть 2<i>S</i> – суммарный вес некоторого набора гирек. Назовём натуральное число <i>k средним</i>, если в наборе можно выбрать <i>k</i> гирек, суммарный вес которых равен <i>S</i>. Какое наибольшее количество средних чисел может иметь набор из 100 гирек?
Докажите, что если числа <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>m</sub></i> отличны от нуля и для любого целого <i>k</i> = 0, 1, ..., <i>n</i> (<i>n < m</i> – 1) выполняется равенство:
<i>a</i><sub>1</sub> + <i>a</i><sub>2</sub>·2<sup><i>k</i></sup> + <i>a</i><sub>3</sub>·3<sup><i>k</i></sup> + ... + <i>a<sub>m</sub>m<sup>k</sup></i> = 0, то в последовательности <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>m</sub></i> ...
Докажите, что для любого натурального числа <i>a</i><sub>1</sub> > 1 существует такая возрастающая последовательность натуральных чисел <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, <i>a</i><sub>3</sub>, ...,
что <img align="absmiddle" src="/storage/problem-media/109599/problem_109599_img_2.gif"> делится на <i>a</i><sub>1</sub> + <i>a</i><sub>2</sub> + ... + <i>a<sub>k</sub></i> при всех <i>k</i> ≥ 1.
В семейном альбоме есть десять фотографий. На каждой из них изображены три человека: в центре стоит мужчина, слева от мужчины – его сын, а справа – его брат. Какое наименьшее количество различных людей может быть изображено на этих фотографиях, если известно, что все десять мужчин, стоящих в центре, различны?
За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: Кто Ваш сосед справа – умный или дурак? В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит<i> F </i>. При каком наибольшем значении<i> F </i>всегда можно, зная эти ответы, указать на умного человека в этой компании?
Дан ряд чисел<i> 1,1,2,3,5,8,13,21,34,..., </i>каждое из которых, начиная с третьего, равно сумме двух предыдущих. Доказать, что каждое натуральное число<i> n>2 </i>равно сумме нескольких различных чисел указанного ряда.
Для каждой пары действительных чисел<i>a</i>и<i>b</i>рассмотрим последовательность чисел<i>p</i><sub>n</sub>= [2{<i>an</i>+<i>b</i>}]. Любые<i>k</i>подряд идущих членов этой последовательности назовем словом. Верно ли, что любой упорядоченный набор из нулей и единиц длины<i>k</i>будет словом последовательности, заданной некоторыми<i>a</i>и<i>b</i>при<i>k</i>= 4; при<i>k</i>= 5? Примечание: [<i>c</i>] - целая часть, {<i>c</i>} - дробная часть числа <i>c</i>.
Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за<i>n</i>взвешиваний?
Для какого наибольшего<i>n</i>можно придумать две бесконечные в обе стороны последовательности<i>A</i>и<i>B</i>такие, что любой кусок последовательности<i>B</i>длиной<i>n</i>содержится в<i>A</i>,<i>A</i>имеет период 1995, а<i>B</i>этим свойством не обладает (непериодична или имеет период другой длины)?<font size="-1">Комментарий. Последовательности могут состоять из произвольных символов. Речь идет о минимальном периоде.</font>
В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если это кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся. На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре <i>k</i>-е место по числу голосов. Определ...
Из имеющихся последовательностей {<i>b<sub>n</sub></i>} и {<i>c<sub>n</sub></i>} (возможно, {<i>b<sub>n</sub></i>} совпадает с {<i>c<sub>n</sub></i>}) разрешается получать последовательности {<i>b<sub>n</sub> + c<sub>n</sub></i>},
{<i>b<sub>n</sub> – c<sub>n</sub></i>}, {<i>b<sub>n</sub>c<sub>n</sub></i>} и {<sup><i>b<sub>n</sub></i></sup>/<sub><i>c<sub>n</sub></i></sub>} (если все члены последовательности {<i>c<sub>n</sub></i>} отличны от 0). Кроме того, из любой имеющейся последователь...
Докажите, что первые цифры чисел вида 2<sup>2<sup>n</sup></sup> образуют непериодическую последовательность.
За круглым столом сидят десять человек, перед каждым – несколько орехов. Всего орехов – сто. По общему сигналу каждый передаёт часть своих орехов соседу справа: половину, если у него (у того, кто передаёт) было чётное число, или один орех плюс половину остатка – если нечётное число. Такая операция проделывается второй раз, затем третий и так далее, до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.
Имеется набор гирь, веса которых в граммах: 1, 2, 4,... , 512 (последовательные степени двойки) – по одной гире каждого веса. Груз разрешается взвешивать с помощью этого набора, кладя гири на обе чашки весов.
а) Докажите, что никакой груз нельзя взвесить этими гирями более чем 89 способами.
б) Приведите пример груза, который можно взвесить ровно 89 способами.
Рассматривается последовательность слов, состоящих из букв "A" и "B". Первое слово в последовательности – "A", <i>k</i>-е слово получается из (<i>k</i>–1)-го с помощью следующей операции: каждое "A" заменяется на "AAB", каждое "B" – на "A". Легко видеть, что каждое слово является началом следующего, тем самым получается бесконечная последовательность букв: AABAABAAABAABAAAB...
а) На каком месте в этой последовательности встретится 1000-я буква "A"?
б) Докажите, что эта последовательность – непериодическая.