Дано несколько квадратов, сумма площадей которых равна 1. Докажите, что их можно поместить без наложений в квадрат площади 2.
Подробнее
Двое играют в следующую игру. Один называет цифру, а другой вставляет ее по своему усмотрению вместо одной из звездочек в следующей разности:
Затем первый называет еще одну цифру и так далее 8 раз, пока все звездочки не заменятся на цифры. Тот, кто называет цифры, стремится к тому, чтобы разность получилась как можно больше, а второй- чтобы она стала как можно меньше. Докажите, что:
а) второй может расставлять числа так, чтобы получившаяся при этом разность стала бы не больше 4000 независимо от того, какие цифры называл первый;
б) первый может называть цифры так, чтобы разность стала не меньше 4000 независимо от того, куда расставляет эти цифры второй.
Подробнее
Можно ли расставить цифры 0, 1, 2 в клетках листа клетчатой бумаги размером $100 \times 100$ клеток таким образом, чтобы в каждом прямоугольнике $3 \times 4$ клетки оказалось три нуля, четыре единицы и пять двоек?
Подробнее
Когда закончился хоккейный турнир (в один круг), оказалось, что для любой группы команд можно найти команду (может быть, из этой же группы), которая набрала в играх с командами этой группы нечетное число очков. Докажите, что в турнире участвовало четное число команд. (Поражение - 0 очков, ничья - 1 очко, выигрыш - 2 очка.)
Подробнее
На суде в качестве вещественного доказательства предъявлено 14 монет. Эксперт обнаружил, что монеты с 1-й по 7-ю - фальшивые, а с 8-й по 14-ю - настоящие. Суд же знает только то, что фальшивые монеты весят одинаково, настоящие монеты весят одинаково и что фальшивые монеты легче настоящих. В распоряжении эксперта - чашечные весы без гирь.
а) Эксперт хочет доказать суду, что монеты с 1-й по 7-ю - фальшивые. Как он может это сделать, используя только три взвешивания?
б) Покажите, что с помощью трех взвешиваний он может доказать даже больше: что монеты с 1-й по 7-ю - фальшивые, а с 8-й по 14-ю - настоящие.
Подробнее
Дано $n$ точек, $n > 4$. Докажите, что можно соединить их стрелками так, чтобы из каждой точки в каждую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).
Подробнее
Теннисная федерация присвоила всем входящим в нее теннисистам квалификационные номера: сильнейшему - первый номер, следующему по силе - второй и т. д. Известно, что во встречах теннисистов, квалификационные номера которых различаются более, чем на 2, всегда побеждает спортсмен с меньшим номером. Турнир, в котором участвуют 1024 сильнейших теннисиста, проводится по олимпийской системе: участники очередного тура разбиваются по жребию на пары и в следующий тур выходит победитель в каждой паре, так что число участников после каждого тура уменьшается вдвое. Таким образом, после десятого тура будет выявлен победитель. Какой наибольший номер может он иметь?
Подробнее
На бесконечном клетчатом листе белой бумаги $n$ клеток закрашено в черный цвет. В моменты времени $t = 1, 2, \cdots$ происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка $k$ приобретает тот цвет, который имело в предыдущий момент большинство из трех клеток: самой клетки $k$ и ее соседей справа и сверху (если две или три из этих клеток были белыми, то $k$ становится белой, если две или три из них были черными - то черной), а) Докажите, что через конечное время на листе не останется черных клеток; б) Докажите, что черные клетки исчезнут не позже чем в момент времени $t = n$.
Подробнее
$N$ человек не знакомы между собой. Нужно так познакомить друг с другом некоторых из них, чтобы ни у каких трех людей не оказалось одинакового числа знакомых. Докажите, что это можно сделать при любом $N$.
Подробнее
Король обошел шахматную доску $8 \times 8$, побывав на каждом поле ровно один раз и вернувшись последним ходом на исходное поле (король ходит по обычным правилам). Когда нарисовали его путь, соединив отрезками центры полей, которые он последовательно проходил, то получилась замкнутая ломаная без самопересечений.
а) Приведите пример, показывающий, что король мог сделать ровно 28 ходов по горизонтали и вертикали.
б) Докажите, что он не мог сделать меньше, чем 28 таких ходов.
в) Какую наибольшую и какую наименьшую длину может иметь путь короля, если длина стороны клетки равна 1?
Подробнее
На карточках написаны числа, каждое из которых равно «+1» или «-1». Разрешается, указав три карточки, спросить: «Чему равно произведение чисел на этих карточках?» (сами числа нам не сообщают). Какое наименьшее число таких вопросов надо задать, чтобы узнать произведение чисел на всех карточках, если число карточек равно: а) 30; б) 31; в) 32? В каждом случае докажите, что меньшим числом вопросов обойтись нельзя.
г) По окружности написано 50 чисел, каждое из которых равно «+1» или «-1». Требуется узнать произведение всех этих чисел. За один вопрос можно узнать произведение трех стоящих подряд чисел. Какое наименьшее число вопросов необходимо задать?
Подробнее
Задано несколько красных и несколько синих точек. Некоторые из них соединены отрезками. Назовем точку «особой», если более половины из соединенных с ней точек имеют цвет, отличный от ее цвета. Особые точки разрешается перекрашивать: на каждом шагу выбирается любая особая точка и перекрашивается в другой цвет. Докажите, что через несколько шагов не останется ни одной особой точки.
Подробнее
На шахматной доске $8 \times 8$ двое играют в игру «кошки-мышки». У первого одна фишка - мышка, у второго несколько фишек - кошек. Все фишки ходят одинаково: вправо, влево, вверх или вниз на одну клетку. Если мышка оказалась на краю доски, то очередным ходом она спрыгивает с доски. Если
кошка и мышка попадают на одну и ту же клетку, то кошка съедает мышку.
Играющие ходят по очереди, причем второй передвигает своим ходом всех своих кошек сразу (разных кошек можно при этом сдвигать в разных направлениях). Начинает мышка. Она старается спрыгнуть с доски, а кошки стараются до этого ее съесть.
а) Пусть кошек всего две. Мышка уже поставлена на какую-то клетку не на краю. Можно ли так поставить кошек на краю доски, чтобы они сумели съесть мышку?
б) Пусть кошек три, но зато мышка имеет лишний ход: в первый раз она делает два хода подряд. Докажите, что мышка сможет убежать от кошек, каково бы ни было начальное расположение фишек.
Подробнее
Дан треугольник $ABC$ площади 1. Первый игрок выбирает точку $X$ на стороне $AB$, второй - $Y$ на стороне $BC$, затем первый - $Z$ на стороне $AC$. Цель первого - получить треугольник $XYZ$ наибольшей площади, второго - наименьшей. Какую наибольшую площадь может обеспечить себе первый?
Подробнее
Какой наименьший периметр может иметь выпуклый 32-угольник, все вершины которого лежат в узлах клетчатой бумаги со стороной клетки 1?
Подробнее
