Всем привет! Предлагаю решить след. задачи по математике:
1) Может ли 3 ** n + 1 делиться на 10 ** 10 ?
2) В стране Метрополии каждый город связан с каждым дорогой. Злой волшебник установил на всех дорогах одностороннее движение. Тем не менее, оказалось, что из любого города можно добраться до любого другого. Доказать, что существует замкнутый путь, проходящий через все города Метрополии один раз.
1 задачу я вообще не понимаю, как решать. Рассматривание остатков не помогает(.
По 2 — ой имеются след. соображения: Если д-ть, что для любого графа из N вершин существует цикл, проход. через N-1 вершину, то дальше все очевидно.
Любые соображения по решению задач приветствуются.
Спасибо.
По поводу второй, советую почитать про графы, называемые турнирами, в одной из Летних Школ в Севастополе, Лопатин доказывал это. Вот ссылка на видео лекции.
UPD. Интересующая тебя часть на 36 минуте.
1) Если 3^n+1 делится на 10^10, то 3^n оканчивается на 99, а 3^(n-1) оканчивается на 3. Точный квадрат не может оканчиваться на 3, поэтому n-1 нечетно, n четно и 3^n — точный квадрат. Осталось заметить, что если точный квадрат оканчивается на 9, то предпоследняя цифра не может быть нечетной...
Все верно, спасибо. То, что n-четное следует из того, что 3 ** n оканч. на 9 только тогда, когда n=4*m-2
3^n + 1 не может делиться на 100, тем более на 10^10, рассматривание остатков как раз помогает.
А за что минусуют? Вообще-то человек прав. Из кратности 4 следует, что n — нечетное, а из кратности 25, что n сравнимо с 10 по модулю 20, т.е. четное.
"Из кратности 4 следует, что n — нечетное". Я это не понимаю. Можно поподробней, пожалуйста. UPD все понятно. круто)
В пункте 1 достаточно применить эту теорему
к первой задаче
3 в любой степени это нечетное число
(нечет) mod (чет) = (ост <> 0)
+1 не углядел.