Олимпиадные задачи по теме «Методы»

Каждая целочисленная точка плоскости окрашена в один из трех цветов, причем все три цвета присутствуют. Докажите, что найдется прямоугольный треугольник с вершинами трех разных цветов.

Можно ли в клетках бесконечного клетчатого листа расставить натуральные числа таким образом, чтобы при любых натуральных  <i>m, n</i> > 100  сумма чисел в любом прямоугольнике <i>m</i>×<i>n</i> клеток делилась на  <i>m + n</i>?

Пусть <i>a, b, c</i> – положительные числа, сумма которых равна 1. Докажите неравенство:   <img align="middle" src="/storage/problem-media/109792/problem_109792_img_2.gif">

Из промежутка  (2^2<i>n</i>, 2^3<i>n</i>)  выбрано  2^{2<i>n</i>–1} + 1  нечётное число.

Докажите, что среди выбранных чисел найдутся два, квадрат каждого из которых не делится на другое.

В компании из  2<i>n</i> + 1 человека для любых <i>n</i> человек найдётся отличный от них человек, знакомый с каждым из них.

Докажите, что в этой компании есть человек, знающий всех.

По окружности расставлено 100 натуральных чисел, взаимно простых в совокупности. Разрешается прибавлять к любому числу наибольший общий делитель его соседей. Докажите, что при помощи таких операций можно сделать все числа попарно взаимно простыми.

В некоторых клетках доски 2<i>n</i>×2<i>n</i> стоят чёрные и белые фишки. С доски сначала снимаются все чёрные фишки, которые стоят в одной вертикали с какой-то белой, а затем все белые фишки, стоящие в одной горизонтали с какой-нибудь из оставшихся чёрных. Докажите, что либо чёрных, либо белых фишек на доске осталось не более <i>n</i>².

Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета.

Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.

Докажите, что можно разбить все множество натуральных чисел на 100 непустых подмножеств так, чтобы в любой тройке <i>a, b, c</i>, для которой  <i>a</i> + 99<i>b = c</i>,  нашлись два числа из одного подмножества.

Четыре натуральных числа таковы, что квадрат суммы любых двух из них делится на произведение двух оставшихся.

Докажите, что по крайней мере три из этих чисел равны между собой.

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

Внутри выпуклого стоугольника выбрано<i> k </i>точек,2<i><img src="/storage/problem-media/109552/problem_109552_img_2.gif"> k<img src="/storage/problem-media/109552/problem_109552_img_2.gif"> </i>50. Докажите, что можно отметить2<i>k </i>вершин стоугольника так, чтобы все выбранные точки оказались внутри2<i>k </i>-угольника с отмеченными вершинами.

В выпуклом пятиугольнике <i>ABCDE</i> сторона <i>AB</i> перпендикулярна стороне <i>CD</i>, а сторона <i>BC</i> – стороне <i>DE</i>.

Докажите, что если  <i>AB = AE = ED</i> = 1,  то  <i>BC + CD</i>  < 1.

Существует ли выпуклый многоугольник, у которого длины всех сторон равны, а любые три вершины образуют тупоугольный треугольник?

На доске написаны  <i>n</i> > 3  различных натуральных чисел, меньших чем  (<i>n</i> – 1)!.  Для каждой пары этих чисел Серёжа поделил большее на меньшее с остатком и записал в тетрадку полученное неполное частное (так, если бы он делил 100 на 7, то он бы получил  100 = 14·7 + 2  и записал бы в тетрадку число 14). Докажите, что среди чисел в тетрадке найдутся два равных.

Существует ли такая бесконечная возрастающая последовательность <i>a</i>₁, <i>a</i>₂, <i>a</i>₃, ... натуральных чисел, что сумма любых двух различных членов последовательности взаимно проста с суммой любых трёх различных членов последовательности?

Внутри выпуклого 100-угольника выбрана точка <i>X</i>, не лежащая ни на одной его стороне или диагонали. Исходно вершины многоугольника не отмечены. Петя и Вася по очереди отмечают ещё не отмеченные вершины 100-угольника, причём Петя начинает и первым ходом отмечает сразу две вершины, а далее каждый своим очередным ходом отмечает по одной вершине. Проигрывает тот, после чьего хода точка <i>X</i> будет лежать внутри многоугольника с отмеченными вершинами. Докажите, что Петя может выиграть, как бы ни ходил Вася.

Квадрат разбит на  <i>n</i>² ≥ 4  прямоугольников  2(<i>n</i> – 1)  прямыми, из которых  <i>n</i> – 1  параллельны одной стороне квадрата, а остальные  <i>n</i> – 1  – другой. Докажите, что можно выбрать 2<i>n</i> прямоугольников разбиения таким образом, что для каждых двух выбранных прямоугольников один из них можно поместить в другой (возможно, предварительно повернув).

Из клетчатого бумажного квадрата 100×100 вырезали по границам клеток 1950 доминошек (двуклеточных прямоугольников). Докажите, что из оставшейся части можно вырезать по границам клеток четырёхклеточную фигурку вида <b>Т</b> – возможно, повёрнутую. (Если такая фигурка уже есть среди оставшихся частей, считается, что её получилось вырезать.)

Бессмертная блоха прыгает по целым точкам на числовой прямой, стартуя с точки 0. Длина первого прыжка равна 3, второго – 5, третьего – 9, и так далее (длина <i>k</i>-го прыжка равна  2^<i>k</i> + 1).  Направление прыжка (вправо или влево) блоха выбирает самостоятельно. Может ли так случиться, что блоха рано или поздно побывает в каждой натуральной точке (возможно, побывав в некоторых точках больше, чем по разу)?

Поле представляет собой клетчатый квадрат 41×41, в одной из клеток которого замаскирован танк. Истребитель за один выстрел обстреливает одну клетку. Если произошло попадание, танк переползает на соседнюю по стороне клетку поля, если нет – остаётся на месте. При этом после выстрела пилот истребителя не знает, произошло ли попадание. Для уничтожения танка надо попасть в него два раза. Каким наименьшим числом выстрелов можно обойтись для того, чтобы гарантировать, что танк уничтожен?

У нумизмата есть 100 одинаковых по внешнему виду монет. Он знает, что среди них 30 настоящих и 70 фальшивых монет. Кроме того, он знает, что массы всех настоящих монет одинаковы, а массы всех фальшивых – разные, причём каждая фальшивая монета тяжелее настоящей; однако точные массы монет неизвестны. Имеются двухчашечные весы без гирь, на которых можно за одно взвешивание сравнить массы двух групп, состоящих из одинакового числа монет. За какое наименьшее количество взвешиваний на этих весах нумизмат сможет гарантированно найти хотя бы одну настоящую монету?

По кругу записаны 100 целых чисел. Каждое из чисел больше суммы двух чисел, следующих за ним по часовой стрелке.

Какое наибольшее количество положительных чисел может быть среди записанных?

В волейбольном турнире участвовали 110 команд, каждая сыграла с каждой из остальных ровно одну игру (в волейболе не бывает ничьих). Оказалось, что в любой группе из 55 команд найдётся одна, которая проиграла не более чем четырём из остальных 54 команд этой группы. Докажите, что во всём турнире найдётся команда, проигравшая не более чем четырём из остальных 109 команд.

Натуральное число <i>n</i> назовём <i> хорошим</i>, если каждый его натуральный делитель, увеличенный на 1, является делителем числа  <i>n</i> + 1.

Найдите все хорошие натуральные числа.