Category: образование

Category was added automatically. Read all entries about "образование".

Порох еще есть, хоть и отсырел чутка

Вчера встретил в одной статье упоминание школьно-олимпиадной задачи класса для восьмого: делится ли на 3 число 2^99-1 (^ - степень). В школьные времена такие задачи решались на раз, сейчас где-то полчаса потребовалось на разработку модели сферического коня :).

Доказал по индукции, что 2^(2n-1)-1 не делится на 3.
1. n = 1,2,3 - гипотеза верна.
2. Пусть верно для k
3. Для k+1
2^(2k-1)-1 = a
2^(2*(k+1)-1)-1 = 4*2^(2k-1)-1 = 4*(2^(2k-1)-1)+4-1 = 4a+3. Очевидно, что не делится.

А теперь вопрос: нутром чую, что должно быть более простое решение. Подскажите, а?