Фольклор — олимпиадные задачи по математике - сложность 3 с решениями

Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого или чёрного цветов. Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из двух цветов (каждый мудрец выкрикивает цвет один раз). После окончания этого процесса король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака. Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казнённых. Скольким из них гарантированно удастся избежать казни?

Внутри квадрата <i>ABCD</i> лежит квадрат <i>PQRS</i>. Отрезки <i>AP, BQ, CR</i> и <i>DS</i> не пересекают друг друга и стороны квадрата <i>PQRS</i>.

Докажите, что сумма площадей четырёхугольников <i>ABQP</i> и <i>CDSR</i> равна сумме площадей четырёхугольников <i>BCRQ</i> и <i>DAPS</i>.

Дана окружность и точка <i>A</i> внутри неё.

Найдите геометрическое место вершин <i>C</i> всевозможных прямоугольников <i>ABCD</i>, где точки <i>B</i> и <i>D</i> лежат на окружности.

Дан квадрат, внутри которого лежит точка <i>O</i>. Докажите, что сумма углов <i>OAB, OBC, OCD</i> и <i>ODA</i> отличается от 180° не больше чем на 45°.

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

Лёша задумал двузначное число (от 10 до 99). Гриша пытается его отгадать, называя двузначные числа. Если Гриша правильно называет число, или же одну цифру называет правильно, а в другой ошибается не более чем на единицу, то Лёша отвечает "тепло"; в остальных случаях Лёша отвечает "холодно". (Например, если задумано число 65, то назвав 65, 64, 66, 55 или 75, Гриша услышит в ответ "тепло", а в остальных случаях услышит "холодно".)

  а) Покажите, что нет способа, при котором Гриша гарантированно узнает число, истратив 18 попыток.

  б) Придумайте способ, при котором Гриша гарантированно узнает число, истратив 24 попытки (какое бы число ни задумал Лёша).

  в) А за 22 попытки получится?

На плоскости нарисован чёрный равносторонний треугольник. Имеется девять треугольных плиток того же размера и той же формы. Нужно положить их на плоскость так, чтобы они не перекрывались и чтобы каждая плитка покрывала хотя бы часть чёрного треугольника (хотя бы одну точку внутри него). Как это сделать?

Рассмотрим все возможные наборы чисел из множества  {1, 2, 3, ..., <i>n</i>},  не содержащие двух соседних чисел.

Докажите, что сумма квадратов произведений чисел в этих наборах равна  (<i>n</i> + 1)! – 1.

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

  а) меньше  ^<i>mn</i>/₄;

  б) меньше  ^<i>mn</i>/₅.

Плоскость разбита тремя сериями параллельных прямых на равные между собой равносторонние треугольники.

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

а) Даны две одинаковые шестерёнки с 14 зубьями каждая. Их наложили друг на друга так, что зубья совпали (так что проекция на плоскость выглядит как одна шестерёнка). После этого четыре пары совпадающих зубьев выпилили. Всегда ли можно повернуть эти шестерёнки друг относительно друга так, чтобы проекция на плоскость выглядела как одна целая шестерёнка? (Шестерёнки можно поворачивать, но нельзя переворачивать.) б) Тот же вопрос про две шестерёнки с 13 зубьями, из которых выпилили по 4 зуба.

Числа  1, 2, 3, ..., <i>n</i>  записываются в некотором порядке:  <i>a</i>₁, <i>a</i>₂, <i>a</i>₃, ..., <i>a_n</i>.  Берётся сумма  <i>S</i> = ^<i>a</i>₁/₁ + ^<i>a</i>₂/₂ + ... + ^<i>a_n</i>/_<i>n</i>.  Найдите такое <i>n</i>, чтобы среди таких сумм (при всевозможных перестановках  <i>a</i>₁, <i>a</i>₂,...

<i>P</i>(<i>х</i>) – многочлен с целыми коэффициентами. Известно, что числа 1 и 2 являются его корнями. Докажите, что найдётся коэффициент, который меньше –1.

В наборе имеются гири массой 1 г, 2 г, 4 г, ... (все степени числа 2), причём среди гирь могут быть одинаковые. На две чашки весов положили гири так, чтобы наступило равновесие. Известно, что на левой чашке все гири различны. Докажите, что на правой чашке не меньше гирь, чем на левой.

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

В клетки шахматной доски записаны числа от 1 до 64 (первая горизонталь нумеруется слева направо числами от 1 до 8, вторая от 9 до 16 и т. д.). Перед некоторыми числами поставлены плюсы, перед остальными – минусы, так что в каждой горизонтали и в каждой вертикали по четыре плюса и по четыре минуса. Докажите, что сумма всех чисел равна 0.

Восемь волейбольных команд провели турнир в один круг (каждая команда сыграла с каждой один раз). Доказать, что можно выделить такие четыре команды <i>A, B, C</i> и <i>D</i>, что <i>A</i> выиграла у <i>B, C</i> и <i>D</i>; <i>B</i> выиграла у <i>C</i> и <i>D, C</i> выиграла у <i>D</i>.

В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику.

В квадрате 7×7 клеток размещено 16 плиток размером 1×3 и одна плитка 1×1.

Докажите, что плитка 1×1 либо лежит в центре, либо примыкает к границам квадрата.

В правильном десятиугольнике проведены все диагонали. Возле каждой вершины и возле каждой точки пересечения диагоналей поставлено число +1 (рассматриваются только сами диагонали, а не их продолжения). Разрешается одновременно изменить все знаки у чисел, стоящих на одной стороне или на одной диагонали. Можно ли с помощью нескольких таких операций изменить все знаки на противоположные?

Доказать, что из 17 различных натуральных чисел либо найдутся пять таких чисел <i>a, b, c, d, e</i>, что каждое из чисел этой пятёрки, кроме последнего, делится на число, стоящее за ним, либо найдутся пять таких чисел, что ни одно из них не делится на другое.

На полосе бумаги написаны подряд 60 знаков: "×" и "0". Эту полоску разрезают на куски с симметричным расположением знаков. Например:

0,  × ×,  0 × × × × 0,  × 0 ×,  ... .

  а) Докажите, что существует такой способ разрезания, при котором кусков не больше 24.

  б) Приведите пример такого расположения знаков, при котором меньше 15 кусков получить нельзя.

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

Игра происходит на бесконечной плоскости. Играют двое: один передвигает одну фишку-волка, другой – 50 фишек-овец. После хода волка ходит одна из овец, затем, после следующего хода волка, опять какая-нибудь из овец и т. д. И волк, и овцы передвигаются за один ход в любую сторону не более, чем на один метр. Верно ли, что при любой первоначальной позиции волк поймает хотя бы одну овцу?

<i>a</i>₁, <i>a</i>₂, ..., <i>a</i>₁₀₁  – такая перестановка чисел  2, 3, ..., 102,  что <i>a</i>_<i>k</i> делится на <i>k</i> при каждом <i>k</i>. Найти все такие перестановки.