Мы рады объявить о старте новой Открытой математической интернет-олимпиады, которая проводится совместно с Математическим марафоном. Вас опять ждёт 10 интересных задач, так что будет чем заняться на каникулах :)
В рамках 14-го тура Математического марафона по традиции проводится тематический конкурс. Сейчас это - Математические игры и стратегии.
В истории Марафона этой теме была посвящена задача ММ66 (еще несколько задач были близки к этой тематике), во второй Интернет-олимпиаде участникам предлагалось проанализировать, как может повлиять на ход игры Баше случайная составляющая, а в Математический Маневрах под игровые задачи выделялась целая область.
Однако данная тематика далека от исчерпания, и мы предлагаем вам в решить пять новых задач, которые строятся вокруг игры двух человек.
Напомним, что в математических играх каждый игрок делает ходы наилучшим для себя образом. Так что описываемая вами выигрышная стратегия должна обеспечивать победу при любых ответах соперника.
====================
Решения можно присылать на val@dxdy.ru (в этом случае его сразу увидят оба ведущих), на val-etc@yandex.ru или в ЛС.
Не забывайте высылать вместе с решениями свои эстетические оценки задач.
Ведущие Марафона Владимир Лецко и Алексей Извалов
Итак, поехали!
====== 131 =========
Решения принимаются, по крайней мере, до
15.01.2011
.
ММ131
(3 балла) (Прощай 2010-й)
Граф
[показать]
задан на множестве
[показать]
по правилу:
[показать]
, где
[показать]
и
[показать]
- фиксированные натуральные числа.
При каких
[показать]
и
[показать]
, граф
[показать]
:
а) связен;
б) является деревом;
в) является цепью;
г) имеет циклы?
======= 132 ========
Решения принимаются, по крайней мере, до
19.01.2011
.
ММ132
(5 баллов) (Здравствуй 2011-й)
Граф
[показать]
задан на множестве
[показать]
по правилу:
[показать]
, где
[показать]
- фиксированное натуральное число, меньшее 1006.
Сколько периферийных вершин может иметь граф G?
Примечание: Вершина графа называется периферийной, если ее эксцентриситет равен диаметру графа.
======= 133 ========
Оценка за решение задачи ММ133 будет учитываться дважды: в основном Марафоне и в тематическом конкурсе.
Решения принимаются, по крайней мере, до
22.01.2011
.
ММ133 (МИ1)
(3 балла)
На столе лежит N спичек. Петя и Вася поочерёдно берут оттуда от 1 до 5 спичек, однако нельзя повторять число, взятое соперником на предыдущем ходу. Выигрывает тот, кто забирает последнюю спичку. Начинает Петя, своим первым ходом может взять любое количество от 1 до 5. Найдите общий вид чисел N, при которых партию выиграет Вася.
======= 134 ========
Оценка за решение задачи ММ134 будет учитываться дважды: в основном Марафоне и в тематическом конкурсе.
Решения принимаются, по крайней мере, до
26.01.2011
.
ММ134 (МИ2)
(4 балла)
Позицией в игре является конечное множество чисел, записанных в двоичной системе счисления. Игроки по очереди разбивают одно из чисел этого множества на части так, чтобы выполнялись два правила:
1) оба полученных числа должны начинаться с единицы;
2) хотя бы одно из них должно заканчиваться нулём.
Например, 1101 можно разбить только на 110 и 1, а 11010 - на 1 и 1010 или на 110 и 10.
Проигрывает тот игрок, кто не сможет сделать ход согласно правилам.
Кто выиграет, если игра начнётся с числа
[показать]
?
======= 135 ========
Решения принимаются, по крайней мере, до
3.02.2011
.
ММ135
(4 балла)
Конечно ли множество пар натуральных чисел
[показать]
, таких что остатки от деления
[показать]
на
[показать]
и
[показать]
на
[показать]
равны по 2011?
======= 136 ========
Оценка за решение задачи ММ136 будет учитываться дважды: в основном Марафоне и в тематическом конкурсе.
Решения принимаются, по крайней мере, до
8.02.2011
.
ММ136 (МИ3)
(5 баллов)
На столе в открытую лежит 16 карт: 4 туза (считаются за 1 очко), 4 двойки, 4 тройки и 4 четвёрки. Петя и Вася по очереди берут оттуда по одной карте и складывают в отдельную стопку (общую). Выигрывает тот, после чьего хода сумма очков в этой стопке составит 21 очко (или заставивший соперника своим ходом превысить это значение). Петя начинает игру. Кто победит в игре и какой стратегии он должен придерживаться (как реагировать на ходы соперника)?
======= 137 ========
Оценка за решение задачи ММ137 будет учитываться дважды: в основном Марафоне и в тематическом конкурсе.
Решения принимаются, по крайней мере, до
13.02.2011
.
ММ137 (МИ4)
(6 баллов)
Шашки двух игроков стоят на противоположный полях прямоугольника 1x(N+2), между ними N клеток. Начальная скорость каждой шашки равна 1.
Каждый ходом игрок может или передвинуть свою шашку в сторону противника на величину, равную текущей скорости или увеличить скорость на 1 и передвинуть шашку в этом направлении уже на величину увеличенной скорости.
Выигрывает тот, кто поставит свою шашку на шашку противника или перепрыгнет через неё.
Для каких натуральных N, не превосходящих 100, выиграет второй игрок?
======= 138 ========
Решения принимаются, по крайней мере, до
17.02.2011
.
ММ138
(6 баллов)
Доказать, что для любого натурального k найдутся натуральные a, n и g, такие что для всех i из {0,1,... ,k-1}
в системе счисления с онованием g+i, число a является n-i-значным.
======= 139 ========
Задача ММ139 является развитием идеи задачи Кузнецова Сергея Тихоновича.
Оценка за решение этой задачи будет учитываться дважды: в основном Марафоне и в тематическом конкурсе.
Решения принимаются, по крайней мере, до
21.02.2011
.
ММ139 (МИ5)
(7 баллов)
Кнопки калькулятора расположены так, как на цифровой клавиатуре:
Назовём смежными те кнопки, которые имеют общую сторону или отрезок стороны (клавиша 0 смежна с клавишами 1 и 2).
Вначале на индикаторе число 0. Начинает игру Петя, прибавляя к нему любое (им выбранное) число от 0 до 9. Затем Вася прибавляет в полученному числу слагаемое, находящееся на смежной кнопке с той, которую нажимал Петя. Затем Петя делает свой ход, прибавляя число, смежное с нажатым Васей и т.д. Игра заканчивается, когда после очередного действия на индикатор появится некоторое наперёд заданное число N (N>10).
Для каких N наибольшее число вариантов первого хода Пети приведёт его в дальнейшем к победе?
======= 140 ========
Задача ММ140 навеяна вот этой.
Решения принимаются, по крайней мере, до
28.02.2011
.
ММ140
(10 баллов)
На квадратной площади, разлинованной на
[показать]
клеток (полей) собрались
[показать]
человек, каждый из которых является либо рыцарем (всегда говорят правду), либо лжецом (всегда лгут). Каждый расположился на отдельном поле. После этого каждый произнес: "Среди моих соседей поровну рыцарей и лжецов". Какова наибольшая возможная доля рыцарей среди собравшихся?
Примечания:
Соседними считаются поля, имеющие общую сторону;
Каждый из собравшихся знает, кем являются его соседи.
===============