Олимпиадные задачи из источника «Книги, журналы» - сложность 3 с решениями

Бесконечная последовательность чисел <i>x_n</i> определяется условиями:  <i>x</i>_<i>n</i>+1 = 1 – |1 – 2<i>x_n</i>|,  причём  0 ≤ <i>x</i>₁ ≤ 1.

  а) Докажите, что последовательность, начиная с некоторого места, периодическая в том и только в том случае, когда <i>x</i>₁ рационально.

  б) Сколько существует значений <i>x</i>₁, для которых эта последовательность – периодическая с периодом <i>T</i> (для каждого <i>T</i> = 2, 3, ...)?

Через <i>S</i>(<i>n</i>) обозначим сумму цифр числа <i>n</i> (в десятичной записи).

Существуют ли три таких различных натуральных числа <i>m, n</i> и <i>p</i>, что   <i>m + S</i>(<i>m</i>) = <i>n+S</i>(<i>n</i>) = <i>p + S</i>(<i>p</i>)?

В таблице <i>m</i> строк, <i>n</i> столбцов. <i>Горизонтальным ходом</i> называется такая перестановка элементов таблицы, при которой каждый элемент остаётся в той строке, в которой он был и до перестановки; аналогично определяется <i>вертикальный ход</i> ("строка" в предыдущем определении заменяется на "столбец"). Укажите такое <i>k</i>, что за <i>k</i> ходов (любых) можно получить любую перестановку элементов таблицы, но существует такая перестановка, которую нельзя получить за меньшее число ходов.

В четырёхугольнике <i>ABCD</i>  <i>AB = BC = CD</i> = 1,  <i>AD</i> не равно 1. Положение точек <i>B</i> и <i>C</i> фиксировано, точки же <i>A</i> и <i>D</i> подвергаются преобразованиям, сохраняющим длины отрезков <i>AB, CD</i> и <i>AD</i>. Новое положение точки <i>A</i> получается из старого зеркальным отражением в отрезке <i>BD</i>, новое положение точки <i>D</i> получается из старого зеркальным отражением в отрезке <i>AC</i> (где <i>A</i> уже новое), затем на втором шагу опять <i>A</i> отражается относительно <i>BD</i> (<i>D</i> уже новое), затем снова преобразуется <i>D</i&gt...

Пусть <i>n</i> и <i>b</i> – натуральные числа. Через  <i>V</i>(<i>n, b</i>)  обозначим число разложений <i>n</i> на сомножители, каждый из которых больше <i>b</i> (например:

36 = 6·6 = 4·9 = 3·3·4 = 3·12,  так что  <i>V</i>(36, 2) = 5).  Докажите, что  <i>V</i>(<i>n, b</i>) < ^<i>n</i>/_<i>b</i>.

Имеется 100 серебряных монет, упорядоченных по весу, и 101 золотая монета, они также упорядочены по весу. Известно, что все монеты по весу различны. В нашем распоряжении – двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за наименьшее число взвешиваний найти монету, занимающую среди всех монет 101-е место?

Даны три треугольника: <i>A</i>₁<i>A</i>₂<i>A</i>₃, <i>B</i>₁<i>B</i>₂<i>B</i>₃, <i>C</i>₁<i>C</i>₂<i>C</i>₃. Известно, что их центры тяжести (точки пересечения медиан) лежат на одной прямой, а никакие три из девяти вершин этих треугольников не лежат на одной прямой. Рассматриваются 27 треугольников вида <i>A_iB_jC_k</i>, где <i>i, j, k</i> независимо пробегают значения 1, 2, 3. Докажите, что...

Дана таблица <i>n</i>×<i>n</i>, заполненная числами по следующему правилу: в клетке, стоящей в <i>i</i>-й строке и <i>j</i>-м столбце таблицы записано число   <img align="absmiddle" src="/storage/problem-media/98139/problem_98139_img_2.gif">   В таблице зачеркнули <i>n</i> чисел таким образом, что никакие два зачёркнутых числа не находятся в одном столбце или в одной строке. Докажите, что сумма зачёркнутых чисел не меньше 1.

Внутри окружности радиуса 1 расположена замкнутая ломаная (самопересекающаяся), содержащая 51 звено, причём известно, что длина каждого звена равна   <img align="absmiddle" src="/storage/problem-media/98138/problem_98138_img_2.gif"> .   Для каждого угла этой ломаной рассмотрим треугольник, двумя сторонами которого служат звенья ломаной, образующие этот угол (таких треугольников всего 51). Докажите, что сумма площадей этих треугольников не меньше, чем утроенная площадь правильного треугольника, вписанного в окружность.

Круг разбит на <i>n</i> секторов, в некоторых секторах стоят фишки – всего фишек  <i>n</i> + 1.  Затем позиция подвергается преобразованиям. Один шаг преобразования состоит в следующем: берутся какие-нибудь две фишки, стоящие в одном секторе, и переставляются в разные стороны в соседние секторы. Докажите, что через некоторое число шагов не менее половины секторов будет занято.

Точка <i>P</i> лежит на описанной окружности треугольника <i>ABC</i>. Построим треугольник <i>A</i>₁<i>B</i>₁<i>C</i>₁, стороны которого параллельны отрезкам <i>PA, PB, PC</i>

(<i>B</i>₁<i>C</i>₁ || <i>PA,  C</i>₁<i>A</i>₁ || <i>PB,  A</i>₁<i>B</i>₁ || <i>PC</i>). Через точки <i>A</i>₁, <i>B</i>₁, <i>C</i>₁ проведены прямые, пар...

