НГУ

Форумы НГУ
Текущее время: Вс фев 18, 2018 10:07 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Магическое число 15
СообщениеДобавлено: Вт ноя 23, 2004 6:13 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт мар 23, 2004 1:45 pm
Сообщения: 102
Откуда: Ой, а Вы не знаете, да? - Петр Алексеевич
Для натурального числа х обозначим через f(x) общую сумму цифр в десятичных записях числа x и всех его делителей. Например,

f(2)=3, f(3)=4, f(4)=7, f(7)=8, f(8)=15, f(15)=15.

Доказать, что для любого x > 1 последовательность x, f(x), f(f(x)), ... оборвется на числе 15.
Сводится к не очень большому перебору без компа и доступна первокурсникам. Можно ли уменьшить перебор или вообще его устранить?

Название темы изменено с согласия автора //bolbot


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 25, 2004 12:21 am 
а если взять х=5?
f(5)=6, f(6)=12, f(12)=28...
я наверное условие не поняла?


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 25, 2004 12:23 am 
вернее, f(12)=19


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 25, 2004 12:27 am 
упс... поняла... там же дальше будет
f(19)=11
f(11)=3... м-да...


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн ноя 29, 2004 2:42 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт мар 23, 2004 1:45 pm
Сообщения: 102
Откуда: Ой, а Вы не знаете, да? - Петр Алексеевич
Пожалуй, дам подсказки:

1. Сначала показываем, что f(n)<n, для достаточно больших n. Поэтому все последовательности, начатые с произвольного n, начнут циклить. В любом цикле есть число n, для которого f(n)>=n. Такое число назовем критическим..

2. Очень грубую оценку сверху для критических чисел из пункта 1 улучшаем с помощью таких же очень грубых оценок. Уменьшение верхней границы дает возможность для более тонких оценок, что опять позволяет уменьшить саму эту верхнюю оценку. За несколько рассмотрений загоняем все критические числа в интервал до 100.

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

Примерно 1 час работы безоружного гуманоида, даже без калькулятора.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт сен 15, 2009 3:21 am 
Не в сети
Редкий гость

Зарегистрирован: Вт сен 15, 2009 3:19 am
Сообщения: 1
Любопытно:

1 2 3
4 5 6
7 8 9

При сложении чисел по диагоналям, вертикали и горизонтали (крест-накрест) получаем число 15


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс дек 13, 2009 4:30 pm 
Не в сети
Редкий гость

Зарегистрирован: Вс окт 30, 2005 2:25 pm
Сообщения: 2
Нам эту задачу Больбот давал на ТЧ на 1-м курсе ММФ. Обещал решившему зачем автоматом. У меня получился перебор порядка 90 первых чисел.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Магическое число 15
СообщениеДобавлено: Вс дек 13, 2009 5:12 pm 
Не в сети
Опытный автор

Зарегистрирован: Вт авг 29, 2006 4:53 am
Сообщения: 443
Откуда: Кирилл Василевский
MinHerz писал(а):
Можно ли уменьшить перебор или вообще его устранить?
Если это и есть вопрос темы, то непонятно, что Вы хотите сказать этой фразой. Для начала, какое решение здесь, в задаче на доказательство, называется перебором? И какое, соответственно, не перебором? И для переборных решений - как определяется, какое из них лучше ("перебор уменьшен"), а какое хуже?

Что такое вообще сложность вычислений в задаче на доказательство?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 25


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB