|
Страница 1 из 1 [ Сообщений: 5 ]
Автор |
Сообщение |
alex123
|
Заголовок сообщения: Детская задачка про палиндромы Добавлено: 14 дек 2018, 00:47 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
Доказать, что если число `n` не кратно десяти, то существует палиндром, делящийся на `n`.
Палиндром - число, десятичная запись которого одинаково читается слева направо и справа налево, например 123321 или 121.
|
|
|
|
|
|
|
michel
|
Заголовок сообщения: Re: Детская задачка про палиндромы Добавлено: 14 дек 2018, 11:41 |
|
Зарегистрирован: 17 дек 2010, 20:02 Сообщений: 1678
|
Вообще говоря, под палиндромом можно понимать число, составленное из одних единиц, тогда это действительно детская задача. Нетрудно доказать, что всегда можно найти другой палиндром: 123456789123456789...987654321 (где посередине две девятки), который будет делиться на заданное число (нечетное и не кратное 5). Возьмем число N с n периодами (с длиной 9n): 123456789...123456789, тогда его палиндром можно записать как: N*10^{9n}+111...10-N, где число единичек равно 9n. Это выражение можно переписать в виде: N*(10^{9n}-1)+111...10=N*999...9+111...10, где число девяток равно 9n, а единиц 9n. А теперь достаточно воспользоваться результатом "детской" задачи, что найдется число из n единичек, которое делится на заданное число (не кратное 10). P.S. Что-то формулы не отображаются на сайте, поэтому убрал обратные кавычки (которые на букве "ё").
Последний раз редактировалось michel 14 дек 2018, 12:14, всего редактировалось 3 раз(а).
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Детская задачка про палиндромы Добавлено: 14 дек 2018, 11:49 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
michel писал(а): Вообще говоря, под палиндромом можно понимать число, составленное из одних единиц, тогда это действительно детская задача. Нетрудно доказать, что всегда можно найти другой палиндром: 123456789123456789...987654321 (где посередине две девятки), который будет делиться на заданное число. Задача действительно детская, только ваше решение неверное. Ваши палиндромы взаимно-просты с 10, поэтому не могут делиться ни на четные числа, ни на числа, кратные пяти. А на то, на что они могут делиться, прекрасно делятся и палиндромы-репъюниты (числа из одних единиц).
|
|
|
|
|
michel
|
Заголовок сообщения: Re: Детская задачка про палиндромы Добавлено: 14 дек 2018, 12:11 |
|
Зарегистрирован: 17 дек 2010, 20:02 Сообщений: 1678
|
alex123 писал(а): Задача действительно детская, только ваше решение неверное.
Ваши палиндромы взаимно-просты с 10, поэтому не могут делиться ни на четные числа, ни на числа, кратные пяти.
А на то, на что они могут делиться, прекрасно делятся и палиндромы-репъюниты (числа из одних единиц). У Вас в условии задачи говорилось о числах, не кратных 10. О палиндромах-репъюнитах я сказал в самом начале. В одном я согласен с Вами, что мои палиндромы не делятся на четные числа, но они делятся на любое нечетное число, не кратное пяти. Но мою конструкцию нетрудно подправить, если в качестве начального числа взять например: 23456789, тогда мои палиндромы будут делиться и на четные числа. А если взять 56789, тогда они будут делиться на 5, но не на четное число. P.S. Если я правильно понял Вас, что для делимости на четное число в качестве палиндрома берем повторяющиеся одинаковые четные цифры, а для делимости на число, кратное 5, берем повторяющиеся пятерки. Но это действительно неинтересное детское решение.
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Детская задачка про палиндромы Добавлено: 14 дек 2018, 14:39 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
michel писал(а): alex123 писал(а): Задача действительно детская, только ваше решение неверное.
Ваши палиндромы взаимно-просты с 10, поэтому не могут делиться ни на четные числа, ни на числа, кратные пяти.
А на то, на что они могут делиться, прекрасно делятся и палиндромы-репъюниты (числа из одних единиц). У Вас в условии задачи говорилось о числах, не кратных 10. О палиндромах-репъюнитах я сказал в самом начале. В одном я согласен с Вами, что мои палиндромы не делятся на четные числа, но они делятся на любое нечетное число, не кратное пяти. Но мою конструкцию нетрудно подправить, если в качестве начального числа взять например: 23456789, тогда мои палиндромы будут делиться и на четные числа. А если взять 56789, тогда они будут делиться на 5, но не на четное число. P.S. Если я правильно понял Вас, что для делимости на четное число в качестве палиндрома берем повторяющиеся одинаковые четные цифры, а для делимости на число, кратное 5, берем повторяющиеся пятерки. Но это действительно неинтересное детское решение. Если число не кратно 10, это не запрещает ему делиться на какую-то степень двойки или пятерки Да, ваша конструкция тривиально лечится, рецепт вы дали. Правда не полный - на 5 делится, а на 25 уже нет. Со степенями двойки тоже проблема быстро начинается, уже на 16 не делится. Еще одна итерация - и ответ станет верным. Нет, я имел в виду более изящный [и естественный] палиндром. А ваша версия с поправленными репьюнитами страдает той же болезнью, что и рецепт поправки вашего первого решения - не делится на 25 и на 16. И, 100500-й раз - задача малоинтересная и детская. Уровня районной школьной олимпиады, не выше.
|
|
|
|
|
|
|
|
Страница 1 из 1 [ Сообщений: 5 ]
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2 |
|
|
|
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения
|
|
|