Пусть в прямоугольном треугольнике <i>AB</i> и <i>AC</i> – катеты,  <i>AC > AB</i>.  На <i>AC</i> выбрана точка <i>E</i>, а на <i>BC</i> – точка <i>D</i> так, что  <i>AB = AE = BD</i>.

Докажите, что треугольник <i>ADE</i> прямоугольный тогда и только тогда, когда стороны треугольника <i>ABC</i> относятся как  3 : 4 : 5.

<i>n</i> школьников хотят разделить поровну <i>m</i> одинаковых шоколадок, при этом каждую шоколадку можно разломить не более одного раза.

  а) При каких <i>n</i> это возможно, если   <i>m</i> = 9?

  б) При каких <i>n</i> и <i>m</i> это возможно?

На квадратный лист бумаги со стороной <i>a</i> посадили несколько клякс, площадь каждой из которых не больше 1. Оказалось, что каждая прямая, параллельная сторонам листа, пересекает не более одной кляксы. Докажите, что суммарная площадь клякс не больше <i>a</i>.

На какое максимальное число частей могут разбить координатную плоскость <i>xOy</i> графики 100 квадратных трехчлёнов вида

<i>y = a_nx</i>² + <i>b_nx + c_n</i>  (<i>n</i> = 1, 2, ..., 100)?

В прямоугольной таблице <i>m</i> строк и <i>n</i> столбцов  (<i>m < n</i>).  В некоторых клетках таблицы стоят звёздочки, так что в каждом столбце стоит хотя бы одна звёздочка. Докажите, что существует хотя бы одна такая звёздочка, что в одной строке с нею находится больше звёздочек, чем с нею в одном столбце.

Натуральный ряд представлен в виде объединения некоторого множества попарно непересекающихся целочисленных бесконечных арифметических прогрессий с положительными разностями  <i>d</i>₁, <i>d</i>₂, <i>d</i>₃, ... .  Может ли случиться, что при этом сумма   ¹/_<i>d</i>₁ + ¹/_<i>d</i>₂ + ... + ¹/<i>_{d_k}</i>   не превышает 0,9? Рассмотрите случаи:

  а) общее число прогрессий конечно;

  б) прогрессий бесконечное число (в этом случае условие нужно понимат...

На плоскости дано <i>N</i> прямых  (<i>N</i> > 1),  никакие три из которых не пересекаются в одной точке и никакие две не параллельны. Докажите, что в частях, на которые эти прямые разбивают плоскость, можно расставить ненулевые целые числа, по модулю не превосходящие <i>N</i>, так, что суммы чисел по любую сторону от любой из данных прямых равны нулю.

а) Докажите, что если в 3<i>n</i> клетках таблицы 2<i>n</i>×2<i>n</i> расставлены 3<i>n</i> звёздочек, то можно вычеркнуть <i>n</i> столбцов и <i>n</i> строк так, что все звёздочки будут вычеркнуты.

б) Докажите, что в таблице 2<i>n</i>×2<i>n</i> можно расставить  3<i>n</i> + 1  звёздочку так, что при вычеркивании любых <i>n</i> строк и любых <i>n</i> столбцов остаётся невычеркнутой хотя бы одна звёздочка.

Докажите, что если <i>K</i> чётно, то числа от 1 до  <i>K</i> – 1  можно выписать в таком порядке, что сумма никаких нескольких подряд стоящих чисел не будет делиться на <i>K</i>.

Выпуклые четырёхугольники <i>ABCD</i> и <i>PQRS</i> вырезаны соответственно из бумаги и картона. Будем говорить, что они подходят друг к другу, если выполняются два условия:

    1) картонный четырёхугольник можно наложить на бумажный так, что его вершины попадут на стороны бумажного, по одной вершине на каждую сторону;

    2) если после этого перегнуть четыре образовавшихся маленьких бумажных треугольника на картонный, то они закроют весь картонный четырёхугольник в один слой.

  а) Докажите, что, если четырёхугольники подходят друг к другу, то у бумажного либо две противоположные стороны параллельны,

либо диагонали перпендикулярны.

  б) Докажите, что если <i>ABCD</i> – параллелограмм, то можно сделать подходящий к нему картонный четырёхуголь...

В стране 1988 городов и 4000 дорог.

Докажите, что можно указать кольцевой маршрут, проходящий не более, чем через 20 городов (каждая дорога соединяет два города).

Числа 1, 2, 3, ..., <i>N</i> записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число <i>i</i>, то где-то слева от него встретится хотя бы одно из чисел  <i>i</i> + 1  и  <i>i</i> – 1.  Сколькими способами это можно сделать?

Выпуклый <i>n</i>-угольник разрезан непересекающимися диагоналями на треугольники. Разрешается проделывать следующее преобразование (<i>перестройку</i>): взяв пару треугольников <i>ABD</i> и <i>BCD</i> с общей стороной, заменить их на треугольники <i>ABC</i> и <i>ACD</i>. Пусть <i>P</i>(<i>n</i>) – наименьшее число перестроек, за которое можно перевести каждое разбиение в любое. Докажите, что

  а)  <i>P</i>(<i>n</i>) ≥ <i>n</i> – 3;

  б)  <i>P</i>(<i>n</i>) ≤ 2<i>n</i> – 7;

  в)  <i>P</i>(<i>n</i>) ≤ 2<i>n</i> – 10  при  <i>n</i> ≥ 13.

Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (<i>вертикальные</i> и <i>горизонтальные</i> ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу?