Математический марафон

[VAL]

Марафон ушел на летние каникулы.
12-й тур стартует в сентябре.

[VAL]

Стартовал 12-й тур Математического марафона

В рамках тура по традиции будет проводиться тематический конкурс.
Тема конкурса - математика на шахматной доске. С книжками Е.Я,Гика по этой тематике я знаком, но сейчас их под рукой нет. Поэтому теоретически возможен вариант, что какая-нибудь задачка окажется не новой. Но, в0-первых, я надеюсь, что этого не произойдет, а во-вторых, и раньше отдельные марафонские задачки оказывались не новыми и ничего, мир не перевернулся

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

Предлагаемая задача (совсем разминочная) открывает одновременно 12-й тур и тематический конкурс шахматно-математический конкурс. Соответственно и результат учитывается дважды.

ММ111 (Ш-1) (3 балла)

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


Примечание:
Ходы должны делаться по всем правилам щахматной игры.

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

Светлой памяти C5 ЕГЭ посвящается.

ММ112 (6 баллов)

Решить уравнение при всех возможных наборах значений параметров a и b:

$$11x+a^2-2a+b^2+4b+|2x+a^2-2a+4b+b^2|+|-3x+2+a^2-2a-4b-b^2|+|-x-4b-b^2+a^2-2a|+18|x-2|=20$$

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

Познакомиться с решением задач 111 и 112 и обсудить их можно здесь.

[VAL]

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

Оценка за решение задачи ММ113 учитывается дважды в основном Марафоне и в тематическом конкурсе.

ММ113 (Ш-3) (10 баллов)

На множестве полей шахматной доски определим структуру графа $G_N$ следующим образом:
две вершины (два поля) будем считать смежными, если конь может за один ход переместиться из одной вершины в другую.
Аналогично определим граф слона $G_B$, граф ладьи $G_R$, граф ферзя $G_Q$ и граф короля $G_K$.
Для каждого из этих графов:
1. Найти
а) количество ребер;
б) количество компонент связности;
в) радиус и диаметр каждой компоненты;
г) наибольшую клику.
2. Выяснить является ли граф:
а) двудольным;
б) эйлеровым;
в) гамильтоновым;
г) планарным?

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

ММ114 (7 баллов)

Спорный участок имеет форму правильного треугольника периметром 100 м.
Х, отстаивающий свое право собственности, решил для надежности обнести участок забором и приобрел 100 м сетки-рабицы. Но к тому моменту, когда X закупил сетку, состоялся суд, присудивший разделить спорный участок между X и Y. Линия раздела прошла по прямой через центр участка. А Y тут же оградил свою часть. Когда X оградил свою, у него осталось 47 метров неиспользованной сетки.
Найти площади участков, доставшихся X и Y.

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

Познакомиться с решением задач 113 и 114 и обсудить их можно здесь.

[VAL]

Оценка за решение задачи ММ115 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

На диаграмме к задаче ММ111 отсутствовали кони. Исправляя эту явную несправедливость по отношению к невинно пострадавшим животным, администрация Марафона предлагает вниманию участников:

ММ115 (Ш-3) (10 баллов)

На шахматной доске расставлены кони.

Разрешается менять цвет фигур одновременно в клетках на одной вертикали, горизонтали или диагонали (в частности, в одной угловой клетке - считается, что она сама - диагональ). Можно ли получить одноцветный квадрат 5X5 в каком-либо месте доски?

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

Познакомиться с решением задачи 115 и обсудить ее можно здесь.

[VAL]

Задача ММ116 навеяна обсуждением одной из последовательностей в OEIS.

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

Сколько существует связных графов, таких что произведение степеней вершин равно:
а) сумме степеней вершин;
б) сумме квадратов степеней вершин?

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

Оценка за решение задачи ММ117 будет учитываться дважды в основном Марафоне и в тематическом конкурсе. А сама задача ММ117 является прямым продолжением задачи ММ115.

ММ117 (Ш-4) (7 баллов)

На шахматной доске расставлено 64 белых коня. Какое минимальное количество коней нужно заменить черными, так чтобы в полученной позиции, действуя по правилам задачи ММ115, было бы невозможно получить хотя бы один одноцветный квадрат 5Х5?
Каково количество таких позиций?

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

Познакомиться с решением задач 116 и 117 и обсудить их можно здесь.

[VAL]

===============
Задача о задаче (нестареющая классика на новый лад).

ММ118 (7 баллов)

Ведущий Математического марафона придумал задачу. Но, прежде чем помещать ее в Марафон, он решил протестировать задачу и рассказал ее своему коллеге:

- Бывшие одноклассники Петр и Николай встретились на мероприятии, посвященном 40-ю выпуска из школы, и разговорились.
П: Да-а... разбросала нас жизнь, 40 лет тебя не видел и ничего о тебе не слышал. А ведь раньше не разлей вода были, за одной партой сидели. Ну и как ты? Семьей обзавелся?
Н: А как же! У меня три красавца сына!
П: Ну ты даешь! И сколько же им лет?
Н: Надеюсь, ты по-прежнему любишь головоломки? Тогда догадайся сам. Сумма их возрастов равна номеру квартиры, в которой ты жил в школьные годы, а произведение возрастов равно...

... И ведущий Марафона для удобства коллеги написал нужное число на бумажке и продолжил:

- Петр достал ручку и на несколько минут погрузился в вычисления...
П: Ты знаешь, этих данных мне мало.
Н: Ах, да! Забыл добавить, что среднего я назвал в твою честь.
П: Спасибо! Теперь информации достаточно.
Сколько лет сыновьям Николая?

Коллега ведущего погрузился в вычисления (более продолжительные, чем Петр из задачи). Но его комментарий, не отличался от комментария Петра:
- Ты знаешь, этих данных мне мало - сказал он ведущему Марафона.
- Ах, да! - осознал ошибку ведущий - Тогда пусть Петром зовут не среднего, а старшего сына Николая.
- К сожалению, это не спасет задачу. А вот если Николай назовет Петром своего младшего сына, тогда задача будет иметь единственное решение!

Что за число написал ведущий?
================

Познакомиться с решением задачи 118 и обсудить ее можно здесь.

[VAL]

От себя лично и от имени ведущего Марафона поздравляю марафонцев и болельщиков с новогодне-рождественскими праздниками!
И прилагаю новогодний подарок: заключительные задачки 12-го тура.
Постараюсь и впредь делать аналогичные широкие жесты. Обязуюсь опубликовать разбор задачи ММ118 до конца 2010-го года :)

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

Оценка за решение задачи ММ119 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

Заключительная задача тематического конкурса - самая шахматная.
Решения принимаются, по крайней мере, до 19.01.10.

ММ119 (Ш-5) (8 баллов)

Придумать корректную (т.е. ее можно получить из начальной по всем правилам шахматной игры) позицию, в которой белые дают мат в один ход, как можно бОльшим числом способов.

Примечания:
1. Корректность позиции обосновывается указанием ходов к ней приводящих.
2. 8 баллов - это условная цена задачи. Их можеть быть и меньше, и больше, в зависимости от достигнутого результата. Дополнительные призовые баллы могут быть начислены за обоснование неулучшаемости предложенного решения (однако их будет не больше, чем за решение, которое окажется лучше неулучшаемого) :)

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

Заключтельная задача 12-го тура (и 2009-го года) продолжает линию задачи ММ57 и тематического конкурса прошлого тура. (Она имеет непосредственное отношение и еще к одной марафонской задаче, но об этом позже...)

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

ММ120 (8 баллов)

В задаче ММ103 каждому выпуклому многоугольнику был поставлен в соответствие сопровождающий граф:
вершины графа - элементарые многоугольники, на которые разбивается исходный многоугольник своими диагоналями;
две вершины смежны, если соответствующин многоугольники имеют общую сторону.

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

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

Познакомиться с решениями задач 119 и 120 и обсудить их можно здесь.

[VAL]

XIII-ый тур Математического Марафона
(Третья открытая Интернет-олимпиада по математике)


После неприлично затянувшейся паузы Математический марафон продолжается с новыми силами.
В качестве новой силы выступает бывший марафонец, а теперь соведущий Алексей Извалов.
Так что теперь нас, ведущих, двое: Владимир Лецко и Алексей Извалов.

Стать участником марафона может любой желающий. Некоторые задачи вполне доступны школьникам. Для решения других требуются знания, выходящие за рамки школьного курса. Одни задачи могут показаться вам интересными, а другие - не очень. На вкус и на цвет...

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

Ждем от вас комментариев марафонских задач, а также пожеланий Марафону. Эта обратная связь позволит сделать Марафон интереснее для вас.

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

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

В рамках 13-го тура, как обычно, проводится тематический конкурс.
Он является прямым продолжением тематического конкурса из 11-го тура.
Его тематика - комбинаторная геометрия.

Более того, тематические задачи тура, как и задачи ММ57, ММ101, ММ102, ММ103, ММ104 и ММ120, будут так или иначе связаны с выпуклыми многоугольниками.
Не будем отсылать участников к архивам и приведем ряд определений и обозначений, используемых в задачах тематического конкурса, прямо здесь. Тем более, что терминология расширилась (а иногда и немного поменялась).

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

Число сторон исходного выпуклого многоугольника всегда обозначается через n (если иное не оговорено в конкретной задаче).
Исходный многоугольник разбивается своими диагоналями на элементарные.
Точка внутри многоугольника называется особой (полюсом), если в ней пересекаются не менее трех диагоналей.
Если в особой точке пересекаются k диагоналей, то она является полюсом порядка k-2.
Многоугольник без особых точек будем называть ординарным, иначе - особенным.
Структурным графом выпуклого многоугольника будем называть граф, вершинами которого служат вершины и точки пересечения диагоналей исходного многоугольника, а ребрами - отрезки диагоналей и стороны исходного многоугольника.
Дуальный граф - граф геометрически двойственный структурному (вершины - грани плоской укладки структурного графа, две вершины смежны, если соответствующие грани имеют общую сторону).
Сопровождающий граф - дуальный граф без вершины, соответствующей внешней грани.
Будем называть два выпуклых многоугольника изотопными, если изоморфны их структурные графы.
В задаче ММ104 было введено понятие изоморфизма многоугольников. Изоморфными назывались многоугольники, сопровождающие графы которых изоморфны. Можно доказать, что два выпуклых многоугольника изоморфны тогда и только тогда, когда они изотопны. Мы не стали предлагать это утверждение в качестве марафонской задачи. Желающие убедиться в его справедливости могут сделать это самостоятельно (или с помощью книжек: см., например, А.А.Зыков. Основы теории графов).

Пусть n>5. Характеристическим вектором n-угольника будем называть набор $s = (s_1, \ s_2, \ \dots,\ s_m)$, где $m = \left[\frac n2\right]-2, \ s_k$ - число полюсов порядка k.
Два многоугольника будем называть изополярными, если равны их характеристические векторы.
Вектором граней многоугольника будем называть набор $t = (t_3, \ t_4, \ \dots,\ t_n)$, где $t_k$ - количество элементарных k-угольников.
Два многоугольника будем называть однотипными, если равны их векторы граней.

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

Задача ММ121 является прямым продолжением задачи ММ104.
Оценка за решение задачи ММ121 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

ММ121 (КГ-6) (8 баллов)

1. На сколько классов однотипных семиугольников разбиваются выпуклые семиугольники?
2. На сколько классов изотопных семиугольников разбиваются выпуклые семиугольники?

Разбор задачи ММ121 можно посмотреть здесь.

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

Задача ММ122 является прямым продолжением задачи ММ57.
Оценка за решение задачи ММ122 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

ММ122 (КГ-7) (4 балла)

1. Найти формулу для выражения числа вершин структурного графа с данным характеристическим вектором.
2. Найти формулу для выражения числа элементарных многоугольников исходного многоугольника с данным характеристическим вектором.

Разбор задачи ММ122 можно посмотреть здесь.

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

ММ123 (5 баллов)
Квадратная монета со стороной 1 см бросается случайным образом на лист бумаги, разлинованный квадратными клетками со стороной 2 см. Какая вероятность того, что монета попадёт целиком в клетку?

Разбор задачи ММ123 можно посмотреть здесь.

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

ММ124 (4 балла)

Пусть $S_n = 2 + 3 + 5 + 7 +\dots+ p_n$ - сумма n первых простых чисел. Доказать, что $S_n$ является простым тогда и только тогда, когда существует такое простое число q, что $S_n + q$ кратно $2, \ 3, \ 5, \ \dots, \ p_n$.

Разбор задачи ММ124 можно посмотреть здесь.

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

Оценка за решение задачи ММ125 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

ММ125 (КГ-8) (4 балла)

Верно ли, что группа автоморфизмов структурного графа любого n-угольника изоморфна подгруппе группы диэдра n-й степени?

Разбор задачи ММ125 можно посмотреть здесь.

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

ММ126 (4 балла)

Есть 8 шаров, среди которых 6 заряжены нейтрально, один - положительно и один - отрицательно. Есть прибор, который, будучи поднесённым к группе шаров, покажет их общий заряд (он покажет 0 и если в группе нет ни одного заряженного шара, и если они там оба).
За какое наименьшее число измерений можно найти положительный и отрицательный шары в группе?

Разбор задачи ММ126 можно посмотреть здесь.

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

Оценка за решение задачи ММ127 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

ММ127 (КГ-9) (12 баллов)

Существуют ли однотипные, но не изополярные многоугольники?

Разбор задачи ММ127 можно посмотреть здесь.

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

Оценка за решение задачи ММ128 будет учитываться дважды в основном Марафоне и в тематическом конкурсе.

ММ128 (КГ-10) (20 баллов)

На сколько классов изополярных восьмиугольников разбиваются выпуклые восьмиугольники?

Разбор задачи ММ128 можно посмотреть здесь.

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

[VAL]

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

ММ129 (5 баллов)

Будем заполнять бесконечный клетчатый лист бумаги натуральными числами по спирали (каждый следующий виток начинается на вертикали, в которой стоит единица):



Для каждого числа найдём восемь модулей разности его с соседями (по вертикали, горизонтали и диагонали). Количество простых чисел среди этих восьми назовем индексом простоты окружения исходного сила.
Какое наибольшее значение может принимать индекс простоты окружения?
Для скольких чисел достигается это значение?

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

Разбор задачи ММ129 можно посмотреть здесь.

[VAL]

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

ММ130 (6 баллов)

Комната имеет форму прямоугольного параллелепипеда шириной $a$, высотой $b$ и длиной $c$. На стене $a \times b$ сидит таракан. Он находится на расстоянии $\frac{a}2$ от смежной стены и на расстоянии $x$ от потолка, $x\le \frac b2$ и хочет попасть в точку, симметричную исходной относительно центра параллелепипеда.

Для некоторых значений $a, \ b, \ c$ кратчайший путь между этими точками будет проходить через одну и ту же последовательность граней при любом x, $0\le x\le \frac b2$. Для каждой такой последовательности граней приведите пример тройки $a, \ b, \ c$.

Разбор задачи ММ130 можно посмотреть здесь.

[VAL]

XIV тур Математического марафона

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

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

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

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

С решениями задач 14-го тура Марафона можно ознакомиться здесь.

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

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

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

====== 131 =========

ММ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 ========

ММ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 учитывается дважды: в основном Марафоне и в тематическом конкурсе.

ММ133 (МИ1) (3 балла)

На столе лежит N спичек. Петя и Вася поочерёдно берут оттуда от 1 до 5 спичек, однако нельзя повторять число, взятое соперником на предыдущем ходу. Выигрывает тот, кто забирает последнюю спичку. Начинает Петя, своим первым ходом может взять любое количество от 1 до 5. Найдите общий вид чисел N, при которых партию выиграет Вася.


======= 134 ========

Оценка за решение задачи ММ134 учитывается дважды: в основном Марафоне и в тематическом конкурсе.

ММ134 (МИ2) (4 балла)

Позицией в игре является конечное множество чисел, записанных в двоичной системе счисления. Игроки по очереди разбивают одно из чисел этого множества на части так, чтобы выполнялись два правила:
1) оба полученных числа должны начинаться с единицы;
2) хотя бы одно из них должно заканчиваться нулём.
Например, 1101 можно разбить только на 110 и 1, а 11010 - на 1 и 1010 или на 110 и 10.

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

Кто выиграет, если игра начнётся с числа $(2011)_{10}=(11111011011)_2$?


======= 135 ========

ММ135 (4 балла)

Конечно ли множество пар натуральных чисел $(a,b)$, таких что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны по 2011?


======= 136 ========

Оценка за решение задачи ММ136 учитывается дважды: в основном Марафоне и в тематическом конкурсе.

ММ136 (МИ3) (5 баллов)

На столе в открытую лежит 16 карт: 4 туза (считаются за 1 очко), 4 двойки, 4 тройки и 4 четвёрки. Петя и Вася по очереди берут оттуда по одной карте и складывают в отдельную стопку (общую). Выигрывает тот, после чьего хода сумма очков в этой стопке составит 21 очко (или заставивший соперника своим ходом превысить это значение). Петя начинает игру. Кто победит в игре и какой стратегии он должен придерживаться (как реагировать на ходы соперника)?


======= 137 ========

Оценка за решение задачи ММ137 учитывается дважды: в основном Марафоне и в тематическом конкурсе.

ММ137 (МИ4) (6 баллов)

Шашки двух игроков стоят на противоположный полях прямоугольника 1x(N+2), между ними N клеток. Начальная скорость каждой шашки равна 1.
Каждый ходом игрок может или передвинуть свою шашку в сторону противника на величину, равную текущей скорости или увеличить скорость на 1 и передвинуть шашку в этом направлении уже на величину увеличенной скорости.
Выигрывает тот, кто поставит свою шашку на шашку противника или перепрыгнет через неё.
Для каких натуральных N, не превосходящих 100, выиграет второй игрок?


