Выбрано 16 задач 
Убрать все задачи
Есть доска 1×1000, вначале пустая, и куча из n фишек. Двое ходят по очереди. Первый своим ходом "выставляет" на доску не более 17 фишек по одной на любое свободное поле (он может взять все 17 из кучи, а может часть – из кучи, а часть – переставить на доске). Второй снимает с доски любую серию фишек (серия – это несколько фишек, стоящих подряд, то есть без свободных полей между ними) и кладёт их обратно в кучу. Первый выигрывает, если ему удастся выставить все фишки в ряд без пробелов.
а) Докажите, что при n = 98 первый всегда может выиграть.
б) При каком наибольшем n первый всегда может выиграть?
Среди 20 школьников состоялся турнир по теннису. Каждый участник проводил каждый день по одной встрече; в итоге за 19 дней каждый сыграл ровно по одному разу со всеми остальными. Теннисный корт в школе один, поэтому матчи шли по очереди. Сразу после своего первого выигрыша в турнире участник получал фирменную майку. Ничьих в теннисе не бывает. Петя стал одиннадцатым участником, получившим майку, а Вася – пятнадцатым. Петя получил свою майку в одиннадцатый день турнира. А в какой день получил майку Вася?
Точка внутри выпуклого четырёхугольника соединена с вершинами. Получились четыре равных треугольника.
Верно ли, что четырёхугольник – ромб?
В остроугольном неравностороннем треугольнике отметили четыре точки: центры вписанной и описанной окружностей, точку пересечения медиан и ортоцентр. Затем сам треугольник стерли. Оказалось, что невозможно установить, какому центру соответствует каждая из отмеченных точек. Найдите углы треугольника.
Дан остроугольный треугольник ABC.
Найдите на сторонах BC, CA, AB такие точки A', B', C', чтобы наибольшая сторона треугольника A'B'C' была минимальна.
Существует ли неравнобедренный треугольник, у которого медиана, проведённая из одной вершины, биссектриса, проведённая из другой, и высота, проведённая из третьей, равны?
Раскрашенный в чёрный и белый цвета кубик с гранью в одну клетку поставили на одну из клеток шахматной доски и прокатили по ней так, что кубик побывал на каждой клетке ровно по одному разу. Можно ли так раскрасить кубик и так прокатить его по доске, чтобы каждый раз цвета клетки и соприкоснувшейся с ней грани совпадали?
a) Петя и Вася задумали по три натуральных числа. Петя для каждых двух своих чисел написал на доске их наибольший общий делитель. Вася для каждых двух из своих чисел написал на доске их наименьшее общее кратное. Оказалось, что Петя написал на доске те же числа, что и Вася (возможно в другом порядке). Докажите, что все написанные на доске числа равны.
б) Останется ли верным утверждение предыдущей задачи, если Петя и Вася изначально задумали по четыре натуральных числа?
Муравей ползает по замкнутому маршруту по рёбрам додекаэдра, нигде не разворачиваясь назад. Маршрут проходит ровно два раза по каждому ребру.
Докажите, что некоторое ребро муравей оба раза проходит в одном и том же направлении.
В стране несколько городов, некоторые пары городов соединены дорогами, причём между каждыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.
В турнире по теннису (где не бывает ничьих) участвовало более 4 спортсменов. Каждый игровой день каждый теннисист принимал участие ровно в одной игре. К завершению турнира каждый сыграл с каждым в точности один раз. Назовём игрока упорным, если он выиграл хотя бы один матч и после первой своей победы ни разу не проигрывал. Остальных игроков назовём неупорными. Верно ли, что игровых дней, когда была встреча между неупорными игроками, больше половины?
Внутри прямоугольного листа бумаги вырезали n прямоугольных дыр со сторонами, параллельными краям листа. На какое наименьшее число прямоугольных частей можно гарантированно разрезать этот дырявый лист? (Дыры не перекрываются и не соприкасаются.)
В неравнобедренном треугольнике ABC высота из вершины A, биссектриса из вершины B и медиана из вершины C пересекаются в одной точке K.
а) Какая из сторон треугольника средняя по величине?
б) Какой из отрезков AK, BK, CK средний по величине?
Петя прибавил к натуральному числу N натуральное число M и заметил, что сумма цифр у результата та же, что и у N. Тогда он снова прибавил M к результату, потом – ещё раз, и т. д. Обязательно ли он когда-нибудь снова получит число с той же суммой цифр, что и у N?
По доске $n$×$n$ прошла ладья, побывав в каждой клетке один раз, причем каждый её ход был ровно на одну клетку. Клетки занумерованы от 1 до $n^2$ в порядке прохождения ладьи. Пусть $M$ – максимальная разность между номерами соседних (по стороне) клеток. Каково наименьшее возможное значение $M$?
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
|
|
 |
Условие
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение
Рассмотрим граф с вершинами в городах, рёбра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более N нечётных циклов.
Докажем индукцией по количеству вершин, что вершины такого графа можно
покрасить в N + 2 цвета так, чтобы никакие две вершины одного цвета не были соединены ребром.
База для графа из одной вершины очевидна.
Шаг индукции. Пусть утверждение верно для графа, в котором менее k вершин. Рассмотрим граф G с k вершинами, в котором через каждую вершину проходит не более N нечётных циклов. Удалив из этого графа любую вершину A и все выходящие из неё рёбра, мы получим граф H с k – 1 вершиной. Очевидно, через каждую вершину графа H проходит не более N циклов нечётной длины.
Тогда покрасим вершины графа H в N + 2 цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).
Для цвета k (2 ≤ k ≤ N + 2) рассмотрим граф H1k из всех вершин графа H, покрашенных в цвета 1 и k, и всех проведённых между ними рёбер графа G. Поскольку никакие две вершины одинакового цвета в графе H1k не соединены ребром, то в этом графе нет циклов нечётной
длины. Построим граф G1k, добавив к графу H1k вершину A и все выходящие из неё к вершинам H1k рёбра.
Если для некоторого k в графе G1k через
вершину A не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае несложно доказать (см. лемму к задаче 110038), что мы можем так перекрасить вершины графа G1k (используя лишь цвета 1 и k), что все рёбра в этом графе будут соединять пары вершин разных цветов. Так как все остальные вершины графа G покрашены в цвета, отличные от 1 и k, то и во всём графе G никакие две вершины одинакового цвета не соединены ребром.
Остаётся рассмотреть случай, когда для каждого k (2 ≤ k ≤ N + 2) в графе G1k через вершину A проходит хотя бы один цикл нечётной длины.
Заметим, что такой нечётный цикл проходит только по вершинам цветов 1 и k, причём среди них есть хотя бы одна вершина цвета k. Следовательно, через вершину A проходит хотя бы N + 1 цикл нечётной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.
