?

Log in

No account? Create an account
entries friends calendar profile Арбуз - занимательный мир Previous Previous Next Next
две чудные задачи - кросспосты из блога
sklyarevskiy
sklyarevskiy
две чудные задачи
34 комментов или Написать
Comments
georgick From: georgick Date: January 27th, 2007 05:18 am (UTC) (Link)
неверно посчитал.
40! заканчивается на 2 и дальше нормальной закономерности не обнаружить.
я вообще не уверен, что не применяя программирования ее можно решить логически или на пальцах
From: zur_kosmonaft Date: January 27th, 2007 11:10 am (UTC) (Link)
40! заканчивается на 8. мы оба неправильно посчитали, но ты прав в том, что это оказывается не так просто как я думал. Но я попробую все-таки логически. Мой старый ответ отменяется
yaroslaw From: yaroslaw Date: January 28th, 2007 03:33 am (UTC) (Link)
вы уж договоритесь между собой, но 40! заканчивается все же на 6:)))
georgick From: georgick Date: January 28th, 2007 07:25 am (UTC) (Link)
еще раз проверил. Теперь и на калькуляторе.
2
yaroslaw From: yaroslaw Date: January 28th, 2007 03:28 pm (UTC) (Link)
решение-доказательство:
(10^6)! после отбрасывание 0ей оканчивается на ту же цифру что и 8^(10^5)*(10^5)!
Это следует из того, что F[n]:=(10(n-1)+1)(10(n-1)+2)(10(n-1)+3)...(10(n-1)+9)(10n) == 10*n*9! (mod 1000)
где "==" - это сравнение по модулю
поделим на 100 (убираем два нуля, один из 10 другой из 2*5) и получаем
F[n]/100 == n*8 (mod 10), где n теперь от 1 до 10^5,
и 10^6!=П F[n]
после убирания нулей останется П(n*8)=8^(10^5)Пn=8^(10^5)*10^5!
Итого, ответ
Х=8^(10^5)*8^(10^4)*8^(10^3)*8^(10^2)*8^(10^1)8^(10^0) mod 10 = 8^111111 mod 10
111111 == 3 (mod 4) (4 -- периодичность цифры в степенях 8ки)
то есть X = 8^111111 mod 10 = 8^3 mod 10 = 2


ОТВЕТ: 2


ЗЫ упрощенно, для понимания, для 40! мы получим х=4!*(9!/10) mod 10=24*8 mod 10 =4*8 mod 10 = 32 mod 10 = 2.

PS вот так вот, пока строго все формулами не записал, и ошибки найти не мог. На 10 сокращал а про n, которое дает факториал на степень меньше, и забывал%)
georgick From: georgick Date: January 28th, 2007 06:08 pm (UTC) (Link)
логика рассуждения понятна, но тут ошибка в самом начале рассуждений
в формуле
F[n]:=(10(n-1)+1)(10(n-1)+2)(10(n-1)+3)...(10(n-1)+9)(10n) == 10*n*9! (mod 1000)
в правой части не должно быть n.
Я так понимаю, тут имелась в виду следующая закономерность.
(эта же формула, но без n справа при n=2, например)
11*12*.....*19*20 = 1*2*3*...10
И соответсвенно так дальше.
тогда имеем П = 8^(10^5) (без еще одного множителя 10^5! как у вас)
или 10^6! == 8^(10^5) (mod 10)
т.е достаточно найти последюю цифру числа 8^(10^5)
ну а 8 в степени, кратной 4 будет оканчиваться всегда 6

Ответ: 6

Для варианта с 40! имеем следующее. 8*4 = 32




georgick From: georgick Date: January 28th, 2007 06:12 pm (UTC) (Link)
11*12*.....*19*20 = 1*2*3*...10
здесь конечно по модулю 10
yaroslaw From: yaroslaw Date: January 28th, 2007 06:54 pm (UTC) (Link)
я чего-то не понимаю. Ошибка в какой формуле? Если тебе не сложно просмотреть, то я был самым первым, и ответил 6, а потом начал делать выкладки и увидел что там множитель n обязателен.
Ибо 11*12*13...*19*_2_*10
21*22*23...*29*_3_*10
10, 2 и 5 из произведения выбрасывается
остается k1*..*k9*(k+1)

Но ошибка все-же где-то есть. Причем более глубокая. Но подумаю над этим уже завтра.
georgick From: georgick Date: January 28th, 2007 07:28 pm (UTC) (Link)
не отрицал, что вы были первым. Решение ваше тоже почти верное.
From: (Anonymous) Date: January 28th, 2007 04:00 pm (UTC) (Link)
Мне кажется, это все решается следующим способом. Как уже выяснили 9! кончается на 8. Стало быть, если взять количество раз, когда надо умножить 9! на себя (1 000 000 / 10 ), то это будет степень в которую можно возвести 8 для получения последнего числа. 8^100000= 2^300000. Ну а поскольку 2^k (k = 0 mod 4) кончается на 6, то и (2^(4*75))^1000 будет кончаться на 6.
georgick From: georgick Date: January 28th, 2007 06:13 pm (UTC) (Link)
браво!
самое короткое решение.
но почти аналогичное с вышестоящими
yaroslaw From: yaroslaw Date: January 28th, 2007 07:00 pm (UTC) (Link)
самое короткое и тем не менее неправильное.
причину я написал выше.
запишите это решение на языке математики -- и ошибки станут очевидны. Ну и самым коротким оно быть перестанет.

ЗЫ по вашей логике 19! должно заканчиваться на ту же цифру что и 20!.
проверьте.
georgick From: georgick Date: January 28th, 2007 07:27 pm (UTC) (Link)
вероятно, вы опять ошиблись
yaroslaw From: yaroslaw Date: February 2nd, 2007 09:52 pm (UTC) (Link)
короткое решение неверно, потому что 1**9 не заканчивается как 11**19, не равно заканчивается как 21**29 и так далее. Возьмите калькулятор проверьте. это очень просто и тем не менее неочевидно. Я задачу уже решил, нашел недостающий член, до 40! совпадает:) (у вас даже 20! неправильно... а его можно посчитать обычным калькулятором)
Завтра напишу полное решение.
34 комментов или Написать