===== 71 ===== Результат пpедлагаемой задачи учитывается дважды:\\ В Большом Маpафоне и в мини-конкуpсе арифметических задач. ** Конкурсная задача №71 (А-1) ** (4 балла) Назовем n-значное натуральное число "замечательным", если оно равно сумме n-х степеней своих цифр. Конечно ли множеcтво замечательных чисел? Пpимечание:\\ Система счисления десятичная. ** Решение ** Самое маленькое n-значное число больше чем 10(n-1). Сумма n-х степеней цифр n-значного числа не превосходит n*9n.\\ Неравенство n*9^n < 10(n-1) равносильно неравенству 9*n < (10/9)(n-1). Поскольку показательная функция с основанием, большим 1, растет быстрее линейной, последнее неравенство верно для всех достаточно больших n (более точно, для всех натуральных n, больших 60). Таким образом, множество замечательных чисел конечно. ** Обсуждение ** Разумеется, оценка максимально возможного числа цифр замечательного числа, приведенная в решении, завышена. Ведь для чисел, значность которых превышает 60, уже самое маленькое из чисел с данным n превышает сумму n-х степеней цифр самого большого n-значного числа. Предлагая эту задачу, я рассчитывал, что марафонцы не только докажут конечность множества замечательных чисел, но и перечислят все эти числа. Явно ставить вопрос о нахождении всех замечательных чисел я не стал, чтобы не превращать задачу из несложной математической в громоздкую (по времени расчетов) информатическую.\\ Однако к моменту обнародования задачи у меня была готова программка для нахождения замечательных чисел и имелась уверенность в том, что она завершит перебор за реальное (хотя и достаточно большое) время. Но завершить перебор я не успел. В первые же часы после публикации Константин Кноп прислал мне ссылку на mathworld.wolfram.com (между прочим, часто посещаемый мной ресурс), где подробно обсуждаются замечательные числа. На самом деле, они называются нарциссическими числами или числами Армстронга (правда, иногда эти названия применяют лишь к трехзначным замечательным числам). Там же приведен и полный перечень этих чисел. Вот он: ^n ^base-10 n-narcissistic numbers^ |1 |1, 2, 3, 4, 5, 6, 7, 8, 9| |3 |153, 370, 371, 407| |4 |1634, 8208, 9474| |5 |54748, 92727, 93084| |6 |548834| |7 |1741725, 4210818, 9800817, 9926315| |8 |24678050, 24678051, 88593477| |9 |146511208, 472335975, 534494836, 912985153| |10 |4679307774| |11 |32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914| |14 |28116440335967| |16 |4338281769391370, 4338281769391371| |17 |21897142587612075, 35641594208964132, 35875699062250035| |19 |1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826| |20 |63105425988599693916| |21 |128468643043731391252, 449177399146038697307| |23 |21887696841122916288858, 27879694893054074471405, 27907865009977052567814, 28361281321319229463398, 35452590104031691935943| |24 |174088005938065293023722, 188451485447897896036875, 239313664430041569350093| |25 |1550475334214501539088894, 1553242162893771850669378, 3706907995955475988644380, 3706907995955475988644381, 4422095118095899619457938| |27 |121204998563613372405438066, 121270696006801314328439376, 128851796696487777842012787, 174650464499531377631639254, 177265453171792792366489765| |29 |14607640612971980372614873089, 19008174136254279995012734740, 19008174136254279995012734741, 23866716435523975980390369295| |31 |1145037275765491025924292050346, 1927890457142960697580636236639, 2309092682616190307509695338915| |32 |17333509997782249308725103962772| |33 |186709961001538790100634132976990, 186709961001538790100634132976991| |34 |1122763285329372541592822900204593| |35 |12639369517103790328947807201478392, 12679937780272278566303885594196922| |37 |1219167219625434121569735803609966019| |38 |12815792078366059955099770545296129367| |39 |115132219018763992565095597973971522400, 115132219018763992565095597973971522401| Этот же список можно обнаружить в онлайновой энциклопедии целочисленных последовательностей (http://www.research.att.com/~njas/sequences/A005188), а также во многих других местах. В общем, я в очередной раз "изобрел велосипед".\\ Конечно, прежде чем предлагать эту задачку, мне следовало нбрать в поисковике, например, число 28116440335967 и получить несколько сотен ссылок на числа Армстронга.\\ Слабым оправданием мне может служить лишь такой факт:\\ Лет пять назад я несколько раз постил в RU.GOLOVOLOMKA письмо, в котором допытывался у All'а, чем интересна четверка чисел "153, 370, 371, 407". Но никто из подписчиков (а пять лет назад в RU.GOLOVOLOMKA крутилось народу поболее, чем сейчас) так и не отозвался. Разумеется, 10, как основание системы счисления не уникально.\\ Вот перечень всех замечательных чисел для небольших оснований системы счисления b (но записанных в десятичной системе): ^b ^base-b narcissistic numbers^ |2 |1| |3 |1, 2, 5, 8, 17| |4 |1, 2, 3, 28, 29, 35, 43, 55, 62, 83, 243| |5 |1, 2, 3, 4, 13, 18, 28, 118, 289, 353, 419, 4890, 4891, 9113| Ясно, что однозначные числа будут замечательными в любой системе счисления.\\ Для b = 2 иных замечательных чисел не существует. Возникает вопрос: есть ли другие натуральные основания b, для которых не существует неоднозначных замечательных чисел? И еще вопрос: существуют ли натуральные числа, являющиеся неоднозначными замечательными сразу для нескольких оснований? ** Награды ** За правильное решение этой задачи Константин Кноп и Влад Франк получают по 5 призовых баллов. Они (разными путями) получили полный список замечательных чисел.\\ Сергей Аракчеев, Сергей Беляев, Дмитрий Бобровский, Андрей Богданов, Иван Козначеев, Алекс Кочарин, Евгений Машеров, Дмитрий Милосердов, Олег Полубасов, Виктор Филимоненков и Анатолий Казмерчук получают по 4 призовых балла.\\ За некоторые соображения по решению Стас Грицюк получает 1 призовой балл. ** Эстетическая оценка задачи - 2.4 балла ** ----