Форум умных людей

Давно хочу поделиться задачкой, которую я придумал еще школьником. Для dxdy.ru она слишком несерьезная (здесь был оффтоп, который я удалил), но тут должна прийтись в самый раз.
Показать скрытый текст

---

В простейшем варианте, решаемом в уме за несколько минут, задача такая: какое максимальное значение может иметь НОД 2 двузначных чисел, отличающихся порядком цифр. Несмотря на свою простоту, задачка зацепила меня тем, что интуитивно я не смог догадаться об ответе, хотя, казалось бы, что может быть неизвестного в двузначных числах.
Естественно, задача легко обобщается: какое максимальное значение может иметь НОД k n-значных чисел, отличающихся порядком цифр.
В этой задаче мне кажется естественным понимать n-значные числа в расширенном смысле, разрешая 0 в качестве первой цифры, но, если хотите, можете ограничиться только «настоящими» n-значными числами.
Сам я (вроде бы) решил задачу для n=3 и всех k (т. е. k=2,3,4,5,6) и для k=2 и всех n (и даже послал эту последовательность в OEIS). Кроме того, довольно очевидны соображения для случаев, когда k максимально возможное для данного n или близко к нему.

 :roll:

Если возможно использование двухзначных цифр с одинаковыми цифрами, то напрашивается ответ 22.
Если с разными цифрами, то  ???

Интересно!
А почему думаете, что для dxdy несерьёзная. Там же тоже люди разными аспектами математики интересуются :)

Тема перестановки цифр мне очень близка, когда проводил интернет-олимпиаду, включил туда задачу о перестановке предпоследней цифры (http://intelmath.narod.ru/olymp1sol3.html).

Про 2-значные, пока вариант навскидку: 9. Проверю, может, удастся улучшить

Не понял, что у Вас k и что n? Просто числа то k-значные, то n-значные

Илья, так дело в том, что числа, для которых вычисляется нОД, должны состоять из одинаковых цифр. НОД (18, 81)=9

Числа n-значные, а k — это число чисел :)
Насчет магических квадратов и серьезности — не надо воспринимать то, что я пишу, слишком серьезно… Не только в данном случае, но и вообще, если только я не оговариваюсь, что пишу серьезно.
Пишу серьезно: если я кого-то обидел, прошу прощения.
Когда я пишу о числах, отличающихся порядком цифр, я имею в виду отличающиеся числа :)

отличающиеся или неотличающиеся, НОД будет все равно равен наименьшему положительному числу при вычитании с большего меньшее..
или я что-то пропутсил? ))
здаёмси!

Ну вот, например, НОД (19, 91)=1

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

Брута поднял глаза. На самом верху башни металлическими полосами был закреплен сверкающий на солнце большой диск.
– Что это? – прошептал он.
– Причина, по которой у Омнии больше нет флота, – ответил Ом. – Вот почему так полезно иметь под рукой нескольких философов. Они размышляют себе на тему «Истина – это красота, или красота – это истина?» или «Производит ли шум падающее в лесу дерево, если никто его не слышит?», а потом, когда ты уже решишь, что они вообще вот-вот обслюнявятся, один из них и говорит этак невзначай: «Интересной демонстрацией принципов оптики будет размещение на высоком месте тридцатифутового параболического зеркала, способного направлять солнечные лучи на вражеский флот». Философам приходят в голову удивительные идеи. А незадолго до этого в целях демонстрации принципа рычага было изобретено замысловатое устройство, способное метать шары горящей серы на расстояние в две мили. А до этого, насколько я помню, было придумано какое-то подводное судно, которое втыкало в днища кораблей заостренные бревна.

"Мелкие Боги", Т.Пратчетт

Достойный ответ. :good3:

:)

Подумал ещё над задачей: а ведь одной тройкой из девятки можно пожертвовать, зато получить четвёрку: НСД(84, 48)=12