Ошибка.
Попробуйте повторить позже
Аня и Боря играют в игру. Они по очереди (начинает Аня) выписывают по одной цифре, пока не получится шестизначное число. При этом первая выписанная цифра ненулевая и все выписанные цифры различны. Аня выигрывает, если полученное шестизначное число делится хотя бы на одно из чисел: 2,3 или 5. Если этого не случается, то выигрывает Боря. Кто выигрывает при правильной игре?
Источники:
Подсказка 1
Подумаем, какие цифры и на какой позиции могли бы принести Боре победу? Что нужно сделать Ане, чтобы предотвратить это?
Подсказка 2
Если на третий ход Бори оставить ему числа 0, 2, 4, 5, 6, 8, то он проиграет. Значит, если Боря хочет победить, то в свой последний ход он подставит одно из числе 1, 3, 7, 9. Какие еще вынужденные ходы можно приписать Боре?
Подсказка 3
Заметим, что чисел 1, 3, 7, 9 не так уж и много, значит Боря не должен их «закончить» раньше своего третьего хода. Тогда какие цифры он должен ставить в своих ходы?
Подсказка 4
Выходит, что Боря в свои первый и второй ходы должен ставить цифры из {0, 2, 4, 5, 6, 8}. Тогда какие цифры должна поставить Аня, чтобы Боря не смог победить в конце?
Подсказка 5
Аня своим первым и вторым ходом поставит 3 и 9. Осталось лишь разобрать случаи того, какие именно ходы сделает Боря! Подумайте, а как должна поступить Аня вторым ходом, чтобы застать Борю врасплох?
Подсказка 6
Обратите внимание на остатки чисел при делении на 3!
Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 2 . Значит, .
Пусть Аня первым ходом выберет цифру , а вторым ходом - цифру 9. Если Боря на первом или втором ходу выберет цифру из множества , то своим третьим ходом Аня заберет последнюю оставшуюся цифру из множества , и Боря вынужден будет взять свою цифру из , что приведет к его проигрышу. Значит, Боря вынужден взять первые две свои цифры и взяты из множества . Заметим, что Боря вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Ане достаточно подобрать цифру так, чтобы сумма цифр давала бы остаток 2 при делении на 3 . Поскольку и не влияют на остаток этой суммы, все зависит от остатка суммы . Покажем, как действовать Ане в каждом из случаев.
Если делится на 3 , то Аня выберет цифру из набора : поскольку до этого момента эти цифры мог выбирать только Боря, как минимум одна из этих трех цифр останется не выбранной.
Если дает остаток 1 при делении на 3 , Аня выберет цифру . Как мы помним, Боря не мог ее выбрать на первых двух ходах.
Наконец, если дает остаток 2 при делении на 3 , Аня выберет цифру из набора . Боря не мог выбрать обе эти цифры, поскольку тогда , а мы предположили, что дает остаток 2 при делении на 3 .
Таким образом, Аня выиграет.
Аня
Ошибка.
Попробуйте повторить позже
Имеется кучка из 100 камней. Двое играют в следующую игру. Первый игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый может забрать 1,2 или 3 камня, затем второй или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?
Подсказка 1
Давайте внимательно посмотрим на то, какое количество камней всегда может набрать первый игрок, после хода второго. Что можно заметить?
Подсказка 2
Первым ходом первый игрок всегда забирает ровно один камень, поэтому тут не очень интересно. А вот дальше второй игрок забирает один или два камня, а первый от 1 до 3 камней. Какое число камней можно набрать после хода второго и первого вместе?
Подсказка 3
Ровно 3 камня, на следующем ходе 5 камней, дальше 7 и так далее. То есть после хода первого получаются последовательные нечётные числа. А разность чего равняется последовательным нечётным числам?
Подсказка 4
Разность квадратов — это нечётное число. Поэтому, так как первым ходом первый игрок забирает 1 камень, то есть квадрат. А это значит, что после каждого его хода забирается такое количество камней, которое равно квадрату натурального числа!
Докажем, что для любого натурального первый игрок на своём -ом ходе может добиться, чтобы количество забранных из кучки камней равнялось , и второй игрок не сможет ему помешать. Доказательство проведём индуктивно.
В свой первый ход первый игрок забирает один камень, т. е. число забранных камней равно . Пусть в свой -й ход первому игроку удалось сделать так, чтобы количество забранных камней равнялось . В свой -й ход второй игрок может взять от до камней. Поскольку после его хода общее количество забранных камней будет больше и меньше . Первый игрок в свой следующий ход может взять от до камня и точно сможет получить забранных камней независимо от предыдущего хода второго игрока.
Таким образом, поскольку , побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём ходе он возьмёт последний камень.
Ошибка.
Попробуйте повторить позже
На столе лежат кучек по одному ореху в каждой Двое ходят по очереди. За ход нужно выбрать две кучки, где числа орехов взаимно просты, и объединить эти кучки в одну. Выиграет тот, кто сделает последний ход. Для каждого выясните, кто из играющих может всегда выигрывать, как бы ни играл его противник.
Для выигрыша ему достаточно до самого конца объединять имеющиеся кучки так, чтобы была одна большая кучка и несколько кучек по одному ореху. При такой стратегии сохраняется инвариант — нечетность максимальной кучки после хода второго. В случае нечётного второй придерживается такой стратегии до конца, а в случае чётного — до позиции из четырёх кучек и после чего на любой ход первого: или — отвечает ходом
Всегда выигрывает второй
Ошибка.
Попробуйте повторить позже
Даны две кучки спичек. В одной в другой спичек. Двое играют в следующую игру: при своем ходе каждый выбрасывает одну из двух кучек, а другую делит на две не обязательно равные кучки. Проигравшим считается тот, кто не может разделить кучку на две части. Кто может выиграть при правильной игре?
Игра конечна, следовательно, у одного из игроков есть выигрышная стратегия. Докажем, что у второго не может быть выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом выбросим кучку а вторую разделим на и Второй игрок обязательно выбросит кучку и разделит как-то кучку С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом выбросим кучку и разделим кучку так же, как и второй игрок разделил бы ее в соответствии со своей выигрышной стратегией. Теперь будем отвечать на ходы второго по его же стратегии и победим. Значит, у первого тоже есть выигрышная стратегия. Противоречие.
Доказали, что первый игрок имеет выигрышную стратегию.
Первый
Ошибка.
Попробуйте повторить позже
У Саши есть 10 карточек с числами . Он пишет на доске число 0 и предлагает Диме сыграть в игру. Дима своим ходом называет целое число , это число может быть разным от раунда к раунду. Саша выбирает карточек, перед которыми ставит знак «+», а перед остальными карточками ставит знак «-». Результат вычисляется и прибавляется к числу на доске. Какой наибольший по модулю результат через несколько раундов может получить Дима, как бы ни действовал Саша?
Сначала докажем, что Саша может всегда получать результат из отрезка . Будем считать, что текущее число на доске неположительно (в противном случае можно заменить все знаки в рассуждениях на противоположные). Разберем два случая для числа , называемым Димой на очередном раунде.
Случай 1. Пусть .
Тогда поставим знаки так: , а остальные знаки расставим произвольным образом. Так как , результат будет положительным, и число на доске не станет меньше -256. С другой стороны, результат не превосходит , значит, число на доске не станет больше 256.
Случай 2. Пусть .
Если текущее число на доске не равно -256 , Саша может поставить знак минус перед числом 512 и плюсы перед остальными знаками. Результат после вычислений будет равен -1 , поэтому число на доске останется на отрезке . Если же текущее число на доске равно - 256, Саша может поставить знак минус перед числом 256 и плюсы перед остальными знаками. Результат вычислений будет равен 511, поэтому следующее число на доске будет равно 255 за пределы отрезка Саша не вышел.
Теперь докажем, что Дима может добиться результата 256. Будем называть всегда . Если Саша ставит плюс перед числом 512 , результат вычислений будет равен +1 , и число на доске увеличится. Чтобы не допустить появления числа, превосходящего 255, Саше нужно в какой-то момент поставить знак плюс перед другим числом. В такой ситуации результат вычисления отрицательный и по модулю не меньше . Поэтому следующее число на доске не больше, чем , и Дима добился желаемого результата.
Ошибка.
Попробуйте повторить позже
Паша и Вова играют в игру, по очереди зачеркивая клетки доски . Исходно на доске зачеркнута только центральная клетка. За один ход игрок должен выбрать диагональ (в диагонали может быть 1, 2 или 3 клетки) и зачеркнуть в ней все еще не зачеркнутые клетки. Каждым ходом должна быть зачеркнута хотя бы одна новая клетка. Проигрывает тот, кто не может сделать ход. Начинает Паша. Кто из игроков может выиграть вне зависимости от ходов противника?
Источники:
Приведем одну из возможных стратегий за Вову. Покрасим клетки доски в шахматном порядке так, чтобы угловые клетки были черными. В нечетных столбцах крайние клетки будут черными, а в четных белыми. Центральная клетка находится в 51-м столбце, поэтому она сама будет белой.
Каждая диагональ либо полностью черная, либо полностью белая. Обе стратегии будут симметричными, но разными для разных цветов. Для клеток белого цвета будем ходить симметрично относительно центрального столбца (осевая симметрия). Для черных клеток будем ходить симметрично относительно центральной клетки (центральная симметрия).
Докажем, что Вова всегда сможет сделать ход согласно стратегии. Для этого нужно убедиться, что своим ходом он будет зачеркивать хотя бы одну новую клетку. Для черных клеток две диагонали выбранная Пашей и центрально-симметричная ей, выбранная Вовой не имеют общих клеток. При этом Паша смог сделать ход, значит, на выбранной им диагонали была незачеркнутая клетка. Так как до хода Паши ситуация для черных клеток была центрально-симметричной, на Вовиной диагонали перед ходом Паши тоже была незачеркнутая клетка. Паша не мог ее зачеркнуть, значит, Вова своим ходом зачеркнет хотя бы одну новую клетку.
Для белых клеток ситуация несколько иная: две диагонали, проходящие через центральную клетку, симметричны относительно центрального столбца, но других симметричных белых диагоналей на доске нет. Опять же, перед ходом Паши ситуация на белых клетках осе-симметрична, то есть и на диагонали, выбираемой сейчас Пашей, и на диагонали, выбранной по стратегии Вовой, есть незачеркнутые клетки. Но единственная общая клетка, которую могут иметь осе-симметричные белые диагонали, зачеркнута с самого начала, поэтому Паша не может своим ходом зачеркнуть незачеркнутую клетку с Вовиной диагонали. Таким образом, Вова своим ходом зачеркнет хотя бы одну новую клетку.
Итак, мы доказали, что у Вовы всегда есть ход согласно стратегии. Так как ходов конечно (игра закончится не позже, чем через хода, когда точно будут зачеркнуты все клетки), Вова победит.
Ошибка.
Попробуйте повторить позже
На бесконечной шахматной доске стоят ферзь и невидимый король. Известно, что ферзь дал шах по горизонтали, и король ушел из под шаха. Докажите, что ферзь может ходить так, чтобы король наверняка еще раз попал под шах.
Введем нумерацию горизонталей: пусть строка шахматной доски, на которой находится ферзь вначале будет -ой. Над горизонталью с ферзем - горизонтали, а под ней
Если король ушел из под шаха, то он находится либо на -ой, либо на -ой горизонтали.
Пусть первым ходом ферзь сходит на одну клетку вверх. Либо король попадет под шах, либо он был на горизонтали с номером а после своего хода может находиться только на -ой, -ой, или -ой строчке.
Назовем “шагом вправо” следующие два подряд хода ферзя: По диагонали вправо-вниз на три клетки; (после такого хода либо король попадает под шах, либо после своего хода может находиться только на -ой, -ой, или -ой строчке.) На три клетки вверх; (либо король попадает под шах, либо после своего хода находится только на -ой, -ой, или -ой строчке.)
Аналогично “шаг влево”: По диагонали влево-вниз на три клетки; На три клетки вверх;
Заметим, что когда ферзь делает “шаг влево” или “шаг вправо”, он сдвигается на клетки вправо или влево. Также король всегда должен находится на полосе из и -ой горизонтали, иначе попадет под шах. И также можно заметить, что за один “шаг” король будет атакован, если он находился между вертикалями начальной и конечной позиции “шага”. То есть задача сводится к тому, что нужно доказать, что ферзь сможет догнать короля “шагами влево и вправо”, если за один “шаг” ферзь перемещается на клетки по горизонтали, а король максимум на клетки по горизонтали.
Но это утверждение уже легко доказать: отправим мысленно в обе стороны две вспомогательные фигуры, перемещающиеся со скоростью клетки за “шаг”. Пусть ферзь догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит короля, а значит, и ферзь когда-то догонит короля, то есть король когда-то будет под шахом.
Ошибка.
Попробуйте повторить позже
Состав из конечного числа одинаковых вагонов замкнут в кольцо. Вас с куском мела поместили в один из вагонов. Вы можете свободно ходить по составу и делать любые пометки на стенах вагонов. В любой момент вы можете сказать, сколько вагонов в поезде. Если угадаете, то Вас выпустят. Учтите, однако, что до Вас уже многие пытались пройти это испытание. Возможно, они оставляли на стенах какие-то пометки. Опишите алгоритм, который точно поможет спастись.
Пометим вагон, в котором мы оказались какой-нибудь отметкой. Пройдемся по часовой стрелке по составу до тех пор, пока не наткнемся на похожую на нашу пометку, после этого сотрем ее (или зачеркнем), запомним количество вагонов, пройденных от стартовой позиции, и вернемся в начальный вагон, двигаясь против часовой стрелки. Если там пометка оказалась стертой, то мы прошли полный круг и знаем длину состава. Иначе повторим операцию. Вагонов конечное число, поэтому рано или поздно мы сотрем метку в стартовом вагоне и узнаем длину состава.
Ошибка.
Попробуйте повторить позже
Иван Царевич хочет выйти из круглой комнаты с дверями, из которых заперты на ключ. За одну попытку он может проверить любые три двери, расположенные подряд, и если одна из них не заперта, то он в неё выйдет. После каждой попытки Баба-Яга запирает дверь, которая была открыта, и отпирает одну из соседних дверей. Какую именно, Иван Царевич не знает. Как ему действовать, чтобы наверняка выйти из комнаты?
Занумеруем двери числами например, по часовой стрелке. Пусть он будет рассматривать двери с номерами для
Первой попыткой Иван Царевич проверяет двери и Если после этого он не сумел выйти из комнаты, то двери и были заперты. Дверь останется запертой даже после того, как Баба-Яга запрёт открытую и отопрёт одну из соседних.
Второй попыткой Иван Царевич проверяет двери и Если после этого он не сумел выйти из комнаты, то двери были заперты, а с учетом того, что тоже заперта, можно утверждать, что двери и останутся запертыми и после действий Бабы-Яги.
Пусть на шаге он открывает двери с номерами И пусть ему известно, что дверей с номерами точно были закрыты перед его ходом. Тогда после проверки дверей Иваном Царевичем и действий Бабы Яги мы будем знать, что дверей с номерами точно заперты, потому что перед ходом Бабы Яги были заперты соседние к ним двери.
Тогда не более, чем за шагов Иван будет знать все запертые двери и сможет выбрать открытую.
Ошибка.
Попробуйте повторить позже
Дима загадал целое число, а Петя пытается его угадать. На каждом шаге он выбирает целое число и задает Диме вопрос: «Верно ли, что загаданное число равно ?».
(a) Если Петя не угадал, то Дима обязан перезагадать свое число, увеличив его на
(b) Если Петя не угадал, то Дима сообщает Пете, больше или меньше загаданное число, чем а затем обязан перезагадать свое число, либо увеличив его на либо уменьшив его на (Петя не знает, какой из этих двух вариантов выберет Дима).
Может ли Петя действовать так, чтобы через несколько шагов гарантированно угадать текущее загаданное число?
(a) Пусть Дима загадал значение — , а Петя задаст вопросы следующего вида: «Верно ли, что загаданное число равно ?», где — какое-то число, — сумма чисел из предыдущих вопросов. По условию Дима увеличивал свое значение на число из вопроса Пети, если Петя не угадал, поэтому Петин вопрос вида: «Верно ли, что загаданное число равно ?» — по смыслу эквивалентен вопросу: «»
Переберем значения в следующем порядке:
То есть первые несколько вопросов выглядят так:
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
Тогда Петя рано или поздно выберет значение равное изначально загаданному и, спросив «Верно ли, что загаданное число равно » угадает текущее число.
(b) Пусть Петя сначала задаст вопрос, который не изменит числа: «Верно ли, что загаданное число равно ?» Либо он угадает, либо сможет узнать знак загаданного числа. Без ограничения общности далее считаем, что загаданное число положительное, иначе задаем следующие вопросы с противоположным знаком. (И также будем считать - что если Петя угадал число в какой-то момент, то он автоматически выиграл.)
Теперь пусть Петя задает вопросы вида:
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
…
«Верно ли, что загаданное число равно ?»
Если Дима ответит, что загаданное число в данный момент то после вычитания или прибавления к числа новое число также будет строго положительным.
Петя будет задавать вопросы до тех пор, пока впервые не получит ответ, что в данный момент загаданное число Заметим, что такой момент наступит, потому что то есть как минимум на шаг с номером где — изначальное загаданное число, Дима ответит отрицательно на этот вопрос, так как каждый раз число увеличивалось максимум — на сумму чисел во всех предыдущих вопросах.
Перед последним вопросом загаданное число будет лежать в границах то есть после изменения на оно не превосходит по модулю числа
Пусть Петя задаст вопрос: «Верно ли, что загаданное число равно ?» И тем самым поймет знак загаданного числа в данный момент.
То есть теперь нам известны знак и границы, в которых лежит текущее загаданное число.
После этого, пока не угадаем число, будем задавать вопросы:
«Верно ли, что загаданное число равно ?», где — текущее максимальное по модулю значение для загаданного числа (может
быть как положительным, так и отрицательным числом)
«Верно ли, что загаданное число равно ?»
После первого вопроса (про ) мы либо угадали число, либо "потенциальные числа"теперь изменили знак (то есть Дима вычел из загаданного), либо сохранили знак (Дима прибавил к загаданному числу). Следующий вопрос определяет прибавили или вычли и тогда мы снова знаем границы для загаданного числа, но теперь "потенциальных значений"на одно меньше. Значит, такими вопросами число рано или поздно будет угадано.
Ошибка.
Попробуйте повторить позже
На бесконечном шоссе находятся полицейская машина (ездит со скоростью до км/ч) и вор на угнанном мотоцикле (ездит со скоростью до км/ч). Полицейские не знают, в каком месте шоссе находится вор. Как им действовать, чтобы наверняка догнать вора? (Вор не может съехать с шоссе или спрятаться).
Отправим мысленно в обе стороны дороги двух помощников, едущих со скоростью большей, чем скорость вора, но меньшей, чем скорость полицейской машины. Пусть полицейская машина догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит угонщика, а значит, и полицейский когда-то догонит угонщика.
Ошибка.
Попробуйте повторить позже
Кащей и Василиса играют в игру. Изначально пять одинаковых пустых вёдер ёмкостью стоят по кругу. За ход Кащей берёт изо рва литр воды и распределяет его по вёдрам как ему заблагорассудится, а затем Василиса опустошает любые два соседних ведра. Кащей выигрывает, если после какого-то его хода хотя бы одно из вёдер переполнится. При каких Василиса может не допустить этого?
Сначала покажем, что при емкости вёдер Кащей сможет добиться того, что ведро будет переполнено. Если то Кощею достаточно литр поместить в одно какое-то ведро.
Иначе пусть где и пусть ведра пронумерованы по кругу: соответственно. Тогда пусть Кощей наливает в первое ведро а в третье литров воды.
Василиса может опустошить только одно из ведер: либо первое, либо третье, потому что они не стоят рядом. Дальше будет действовать следующим образом: если Василиса не опустошает первое ведро, то пусть Кащей просто дольет в первое ведро литр и в нем станет поэтому это ведро переполнится. Иначе Василиса опустошила первое ведро, но тогда третье ведро осталось заполненным. Пусть Кощей также наливает в первое ведро , а в третье литров воды до того момента, когда либо Василиса не опустошает первое ведро (тогда Кощей доливает в первое ведро литр и побеждает), либо в третьем ведре станет где — число раз, когда Василиса не опустошала третье ведро.
В случае же Василиса сможет не допустить победы Кащея. Пусть она будет действовать следующим образом: сначала опустошает ведро, потом ведро, потом потом потом и так далее по кругу. Тогда каждое ведро не опустошается не более, чем хода Кащея, то есть в каждом ведре может быть налито Кащеем за хода максимум литра, после чего оно опустошается. Значит, что ни одно из ведер не переполнится. И Василиса побеждает.
При
Ошибка.
Попробуйте повторить позже
На столе лежат карточек с номерами от до каждый номер встречается по разу. Двое по очереди забирают себе по карточке со стола. Если в какой-то момент один из игроков собрал карточки с суммой то он победил. Иначе объявляется ничья. Есть ли у какого-нибудь из игроков выигрышная стратегия?
Разместим все карточки в квадрате как показано на рисунке (составляем так называемый магический квадрат). Заметим, что игрок выиграл тогда и только тогда, когда он первый забирает себе целый столбец, целую строку либо целую диагональ (сумма чисел на вертикалях, горизонталях и диагоналях магического квадрата постоянна, в нашем случае — ). Будем отмечать карточки, которые забирает -ый игрок крестиками, а карточки второго — ноликами. Наша игра свелась в игру в крестики-нолики. Но, как известно, при правильной игре в крестики-нолики, ни у кого нет выигрышной стратегии.
Ни у кого
Ошибка.
Попробуйте повторить позже
Сяо расставляет на ребрах двух одинаковых кубов стрелочки, потом Бяо совмещает кубы. Сяо выигрывает, если совпало меньше половины стрелок, Бяо если больше, иначе ничья. Кто выигрывает при правильной игре?
Докажем, что Сяо может расставить на ребрах двух кубов стрелочки так, чтобы вне зависимости от действий Бяо совпала ровно половина стрелочек. Сначала покажем построение на первом кубе. Выделим одну вершину на кубе – скажем, верхний правый угол на верхней грани. Расставим стрелки на ребрах так, чтобы они образовывали поток из этой вершины в диаметрально противоположную. Теперь рассмотрим второй куб. Выделим в нем ту же вершину, сделаем все ребра исходящими из нее. Для каждой из трех смежных с ней вершин сделаем все ребра входящими в нее. Для диаметрально противоположной вершины наоборот сделаем все ребра входящими в нее. Тогда для всех вершин, смежных с диаметрально противоположной, все ребра являются исходящими.
Отметим, что каждая вершина второго куба такова, что либо все ребра из нее исходят, либо все входят. Более того, если в некоторую вершину ребра входят, значит из каждой соседней вершины ребра выходят, и наоборот. Это значит, что результатом любого вращения второго куба может быть только один из двух вариантов расстановки стрелочек: исходный, и такой, который получается из исходного заменой всех стрелочек на противоположные. Первый вариант получается всегда, когда из верхнего правого угла верхней грани ребра исходят, а второй – когда наоборот входят. И нетрудно видеть, что для каждого варианта ровно из стрелочек совпадают с расстановкой на первом кубе.
Теперь докажем, что Бяо может всегда действовать так, чтобы после поворота второго кубика совпало хотя бы ребер. Выделим произвольное ребро на первом кубе. Отметим, что второй куб всегда можно повернуть так, чтобы направление на этом ребре у них совпало. Действительно, возможно, оно у них и так совпадает, и поворот не требуется. Иначе, выделим произвольную грань, которой принадлежит это ребро, и рассмотрим композицию поворота на относительно оси, перпендикулярной этой грани, и на относительно оси, параллельной этой грани. Первый поворот переводит ребро в противоположное на выбранной грани, а второй – наоборот, переводит противоположное ребро в исходное. В результате этих двух поворотов получилась расстановка стрелочек, в которой направление выбранного ребра поменялось. Это означает, что из всех способов поворота второго куба ровно у половины направление на выделенном ребре совпадает с направлением на первом кубе, и ровно у половины – нет. Действительно, композиция поворота на относительно оси, параллельной фиксированной грани, и поворота на относительно оси, перпендикулярной этой грани, является обратным преобразованием к композиции выше. Поэтому композиция поворотов выше является взаимно однозначным соответствием, и разбивает все повороты второго куба на пары, в каждой из которых у одного поворота направление на фиксированном ребре совпадает с первым кубом, а у другого – нет.
Рассмотрим всевозможные варианты расстановок стрелочек, полученные поворотом второго куба. Обозначим их количество как Просуммируем по всем ним количество совпадающих по направлению ребер с ребрами первого куба. По доказанному выше ясно, что получится число так как для каждого из ребер ровно половина из расстановок совпадает с первым кубом по направлению этого ребра. Тогда, по принципу Дирихле, существует расстановка, в которой с первым кубом совпадает по направлению хотя бы ребер. Бяо достаточно вернуть эту расстановку.
Поскольку у каждого игрока существует стратегия, по которой он не проигрывает, результатом может стать только ничья.
Никто
Ошибка.
Попробуйте повторить позже
По кругу расположены луночек, одна из которых отмечена. Петя и Вася играют в следующую игру. В начале игры Вася кладет шарик в одну из луночек. Далее за каждый ход Петя называет натуральные число (числа могут отличаться на разных ходах), а Вася перемещает шарик из луночки, в которой он находится, на луночек по часовой либо против часовой стрелки на свой выбор. Сможет ли Петя играть так, чтобы через несколько ходов шарик гарантированно попал в отмеченную луночку?
Приведём стратегию. Занумеруем луночки по часовой стрелке числами от до так, что номер имеет отмеченная луночка. Если шарик находится в луночке номер он называет число Если Вася сдвинет шарик против часовой стрелки, то он немедленно попадет в отмеченную луночку. Значит, он вынужден сдвинуть шарик по часовой стрелке, то есть в луночку номер где Так как делится на то четно. Таким образом, после первого шага шарик обязательно находится в луночке с четным номером. Аналогично, на следующем шаге номер луночки будет обязательно делиться на и так далее. Поэтому не позже чем на -м шаге номер луночки будет делиться на а такая луночка только одна — отмеченная.
Да, сможет
Ошибка.
Попробуйте повторить позже
По кругу стоит блюдце, на каждом по конфете. Сначала Малыш выбирает натуральное , затем Карлсон — натуральное . Малыш берет конфету с любого блюдца. Отсчитав от этого блюдца -е блюдце по часовой стрелке, берет с него конфету Карлсон. Отсчитав уже от этого блюдца -е блюдце по часовой стрелке, берет с него конфету Малыш (если она там еще есть). Отсчитав от блюдца Малыша -е блюдце по часовой стрелке, берет с него конфету Карлсон (если она там еще есть), и т.д. Какое наибольшее число конфет может себе гарантировать Карлсон, как бы ни играл Малыш?
Стратегия Карлсона будет взять число если если Можно считать, что Карлсон отсчитывает в сторону против часовой стрелки. Пронумеруем блюдца с помощью их остатков по модулю против часовой стрелки, то есть начиная с первого выбранного Малышом. Тогда Малыш получит блюдца при этом Карлсон получает номера то есть забирает у Малыша все блюдца, кроме первых двух. Остаётся заметить, что — простое число, поэтому в последовательности Малыша и, Карлсона все тарелки будут различны. Отсюда Карлсон получит все тарелки, кроме двух, то есть Нетрудно убедиться, что меньше 2 конфет Малыш не получит, иначе тогда Карлсон получит ровно конфету.
Ошибка.
Попробуйте повторить позже
Коля и Саша играют в игру на клетчатой доске Коля начинает и своим ходом красит одну клетку в красный цвет, а Саша — в синий. Ходят по очереди, перекрашивать ранее закрашенные клетки нельзя. В конце игры Коля ищет красный клетчатый прямоугольник наибольшей площади, и Саша платит ему столько рублей, сколько в этом прямоугольнике клеток. Какой наибольший заработок может гарантировать себе Коля, как бы ни играл Саша?
Играя за Сашу, поделим всю доску на квадратики затем введём шахматную раскраску на них. “Чёрные” квадратики будем красить “вертикально”, то есть на ход Пети закрашивать вторую клетку из вертикальной доминошки, в которую он попал. В “белых” будем действовать аналогично “горизонтально”. В итоге все квадратики будут иметь один из видов (заменим красный и синий цвета на крестики и нолики)
При этом первые два не могут быть рядом (будем звать их горизонтальными), как и (вертикальные), а можно получить в любом квадратике (диагональные). Нетрудно видеть, что при таких условиях из них можно сложить “полосу” не длиннее четырёх крестиков (ширины ). Для этого нужно взять горизонтальный, а затем добавить по бокам вертикальный и диагональный, либо наоборот. Если же рассматривать полосу ширины два, то она не может иметь длину больше двух. Действительно, либо она идёт прямо по квадратику и имеет длину не более одного, либо идёт между квадратиками, тогда хотя бы один из них не является вертикальным (считаем, что полоса ориентирована вертикально), откуда даже её общая часть с ними имеет длину не более единицы. В итоге максимальная длина такой полосы, если она находится на пересечении квадратиков, будет равна площадь — Полоса длины три или четыре (а шире их не бывает) имеет длину не более единицы, поскольку иначе бы существовал квадратик полностью из крестиков либо два горизонтальных/вертикальных были бы рядом. В результате такая стратегия приводит к максимальному выигрышу для Коли.
Чтобы добиться этого выигрыша, Коле нужно покрасить фигуру ниже (можно убедиться, что так сделать можно всегда, если Саша хочет избежать фигуры площади )
Где нолики стоят там, где они должны быть, чтобы фигура площади не получилась уже на следующем ходу. Далее Коля может воспользоваться неограниченной с двух сторон последовательностью из двух крестиков в центре — её нетрудно за два хода “вытянуть” до длины
Ошибка.
Попробуйте повторить позже
Есть неокрашенных клетчатых прямоугольников Катя и Геля ходят по очереди, начинает Катя. Каждым ходом Катя выбирает цвет — черный или белый, — а Геля красит в этот цвет одну из еще не окрашенных клеток в любом из прямоугольников. Игра заканчивается, когда все прямоугольники полностью покрашены. Катя получает от Гели столько рублей, сколько сможет выбрать по-разному окрашенных прямоугольников. Какое наибольшее число рублей она может наверняка получить, как бы ни играла Геля?
Приведём стратегию Гели, когда Катя получит не более двух рублей. Выстроим прямоугольники в один большой прямоугольник будем красить с левого верхнего угла направо по стороне длины в черный цвет, а с правого нижнего налево вдоль стороны такой же длины — в белый (если строчка закончилась начнем снова так же красить следующую строчку). Тогда строчки длины будут одноцветным и одна, быть может, разноцветной: сначала сколько-то черных клеток, потом все белые. Отсюда видно, что получилось не более различных видов раскраски.
Чтобы добиться двух рублей, играя за Катю, достаточно раз сказать черный цвет и раз белый. Очевидно, что хотя бы два разноцветных прямоугольника мы так получим.
Ошибка.
Попробуйте повторить позже
Игра происходит на клетчатом поле . Петя и Вася ходят по очереди, начинает Петя. Он ставит в свободные клетки крестики, Вася — нолики. Когда все клетки заполнены, подсчитывается количество строк и столбцов, в которых крестиков больше, чем ноликов, — число и количество строк и столбцов, в которых ноликов больше, чем крестиков, — число (всего строк и столбцов — ). Какую наибольшую разность может обеспечить Петя, как бы ни играл Вася?
Первый игрок может занять первым ходом центральную клетку, а далее действовать симметрично второму игроку (относительно центра). В результате в центральных строке и столбце крестиков будет больше, а все остальные разобьются на пары центрально симметричных (так столбцу будет соответствовать столбец, горизонтально симметричный ему), где один ходит в (как множество таких), а другой — в поскольку число крестиков и ноликов в них будет также симметричным. В итоге разница
Второму игроку, чтобы не допустить худшего для себя исхода, следует играть так — если у него есть возможность сходить (центрально) симметрично ходу первого игрока, то он так и делает. Иначе он ходит в случайное место, но не в центр. В итоге он добьётся того же симметричного распределения, как добивался выше первый с тем же результатом.
Ошибка.
Попробуйте повторить позже
Есть запечатанных коробок карандашей, в которых карандашей (на каждой написано, сколько в ней). Петя и Вася берут себе по очереди по карандашу, пока не разберут все; начинает Петя. Каждый игрок в любой момент имеет право распечатать коробку, заплатив за это рубль сопернику. Кто и сколько рублей выиграет при наилучшей игре сторон?
Заметим, что Вася может открыть не более одной коробки. Действительно, если Петей открывается коробка с чётным числом карандашей, то следующую коробку также придётся открывать Пете. Тогда Петя должен открыть хотя бы одну коробку с нечётным числом карандашей. Васе же достаточно ровно в этот момент открыть другую нечётную коробку — суммарно в них будет чётное число карандашей, поэтому следующую коробку также открывает Петя. Почему одну коробку Васе придётся открыть? Потому что Петя может начать игру с нечётной коробки, возьмёт из неё последний карандаш, поэтому Васе придётся открыть вторую. В итоге Вася откроет на три коробки меньше и выиграет рубля.
Вася рубля