Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№98

Предлагаемая задача не входит в тематический конкурс. Результат учитывается только в основном Маpафоне.

Конкурсная задача №98 (7 баллов)

Васю Пупкина заслали в тыл врага с целью выявить секретный код, ввод которого предотвратит термоядерный взрыв.
Вася незамеченным проник в святая святых и сфотографировал секретный код на мобильник. Но, пробираясь к своим, Вася потерял мобильник и теперь пытается вспомнить код.
- Помню только, что код состоял из трех чисел, расположенных строго в порядке возрастания - удрученно докладывает Вася руководству.
- А какие числа: двузначные, трехзначные,..?
- Не помню…
- Вася, но ведь ты по образованию математик! Вспомни, может быть, среди чисел были какие-нибудь особенные: квадраты, кубы,..
- Нет, таких не было, но я припоминаю, что сложив сумму квадратов цифр одного из этих чисел с суммой кубов цифр другого я получил сумму этих двух чисел.
- Это уже кое-что! Но код можно вводить только один раз. В случае неверного кода взрыв неминуем. Вспоминай дальше.
- Вспомнил! Эти числа могли служить количествами вершин, граней и, соответственно, ребер некоторого выпуклого многогранника. Я даже мысленно представил себе подходящий многогранник.
- Хорошо. Дальше.
- Так… Каждое из чисел представлялось в виде суммы двух натуральных квадратов.
- Что еще? Ах, да! По крайней мере два из них были простыми…
- А еще У двух чисел были одинаковые значения функции Эйлера…
- Все! Больше ничего не помню.

1. Помогите Васе спасти человечество.
2. Какие из пришедших на память Васе соотношений избыточны?

Решение

Приведу немного подкорректированное решение Эдварда Туркевича.

1. Ответ: 401, 409, 808
Простой анализ соотношения с цифрами показывает, что числа состоят не более чем из 4 цифр. Заложив в программку все соотношения, получим единственную тройку (401, 409, 808).

2. Ищем излишние условия:
Убирая в программке по одному соотношению, получаем:
а) условие «строго в порядке возрастания» необходимо - (41, 41, 80);
б) условие «не квадраты» необходимо - (41, 61, 100);
в) условие «не кубы» излишнее;
г) условие «условия с цифрами» необходимо - (97, 113, 208);
д) условие «многогранник» необходимо - (41, 61, 82);
е) условие «представление в виде суммы двух натуральных квадратов» излишнее;
ж) условие «по крайней мере два простые» излишнее;
з) условие «у двух чисел одинаковые значения функции Эйлера» необходимо - (50, 53, 101).

Условие «не кубы» излишнее вовсе, а одно из условий «представление в виде суммы двух натуральных квадратов» и «по крайней мере два простые» необходимо - (13, 21, 32)

Все указанные тройки удовлетворяют условию «многогранник».
Например, тройку (401, 409, 808) можно получить, поместив на боковые грани 392-угольной пирамиды 8 низеньких (чтобы выпуклость сохранилась) тетраэдров.

Обсуждение

Используя все (включая избыточные) условия задачи, можно существенно сократить (но не исключить) перебор.

Ориентируясь на условие д), Обозначим исходные числа через В, Г и Р соответсвенно.

Из г) следует, что числа не более чем четырехзначны. Поэтому сумма квадратов цифр одного из них, сложенная с суммой кубов цифр другого, не превышает 4*93 + 3*92 + 82 = 3223. Но тогда сумма чисел не превышает 3223. А для чисел, не превышающих 3223, сумма квадратов цифр одного из них, сложенная с суммой кубов цифр другого, не превышает 23 + 3*93 + 1+3*92 = 2439. Учитывая, что не только каждое слагаемое, но и сумма не должны теперь превышать 2439, можно показать, что В не превосходит 999, а Г - 1299.

Из условий ж) и з) можно заключить, что В простое, а среди Г и Р ровно одно составное. В противном случае, значения функции Эйлера всех трех чисел будут различны.

Условие е) позволяет перебирать в качестве потенциальных В только простые вида 4k+1…

Выясним теперь связь между В, Г и Р, вытекающую из д). Наиболее очевидное соотношение Р = В + Г -2, вытекающее из теоремы Эйлера, заметили все участники Марафона. Но часть из них ограничились лишь этим соотношением. На самом деле оно не является достаточным. Каждая грань многогранника ограничена не менее, чем тремя ребрами. При этом каждое ребро учитывается дважды. Поэтому 3Г ≤ 2Р = 2(В + Г - 2). Откуда Г ≤ 2В - 4. (Этого соотношения тоже не достаточно для существования многогранника, но достаточно для решения задачи.)

Игнорирование последнего соотношения частью марафонцев позволили им рассмотреть, «многогранники», например, с 43-я вершинами, 98-ю гранями и 139-ю ребрами, что в свою очередь привело их к выводу о необходимости условия е). Аналогично «многогранник» с с 317-ю вершинами, 634-я гранями и 949-ю ребрами «доказывает» необходимость условия ж).

Многие конкурсанты рассматривали условия б) и в) как одно. Я считал такой подход правильным (как и подход тех, кто эти условия разделил) ;-)

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

Алексей Волошин заинтересовался достаточными условиями существования многогранников с заданными количествами вершин, граней и ребер. Добавим, к двум уже имеющимся соотношениям (B+Г-Р = 2 и 2Р ≥ 3Г) еще одно. Поскольку из каждой вершины выходит не менее трех ребер и при этом каждое ребро учитывается дважды, 2P ≥ 3В. Оказывается трех этих ограничений вполне достаточно. Во-первых, легко убедиться, что наименьшая тройка, для которой проходят все три соотношения: В = Г = 4, Р = 6. Пусть теперь натуральные числа В, Г, Р удовлетворяют всем трем соотношениям. Если В = Г, то искомым многогранником будет В-1-угольная пирамида. Пусть Г больше В и Г-В = k. Тогда возьмем В-1-k-угольную пирамиду (такая пирамида существует, поскольку из наших условий следует Г ≤ 2В - 4, откуда В-1-k не меньше 3). На k треугольных гранях этой пирамиды как на основаниях построим маленькие треугольные пирамидки (если граней исходной пирамиды не хватит, то воспользуемся гранями уже построенных пирамидок). Ясно, что полученный многогранник будет иметь требуемые характеристики. Если же В больше Г, то мы наоборот будем отрезать уголки от основонаия В-1-k-угольной пирамиды (или вновь возникшие трехгранные уголки) так, чтобы на каждом шаге наращивать число граней на одну, вершин на две, а ребер на три.

Награды

За решение задачи 98 Алексей Волошин и Влад Франк получают по 7 баллов, Эдвард Туркевич - 6 баллов, Алексей Извалов - 5 баллов, Андрей Халявин и Виктор Михайлов - по 4 балла, Николай Дерюгин и Усимов - по 3 балла.

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


 

 


Страница: [[marathon:problem_98]]

marathon/problem_98.txt · Последние изменения: 2019/07/04 12:30 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006