• Правила марафона
• Рейтинг участников
• Архив Марафона

Внимание! В условии задачи ММ160 исправлена опечатка

Продолжается 16-й тур Математического марафона

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

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

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

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

Ведущий Марафона — Vladimir letsko

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

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

Конкурсная задача ММ151 (ТГ-1) (4 балла)

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

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

Конкурсная задача ММ152 (6 баллов)

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

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

Конкурсная задача ММ153 (ТГ-2) (4 балла)

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

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

Конкурсная задача ММ154 (5 баллов)

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

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

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

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

Конкурсная задача ММ155 (4 балла)

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

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

Конкурсная задача ММ156 (ТГ-3) (5 баллов)

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

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

Конкурсная задача ММ157 (6 баллов)

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

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

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

Конкурсная задача ММ158 (ТГ-4) (7 баллов)

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

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

Конкурсная задача ММ159 (6 баллов)

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

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

Конкурсная задача ММ160 (ТГ-5) (10 баллов)

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

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

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

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

Решение

Еще раз приведу решение Андрея Халявина.

Расставим черные бусины в углы многоугольника, которые меньше развернутого, и белые - в углы больше развернутого. Конфигурация черных и белых бусин однозначно определяет цвет сторон. В обратную сторону однозначность нарушается, только если все стороны зеленые. Но возникающие при этом две две конфигурации переводятся друг в друга поворотом. Таким образом задача свелась к подсчету числа ожерелий из бусин двух цветов. При этом черных бусин не меньше трех, так как в многоугольнике не меньше трех углов, меньших развернутого. (Для доказательства достаточно рассмотреть выпуклую оболочку исходного многоугольника.) С другой стороны, любая конфигурация, в которой не менее трех черных бусин, очевидно, возможна. (Достаточно взять правильный 20-угольник и вдавить внутрь вершины, соответствующие белым бусинам.) Подсчитаем количество черно-белых ожерелий без учета ограничения, что черных бусин не менее трех. Воспользуемся леммой Бернсайда. В качестве группы преобразований G выступает группа диэдра, состоящая из 20-и симметрий и 20-и поворотов (включая тождественный). Если g из G - симметрия, ось которой проходит через две бусины, то для g имеется 2¹¹ неподвижных конфигураций. Если же ось симметрии не проходит через бусины, для g имеется 2¹⁰ неподвижных конфигураций. Значит, вклад симметрий 10(2¹¹+2¹⁰). Для поворотов имеем сумму . Итого получаем (10(2¹¹+2¹⁰)+2²⁰+2¹⁰+2*2⁵+4*2⁴+4*2²+8*2)/40=27012.

Очевидно, что существует ровно одно ожерелье из белых бусин, одно ожерелье с одной черной бусиной и 10 ожерелий с двумя черными бусинами. Поэтому окончательно получаем 27012-1-1-10=27000 классов 20-угольников.

Обсуждение

Задача о подсчете числа ожерелий широко известна. Наиболее подробное и доступное изложение (среди известных мне) можно найти в книге Дж. Андерсона “Дискретная математика и комбинаторика”.

Разумеется, вместо 20-угольников можно было рассматривать произвольные n-угольники. Число 20 привлекло меня красотой ответа, являющегося в этом случае круглым числом и, к тому же, полным кубом!

С помощью леммы Бернсайнда можно вывести и явную формулу для подсчета ожерелий, в которых число бусин каждого цвета фиксировано. Например, число черно-белых ожерелий из n бусин, среди которых и m черных, подсчитывается по формуле . Вывод этой формулы можно посмотреть, например, здесь: http://www.omsu.omskreg.ru/vestnik/articles/y1998-i2/a021/article.html При n = 20, суммируя по всем m ≥ 3, вновь получим 27000.

Интересно, что если не различать полусвободные и зажатые стороны, задача станет сложнее. Пусть свободным сторонам соответствуют белые бусины, а прочим - красные. Если сторона не является свободной, то хотя бы одна из соседних с ней сторон тоже не является свободной. Поэтому красная бусина не может быть окружена белыми. Таким образом, при n > 5 интересующее нас число классов равно количеству ожерелий, которые можно составить из n белых и красных бусин, при условии, что никакая красная бусина не окружена белыми. Я посчитал количество классов для всех n ≤ 18 (например, при n=18 получается 799 классов), но общей формулы мне вывести не удалось.

В заключение еще об одной классификации, для которой мне не удалось вывести общую формулу для подсчета числа классов. Будем считать эквивалентными n-угольники, у которых поровну как внутренних, так и внешних диагоналей. Можно показать, что число классов не превосходит (n⁴-10n³+39n²-70n+56)/8. Но, начиная с n=6, эта оценка завышена.

Награды

За правильное решение задачи ММ150 Алексей Волошин, Анатолий Казмерчук и Андрей Халявин получают по 12 призовых баллов. Сергей Половинкин получает 11, Виктор Филимоненков - 9 призовых баллов.

Эстетическая оценка - 4.7 балла

Разбор задачи ММ150 подготовил Владимир Лецко