|
Подскажите ход решения.
задан 17 Фев '13 23:54 
Decron |
|
Заметим, что $%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 
falcao |
получил что общая сумма динаров задается функцией 0,5 n(n+1)+ a, где n- текущий месяц, а- начальная сумма. Как определить кратность 2013? неужели перебирать остатки и искать цикличность?
Что за олимпиада? Онлайн?
нет,просто демоверсия. решений к ней не приведено, а понять как решается хочется, вдруг на очном туре что-нибудь похожее попадется
Формула, конечно, верная, но перебирать остатки от деления на такое большое число долго.
Главное - правильно выбрать гипотезу, что именно доказывать?
если мы теоретически определим, что число 0,5n(n+1) где n- натуральное, при делении на 2013 дает все остатки, кроме какого - то k , то a=2013-k. Только вот как найти этот остаток k?