РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 5 6 7 8 9
Атрибут

Всего: 86 1–20 | 21–40 | 41–60 | 61–80 | 81–86

Добавить в вариант

Тип 0 № 5899 Добавить в вариант

На плоскости отмечены 4900 различных точек, каждая из которых красного или синего цвета. Для каждой синей точки нарисована окружность радиуса 1 с центром в этой точке. Оказалось, что на каждой нарисованной окружности лежат ровно две красные точки. Какое максимальное число отмеченных точек синего цвета могло быть?

Решение.

Обозначим число красных точек за k. Окружности из условия задачи будем называть синими окружностями. Нарисуем новые красные окружности радиуса 1 с центром в каждой из красных точек. Заметим, что красная точка лежит на синей окружности тогда и только тогда, когда соответствующая синяя точках лежит на соответствующей красной окружности. По условию задачи на каждой синей окружности лежат ровно две красные точки. Это условие равносильно тому, что через каждую синюю точку проходят ровно две красные окружности, т. е. каждая синяя точка есть точка пересечения двух красных окружностей.

Две различные окружности на плоскости имеют не более двух общих точек, всего пар красных точек ровно $дробь: числитель: k умножить на левая круглая скобка k минус 1 правая круглая скобка , знаменатель: 2 конец дроби ,$ и поэтому число попарных пересечений красных окружностей не превосходит $k левая круглая скобка k минус 1 правая круглая скобка .$ Значит, синих точек не более чем $k левая круглая скобка k минус 1 правая круглая скобка ,$ и тогда всего точек не более чем $k левая круглая скобка k минус 1 правая круглая скобка плюс k=k в квадрате .$ Но всего точек 4900; следовательно, $k больше или равно 70.$

Ситуации, когда $k=70,$ легко добиться: достаточно расположить 70 красных точек на одной прямой на близком расстоянии, нарисовать с центрами в этих точках окружности радиуса 1 и в точках пересечения этих окружностей расположить синие точки. Очевидно, что никакие три окружности не пересекутся в одной точке.

Ответ: 4830.

Аналоги к заданию № 5897: 5898 5899 Все

Решение · Прототип задания · Помощь

Тип 0 № 6049 Добавить в вариант

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

Решение · Помощь

Тип 0 № 6236 Добавить в вариант

Среди пенсионерок одной из планет Тау Кита распространено следующее времяпрепровождение: доска в клетку размером 2016 на 2017 раскрашивается золотой и серебряной красками в шахматном порядке, после чего в вершинах каждой из клеток записываются числа 0 или 1 таким образом, чтобы сумма чисел в вершинах любой золотой клетки была бы четной, а в вершинах любой серебряной клетки  — нечетной. Какой может получиться сумма чисел, записанных в четырёх вершинах самой доски?

Решение · Помощь

Тип 0 № 6526 Добавить в вариант

Перед вами куб. Раскрасьте его вершины так, чтобы выполнялись следующие условия:

1)  у каждой синей вершины одинаковое количество синих соседей;

2)  у каждой красной вершины тоже одинаковое количество синих соседей;

3)  присутствовали бы вершины обоих цветов.

Раскраски, удовлетворяющие условиям 1 и 2 называются совершенными.

Решение · Помощь

Тип 21 № 6527 Добавить в вариант

Раскраски данного куба в 2 цвета, удовлетворяющие следующим условиям, называются совершенными.

1)  у каждой синей вершины было одинаковое количество синих соседей;

2)  у каждой красной вершины тоже было бы одинаковое количество синих соседей;

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

Решение.

Во-первых, есть две тривиальные раскраски, в которых отсутствует один из-цветов.

Далее, у каждой синей вершины может быть ноль, один или два синих соседа (случай, когда синих соседей три, приводит нас к тривиальной раскраске). Обозначим количество синих вершин за x, красных за y, количество красных соседей у синей вершины за a, а количество синих соседей у красной вершины за b. Все эти числа для нетривиальных раскрасок больше нуля. Тогда количество ребер, концы которых покрашены в разные цвета, можно посчитать двумя способами: с одной стороны, это xa, а с другой стороны это уb. Таким образом, $xa= yb.$

Пусть x равно 5 или 7. Тогда yb  — это произведение двух натуральных чисел, не превосходящих 3. Поэтому оно не может делиться на 5 или 7. Значит, эти случаи невозможны. Аналогично у не может быть равно 5 или 7, т. е. x не может быть равно 1 или 3. Значит, осталось рассмотреть три возможных значения x: 6, 4 и 2.

Пусть $x=2.$ Тогда у нас ровно две синих вершины (см. первый рисунок в решении задачи 1). Они могут находиться на одном ребре, в противоположных углах одной грани или быть противоположными вершинами куба. Легко убедиться, что только последний вариант даёт нам совершенную раскраску. Две противоположные вершины можно выбрать 4 способами, значит, раскрасок такого типа 4.

Случай $x=6$ полностью аналогичен: вместо синих вершин достаточно рассмотреть красные. (рисунок 2).

Пусть теперь $x=4.$ Заметим, что так как $x=y=4,$ число a должно быть равно b. Число a может принимать значения 1, 2 или 3. Рассмотрим все эти варианты.

1)  Когда $a=3.$ То есть, у каждой синей вершины все соседи красные. Аналогично у каждой красной вершины все соседи синие. Это возможно только при раскраске, изображённой на рисунке 3 или при такой же раскраске, в которой цвета поменяны местами.

2)  Когда $a=2.$ То есть у каждой синей вершины ровно один синий сосед. Все остальные их 4 соседа красные, значит, оставшиеся две синие вершины находятся на ребре, противоположном соединяющему первые две синие вершины (рисунок 4). Всего у куба 6 пар рёбер, значит, раскрасок такого типа тоже 6.

3)  Когда $a=1.$ В этом случае синие вершины должны образовывать цикл из 4 вершин. Очевидно, это возможно только в том случае, когда они лежат на одной грани. Шесть граней дают нам шесть раскрасок такого вида.

Итого получаем 2 + 4 + 4 + 2 + 6 + 6  =  24 раскраски.

Ответ: 24.

Решение · Помощь

Тип 21 № 6699 Добавить в вариант

Find all positive integer K such that the tiles depicted to the right can tile the chess board of size (N + K) × (N + K).

Пусть K  — произвольное неотрицательное целое число. Исследуйте, для каких K можно покрыть шахматную доску размера (N + K) × (N + K) фигурками вида, указанного на рисунке справа, а для каких  — нет.

Решение · Помощь

Тип 21 № 6707 Добавить в вариант

Find all positive integer K such that the tiles depicted to the right can tile the chess board of size

(2(N + K) +2) × (2(N + K) + 2).

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

(2(N + K) +2) × (2(N + K) + 2)

фигурками вида, указанного на рисунке справа, а для каких  — нет.

Решение · Помощь

Тип 0 № 6762 Добавить в вариант

В каждой клетке полоски длины 100 стоит по фишке. Можно за 1 рубль поменять местами любые две соседние фишки, а также можно бесплатно поменять местами любые две фишки, между которыми стоят ровно три фишки. За какое наименьшее количество рублей можно переставить фишки в обратном порядке?

(Егор Бакаев)

Решение · Помощь

Тип 0 № 6777 Добавить в вариант

В клетчатом деревянном квадрате 102 клетки намазаны чёрной краской. Петя, используя квадрат как печать, 100 раз приложил его к белому листу, и каждый раз эти 102 клетки (и только они) оставляли чёрный отпечаток на бумаге. Мог ли в итоге на листе получиться квадрат 101 · 101, все клетки которого, кроме одной угловой, чёрные?

(Александр Грибалко)

Решение · Помощь

Тип 0 № 6784 Добавить в вариант

Некоторые из чисел 1, 2, 3, ..., n покрашены в красный цвет так, что выполняется условие: если для красных чисел a, b, c (не обязательно различных) $a левая круглая скобка b минус c правая круглая скобка$ делится на n, то $b=c.$ Докажите, что красных чисел не больше, чем $\varphi левая круглая скобка n правая круглая скобка$ (количество натуральных чисел, не превосходящих n и взаимно простых с n).

(Александр Семенов)

Решение · Помощь

Тип 0 № 6863 Добавить в вариант

