Подскажите ход решения.

Ходжа Насреддин подрядился научить ишака читать. Эмир установил ему следующие правила: «Сейчас ты получишь какую пожелаешь сумму, меньшую 10000 динаров, на покупку ишака, а затем каждый месяц будешь получать столько динаров, сколько месяцев прошло с начала учения (в первый месяц—один, во второй—два, и т. д.). Но когда общая сумма, которую я тебе выплатил, окажется кратной 2013 динарам, я устрою ослу экзамен.» Сможет ли Ходжа указать такую сумму на покупку ишака (целое число динаров), что экзамен никогда не наступит?

задан 17 Фев '13 23:54

изменен 18 Фев '13 0:21

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

получил что общая сумма динаров задается функцией 0,5 n(n+1)+ a, где n- текущий месяц, а- начальная сумма. Как определить кратность 2013? неужели перебирать остатки и искать цикличность?

(18 Фев '13 0:19) Decron

Что за олимпиада? Онлайн?

(18 Фев '13 0:33) DocentI

нет,просто демоверсия. решений к ней не приведено, а понять как решается хочется, вдруг на очном туре что-нибудь похожее попадется

(18 Фев '13 0:41) Decron

Формула, конечно, верная, но перебирать остатки от деления на такое большое число долго.
Главное - правильно выбрать гипотезу, что именно доказывать?

(18 Фев '13 0:41) DocentI

если мы теоретически определим, что число 0,5n(n+1) где n- натуральное, при делении на 2013 дает все остатки, кроме какого - то k , то a=2013-k. Только вот как найти этот остаток k?

(18 Фев '13 0:44) Decron
10|600 символов нужно символов осталось
0

Заметим, что $%2013=3\cdot11\cdot61$%. В данном случае Ходжа может добиться даже того, чтобы выданная ему сумма никогда не делилась на $%3$%. Рассмотрим числа дополнительных выплат: это $%1,3,6,10,15,21,\ldots$%. Как уже было сказано, это числа вида $%n(n+1)/2$%. Их остатки от деления на $%3$% таковы: $%1,0,0,1,0,0,\ldots$%, и остаток $%2$% никогда не встречается.

Сначала надо доказать сам этот факт. Он следует из периодичности, а она следует из того, что $%(n+3)(n+4)-n(n+1)=6n+12$% делится на $%3$%.

Таким образом, Ходже достаточно назвать число $%a$%, дающее при делении на $%3$% остаток $%1$%. Например, $%a=1$%. Или, если по максимуму, то он может потребовать у эмира $%9997$% динаров. Тогда остатки будут иметь вид $%2,1,1,2,1,1,\ldots$%, и остаток $%0$% не встретится.

А вот если бы вместо $%2013$% было число $%2048$% (степень двойки), то экзамена бы не удалось избежать. В общем виде эта задача, сформулированная чисто на языке чисел, не так давно здесь разбиралась.

ссылка

отвечен 18 Фев '13 1:31

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,621
×759

задан
17 Фев '13 23:54

показан
780 раз

обновлен
18 Фев '13 1:31

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru