Интересные задачи по математике

23 ноября 2011

Разбор задачи ММ141 Математического Марафона

======= 141 ========

ММ141 (3 балла)

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

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

Решение

Проще всего найти подходящее число, взяв достаточно большое (больше $10^9$ ) простое число $p$ так, чтобы $p^2+p+1$ тоже было простым. Тогда в качестве $n$ подойдет $p^2$ .
Наименьшее подходящее $p=1000003271$ . Тогда $n=1000006542010699441$ , $\sigma(\sigma(n))=1000006543010702714$ и $\frac{\sigma(\sigma(n))}n\approx 1.000000000999997$ .

Обсуждение

Не обязательно добиваться простоты числа $p^2+p+1$ . Достаточно, чтобы оно не имело малых простых делителей.
Например, iPhonograph взял $n=252097801217^2$ . Тогда $\sigma(n)=53840489083\cdot 1180399778329$ и $\sigma(\sigma(n))<1.000000001n$ .
Эта идея - использовать отсутствие малых множетелей вместо простоты - позволила Андрею Халявину доказать то, что, по сути, было очевидно и остальным участникам. А именно: для любого $M$ найдутся натуральные $n$ такие, что $\sigma(\sigma(n))<n(1+\frac1M)$ .
В самом деле, большинству участников (и ведущему) представляется очевидным, что существует бесконечно много простых $p$ таких, что $p^2+p+1$ тоже просто. Но "представляется очевидным" - не доказательство.
Андрей же доказал, что для каждого достаточно большого простого числа $p$ найдется показатель степени $k$ (ну очень большой!) такой, что $\sigma(p^k)$ не имеет малых делителей. И отсюда получить требуемое утвержденеие.

Гораздо более интересной, чем ММ141 является такая задача: Существуют ли натуральные числа $n>1$ такие, что $\sigma(\sigma(\sigma(n)))<1.5n?$
Но эту задачу мне решить не удалось. Ясно, что необходимым (но недостаточным) условием является существование такого натурального $n,$ что числа $n, \ \sigma(n), \ \sigma(\sigma(n))$ - нечетны.
Единственный извесстный мне нетривиальный пример дает число $n=81$ .

Награды

За правильное решение задачи ММ141 Алексей Волошин, Сергей Половинкин, Николай Дерюгин, Евгений Гужавин, iPhonograph, Sirion и Анатолий Казмерчук получают по 3 призовых балла. За правильное решение более общей задачи Андрей Халявин получает 5 призовых баллов. За верные идеи (не доведенные до конца) Александр Ларин и Кирилл Веденский получают 2 и 1 балл, соответсвенно.

Эстетическая оценнка задачи 4 балла

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

29 мая 2011

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

Владимир Лецко начинает новый тур Математического Марафона. От меня в этот раз в нём всего одна задача, так что буду осуществлять в основном информационную поддержку.
Задачи очень интересные, за короткой формулировкой открывается широкий простор для мысли. Есть, чем заняться на каникулах :)

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

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

Решения принимаются до 10.09.11

ММ141 (3 балла)

Существуют ли натуральные числа n, большие единицы, такие, что
$\sigma(\sigma(n))<1.000000001n$

$\sigma(n)$ - сумма натуральных делителей числа n.

==================================
Решения принимаются до 14.09.11
ММ142 (4 балла)

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

Найти n.
==================================

В Тематическом конкурсе тура - вновь комбинаторная геометрия

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

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

Решения принимаются до 18.09.11
ММ143 (КГ-11) (4 балла)

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

Решения принимаются до 23.09.11
ММ144 (5 баллов)

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

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

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

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

Решения принимаются до 27.09.11

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

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

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

Решения принимаются до 1.10.11

ММ146 (4 балла)

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

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

Решения принимаются до 7.10.11

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

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

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

Решения принимаются до 15.10.11

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

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

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

Решения принимаются до 22.10.11

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

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

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

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

Решения принимаются до 31.10.11

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

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

Разборы задач математических олимпиад на сайте

01 января 2011

С Новым Годом!!!

Уважаемые читатели! Поздравляем вас с Новым Годом!

2010 год для развития проекта «Приглашение в мир математики» оказался очень продуктивным. Общение с вами перешло из переписки по электронной почте в блоги. Там вы почти каждый день можете увидеть новый интересный математический факт, новую задачу и её решение.

В этом году вы начали участвовать в наших математических конкурсах. Прошли три интернет-олимпиады и запущена четвёртая. Кроме того, проводились математические маневры – первый в истории конкурс, в котором сочетаются принципы пошаговой стратегии и олимпиады по математике.

На 2011 год планы не менее смелые. Во-первых, мы будем продолжать готовиться к олимпиаде Кенгуру-2011 и к внешнему оцениванию по математике ЗНО-2011. Кроме того, скоро появятся новые логические флеш-игры. И, разумеется, будут продолжаться математические конкурсы и публикация интересного из мира математики.

Желаем вам в новом году счастья, здоровья и чтобы все задачи решались красиво и легко!

20 декабря 2010

Четвёртая открытая интернет-олимпиада по математике: XIV тур Математического марафона

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

На каникулах будет чем заняться :)

13 ноября 2010

Математические Маневры: AfterParty

В игре сделано 14 ходов, это заняло 23 дня реального времени, и участники пришли к согласию, что соревновательную часть первых Математических маневров стоит завершить.

По итогам игры I место завоевала команда Портала естественных наук E-Science.ru!
Ею контролируется 73% территории острова и заработано 652 балла.

ІІ места удостоена команда Форума умных людей Nazva.net!
Они первыми вступили в маневры и продержались на острове до конца игры, контролируя к её завершению 18% территории и имея 617 баллов.

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

На IV месте - вольный стрелок Armless, заработавший 32 балла при высадке на Мысе простых чисел.

На V месте - Евгений, занимающий сейчас Квадратный пляж и имеющий 25 баллов.

VI место - команда форума Логические задачи и головоломки Smekalka.pp.ru. Включившиеся в Маневры со старта и не закрепившиеся на острове, они, почему-то, не использовали преимущество своего положения и не атаковали прибрежные провинции в середине игры. В итоге на счету 24 балла.

VII место по счёту, но не по значению - вольный стрелок Tifuera, заработавший 10 баллов при высадке на Мыс простых чисел. Ослабленная его атакой оборона мыса впоследствии не смогла противостоять штурму Armless'a.

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

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

Математические маневры

Игра "Математические маневры" представляет собой объединение пошаговой стратегии и олимпиады по математике. Имеется математический остров, вот он:

Карта его состоит из 11 областей. В каждой области есть несколько укреплений – задач. Игроки решают задачи и получают контроль над областью. Чтобы удержать область, нужно после захвата укрепить её своими задачами. Победит тот, кто захватит весь остров.

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

Как принять участие в маневрах?
Для этого в комментарии к заглавному посту сообшите свою форму участия: личную или командную, желаемый цвет (лучше в RGB-формате) и начинайте штурмовать укрепления. Если у вас нет территорий на острове, можете решать задачи в любой прибрежной области, если же есть, то в областях, смежных с контролируемыми. Чтобы перейти к области, щёлкните по ней на карте острова.

Область переходит под контроль игрока, решившего последнюю нерешённую задачу в ней.
Игра состоит из ходов, 1 ход занимает двое суток. В течение первых суток игроки отправляют решения задач как комментарии к соответствующему посту. С началом вторых суток комментарии открываются и обороняющаяся сторона сообщает об успешности взятия укреплений.

В течение всего следующего хода после захвата игрок должен представить организаторам задачи (с решениями) для укрепления. Их можно отправлять в течение первого полухода как комментарии (они будут скрыты) или на почту intelmath@narod.ru или в личные сообщения на форумах. В одной области можно разместить до 3 задач.

Задачи должны быть на темы, изучающиеся в средней школе или на 1 курсе не физико-математических вузов. Тематика задач области не обязательно должна совпадать с её названием.

Баллы:
Решение задачи первым: 5 баллов
Решение задачи не первым (но в течение того же хода): 3 балла
Захват области: 10 баллов
За каждый ход удерживания области: 1 балл
За составление задачи 7 баллов.

Текущие баллы:
Smekalka - 24
Nazva - 83+85=168+58=226+34=260+54=314+51= 365+35=400+38=438+69=507+64=571+13=584+16=600+16=616+1=617
Zhekas - 34+25=59+30=89+36=125+41=166+7=173
E-science.ru - 65+114=179+76=255+71=326+61=387+79= 466+44=510+53=563+43=606+28=634+18=652
Tifuera - 10
Mudrec - 0
Armless - 15+17=32
DMA - 0
Евгений 5+5=10+15=25

12 ноября 2010

Конкурс магических квадратов

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

Нетрадиционные пандиагональные квадраты

Конкурс начинается 12 ноября текущего года и продлится до 18.00 мск. 12 января 2011 г.
В конкурсе могут принять участие все желающие.
Можно решить одну или несколько из предложенных задач.
Решения присылайте на e-mail: natalimak1@yandex.ru или в личные сообщения на форуме dxdy.ru.
Если найдены лучшие решения одной и той же задачи, их тоже надо присылать.
Общее требование ко всем задачам: каждый построенный квадрат должен состоять из различных чисел.

Лучшие решения будут представлены по окончании конкурса.

О магических квадратах, простых числах и числах Смита можно посмотреть в Википедии.
Вопросы по задачам можно задавать в [2], а также в личные сообщения на форуме dxdy.ru.

Задача №1

Известен наименьший пандиагональный квадрат 6-го порядка из последовательных простых чисел.
Смотрите последовательность A073523 в OEIS.

Построить наименьшие пандиагональные квадраты из последовательных простых чисел порядков 4 и/или 5.

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

Задача № 2

Известный пандиагональный квадрат 6-го порядка из чисел Смита имеет наименьшую магическую константу 5964.
Вот этот квадрат:

22	2902	94	1633	202	1111
265	634	562	391	1894	2218
1642	1219	1678	985	319	121
355	526	913	1966	346	1858
2785	166	922	535	1282	274
895	517	1795	454	1921	382

Авторы квадрата С. Беляев и Н. Макарова.

Доказать, что данный квадрат является наименьшим или построить пандиагональный квадрат 6-го порядка из чисел Смита с меньшей магической константой.

Задача № 3

Построенный В. Павловским пандиагональный квадрат 7-го порядка из простых чисел имеет магическую константу 1649. Этот квадрат является регулярным и построен с использованием примитивного квадрата.
Доказать, что:
а) данный квадрат является наименьшим среди регулярных пандиагональных квадратов 7-го порядка из простых чисел;
б) не существует нерегулярных пандиагональных квадратов 7-го порядка из простых чисел с меньшей магической константой.
Если а) и/или б) неверно, привести опровергающие примеры.

Примечание: о примитивных квадратах и регулярных пандиагональных квадратах см. [1].

Задача № 4

Для построения идеального квадрата 7-го порядка достаточно найти 7 последовательностей вида $a_i, a_{i+1}, a_{i+2}, a_{i+3}, a_{i+4}, a_{i+5}, a_{i+6}, i = 1, 8, 15, ..., 43$ , удовлетворяющих следующим условиям:

$a_i + a_{i+6} = a_{i+1} + a_{i+5} = a_{i+2} + a_{i+4} = 2a_{i+3}, a_1 + a_{43} = a_8 + a_{36} = a_{15} + a_{29} = 2a_{22}$

Пример идеального квадрата 7-го порядка из последовательностей (простых чисел), удовлетворяющих указанному условию:

20233	27799	30637	37123	44017	7753	13759
43093	7717	13723	19309	26863	34429	36187
25939	33493	39979	42157	6793	13687	19273
5857	12763	19237	25903	32569	39043	45949
32533	38119	45013	9649	11827	18313	25867
15619	17377	24943	32497	38083	44089	8713
38047	44053	7789	14683	21169	24007	31573

Магическая константа квадрата равна 181321. Автор квадрата Н. Макарова.

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

Примечание: пандиагональный квадрат называется идеальным, если он обладает свойством ассоциативности.

Задача № 5

Известный на сегодня пандиагональный квадрат 7-го порядка из чисел Смита имеет очень большую магическую константу – 696745.

Вот этот квадрат:

37678	778	70582	381802	202	25618	180085
381298	23962	1921	217642	382	54814	16726
180346	54418	958	16222	405058	265	39478
39982	381361	37822	2182	234382	562	454
56218	180526	58	24214	16285	418918	526
517	53842	381622	54562	2362	180022	23818
706	1858	203782	121	38074	16546	435658

Автор квадрата Н. Макарова.
Для сравнения: магические константы пандиагональных квадратов из чисел Смита порядков 4 – 6 соответственно: 14560 (наименьшая), 8318 (наименьшая), 5964.
Представленный квадрат построен с использованием примитивного квадрата.

Применяя этот же алгоритм или разработав другой, построить пандиагональный квадрат 7-го порядка из чисел Смита с меньшей магической константой.

Задача № 6

Не найдено ни одного пандиагонального квадрата 9-го порядка из простых чисел. Не разработан алгоритм для такого построения. Разработан алгоритм построения идеального квадрата 9-го порядка, но идеальный квадрат из простых чисел пока не найден.

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

Задача № 7

В [2] приведены примеры построения пандиагональных квадратов порядков 11 и 13 из простых чисел с использованием примитивных квадратов. Используя этот алгоритм или разработав другой, построить пандиагональный квадрат 17-го порядка из простых чисел с любой, по возможности наименьшей, магической константой.

1. THE ALGEBRAIC THEORY OF DIABOLIC MAGIG SQUARES. By Barkley Rosser and R. J. Walker
http://narod.ru/disk/23700701000/Rosser1939.rar.html

Примечание: статья переведена на русский язык С. В. Беляевым. Перевод здесь: http://svb.hut/DOWN/Rosser_ru.pdf

2. Тема “Магические квадраты” topic12959.html