Для каких k можно закрасить на белой клетчатой плоскости несколько (конечное число, большее нуля) клеток в чёрный цвет так, чтобы на любой клетчатой вертикали, горизонтали и диагонали либо было ровно k чёрных клеток, либо вовсе не было чёрных клеток?

(А. Динев, К. Гаров, Н. Белухо)

Решение.

I способ. Закрасим чёрным сначала k клеток, стоящих подряд вдоль одной из диагоналей, идущсй вправо-вниз. Затем сдвинем эту картинку по диагонали вправо-вверх на $k, 2 k, 3 k, \ldots, левая круглая скобка k минус 1 правая круглая скобка k$ клеток. Получится множество A из $k в квадрате$ чёрных клеток, которое каждая горизонталь и вертикаль пересекает не более чем по одной клетке, а каждая диагональ имеет с A либо 0, либо k общих клеток (см. рис. слева для $k=3 правая круглая скобка .$ При этом всё множество A лежит в квадрате $k в квадрате \times k в квадрате .$

Заметим, что если квадрат $n \times n$ сдвинуть на $2 n$ клеток по вертикали, то не существует диагонали, пересекающей оба эти квадрата (см. рис. справа для $n=3 правая круглая скобка .$ Поэтому, сдвинув множество A на $2 k в квадрате , 4 k в квадрате , \ldots, 2 левая круглая скобка k минус 1 правая круглая скобка k в квадрате$ вверх, мы получим множество B из $k в кубе$ чёрных клеток, которое каждая горизонталь пересекает не более чем по одной клетке, а каждая вертикаль и диагональ имеет с B либо 0, либо k общих клеток. При этом все множество B лежит в квадрате $2 k в кубе \times 2 k в кубе .$

Теперь, сдвинув множество B на $4 k в кубе , 8 k в кубе , \ldots, 4 левая круглая скобка k минус 1 правая круглая скобка k в кубе$ вправо, мы получим искомое множество из $k в степени левая круглая скобка 4 правая круглая скобка$ чёрных клеток.

Замечание. Другими словами, построенное множество состоит из клеток с «координатами»

$левая круглая скобка минус i плюс k j плюс 4 m k в кубе , i плюс k j плюс 2 n k в квадрате правая круглая скобка ,$ $0 меньше или равно i,$ $j, m, n меньше k.$

II способ. Есть 4 вида линий. Линии, на которых есть чёрные клетки, назовём покрываемыми. Требуется, чтобы на каждой покрываемой линии было ровно по k чёрных клеток. тем же множеством покрываемых линий у каждого.

Набор чёрных клеток, для которого на каждый прокрываемый линии содержится ровно k клеток, назовем k-набором. Из k-набора можно получить 2k-набор. Для этого вырежем квадрат, содержащий k-набор, и разместим его копии в квадратах, отмеченных буквами на рисунке.

Назовем k-набор супернабором, если его можно разбить на 1-наборы с тем же множеством покрываемых линий у каждого. Указанный выше метод из k-супернабора строит 2k-супернабор. Действительно, разобьём k-супернабор на 1-наборы. Возьмём один из них. Его копии на однобуквенных местах образуют 1-набор, который покрывает то же множество линий, что и $2 k$ -набор. Весь $2 k$ -набор разобьётся на такие 1-наборы, значит, это 2k-супернабор.

В k-супернаборе легко выделить l-набор для любого $l меньше или равно k:$ взять в нём l разных 1-наборов с тем же множеством покрывающих линий у каждого.

Осталось заметить, что 1-супернабор существует: он состоит, например, из одной клетки. Тогда для каждого k мы сможем создать сначала N-супернабор с $N больше k,$ а затем получить из него нужный нам k-набор.

Замечание. В решении 1 получается $k в степени левая круглая скобка 4 правая круглая скобка$ клеток в квадрате со стороной порядка $4 k в степени левая круглая скобка 4 правая круглая скобка .$ В решении 2  — менее $4 k в кубе$ клеток, порядок стороны  — менее $k в кубе .$

Ответ: для всех натуральных k.

Решение · Помощь

Тип 0 № 7005 Добавить в вариант

Клетчатый квадрат 1024 × 1024 разрезан на квадраты 324 × 32. Можно ли раскрасить все его клетки в 512 цветов так, чтобы в каждой строке, в каждом столбце и в каждом из получившихся квадратов 32 × 32 каждый цвет встречался ровно два раза?

Решение.

Докажем следующую лемму. Пусть квадрат $n в квадрате \times n в квадрате$ разбит на $n в квадрате$ квадратов $n \times n .$ Все его клетки можно раскрасить в $n в квадрате$ цветов так, чтобы в каждой строчке, в каждом столбце и в каждом квадрате разбиения каждый цвет встречался ровно один раз (этот принцип используется в головоломках «судоку»).

Приведем одну из возможных конструкций раскраски (пример для $n=3$ показан на рисунке). Пусть A  — левый-верхний квадрат $n \times n .$ Покрасим его в $n в квадрате$ разных цветов. Теперь покрасим следующий справа квадрат $n \times n,$ сдвинув строчки квадрата A по циклу. Еще раз сдвинув их по циклу, покрасим следующий квадрат, и т. д.

Теперь покрасим следующие n строк. Для этого самый левый квадрат в них покрасим, сдвинув по циклу столбцы квадрата A. Следующие квадраты в этих строках покрасим, снова сдвигая строки по циклу.

Продолжая далее сверху вниз, покрасим весь квадрат. Пример раскраски квадрата $9 \times 9$ приведен на рисунке. Из доказанной леммы легко следует решение задачи. Раскрасим квадрат $1024 \times 1024$ в 1024 цвета, как требуется в лемме; затем разобьем все цвета на 512 пар, и в каждой паре заменим один из цветов на другой. Теперь в каждой строчке, в каждом столбце и в каждом квадрате все 512 цветов встречаются по два раза.

Ответ: можно.

Решение · Помощь

Тип 0 № 7019 Добавить в вариант

Клетки доски 100 × 100 раскрашены в чёрный и белый цвета в шахматном порядке. Можно ли перекрасить ровно 2018 различных клеток этой доски в противоположный цвет так, чтобы в каждой строке и в каждом столбце оказалось одно и то же количество чёрных клеток?

(Ю. Чеканов)

Решение.

Решение 1. Ясно, что строки доски можно переставлять как угодно, и столбцы тоже. Переставим все нечётные столбы влево, а вое нечётные строки вниз. В итоге из исходной доски получится доска, разделённая на 4 одинаковых квадрата  — два противоположных из них белые, а остальные чёрные.

Пусть после перекраски в каждой строке и каждом столбце оказалось по $50 плюс k$ чёрных клеток; тогда в каждом столбце и в каждой строке перекрашено на k белых клеток больше, чем чёрных. Пусть в одном из чёрных квадратов перекрашено а клеток. По замечанию выше, в каждом из белых квадратов перекрашено по $a плюс 50 k$ клеток, а тогда в другом чёрном квадрате также перекрашено $левая круглая скобка a плюс 50 k правая круглая скобка минус 50 k=a$ клеток. Значит, общее число перекрашенных клеток равно

$2 a плюс 2 левая круглая скобка a плюс 50 k правая круглая скобка =4 левая круглая скобка a плюс 25 k правая круглая скобка ,$

то есть оно делится на 4 и потому не может равняться 2018.

Решение 2. Пронумеруем строки снизу вверх, а столбы справа налево, числами от 1 до 100 (пусть левая нижняя клетка чёрная). Тогда у каждой чёрной клетки чётная сумма координат, a у каждой белой  — нечётная.

Рассмотрим сумму координат всех чёрных клеток (до или после перекраски). Поскольку в каждой строке их поровну, сумма их ординат делится на $1 плюс 2 плюс \ldots плюс 100=5050,$ аналогично сумма абсцисс также делится на 5050. В частности, эта сумма до и после перекраски была чётной, то есть изменилась на чётное число.

С другой стороны, при перекраске исходно чёрной клетки в белый цвет наша сумма чётности не меняла, а при перекраске исходно белой в чёрный  — меняла. Это значит, что было перекрашено чётное количество белых клеток.

Пусть w и b  — количества перекрашенных исходно белых и исходно чёрных клеток, соответственно. Тогда $w плюс b=2018,$ а $w минус b$ делится на 4, поскольку как исходное, так и полученное количество чёрных клеток делится на 4. Значит,

$w= дробь: числитель: левая круглая скобка левая круглая скобка w плюс b правая круглая скобка плюс левая круглая скобка w минус b правая круглая скобка правая круглая скобка , знаменатель: 2 конец дроби$

нечётное число. Противоречие.

Ответ: нет.

Решение · Помощь

Тип 0 № 7048 Добавить в вариант

Каждый отрезок с концами в вершинах правильного 100-угольника покрасили  — в красный цвет, если между его концами чётное число вершин, и в синий  — в противном случае (в частности, все стороны 100-угольника красные). В вершинах расставили числа, сумма квадратов которых равна 1, а на отрезках  — произведения чисел в концах. Затем из суммы чисел на красных отрезках вычли сумму чисел на синих. Какое наибольшее число могло получиться?

Решение · Помощь

Тип 0 № 7083 Добавить в вариант

Изначально на белой клетчатой плоскости конечное число клеток окрашено в чёрный цвет. На плоскости лежит бумажный клетчатый многоугольник M, в котором больше одной клетки. Его можно сдвигать, не поворачивая, в любом направлении на любое расстояние, но так, чтобы после сдвига он лежал «по клеткам». Если после очередного сдвига ровно одна клетка у M лежит на белой клетке плоскости, эту белую клетку окрашивают в чёрный цвет и делают следующий сдвиг. Докажите, что существует такая белая клетка, которая никогда не будет окрашена в чёрный цвет, сколько бы раз мы ни сдвигали M по описанным правилам.

Решение.

Решение 1. Вместо клеток будем рассматривать их центры, которые назовём узлами. Проведём вертикальную прямую через самой левый узел бумажной фигуры. Если эта прямая не содержит других узлов фигуры, то будем поворачивать прямую по часовой стрелке до тех пор, пока на неё не попадёт ещё один узел фигуры. Мы нашли такую прямую l, содержащую не менее двух узлов фигуры, что все узлы фигуры лежат по одну сторону от l.

Каждый узел плоскости находится на каком-то ориентированном расстоянии от l (расстояния до узлов, лежащих в той же полуплоскости, что и фигура, берём со знаком минус). Пусть r максимальное из таких расстояний до чёрных узлов. Докажем, что все узлы с расстоянием, большим r, останутся белыми. Предположим противное и рассмотрим первый такой узел, который стал чёрным. Значит, он накрыт сдвигом фигуры. Но тогда фигура накрывает ещё хотя бы один узел с таким же расстоянием (l фиксирована, расстояния  — тоже, фигура сдвигается). Так как фигура накрывает хотя бы два белых узла, то окрашивать узел нельзя. Противоречие.

Решение 2. Построим клетчатый прямоугольник, содержащий все черные клетки. Обозначим прямую, содержащую правую сторону прямоугольника за p. Аналогично определим прямые l («левая»), v («верхняя»), n («нижняя»). Заметим теперь, что у M ровно одна самая верхняя клетка, иначе ни одна клетка выше v не будет покрашена (рассмотрим первый момент, когда многоугольник вышел за v, тогда у него выше v хотя бы две точки и они обе белые). Аналогично есть одна самая правая, левая и нижняя. Обозначим их V, P, L и N соответственно (ясно, что они все различны).

Покажем теперь, что если была покрашена клетка выше v, то она была покрашена клеткой V фигуры M. Предположим противное и возьмём первый момент, когда это не так. Тогда некая клетка выше v была закрашена другой клеткой фигуры $М.$ Посмотрим на клетку, где в этот момент находилась V. Она тоже выше v, и при этом уже чёрная (иначе условие покраски не выполняется), значит, была покрашена нами ранее. Но тогда она была покрашена клеткой V и фигура M лежала на плоскости так же. Но такого быть не может, так как тогда в M было бы не менее, чем две белые клетки. Аналогично доказываются утверждения про клетки правее p, левее l и ниже n. Рассмотрим теперь любую клетку, которая лежит и выше v, и правее p. С одной стороны она могла быть покрашена только клеткой V, c другой  — только клеткой P. Значит, покрасить мы её не можем.

Замечание. Связность фигуры-шаблона не важна. Если фигура не помещается ни в горизонталь, ни в вертикаль, то окрашено будет конечное число клеток.

Решение · Помощь

Тип 0 № 7121 Добавить в вариант

Какую наибольшую длину может иметь замкнутая самонепересекающаяся ломаная, идущая по линиям сетки клетчатого поля размером $8 \times 8 ?$

Аналоги к заданию № 7121: 7125 Все

Решение · Критерии · Помощь

Тип 0 № 7125 Добавить в вариант

Какую наибольшую длину может иметь замкнутая самонепересекающаяся ломаная, идущая по линиям сетки клетчатого поля размером $6 \times 10$ ?

Аналоги к заданию № 7121: 7125 Все

Решение · Прототип задания · Критерии · Помощь

Тип 21 № 7168 Добавить в вариант

Мастер Ли Си Цын делает веера. Каждый веер состоит из 6 секторов, покрашенных с двух сторон в красный и синий цвета (см. рис.). Причем если одна из сторон сектора покрашена в красный цвет, то обратная покрашена в синий и наоборот. Каждые два веера, сделанные мастером отличаются раскраской (если одна раскраска переходит в другую при переворачивании веера, то они считаются одинаковыми). Какое набольшее количество вееров может сделать мастер?


Нераскрашенный веер	Раскрашенный веер	Обратная сторона

Решение · Помощь

Тип 0 № 7285 Добавить в вариант

Вершины правильного 100-угольника раскрашены случайным образом в два цвета: 50 вершин  — в белый цвет, 50  — в черный. Докажите, что можно разбить все вершины на 25 групп по 4 вершины так, чтобы в каждой группе было по две вершины каждого цвета, и вершины каждой группы являлись вершинами некоторого прямоугольника.

Решение · Критерии · Помощь

Тип 0 № 7387 Добавить в вариант

В какое наименьшее число цветов можно окрасить все клетки квадрата 6 на 6 так, чтобы в каждой горизонтали, вертикали и диагонали квадрата все клетки имели разный цвет? Пояснение: под диагональю квадрата понимаются все ряды из не менее, чем двух клеток, идущие диагонально от одного края квадрата до другого под углом 45º или 135º к горизонтали.

Решение.

Приведём пример раскраски в 7 цветов, удовлетворяющей условию задачи. Рассмотрим квадрат 7 на 7, и окрасим его требуемым образом в 7 цветов с помощью известного приёма: окраска каждой следующей горизонтали получается из раскраски предыдущей циклическим сдвигом на 2 клетки. Затем выберем в нём левый нижний угловой квадрат 6 на 6, это и будет требуемый пример. Докажем минимальность 7 цветов. Каждая горизонталь квадрата содержит 6 клеток, поэтому для корректной раскраски потребуется не менее 6 цветов. Предположим, что нам удалось выкрасить квадрат в 6 цветов требуемым в условии образом, тогда клеток каждого цвета будет ровно 6 и располагаться они будут все в различных вертикалах и горизонталях квадрата. Назовём цвет, в который окрашена левая нижняя угловая клетка А квадрата чёрным, и покажем, что оставшиеся 5 чёрных клеток не могут располагаться в правом верхнем квадрате 5 на 5 в разных вертикалях и горизонталях и при этом не лежать на его главной диагонали, уже контролируемой клеткой А. В противном случае можно считать, что не меньше трёх из них располагались бы ниже главной диагонали в фигуре «лесенка» из 10 клеток, состоящей из 4 полосок по 4,3,2,1 клеток соответственно. Однако непосредственно проверяется, что для любой клетки «лесенки» клетки, не находящиеся с окрашенной в одной горизонтали, вертикали или горизонтали могут корректно содержать ещё не более одной чёрной клетки. Возможные положения этой второй чёрной клетки рассмотрены на рисунке. Клетки, контролируемые ей, окрашены светло-серым цветом. Следовательно. раскрасить квадрат 6 на 6 требуемым образом в условии образом в 6 цветов невозможно.

Ответ: в 7 цветов.

Решение · Критерии · Помощь

Всего: 86 1–20 | 21–40 | 41–60 | 61–80 | 81–86