Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Интересные задачки » Разное




 Страница 1 из 1 [ Сообщений: 5 ] 



Автор Сообщение
 Заголовок сообщения: Детская задачка про палиндромы
 Сообщение Добавлено: 14 дек 2018, 00:47 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
Доказать, что если число `n` не кратно десяти, то существует палиндром, делящийся на `n`.

Палиндром - число, десятичная запись которого одинаково читается слева направо и справа налево, например 123321 или 121.


Вернуться наверх 
 Заголовок сообщения: 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 раз(а).

Вернуться наверх 
 Заголовок сообщения: Re: Детская задачка про палиндромы
 Сообщение Добавлено: 14 дек 2018, 11:49 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
michel писал(а):
Вообще говоря, под палиндромом можно понимать число, составленное из одних единиц, тогда это действительно детская задача.
Нетрудно доказать, что всегда можно найти другой палиндром: 123456789123456789...987654321 (где посередине две девятки), который будет делиться на заданное число.



Задача действительно детская, только ваше решение неверное.

Ваши палиндромы взаимно-просты с 10, поэтому не могут делиться ни на четные числа, ни на числа, кратные пяти.

А на то, на что они могут делиться, прекрасно делятся и палиндромы-репъюниты (числа из одних единиц).


Вернуться наверх 
 Заголовок сообщения: Re: Детская задачка про палиндромы
 Сообщение Добавлено: 14 дек 2018, 12:11 
Не в сети

Зарегистрирован: 17 дек 2010, 20:02
Сообщений: 1678
alex123 писал(а):
Задача действительно детская, только ваше решение неверное.

Ваши палиндромы взаимно-просты с 10, поэтому не могут делиться ни на четные числа, ни на числа, кратные пяти.

А на то, на что они могут делиться, прекрасно делятся и палиндромы-репъюниты (числа из одних единиц).

У Вас в условии задачи говорилось о числах, не кратных 10.
О палиндромах-репъюнитах я сказал в самом начале.
В одном я согласен с Вами, что мои палиндромы не делятся на четные числа, но они делятся на любое нечетное число, не кратное пяти. Но мою конструкцию нетрудно подправить, если в качестве начального числа взять например: 23456789, тогда мои палиндромы будут делиться и на четные числа. А если взять 56789, тогда они будут делиться на 5, но не на четное число.
P.S. Если я правильно понял Вас, что для делимости на четное число в качестве палиндрома берем повторяющиеся одинаковые четные цифры, а для делимости на число, кратное 5, берем повторяющиеся пятерки. Но это действительно неинтересное детское решение.


Вернуться наверх 
 Заголовок сообщения: 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

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: