Выбрано 10 задач 
Убрать все задачи
Есть доска 1×1000, вначале пустая, и куча из n фишек. Двое ходят по очереди. Первый своим ходом "выставляет" на доску не более 17 фишек по одной на любое свободное поле (он может взять все 17 из кучи, а может часть – из кучи, а часть – переставить на доске). Второй снимает с доски любую серию фишек (серия – это несколько фишек, стоящих подряд, то есть без свободных полей между ними) и кладёт их обратно в кучу. Первый выигрывает, если ему удастся выставить все фишки в ряд без пробелов.
а) Докажите, что при n = 98 первый всегда может выиграть.
б) При каком наибольшем n первый всегда может выиграть?
Среди 20 школьников состоялся турнир по теннису. Каждый участник проводил каждый день по одной встрече; в итоге за 19 дней каждый сыграл ровно по одному разу со всеми остальными. Теннисный корт в школе один, поэтому матчи шли по очереди. Сразу после своего первого выигрыша в турнире участник получал фирменную майку. Ничьих в теннисе не бывает. Петя стал одиннадцатым участником, получившим майку, а Вася – пятнадцатым. Петя получил свою майку в одиннадцатый день турнира. А в какой день получил майку Вася?
Точка внутри выпуклого четырёхугольника соединена с вершинами. Получились четыре равных треугольника.
Верно ли, что четырёхугольник – ромб?
В остроугольном неравностороннем треугольнике отметили четыре точки: центры вписанной и описанной окружностей, точку пересечения медиан и ортоцентр. Затем сам треугольник стерли. Оказалось, что невозможно установить, какому центру соответствует каждая из отмеченных точек. Найдите углы треугольника.
Дан остроугольный треугольник ABC.
Найдите на сторонах BC, CA, AB такие точки A', B', C', чтобы наибольшая сторона треугольника A'B'C' была минимальна.
Существует ли неравнобедренный треугольник, у которого медиана, проведённая из одной вершины, биссектриса, проведённая из другой, и высота, проведённая из третьей, равны?
Раскрашенный в чёрный и белый цвета кубик с гранью в одну клетку поставили на одну из клеток шахматной доски и прокатили по ней так, что кубик побывал на каждой клетке ровно по одному разу. Можно ли так раскрасить кубик и так прокатить его по доске, чтобы каждый раз цвета клетки и соприкоснувшейся с ней грани совпадали?
a) Петя и Вася задумали по три натуральных числа. Петя для каждых двух своих чисел написал на доске их наибольший общий делитель. Вася для каждых двух из своих чисел написал на доске их наименьшее общее кратное. Оказалось, что Петя написал на доске те же числа, что и Вася (возможно в другом порядке). Докажите, что все написанные на доске числа равны.
б) Останется ли верным утверждение предыдущей задачи, если Петя и Вася изначально задумали по четыре натуральных числа?
Муравей ползает по замкнутому маршруту по рёбрам додекаэдра, нигде не разворачиваясь назад. Маршрут проходит ровно два раза по каждому ребру.
Докажите, что некоторое ребро муравей оба раза проходит в одном и том же направлении.
В стране несколько городов, некоторые пары городов соединены дорогами, причём между каждыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.
|
|
 |
Условие
В стране несколько городов, некоторые пары городов соединены дорогами, причём между каждыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.
Решение
Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам. В этом графе между каждыми двумя вершинами есть единственный путь, следовательно, в нем нет циклов (дерево). По условию, в этом графе есть 100 вершин, из которых выходит ровно одно ребро (висячие вершины) – пусть это вершины A1, A2, ..., A100.
Для каждой пары висячих вершин Ai и Aj существует единственный путь между ними, назовём количество рёбер на этом пути расстоянием между этими вершинами и будем обозначать через d(Ai, Aj).
Из конечности числа способов разбить эти 100 вершин на 50 пар следует,
что при одном из способов достигается максимум суммы расстояний между вершинами
в парах. Соединим пары вершин при этом разбиении 50 новыми рёбрами
(остальные рёбра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа.
Предположим противное, пусть при удалении ребра между вершинами B и C граф распался на две компоненты. Ясно, что удалённое ребро было старым, а вершины B и C принадлежат разным компонентам. В каждой части должна быть вершина, из которой выходит ровно одно старое ребро, а каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины Ai и Aj, а в другой – соединяющее вершины Ak и Am. Пути l и L, соединяющие соотвественно Ai с Ak и Aj с Am, должны содержать ребро BC. Следовательно, путь из Ai в Aj состоит из участка пути l, соединяющего Ai с B, и участка пути L, соединяющего B с Aj. Аналогично путь из Ak в Am проходит через точку C. Таким образом, d(Ai, Aj) + d(Ak, Am) = d(Ai, Ak) + d(Aj, Am) – 2, что противоречит максимальности суммы расстояний в выбранных парах.
