Задача 65675

Темы:    [ Десятичная система счисления ] [ Правило произведения ] [ Принцип Дирихле (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Евдокимов М.А.

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

Решение 1

  Оценим число 2016-значных квадратов. Их не меньше чем  10^2016/2 – 10^2015/2 – 1 > 10¹⁰⁰⁰.
  Различных наборов из 2016 цифр (без учёта их порядка) не больше, чем наборов, в которых каждая цифра встречается не более 2016 раз, то есть 2017¹⁰. Значит, найдётся такой набор из 2016 цифр, перестановками которых можно получить не менее чем  10¹⁰⁰⁰ : 2017¹⁰ > 10¹⁰⁰⁰ : 10¹⁰⁰ = 10⁹⁰⁰  квадратов, и уж тем более 2016.

Решение 2

  Предъявим такое 2016-значное число в явном виде. Рассмотрим все 1008-значные числа вида  x_a,b = 4·10¹⁰⁰⁷ + 10^a + 10^b,  где  1007 > a > b ≥ 0
2a ≠ b + 1007.

Заметим, что  (x_a,b)² = 16· 10²⁰¹⁴ + 8·10^1007+a + 8·10^{1007 +b} + 10^2a + 2·10^a+b + 10^2b.   (1)
  В силу условия  1007 > a > b  имеем  2014 > 1007 + a > 1007 + b > a + b > 2b,  2014 > 1007 + a > 2a > a + b > 2b.
  Из этих неравенств, а также из условия  2a ≠ b + 1007  следует, что все слагаемые в правой части равенства (1) соответствуют разным цифрам числа (x_a,b)². Следовательно, для всех допустимых a, b число (x_a,b)² состоит из фиксированного набора цифр: трёх единиц, одной двойки, одной шестёрки, двух восьмёрок и 2009 нулей.
  Всего допустимых пар чисел a, b не меньше, чем  1007·1006 : 2 – 1007 = 1007·502. 
  Значит, из любого числа вида (x_a,b)² перестановкой цифр можно получить  1007·502 > 2016  разных 2016-значных полных квадратов.

Ответ

Существует.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Год	2016
Номер	79
класс
Класс	9
задача
Номер	5