Найдите наибольший шестизначный палиндром, который делится на 15.

Step-by-step solution

1. 1

   Запишем общий вид шестизначного палиндрома. Любое такое число имеет вид

   $\overline{abccba}$

   где $a, b, c$ — цифры, причём $a\neq 0$. Таким образом, вместо шести свободных цифр остаётся только три — это сразу сокращает перебор с $900\,000$ чисел до $900$.

2. 2

   Разделим условие делимости. Так как $15=3\times 5$ и $\gcd(3,5)=1$, число делится на $15$ тогда и только тогда, когда оно делится и на $3$, и на $5$. Рассмотрение делимости на простые множители по отдельности делает задачу выполнимой вручную.

3. 3

   Используем правило делимости на 5, чтобы определить первую цифру. Для делимости на $5$ последняя цифра должна быть $0$ или $5$. В палиндроме последняя цифра равна первой, а шестизначное число не может начинаться с $0$, значит

   $a=5$

   и число имеет вид $\overline{5bccb5}$. Значит, все подходящие числа начинаются с $5$ — ни один палиндром, делящийся на $15$, не может начинаться с $6$ или больше.

4. 4

   Применим правило делимости на 3 к сумме цифр. Сумма цифр равна

   $5+b+c+c+b+5=10+2b+2c$

   Эта сумма должна делиться на $3$. Рассмотрим по модулю $3$: $10+2b+2c\equiv 1+2(b+c)\equiv 0$, что даёт условие

   $b+c\equiv 1 \pmod 3$

5. 5

   Максимизируем цифры слева направо. Наибольший вклад дают старшие разряды, поэтому сначала подставим $b=9$. Тогда $c$ должно удовлетворять $9+c\equiv 1\pmod 3$, то есть $c\equiv 1\pmod 3$, значит $c\in\{1,4,7\}$ и наибольшее — $c=7$. Это объясняет, почему $599995$ не подходит: сумма его цифр $46$ не делится на $3$.

6. 6

   Соберём число и проверим. При $a=5$, $b=9$, $c=7$ получаем

   $597795$

   Проверим: число оканчивается на $5$, значит делится на $5$; сумма цифр $5+9+7+7+9+5=42$ делится на $3$; и действительно

   $597795=15\times 39853$

   Так как $b=9$ — наибольшая возможная вторая цифра, а $c=7$ — наибольшая допустимая третья, большего шестизначного палиндрома, делящегося на $15$, не существует.