Поиск задач
Ищите по условию, ответу и решению. Можно сузить поиск темой, сложностью и источником, а ввод одного числа — это поиск задачи по её номеру.
Найдено задач: 1597
У каждой из 100 девочек есть по 100 шариков; среди этих 10000 шариков есть по 100 шариков 100 различных цветов. Две девочки могут обменяться, передав друг другу по шарику. Они хотят добиться того, чтобы у каждой девочки было по 100 разноцветных шариков. Докажите, что они могут добиться этого такой серией обменов, чтобы любой шарик участвовал не более чем в одном обмене.
Ответ:
Решение:
В стране 998 городов. Некоторые пары городов соединены двусторонними авиарейсами. Согласно закону, между любой парой городов должно быть не больше одного рейса. Другой закон требует, чтобы для любой группы городов было не больше $5k+10$ рейсов, соединяющих два города этой группы, где $k$ — количество городов в группе. В настоящий момент законы соблюдены. Докажите, что министерство развития может ввести несколько новых рейсов так, чтобы законы по-прежнему соблюдались, а общее количество рейсов в стране стало равным 5 000.
Ответ:
Решение:
В стране $N$ городов. В ней действует $N(N-1)$ дорог с односторонним движением: по одной дороге из $X$ в $Y$ для каждой упорядоченной пары городов $X\ne Y$. У каждой дороги есть цена её обслуживания. Для данного $k=1,\ldots,N$ рассмотрим все способы выделить $k$ городов и $N-k$ дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём $k$-оптимальной. Докажите, что города можно пронумеровать от 1 до $N$ так, что при каждом $k=1,2,\ldots,N$ существует $k$-оптимальная система дорог с выделенными городами $1,2,\ldots,k$.
Ответ:
Решение:
В стране $2n$ городов ($n$ — натуральное), некоторые из них соединены двусторонними беспосадочными авиалиниями. Из любого города можно попасть в любой другой, возможно, с пересадками. Президент хочет разделить страну на две области и включить каждый город в одну из двух областей. При этом авиалинии разделятся на $k$ межобластных и $m$ внутриобластных. Докажите, что президент может добиться того, чтобы выполнялось неравенство $k-m\geqslant n$.
Ответ:
Решение:
На олимпиаду приехало несколько участников из $n\gt 1$ регионов, некоторые из них дружат (дружба всегда взаимна). Выяснилось, что для произвольной рассадки нескольких (хотя бы трёх) участников за круглым столом, при которой любые два соседа дружат, участников из каждого региона за столом окажется не более половины общего числа детей за столом. Докажите, что участников можно рассадить по $n$ кабинетам так, чтобы любые два друга оказались в разных кабинетах.
Ответ:
Решение:
Пятачок и Винни-Пух решили съесть квадратную шоколадку $7\times7$. Они поочерёдно по клеточкам выедают из неё кусочки: Пятачок — $1\times1$, Винни-Пух — $2\times1$ или $1\times2$ (кусочки можно выедать не обязательно с краю). Первый ход делает Пятачок. Если перед ходом Винни-Пуха в шоколадке не осталось ни одного кусочка $2\times1$ или $1\times2$, то вся оставшаяся шоколадка достаётся Пятачку. Кто из друзей сможет съесть больше половины всей шоколадки вне зависимости от действий второго?
Ответ:
Решение:
У Малыша и Карлсона есть длинная шоколадка $15\times100$. Они по очереди выедают из неё квадратные куски любого размера (куски можно выедать только по линиям сетки). Начинает Карлсон. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Ответ:
Решение:
Юра и Яша играют в следующую игру, делая ходы по очереди. Первым ходит Юра.
Изначально на доске написано число $n$. Игрок в свой ход может прибавить к числу на доске любой его натуральный делитель, стереть старое число и записать новое. (Например, если на доске написано число 12, то можно его стереть и написать одно из чисел 13, 14, 15, 16, 18, 24.)
Рассмотрим все возможные натуральные значения $n$ от 2 до 59 включительно.
1. Для скольких из них Юра имеет выигрышную стратегию, если проигрывает тот, кто получит после своего хода число, не меньшее 60?
2. Для скольких из них Юра имеет выигрышную стратегию, если побеждает тот, кто получит после своего хода число, не меньшее 60?
Изначально на доске написано число $n$. Игрок в свой ход может прибавить к числу на доске любой его натуральный делитель, стереть старое число и записать новое. (Например, если на доске написано число 12, то можно его стереть и написать одно из чисел 13, 14, 15, 16, 18, 24.)
Рассмотрим все возможные натуральные значения $n$ от 2 до 59 включительно.
1. Для скольких из них Юра имеет выигрышную стратегию, если проигрывает тот, кто получит после своего хода число, не меньшее 60?
2. Для скольких из них Юра имеет выигрышную стратегию, если побеждает тот, кто получит после своего хода число, не меньшее 60?
Ответ:
Решение:
Германн и Чекалинский разложили на столе 13 различных карт. Каждая карта может лежать в одном из двух положений: рубашкой вверх или рубашкой вниз. Игроки должны по очереди переворачивать по одной карте. Проигрывает тот игрок, после хода которого повторится какая-то из предыдущих ситуаций (включая изначальную). Первый ход сделал Чекалинский. Кто сможет выиграть независимо от того, как будет играть соперник?
Ответ:
Решение:
Есть две коробки, в одной 2017 конфет, а в другой 2018. Играют двое, ходят по очереди. За один ход каждый может съесть любое количество конфет, отличное от нуля, из любой коробки. Правила игры не допускают, чтобы после какого-то хода число конфет в одной из коробок делилось на число конфет в другой. Проигрывает тот, кто не может сделать ход, не нарушив этого условия. Кто сможет выиграть: начинающий игру или второй игрок, как бы ни играл его соперник?
Ответ:
Решение:
Двум мудрецам, А и Б, назначено испытание. Наутро их приведут в комнату, где на столе по кругу будут лежать шесть одинаковых с виду таблеток, из которых четыре безвредны, а две отравлены. Затем мудрецу А сообщат, какие таблетки отравлены, но передать информацию Б он уже не сможет. Мудрецы должны по очереди (начинает А) съедать по таблетке, пока не останется только две ядовитых. Как мудрецам заранее договориться, чтобы успешно пройти испытание?
Ответ:
Решение:
Коля и Дима играют в игру на доске $8\times8$, делая ходы по очереди, начинает Коля. Коля рисует в клетках крестики, а Дима накрывает прямоугольниками $1\times2$ (доминошками) пары соседних по стороне клеток доски. За свой ход Коля должен поставить один крестик в любую пустую клетку (т. е. в клетку, в которой ещё не нарисован крестик и которая ещё не покрыта доминошкой). Дима за свой ход должен накрыть доминошкой две клетки (ещё не накрытые другими доминошками), в которых суммарно чётное число крестиков (0 или 2). Проигрывает тот, кто не может сделать ход. Кто из игроков имеет выигрышную стратегию?
Ответ:
Решение:
Вася задумал восемь клеток шахматной доски, никакие две из которых не лежат в одной строке или в одном столбце. За ход Петя выставляет на доску восемь ладей, не бьющих друг друга, а затем Вася указывает все ладьи, стоящие на задуманных клетках. Если количество ладей, указанных Васей на этом ходе, чётно (то есть 0, 2, 4, 6 или 8), то Петя выигрывает; иначе все фигуры снимаются с доски и Петя делает следующий ход. За какое наименьшее число ходов Петя сможет гарантированно выиграть?
Ответ:
Решение:
Петя и Вася по очереди выписывают на доску натуральные числа, не превосходящие 2018 (выписывать уже имеющееся число запрещено); начинает Петя. Если после хода игрока на доске оказываются три числа, образующих арифметическую прогрессию, — этот игрок выигрывает. У кого из игроков есть стратегия, позволяющая ему гарантированно выиграть?
Ответ:
Решение:
На окружности отмечено 99 точек, делящих эту окружность на 99 равных дуг. Петя и Вася играют в игру, делая ходы по очереди. Первым ходит Петя; своим первым ходом он окрашивает в красный или синий цвет любую отмеченную точку. Затем каждый из игроков своим ходом может окрасить в красный или синий цвет любую неокрашенную отмеченную точку, соседнюю с уже окрашенной. Вася выигрывает, если после окрашивания всех точек найдётся равносторонний треугольник, все три вершины которого окрашены, причём в один и тот же цвет. Может ли Петя ему помешать?
Ответ:
Решение:
Коля и Дима играют в игру на доске $8\times8$, делая ходы по очереди, начинает Дима. Коля рисует в клетках крестики, а Дима накрывает прямоугольниками $1\times2$ (доминошками) пары соседних по стороне клеток доски. За свой ход Коля должен поставить один крестик в любую пустую клетку (т.е. в клетку, в которой ещё не нарисован крестик и которая ещё не покрыта доминошкой). Дима за свой ход должен накрыть доминошкой две соседних клетки (ещё не накрытые другими доминошками), в которых суммарно чётное число крестиков (0 или 2). Проигрывает тот, кто не может сделать ход. Кто из игроков имеет выигрышную стратегию?
Ответ:
Решение:
Два разбойника украли 300 золотых монет. Они решили поделить их следующим образом: первый разбойник кладёт в мешочек несколько монет (возможно, все), а второй разбойник выбирает, кому этот мешочек достанется; затем это действие повторяется ещё несколько раз. Делёж заканчивается, когда
- либо все деньги кончились,
- либо кому-нибудь досталось 11 мешочков — в этом случае все остальные деньги сразу же достаются другому разбойнику.
Ответ:
Решение:
Дана бесконечная клетчатая плоскость. Учительница и класс из 30 учеников играют в игру, делая ходы по очереди — сначала учительница, затем по очереди все ученики, затем снова учительница, и т. д. За один ход можно покрасить единичный отрезок, являющийся границей между двумя соседними клетками. Дважды красить отрезки нельзя. Учительница побеждает, если после хода одного из 31 игроков найдется клетчатый прямоугольник $1\times2$ или $2\times1$ такой, что у него вся граница покрашена, а единичный отрезок внутри него не покрашен. Смогут ли ученики помешать учительнице победить?
Ответ:
Решение:
Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?
Ответ:
Решение:
Есть поле, разделённое на две половины: левую и правую. Изначально на левой лежит $a$ камней, а на правой — $b$ камней. Юра и Яша играют в следующую игру, делая ходы по очереди. Первым ходит Юра.
Игрок в свой ход должен переложить с одной половины поля на другую один или несколько камней, причём больше, чем соперник переложил на предыдущем ходу (первым ходом можно переложить любое количество камней, большее 0). Проигрывает тот, кто не может сделать ход.
1. Какое наибольшее количество ходов может быть сделано в игре, если $a=7$ и $b=10$?
2. Рассмотрим все пары натуральных чисел $(a,b)$ такие, что $1\leqslant a\leqslant 10$ и $1\leqslant b\leqslant 10$. Для скольких из них Юра имеет выигрышную стратегию? (Если числа $a$ и $b$ различны, то пары $(a,b)$ и $(b,a)$ считаются различными.)
Игрок в свой ход должен переложить с одной половины поля на другую один или несколько камней, причём больше, чем соперник переложил на предыдущем ходу (первым ходом можно переложить любое количество камней, большее 0). Проигрывает тот, кто не может сделать ход.
1. Какое наибольшее количество ходов может быть сделано в игре, если $a=7$ и $b=10$?
2. Рассмотрим все пары натуральных чисел $(a,b)$ такие, что $1\leqslant a\leqslant 10$ и $1\leqslant b\leqslant 10$. Для скольких из них Юра имеет выигрышную стратегию? (Если числа $a$ и $b$ различны, то пары $(a,b)$ и $(b,a)$ считаются различными.)
Ответ:
Решение: