Задачи IV открытой интернет-олимпиады по математике: XIV тура Математического марафона

главная страница сайта Приглашение в мир математики

В рамках 14-го тура Математического марафона по традиции проводится тематический конкурс. Сейчас это - Математические игры и стратегии.

В истории Марафона этой теме была посвящена задача ММ66 (еще несколько задач были близки к этой тематике), во второй Интернет-олимпиаде участникам предлагалось проанализировать, как может повлиять на ход игры Баше случайная составляющая, а в Математический Маневрах под игровые задачи выделялась целая область.

Однако данная тематика далека от исчерпания, и мы предлагаем вам в решить пять новых задач, которые строятся вокруг игры двух человек.

Напомним, что в математических играх каждый игрок делает ходы наилучшим для себя образом. Так что описываемая вами выигрышная стратегия должна обеспечивать победу при любых ответах соперника.

====================

Решения можно присылать на val@dxdy.ru (в этом случае его сразу увидят оба ведущих), на val-etc@yandex.ru или в ЛС.

Не забывайте высылать вместе с решениями свои эстетические оценки задач.

Ведущие Марафона Владимир Лецко и Алексей Извалов

Итак, поехали!

====== 131 =========
Решения принимаются, по крайней мере, до 15.01.2011 .

ММ131 (3 балла) (Прощай 2010-й)

Граф G=\left<V,E\right> задан на множестве V = \{1, 2,\dots, 2010\} по правилу: \{x,y\} \in E \Leftrightarrow x+y = a \vee x+y = b , где a и b - фиксированные натуральные числа.
При каких a и b , граф G :
а) связен;
б) является деревом;
в) является цепью;
г) имеет циклы?

Решение задачи
======= 132 ========
Решения принимаются, по крайней мере, до 19.01.2011 .

ММ132 (5 баллов) (Здравствуй 2011-й)

Граф G=\left<V,E\right> задан на множестве V = \{1, 2,\dots, 2011} по правилу: \{x,y\} \in E \Leftrightarrow |x-y| > a , где a - фиксированное натуральное число, меньшее 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.

Проигрывает тот игрок, кто не сможет сделать ход согласно правилам.

Кто выиграет, если игра начнётся с числа (2011)_{10}=(11111011011)_2 ?
Решение задачи
======= 135 ========
Решения принимаются, по крайней мере, до 3.02.2011 .

ММ135 (4 балла)

Конечно ли множество пар натуральных чисел (a,b) , таких что остатки от деления a^2 на b и b^2 на a равны по 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 баллов)

Кнопки калькулятора расположены так, как на цифровой клавиатуре:
\begin{tabular}{|c|c|c|} \hline 7 & 8 & 9 \\ \hline 4 & 5 & 6 \\ \hline 1 & 2 & 3 \\ \hline \multicolumn{2}{|c|}{0}\\ \cline{1-2} \end{tabular}
Назовём смежными те кнопки, которые имеют общую сторону или отрезок стороны (клавиша 0 смежна с клавишами 1 и 2).
Вначале на индикаторе число 0. Начинает игру Петя, прибавляя к нему любое (им выбранное) число от 0 до 9. Затем Вася прибавляет в полученному числу слагаемое, находящееся на смежной кнопке с той, которую нажимал Петя. Затем Петя делает свой ход, прибавляя число, смежное с нажатым Васей и т.д. Игра заканчивается, когда после очередного действия на индикаторе появится результат, больший некоторого наперёд заданного числа N (N>10). Игрок, сделавший такой ход, проигрывает.
Для каких N наибольшее число вариантов первого хода Пети приведёт его в дальнейшем к победе?
Решение задачи
======= 140 ========
Задача ММ140 навеяна вот этой.
Решения принимаются, по крайней мере, до 28.02.2011 .

ММ140 (10 баллов)

На квадратной площади, разлинованной на nxn клеток (полей) собрались n^2 человек, каждый из которых является либо рыцарем (всегда говорят правду), либо лжецом (всегда лгут). Каждый расположился на отдельном поле. После этого каждый произнес: "Среди моих соседей поровну рыцарей и лжецов". Какова наибольшая возможная доля рыцарей среди собравшихся?

Примечания:
Соседними считаются поля, имеющие общую сторону;
Каждый из собравшихся знает, кем являются его соседи.
Решение задачи
===============

Задайте вопрос на блоге о математике