======= 138 ========

ММ138 (6 баллов)

Доказать, что для любого натурального k найдутся натуральные a, n и g, такие что для всех i из {0,1,... ,k-1}
в системе счисления с онованием g+i, число a является n-i-значным.


======= 139 ========

Задача ММ139 является развитием идеи задачи Кузнецова Сергея Тихоновича.
Оценка за решение этой задачи учитывается дважды: в основном Марафоне и в тематическом конкурсе.


ММ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 навеяна вот этой.

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

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

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

[VAL]

XV тур Математического марафона

Познакомиться с решениями задач XV-го тура и обсудить их можно здесь.

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

ММ141 (3 балла)

Существуют ли натуральные числа $n>1$ такие, что $\sigma(\sigma(n))<1.000000001n$?
($\sigma(n)$ - сумма натуральных делителей числа $n$.)

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

ММ142 (4 балла)

Все 80 натуральных делителей натурального числа n расположили в порядке возрастания. Оказалось, делители с первого по четвертый образуют геометрическую прогрессию, делители с четвертого по седьмой - арифметическую прогрессию, а восьмой делитель меньше 200.
Найти n.

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

В Тематическом конкурсе тура - вновь комбинаторная геометрия.
Более того, во всех тематических задачах, кроме КГ-11, речь вновь пойдет о многоугольниках. Но на этот раз - не обязательно выпуклых.

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

ММ143 (КГ-11) (4 балла)

Девять из десяти ребер пятиугольной пирамиды имеют длину 1. В каком диапазоне может изменяться длина 10-го ребра?

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

ММ144 (5 баллаов)

На поле e4 стоит чёрный король. Первый игрок ставит на любую клетку доски, не находящуюся под боем чёрного короля, белых королей (по одному за ход). Второй игрок делает (правильный) ход чёрным королём. Игра заканчивается, когда у чёрного короля не будет ходов. Каково минимальное количество ходов, за которое первый игрок может достичь цели?

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

В задачах КГ-12 - КГ-15 будем придерживаться следующих определений и обозначений:

Под многоугольником мы будем понимать плоскую замкнутую несамопересекающуюся ломаную, никакие три последовательные вершины которой не коллинеарны. Число сторон исходного многоугольника обозначим через n.
Назовем сторону многоугольника свободной, если продолжение этой стороны за каждую ограничивающую ее вершину в некоторой окрестности этой вершины лежит вне многоугольника.
Назовем сторону полусвободной, если вне многоугольника лежит продолжение стороны ровно за одну из двух ограничивающих ее вершин. Сторону, не являющуюся ни свободной, ни полусвободной, будем называть зажатой. Например, сторона AB (рис. 1), является свободной, сторона BC - полусвободной, а сторона EF - зажатой.
Диагональ, все точки которой принадлежат многоугольнику, будем называть внутренней. Диагональ, не имеющую с многоугольником общих точек, за исключением вершин, которые она соединяет, будем называть внешней. Например, диагональ BF (рис. 1) - внутренняя, а диагональ BD - внешняя (диагональ BE не является ни внешней, ни внутренней).




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

ММ145 (КГ12) (3 балла)

Сколько внешних диагоналей может иметь n-угольник?

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

ММ146 (4 балла)

При каких $D$ существуют графы диаметра $D$, у которых сумма квадратов степеней вершин равна $D^2$?

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

ММ147 (КГ13) (6 баллов)

Какое наименьшее число внутренних диагоналей может иметь n-угольник, у которого ровно один угол больше развернутого?

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

ММ148 (КГ14) (8 баллов)

Сколько внутренних диагоналей может иметь n-угольник?

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

ММ149 (8 баллов).

При каком наименьшем $n$ в группе перестановок $S_n$ существует подгруппа порядка 253? Привести пример такой подгруппы.

Примечание: Задачу можно решить на бумажке, без компьютерного перебора

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

ММ150 (КГ15) (12 баллов)

Каждому n-угольнику поставим в соответствие ожерелье из n бусин белого, зеленого и красного цветов следующим образом: свободой стороне соответствует белая бусина; полусвободной - зеленая; зажатой - красная.
Два n-угольника назовем эквивалентными, если им соответствуют одинаковые ожерелья (ожерелье не меняется при поворотах и переворачивании). На сколько классов эквивалентности разобьются 20-угольники?

[VAL]

XVI тур Математического марафона

В XVI-м туре Математического Марафона традиционно будет проводиться тематический конкурс.
На этот раз тематика конкурса - Графы.
Если кому-то их участников или болельщиков покажется, что к некоторым тематическим задачам графы "притянуты за уши",.. не стану с ними спорить :)

Познакомиться с решениями задач XV-го тура и обсудить их можно здесь.

========= 151 ==========

ММ151 (ТГ-1) (4 балла)

Каждая клетка доски $4\times 4$ покрашена либо в черный, либо в белый цвет.
На множестве клеток задана структура графа. Две клетки смежны, если: они одного цвета; у них поровну соседей каждого цвета. (Соседними считаются клетки имеющие общую сторону.)
Какое наименьшее и наибольшее количество ребер может иметь такой граф, если:
а) количество клеток одного цвета может быть любым;
б) черных и белых клеток поровну?

========= 152 ==========

ММ152 (6 баллов)

Сколькими способами можно разрезать квадрат на 10 квадратов.
Два разрезания считаются неразличимыми, если в итоге получится поровну квадратов каждого размера.

========= 153 ==========

ММ153 (ТГ-2) (4 балла)

Пусть n, m и k означают соответственно число вершин, ребер и связных компонент графа.
Какое наименьшее количество изолированных вершин может иметь граф, для которого выполняется соотношение 11k = 10n = 8m?

========= 154 ==========

ММ154 (5 баллов)

Математик D предложил математикам A, B и C следующую задачку:

Я загадал два натуральных числа (не обязательно различных), каждое из которых не превосходит 20.
Сейчас я сообщу A сумму квадратов, B - произведение, а C - сумму этих чисел, а вы должны будете отгадать эти числа.
Узнав предназначенную информацию математики разговорились.
A: Я не знаю этих чисел.
B: Я тоже их не знаю.
C: И я не знаю.
B: Тогда я их знаю.
C: А я не знаю.
А: Зато я узнал их еще до того, как ты в первый раз это сказал.

Что это за числа?

========= 155 ==========

ММ155 (4 балла)

Существует ли цепочка из 1000 последовательных натуральных чисел, каждое из которых имеет не менее 1000 натуральных делителей?

========= 156 ==========

ММ156 (ТГ-3) (5 баллов)

На занятии по дискретной математике на доске был изображен некоторый граф.
Вася Пупкин записал в тетрадку количество вершин и ребер каждой связной компоненты графа, а также степени вершин самой большой (по количеству вершин) компоненты.
Но само изображение графа он срисовать забыл. Кроме того, он забыл, за какую именно из вышеперечисленных характеристик отвечает каждое из записанных чисел.
Сможет ли Вася решить домашнее задание "Найти диаметры каждой связной компоненты", если у него в тетрадке записаны числа: 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 9?

========= 157 ==========

ММ157 (6 баллов)

В треугольнике ABC, отличном от прямоугольного, проведены высоты AE и CF, пересекающиеся в точке H. Через точки A и H проведены перпендикуляры к EF, пересекающие прямую BC в точках K и L.
Найти KL, если радиус окружности, вписанной в треугольник ABC равен r, а BC = a.

========= 158 ==========

Задача ММ158 предложена Олегом Полубасовым

ММ158 (ТГ-4) (7 баллов)

I. Города занумерованы от 1 до N. Дорога, непосредственно соединяющая города i и j, существует, если и только если $|i-j|$ - простое число. Длина дороги равна $|i-j|$.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N.
II. Заменим в I $|i-j|$ нат $i+j$.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N, при условии, что полученный граф гамильтонов.

========= 159 ==========

ММ159 (6 баллов)


Для натурального числа n, большего 1, обозначим через $qu(n)$ отношение суммы количеств единиц во всех записях числа n в системах счисления с натуральными основаниями, большими 1, к самому числу n.
Найти наибольшее и наименьшее значение $qu(n)$ и предел $qu(n)$ при n, стремящимся к бесконечности.
Конечны ли множества чисел, для которых $qu(n)$: меньше 1; больше 1; равно 1?

========= 160 ==========

ММ160 (ТГ-5) (10 баллов)

На множестве натуральных чисел от 1 до 10460353203 структура графа G задается так:
вершины a и b смежны <=> множества цифр в g-ичной записи чисел a и b различны при любом натуральном $g > 2$.
Является ли G:
a) двудольным;
b) связным;
с) ациклическим?
d) Чему равна степень вершины 3?
e) Есть ли G вершины, степень которых больше чем 10000000000?

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

[VAL]

После некоторой задержки стартовал
17-й тур Математического марафона!

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

