Задача про числа-палиндромы

        И снова приветствую всех тех, кто серьёзно готовится к профильному ЕГЭ и всерьёз претендует на решение самых сложных задач 19 (они же С6)! Как и обещал, продолжаем разбирать самые разнообразные и необычные задачи на теорию чисел и способы успешно расправляться с такими монстрами. Хотя для подготовленного ученика в задачах 19 страшного особо ничего и нету.)

Использование признаков делимости и перебора на ограниченном множестве. Задача про числа-палиндромы.

        В данном материале я хотел бы разобрать очередную необычную и не самую сложную задачку про так называемые числа-палиндромы. Для начала, что это вообще за зверь такой (для тех, кто не в курсе)?

        Палиндром — это слово, число или даже целый текст, одинаково читающееся в обоих направлениях. Как слева направо, так и справа налево.

        Примеры:

        Число 12321, слово «ротор», красивое женское имя Анна, словосочетание «искать такси», а также всем известная бородатая фраза «А роза упала на лапу Азора». В общем, идея понятна, я думаю. :)

        В нашей задаче, разумеется, речь пойдёт о числах. Что ж, давайте теперь посмотрим на саму задачу.

 

       

        Вот такая вот задачка. Как к ней подступиться? Ну, во-первых, в каждом из пунктов речь идёт о делимости на 15. Стало быть, нашей отправной точкой будут признаки делимости чисел нацело. Это тема 6-го класса средней школы. Других вариантов просто нет. И какие же это признаки, спросите вы?

        Вспоминаем 6-й класс, ищем там признак делимости на 15 и… вы правы! Такого признака нету. Но! Зато есть признаки делимости чисел на 3 и на 5. А что такое 15? Это не что иное, как 3·5! Элементарно, Ватсон! :) Стало быть, если какое-либо натуральное число одновременно делится нацело на тройку и пятёрку, то автоматически оно будет делиться и на пятнадцать. Поэтому давайте-ка быстренько освежим в памяти признаки делимости чисел на 3 и на 5. Вот они:

        Признак делимости на 3

        Натуральное число делится нацело на 3, если сумма его цифр делится на 3.

        Скажем, число 12384 точно поделится на 3, так как сумма его цифр 1+2+3+8+4 = 18 делится на 3. А вот 23576 даже и пытаться не стоит, так как его сумма цифр 2+3+5+7+6 = 23 не делится на 3.

        Признак делимости на 5

        Натуральное число делится нацело на 5, если оно заканчивается цифрой 0 или 5.

        Например, на 5 делится число 12345, так как оно заканчивается на пятёрку. Или 1234567890, так как оно заканчивается нулём. Ну, в общем, вы поняли. Признак очень простой.

        Значит, натуральное число делится на 15 тогда и только тогда, когда оно одновременно делится на 3 (по сумме цифр) и на 5 (по последней цифре). Что ж, теоретическая база подготовлена, пора приступать к разбору нашей задачи. Итак,

​          

        а) Приведите пример числа-палиндрома, который делится на 15.

 

        Прежде чем что-то решать, давайте посмотрим, как вообще устроены числа-палиндромы:

        И так далее… 

        Здесь a, b, c и так далее — цифры натурального числа. В общем случае — различные. Черта сверху ставится для того, чтобы обозначить тот факт, что перед нами именно цифры, а не произведение типа a·b·c.

        Скажем, запись  

       

        означает трёхзначное натуральное число, которое в десятичной форме запишется так:

        

        Что ж, давайте теперь искать числа-палиндромы, делящиеся на 15. Для начала поищем их среди двузначных чисел. Это числа 11, 22, 33, 44 и так далее до 99. Можно заметить, что все они делятся на простое число 11:

        11=11·1

        22=11·2

        33=11·3

        И так далее. Наименьшее число, которое делится как на 11, так и на 15 — это 11·3·5 = 165 - уже трёхзначное.  Облом. Значит, среди двузначных чисел таковых нету.

        Что ж, поехали шерстить трёхзначные числа. :) Трёхзначное число-палиндром имеет вид

         

Раз оно делится на 15, то должно делиться как на 5 (по последней цифре), так и на 3 (по сумме цифр).

Значит, согласно признаку делимости на 5, последняя цифра (a) может быть только 0 или 5. Третьего не дано. :)

        А теперь прикинем. Если a = 0, то наше число имеет вид  

           

        и никак не является трёхзначным. Значит, единственный устраивающий нас вариант - это

        а = 5.

        Поэтому трёхзначные числа-палиндромы, делящиеся на 5, имеют вид: 

           

        Что ж, кое-чего уже проясняется. :)

       

        А теперь в игру дополнительно вступает признак делимости на 3. Составляем сумму цифр:

        5 + b + 5 = 10 + b,

        где b, будучи цифрой числа, принимает значения 0, 1, 2, 3, …, 9.

        Теперь понятно, как расправиться с пунктом а). Подберём число b так, чтобы выражение для суммы цифр 10 + b делилось бы на 3. Например, при b = 2 получим:

        10+b = 10+2 = 12 — делится на 3.

        Следовательно, самое первое по счёту трёхзначное (и вообще глобально) число-палиндром, делящееся на 15, - это число 525.

        Всё, этого вполне достаточно для ответа на вопрос пункта а).

        Ответ: Например, 525.

 

        Переходим к пункту б).

        б) Сколько существует пятизначных чисел-палиндромов, делящихся на 15?

 

        Все пятизначные числа-палиндромы имеют вид: 

           

        Здесь снова рулят признаки делимости чисел на пятёрку и на тройку. Как и в предыдущем пункте, начнём с признака делимости на 5. Это означает, что последняя цифра в нашем числе (т.е. а) может быть равна либо нулю, либо пятёрке.

        Нулём цифра а быть никак не может, поскольку в таком случае наше число примет вид  

           

        и попросту не будет пятизначным. Значит, а = 5 (и только 5).

        Итак, наши пятизначные кандидаты предварительно обретают вот такой вид:

        

        Теперь снова подключаем признак делимости чисел на 3 по сумме цифр. В нашем случае:

        5 + b + c + b + 5 = 10 + 2b + c — должно делиться на 3.

        В предыдущем пункте мы варьировали только одну единственную цифру b, добиваясь делимости на 3 суммы цифр (напомню, это было выражение 10+b). Здесь же нам надо варьировать уже две цифры — b и c. И как нам теперь быть? Ведь число всевозможных вариантов стало гораздо больше! Да, не спорю, больше. На первый взгляд может показаться, что вариантов и вправду довольно много и перебирать их все очень долго и муторно. Но давайте подумаем: ведь b и с — не просто числа, а цифры натурального числа. Которые могут принимать очень ограниченные значения — 0, 1, 2, 3, …, 9. Поэтому, если мы как-то зафиксируем b, последовательно придавая ему значения от 0 до 9, то в каждом из случаев варьировать уже придётся только одну цифру c. Давайте посмотрим, как это делается. Первый случай я разберу подробно, а остальные — кратко.

        Итак, первый вариант b = 0. Тогда сумма цифр 10 + 2b + c нашего числа будет равна:

        10+2·0+c = 10+c.

        Когда выражение 10+c делится на 3? Очевидно, в трёх ситуациях:

        10+c = 12 (тогда c = 2),

           10+c = 15 (тогда c = 5),

        10+c = 18 (тогда c = 2).

        Всё. Больше, чем 8 (например, 11) число с быть уже никак не может. Ещё раз напоминаю, что наши буковки — это на самом деле циферки. :) То есть, 0, 1, 2, …, 9. Этот случай дал нам три пятизначных числа-палиндрома делящихся на 15. Какие же это числа? Пожалуйста, вот они:

        50205, 50505 и 50805 (3 числа).

        Пусть теперь b = 1. В этом случае сумма цифр нашего числа будет такая:

        10+2·1+c = 12+c

        Добиваясь теперь, чтобы выражение 12+c делилось на 3, получим с = {0; 3; 6; 9}. Итого выплыли ещё 4 числа-палиндрома (51015, 51315, 51615, 51915).

        Уловили закономерность? :) Да! Надо разобрать оставшиеся 8 случаев. Не так уж и много, по большому счёту. Добрый вечер! Буду краток. :)

        

 

        Подобная процедура в целочисленных задачах называется перебор на ограниченном множестве. Суть метода заключается в том, что, если число всевозможных вариантов не очень большое (в нашем случае — всего 10), то мы просто перебираем все-все возможные случаи и отбираем всё то, что нас устраивает. :)

А теперь подсчитываем наших цыплят палиндромов:

3 + 4 + 3 + 3 + 4 + 3 + 3 + 4 + 3 + 3 = 33

        Итого тридцать три коровы пятизначных числа-палиндрома, делящихся на 15! :)

Ответ: 33.

 

        Теперь, когда проведено столь масштабное исследование, самый сложный пункт в) многим ученикам может показаться совсем пустяковым. :) Сейчас всё увидите!

 

в) Найдите 37-е по величине число-палиндром, которое делится на 15.

 

        Для ответа на вопрос сначала подсчитаем все трёхзначные и четырёхзначные числа-палиндромы.

        Одно из трёхзначных (самое первое вообще среди таких чисел) мы уже нашли — это 525. Давайте найдём все остальные. Для этого снова обратимся к нашей сумме цифр (см. пункт а)):

         10 + b – делится на 3.

        Тогда b = {2; 5; 8} — три трёхзначных числа-палиндрома (т.е. 525, 555 и 585).

        Разбираемся теперь с четырёхзначными числами-палиндромами.  Здесь всё аналогично. Они имеют вот такую запись:

        По признаку делимости на 5, последняя (и первая) цифры могут быть равны 0 или 5. Сразу, по понятным причинам, отметаем ноль и получаем:

        По признаку делимости на 3 составляем сумму цифр:

5 + b + b + 5 = 10 + 2b.

        Чтобы эта штука делилась на 3, цифра b должна принимать лишь одно из трёх значений: b = {1; 4; 7}. Итого получаем три четырёхзначных числа-палиндрома (5115, 5445 и 5775).

        Тогда получается, что всего трёх-, четырёх- и пятизначных чисел-палиндромов, делящихся на 15, будет: 

        3 (трёхзначные)+3 (четырёхзначные)+33 (пятизначные) = 39 чисел.

        Тогда очевидно, что искомое 37-е число-палиндром — пятизначное. Гуд.) Идём дальше.

        А теперь смотрим на результаты нашего исследования пятизначных чисел в пункте б). Я не стал для каждого случая выписывать их все, но зато можно заметить, что при росте b все наши получаемые числа располагаются в порядке возрастания. Это значит, что самое последнее, 39-е число будет соответствовать случаю b=9, c=8. Тогда искомое 37-е по величине число-палиндром, делящееся на 15, будет соответствовать случаю b=9, c=2, т.е. 59295.

        Вот и всё! :)

        Ответ: 59295.

 

        Как видите, ничего сложного. Если знать пару признаков делимости и понимать суть задания (что такое число-палиндром и немного что такое десятичная запись числа). Да, в пункте б) надо разбирать 10 случаев, но все они совсем простые и решаются фактически в уме. Главное — не бояться!