Задача по комбинаторике

Будь мужиком — иди напролом. Потратишь несколько недель на перебор и поймёшь, что на самом-то деле тебе глубоко плевать на последнюю цифру этой суммы.
Ну действительно, мне спать захотелось от одной только формулировки...

убийца садов^W^W Ответ - 9. Это мне сказал Питон.

Ну вот. 9. Хорошо. Но посмотри на проделанную работу...
Вот представь, что ответ вышел не 9, а 7. То что? Что изменилось бы? Какие рухнули бы теории?
Это глупо и уныло.
Лучше бы водки выпил, ну. Сегодня днюха Ленина всё-таки...

Ничто бы не не изменилось. Ты, пожалуй, прав.

Вообще, решать такие вещи толпой нердов под алкоголь - веселуха. Особенно если бумаги нет.

толпой нердов под алкоголь - веселуха

Вот здесь, пожалуй, соглашусь.
Правда в моем коллективе алкоголиков мы обычно просчитываем более прикладные задачи.
Например сколько моль водки падла-разливающий пролил на стол, какова её энергоёмкость и прочая весёлая чушь...

1. Строишь бином Ньютона для (1+x)^n
2. Подставляешь числа, получаешь озарение
3. Доказываешь простую лемму

Как-как. Учительницу слушать.

Ответ - 9. Это мне сказал Питон.

Ты спросил у Питона что-то не то, потому что там ответ 5 и мой Питон только подтверждает это.

там ответ 5 и мой Питон только подтверждает это

Математика уровня 7 класса тоже :3

Ну я на всякий случай питоном проверил, потому что я посчитал и получил 5, а выше было мнение, что не 5.

import operator
def fact(n): 
    return reduce(operator.mul, xrange(1, n + 1), 1)


sum=0
i=0
for i in range(0, 2014):
	sum=sum+4**i*(fact(2014)/(fact(i)*fact(2014-i)))
print sum

Факториал спёр откуда-то. Формула, вроде как, правильная. Последняя цифра выведенного 1409-значного числа = 9. А у тебя какой код?

А как ты посчитал? Выше предложенным методом через бином?

range(0, 2014)

Это будет от 0 до 2013 включительно, 2014 потерялось.

А как ты посчитал? Выше предложенным методом через бином?

Ну да, это и есть бином.

Ай блин, коварно.

Да, заменил 2014 на 2015 - получился ответ 5. Заодно попросил вывести i для проверки - 2014. Понял, спасибо. С биномом буду разбираться.

Решил.

При ближайшем рассмотрении эта сумма оказалась всего лишь (4+1)^2014=5^2014.

Молодец, осталось тривиально доказать, что пять в любой натуральной степени на пятерку и будет оканчиваться.

5*5 даёт 25, на конце 5. При каждом следующем возведении в степень разряд единиц опять умножается в 5 раз > 5*5=25, на конце 5.

Хорошо, попробуй ради интереса немного модифицировать задачу: найти последнюю цифру суммы (сочетание из 2014 по 0) + (сочетание из 2014 по 1) + (сочетание из 2014 по 2) ... + (сочетание из 2014 по 2014).

(1+1)^2014=2^2014.

Окончания степеней двойки: 2, 4, 8, 6, 2, 4, 8, 6, каждый 4-ый раз цифра повторяется. Ближайшее число после 2014, делящееся на 4=2016. Ответ - 8?

Почти. Сам же говоришь, что 2^{4k} = 6 mod 10, значит 2^{4k-2} = 4 mod 10, а не восемь, но это уже обидная невнимательность. Молодец.

Да. Точно, тупанул. Если честно, я был не совсем уверен, что потом делать после нахождения, через сколько чередуются и нахождения ближайшего делящегося числа.