Решения задач можно посмотреть здесь

========= 161 ==========

ММ161 (РК-1) (3 балла)

По мотивам задачи ММ132 (и ряда других)

Граф $G=<V,E>$ задан на множестве $V = \{1, 2, ..., 1000000000000\}$ по правилу: $\{a,b\} \in E$ тогда и только тогда, когда сумма чисел $a$ и $b$ равна некоторой четной натуральной степени их разности.
Найти число связных компонент $G$ и диаметр наибольшей компоненты.


========= 162 ==========

ММ162 (РК-2) (4 балла)


По мотивам задачи ММ94

Пару различных натуральных чисел a и b назовем похожими, если $\varphi(a)=\varphi(b), \ \sigma(a)=\sigma(b), \ \tau(a)=\tau(b)$, где $\varphi(n), \ \sigma(n)$ и $\tau(n)$, соответственно функция Эйлера, сумма и число натуральных делителей числа $n$ (см. разбор ММ94).
Существуют ли похожие числа a и b такие, что $\tau(a)=\tau(b)=4$?


========= 163 ==========

ММ163 (РК-3) (5 баллов)

По мотивам задачи ММ94 (и ММ162)

Пару похожих чисел a и b назовем s-парой, если $a = spq, \ b=s^3r$, где $p, q, r, s$ - попарно различные простые числа. Проверить истинность каждого из следующих утверждений:
1. Для каждого простого s найдется хотя бы одна s-пара.
2. Для некоторых простых s существует более одной s-пары.
3. Для каждого простого s число s-пар конечно.


========= 164 ==========

ММ164 (РК-4) (6 баллов)

По мотивам задачи ММ135

В задаче ММ135 приведено несколько рекуррентных последовательной вида $a_{i+1}=da_i-a_{i-1}$ соседние члены которых дают бесконечные множества пар натуральныхчисел $(a,b)$ таких, что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны 2011.
Существует ли натуралное число $c<2000000$, для которого найдется не менее 100 последовательностей с попарно различными $d$, соседние члены которых дают бесконечные множества пар натуральных чисел $(a,b)$ таких, что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны $c$?


========= 165 ==========

ММ165 (РК-5) (7 баллов)

По мотивам задачи ММ74

Вася и Петя поспорили.
Вася утверждает, что объем выпуклого многогранника, все грани которого правильные многоугольники, а все 15 ребер имеют длину 1 заведомо больше объема каждого из выпуклых многогранников, о которых идет речь в задаче ММ74. Петя же утверждает, что не больше, а меньше.
В качестве третейского судьи позвали Федю. Подумав, Федя пришел к выводу, что возможны разные типы выпуклых многогранников с единичными ребрами, все грани которых - правильные многогранники. Для одних объем, заведомо больше объема любого из многогранников из ММ74, а для других - наоборот меньше.
Кто прав?


========= 166 ==========

ММ166 (3 балла)

Для каждого из натуральных чисел от 1 до 10000000000 находят знакочередующуюся сумму всех натуральных делителей, упорядоченных по возрастанию (делитель 1 берется со знаком минус).
Сколько отрицательных и сколько нечетных чисел при этом получится?


========= 167 ==========

ММ167 (4 балла)

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


========= 168 ==========

ММ168 (5 баллов)

Существует ли многогранник, у которого ровно:
2 диагонали;
5 диагоналей;
7 диагоналей?


========= 169 ==========

ММ169 (6 баллов)

Для каждого натурального числа n обозначим $s(n)=\frac{\varphi(\sigma(n))}{\sigma(\var\phi(n))}$, где $\varphi(n)$ - функция Эйлера, а $\sigma(n)$ - сумма натуральных делителей числа $n$. Может ли $s(n)$ быть:
а) меньше $\frac1{50}$
б) больше 7?


========= 170 ==========

ММ170 (8 баллов)

Прямоугольный параллелепипед склеили из единичных некрашеных кубиков. После этого три грани параллелепипеда покрасили в красный цвет. Остальные три грани покрасили в синий, желтый и зеленый цвета (по одной в каждый цвет).
Оказалось, что некрашеных кубиков в два раза больше, чем кубиков, имеющих, по крайней мере, одну красную грань. Количества кубиков, имеющих хотя бы одну синюю (желтую, зеленую) грань также являются делителями количества некрашеных кубиков.
Найти объем параллелепипеда.

[VAL]

Сбылось! Математический марафон возвращается! И это не первоапрельская шутка.

Тематический конкурс, традиционно проходящий в рамках тура, посвящен арифметике. В зачет конкурса идут первые 5 задач тура. "Садистская" задачка ММ180, по сути, тоже арифметическая. Но я счел ее слишком сложной для конкурса. (Возможно просто не нашел более простого решения.)

Познакомиться с решениями задач XVIII-го тура и обсудить их можно здесь.

========= 171 ==========

ММ171 (А-1) (5 баллов)

Вася, Петя, Коля и Федя хвалились параллелепипедами, которые они склеили из единичных кубиков. Васин параллелепипед имел размеры $a\times b\times c$. Петин - $(a+1)\times b\times c$, Колин - $(a+1)\times (b+1)\times c$, а Федин - $(a+1)\times (b+1)\times (c+1)$.
- Зато у моего параллелепипеда диагональ целочисленная - сказал Вася.
- Подумаешь! У моего тоже диагональ целочисленная - заявил Петя.
- И у моего - заметил Коля.
- И у моего тоже - не отстал от товарищей Федя.
Найти максимально возможное количество честных среди перечисленных мальчиков.


========= 172 ==========

ММ172 (А-2) (5 баллов)

Доказать, что существует бесконечно много хитовых abc-троек, таких что c является степенью пятерки.

Примечание:
Тройка натуральных чисел $a,b,c$ называется хитовой abc-тройкой, если $a+b = c$, $GCD(a,b) = 1$ и $c > rad(abc)$.
Примечание к примечанию:
Пусть $n = p_1^{\alpha_1}\dots \p_k^{\alpha_k}$, тогда $rad(n) = p_1\dots p_k$

========= 173 ==========

ММ173 (А-3) (5 баллов)

Решения принимаются, по крайней мере, до 5.05.13

Последовательность состоит из натуральных чисел, представимых в виде суммы четырех своих (попарно различных) делителей, расположенных в естественном порядке. Найти стомиллиардный член этой последовательности.

========= 174 ==========

ММ174 (А-4) (7 баллов)

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

Примечание:
Система счисления десятичная.

========= 175 ==========

ММ175 (А-5) (8 баллов)

Натуральное число n назовем g-2-числом, если число 2n, записанное в системе счисления c основанием g получается из n перестановкой цифр. Какие основания встречаются (в натуральном ряду) чаще: те, для которых существуют трехзначные g-2-числа, или те, в которых нет трехзначных g-2-чисел?

Примечание:
Расcматриваются позиционные системы счисления с натуральными основаниями $g>1$.

========= 176 ==========

ММ176 (5 баллов)

Сколько точек экстремума, не являющихся точками разрыва, имеет функция $f(x) = \{x\}+\{x^2\}+\{x\}^2$ ?

Примечание:
$\{x\}$ - дробная часть числа $x$.

========= 177 ==========

ММ177 (6 баллов)

В розыгрыше кубка мира участвуют 128 равных по силе шахматистов. 10 из них представляют Россию, 8 - Украину. После жеребьевки в первом раунде встречаются №1 и №2, № 3 и №4, ..., №127 и №128. Во втором раунде победитель первой пары встречается с победителем второй, победитель третьей - с победителем четвертой и т. д. Российским шахматистам по жребию достались номера 1, 9, 17, 25, 33, 41, 49, 57, 65 и 73; украинским - 2, 18, 34, 50, 66, 82, 98, 114.
За первое место выплачиваются призовые - 200000 долларов, за второе - 10000 долларов.. За остальные места призовые не выплачиваются.
Какой финал более вероятен: чисто российский или чисто украинский?
Каковы российское и украинское призовые мат. ожидания?


========= 178 ==========

ММ178(Оладьи на сковородке) (9 баллов)

В единичный круг поместим (без наложений) $k$ кругов одинакового радиуса. Обозначим через $S_k$ максимальное значение площади этих $k$ кругов. Расставить числа $S_1,S_2\dots, S_{12}$ в порядке возрастания.


========= 179 ==========

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

Имеется 11 монет: 2 золотых; 4 серебряных; 5 бронзовых. Известно, что одна золотая, одна серебряная и 2 бронзовых монеты - фальшивые. Все настоящие монеты равны по весу. Все фальшивые тоже равны по весу, но легче настоящих.Золотые, серебряные и бронзовые отличаются друг от друга по внешнему виду. За четыре взвешивания на чашечных весах без гирь определить фальшивые монеты.

========= 180 ==========

ММ180 (13 баллов)

Назовем натуральное число "трижды нечетным", если само число, сумма его делителей и сумма суммы его делителей нечетны. Может ли "трижды нечетное" число быть кратно 821?