>>6066873Вообще, оно решается перебором, но не таким. Тут перебор на основе диаграмм Юнга.
Диаграмма Юнга - это несколько натуральных чисел, расположенных по неубыванию. Сумма этих чисел называется весом диаграммы. Количество чисел называется количеством строк диаграммы. Например, (10, 5, 4) - диаграмма веса 19 из трёх строк, (19) - веса 19 из одной строки, (15, 1, 1, 1, 1) - веса 19 из пяти строк. Диаграммы называются так потому, что их изображают клеточками как на пикрелейтед. Такой способ изображения позволяет очень быстро изобразить все диаграммы заданного веса из нужного количества строк: заполняем строки как можно большим количеством квадратиков, потом спускаем квадратики из верхних строк в нижние, пока это возможно.
Мы ищем трёхзначное число, попадающее под два условия. Сначала нам нужно найти такие три цифры a, b, c, что a+b+c = 20 - это первое условие. Потом - проверить найденные варианты вторым условием.
Числа a,b,c будем искать с помощью диаграмм Юнга веса 20 из трёх строк, причем в каждой строке не больше девяти клеточек (цифра не может быть больше 9). Все такие диаграммы - это (9, 9, 2), (9, 8, 3), (9, 7, 4), (9, 6, 5), (8, 8, 4), (8, 7, 5), (8, 6, 6), (7, 7, 6). Восемь вариантов. Можно было бы уже тестировать их вторым условием, но оптимизируем ещё немного.
Заметим, что если a и b делятся на 3, но c не делится на 3, то a^2+b^2+c^2 не будет делиться на 3. Выкинем из рассмотрения все диаграммы, в которых два числа делятся на 3, а третье - не делится. Останутся (9, 7, 4), (8, 8, 4), (8, 7, 5), (7, 7, 6). Осталось всего четыре варианта - перебор успешно оптимизирован.
Дальше пользуемся признаками делимости на 3 и на 9. Число делится на 3 (на 9), если сумма его цифр делится на 3 (на 9).
9^2 + 7^2 + 4^2 = 146. Не делится на 3, не подходит.
8^2 + 8^2 + 4^2 = 144. Делится на 9, не подходит.
8^2 + 7^2 + 5^2 = 12. Подходит.
7^2 + 7^2 + 6^2 = 134. Не делится на 3, не подходит.
Итак, искомое трёхзначное число может состоять только из цифр 8, 7 и 5. Их можно расставить в числе в произвольном порядке.
Ответами будут числа 875, 857, 785, 758, 587, 578.
От нас просят выбрать какое-нибудь одно. Возьмём 578 как самое маленькое.
>>6066883Да, меня мой опыт научил, что объяснять через деньги, товары и торговлю - обычно самый лучший способ что-то объяснить школоте. Все любят деньги.
