Метод Гаусса.

[No Good 3,795]

господин хан.

А Фальк пришёл к успеху.

[Isaac New 3,552]

При n=2 выражение не делится на 240.

Ну да, на 16 оно делиться не будет. Мой косяк. Не увидел в твоём разложении лишнюю двойку

[Dramon 4,917]

Я себя совсем тупым почувствовал прочитав и не поняв большую часть написанного...(

[Кусяша 1,150]

Я себя совсем тупым почувствовал прочитав и не поняв большую часть написанного...(

Просто, ты слишком стар.

[IvPBay 459]

Да что всё так сложно?

Посмотрел - надо на 120. Твоё решение вроде под него подходит.

[IvPBay 459]

Вам этого не объясняли что ли? Проверяешь сначала для n=1, затем предполагаешь, что это выполняется при n=k, а потом доказываешь, что утверждение верно для n=k+1. Но это уж если совсем ничего не будет работать. 240=2*2*2*2*3*5. Переформируй как-нибудь то выражение, чтобы было видно, что оно будет делиться на это произведение.

А, это она и есть? Я ей целую пару коверкал выражение, но безрезультатно.

[IvPBay 459]

1) Докажем, что выражение делится на 5. Рассмотрим всевозможные остатки n по модулю 5.

Если остаток 0, то скобка n делится на 5

Если остаток 1 или 4 - то выражение n^2-1 делится на 5

Если остаток 2 или 3 - то выражение n^2+1 [в терминах остатков это будет то же самое, что и скобка n^2-5n+26. Те, кому это не очевидно, могут сами в этом убедиться руками] делится на 5

2) Докажем, что выражение делится на 3. Рассмотрим всевозможные остатки n по модулю 3.

Если остаток 0, то скобка n делится на 3

Если остаток 1 или 2, то скобка n^2-1 делится на 3

3) Докажем, что выражение делится на 8

3.1) n - нечётна, тогда скобка n^2-1 раскладывается на 2 множителя: n-1 и n+1, каждый из которых чётен, а один из которых обязательно будет делиться на 4

3.2) n делится на 8 - всё понятно

3.3) n делится на 4, но не делится на 8 - тогда скобка n^2-5n+26 чётна и всё произведение делится на 8

3.4) n делится на 2, но не делится на 4 - тогда скобка n будет делиться на 2, а скобка n^2-5n+26 по модулю 4 будет n^2-n+2 и будет сравнима с нулём по модулю 4 при n сравнимом с 2 по модулю 4 (огосспади, будет делиться на 4, если n при делении на 4 даёт остаток 2. [если предыдущее предложение оказалось для вас слишком сложно] Подставить и проверить)

Итог: выражение делится на 3, на 5, на 8, а значит - [на этом месте можно шарахнуть из пушки по воробьям и сказать "по китайской теореме об остатках"], так как 3, 5 и 8 взаимно-просты - выражение делится на 240

P.S. Могу записать в терминах сравнений по модулю, но тогда ни одной русской буквы в решении не останется

Не совсем понятно с этой теоремой, на 3 я сам доказал, это легко, а вот на 5 и 8.

[Isaac New 3,552]

А, это она и есть? Я ей целую пару коверкал выражение, но безрезультатно.

Нет, это есть разложение на примарные [степени простых] множители и доказательство делимости по частям. Если нужна именно индукция - можно и индукцию:

Что такое математическая индукция?Нажмите здесь!

 

Поскольку на первой странице гугла по запросу "ММИ для чайников" нет ничего интересного для меня - расскажу своими словами. Кратко. Допустим надо доказать некоторое утверждение для всех натуральных n. Или для всех натуральных n больших 1000. Или для всех чётных n. Зависит от вашей фантазии и фантазии составителя задачи. Но сейчас мы поговорим о самом простом случае. Что-то требуется доказать для всех натуральных n. Что вы делаете? Вы решаете две подзадачи.

а) Верно ли это при n=1. Это называется база индукции.

б) Следует ли из из верности задачи при n=k верность задачи при n=k+1 [если вы только начинаете знакомиться с ММИ - то делая две разные буквы вы страхуете себя от одних ошибок и приближаете к другим. Как и во всех подобного рода задачах]. Это называется переход индукции.

Почему а) и б)? Давайте посмотрим. У нас в задаче надо доказать для любого натурального n. Ну-с, начнём наш перебор.

n=1. Утверждение верно? Верно. Это случай а)

n=2. Утверждение верно? Заметим, что оно верно при n=1 и из того, что оно верно при n=1 по б) следует, что оно верно при n=2. То есть, при n=2 всё ок.

n=3. Утверждение верно? Заметим, что оно верно при n=2 и из того, что оно верно при n=2 по б) следует, что оно верно при n=3. То есть, при n=3 всё ок.

n=4. Утверждение верно? Заметим, что оно верно при n=3 и из того, что оно верно при n=3 по б) следует, что оно верно при n=4. То есть, при n=4 всё ок.

Дальше алгоритм, думаю, понятен.

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

Начинающим обычно объясняют ММИ, как искусство шагать по лестнице. Если вы умеете шагать на первую ступеьку лестницы и умеете подниматься на одну ступеньку - вы же пройдёте по лестнице, да? Ну, а мы сейчас попробуем применить только что полученное тайное знание для решения одной задачи.

[Cкрыть]

Задача) Докажем, что при любом натуральном n выражение n(n^2-1)(n^2-5n+26) делится на 120.

Для простоты докажем, что при лбом целом неотрицательном n выражение делится на 120. Понятно, что данные задачи равносильны.

База: n=0. Думаю, довольно очевидно, что 0 делится на 120.

Переход. Пусть для некоторого k выражение k(k^2-1)(k^2-5k+26) делится на 120. Докажем, что (k+1)((k+1)^2-1)((k+1)^2-5k+26) делится на 120.

О боже, сколько скобочек. Так и запутаться недолго. Всё. С этого момента - только многочлены, только хардкор!

Ещё раз тот же самый переход, но только с раскрытыми скобочками:

Пусть для некоторого k выражение k^5-5k^4+25k^3+5k^2-26k делится на 120. Надо доказать, что выражение (k+1)^5-5(k+1)^4+25(k+1)^3+5k^2-26(k+1)=... делится на 120. Вы всё ещё видите слишком много скобочек? Я тоже, поэтому я сейчас раскрою их все, но специальным образом. Раскрывая каждую скобочку я первое слагаемое занесу в зелёные скобки, а все остальные в красные. Итак,

...=(k^5-5k^4+25k^3+5k^2-26k )+(5k^4+10k^3+10k^2+5k+1-20k^3-30k^2-20k-5+75k^2+75k+25+10k+5-26 )=... А мы напоминаем, что спонсор раскрытия скобочек - бином Ньютона. Итак. У нас два слагаемых. Первое, как мы видим, по предположению индукции делится на 120. А вот в красных скобках какая-то абракадабра. Давайте её упростим и взглянем поподробнее.

5k^4-10k^3+55k^2+70k. Согласитесь, в этом милом многочленике не сразу угадывается та страшная абракадабра из зелёных скобок? А мы продолжаем. Итак. Теперь придётся ещё раз включить мозг и подумать. Если вдруг внезапно указом президента окажется, что вот этот милый многочлен будет при любом целом неотрицательном k делиться на 120 - то как вы думаете, что произойдёт? Правильно, мы решим задачу, потому что тогда выражение в зелёных скобках будет делиться на 120 по предположению, а в красных - по указу президента. А значит, что мы докажем переход индукции.

Но где взять такой хороший указ президента? Можно порыться в государственном архиве, но никто не гарантирует, что даже там вы его найдёте. Давайте изобретём этот указ сами? Итак, перед нами стоит новая задача:

2) Доказать, что при любом целом неотрицательном k выражение 5k^4-10k^3+55k^2+70k делится на 120 или, что то же самое, доказать, что при любом целом неотрицательном k выражение 5(k^4-2k^3+11k^2+14k) делится на 120. Или, что то же самое - доказать, что при любом целом неотрицательном k выражение k^4-2k^3+11k^2+14k делится на 24. Это выражение тоже раскладывается на множители и можно поизобретать решения, которые с этого момента более изящные и просттые, но зачем? Задачу 2) будем решать методом математической индукции

Итак, база. При k=0 выражение k^4-2k^3+11k^2+14k делится на 24. Думаю, что много кто догадается, что 0 делится на 24

Переход. Пусть при k=m выражение делится на 24. Докажем, что при k=m+1 выражение также делится на 24. Для этого рассмотрим наше выражение при k=m+1.

Это будет (m+1)^4-2(m+1)^3+11(m+1)^2+14(m+1)=... Опять много скобочек, да? Давайте снова попросим дядю Ньютона раскрыть их. Итак,

...=(m^4-2m^3+11m^2+14m)+(4m^3+6m^2+4m+1-6m^2-6m-2+22m+11+14)

Дальше мы снова заметим, что то, что образовалось в зелёных скобках делится на 24 по предположению индукции. А что такое написано в красных скобках? А вот, что:

4m^3+20m+24. Осталось доказать, что при лбом целом неотрицательном m данное выражение будет делиться на 24. На этот раз мы точно не будем ждать президентского указа, а сами докажем задачу 3)

3) Доказать, что при любом целом неотрицательном m выражение 4m^3+20m+24 делится на 24. Или, что равносильно, доказать, что при любом целом неотрицательном m выражение m^3+5m+6 делится на 6. Те, кто всё ещё не очень понимают суть метода математической индукции могут доказать это используя данный метод самостоятельно (а мы пока в скобочках напишем им подсказку: ((q^3+3q^2+3q+1)+(5q+5)+6)), сами же сделаем так.

Очевидно, что m^3+5m+6 делится на 6 тогда и только тогда, когда m^3+5m делится на 6.

Очевидно, что m^3+5m делится на 6 тогда и только тогда, когда m^3-m делится на 6.

Очевидно, что m^3-m делится на 6 тогда и только тогда, когда m(m-1)(m+1) делится на 6

Очевидно, что (m-1)m(m+1) - произведение трёх последовательных целых неотрицательных чисел. А среди трёх последовательных целых неотрицательных чисел есть число, кратное двум. А также есть число, кратное трём. Так как 2 и 3 взаимно-просты - то всё произведение делится на 6 при любом целом неотрицательном m.

Таким образом мы решили задачу 3)

Таким образом мы решили задачу 2)

Таким образом мы решили задачу 1)

Если кто-то не понял - может прочесть решение с конца. Иногда от этого тоже наступает просветление.

Не совсем понятно с этой теоремой, на 3 я сам доказал, это легко, а вот на 5 и 8.

Я понимаю, что тут ничего не понятно. Но что именно непонятно? постарайся задать вопрос, ответом на который будет не пересказ текста

Я себя совсем тупым почувствовал прочитав и не поняв большую часть написанного...(

Ну не умею я ставить значки следствия, делимости и сравнения по модулю в данном релакторе

[IvPBay 459]

Да вот с индукцией большие цифры получаются. Всё застопорилось на выражении k^5 + 15k^3 + 60k^2 + 44k. И всё, дальше я не могу.

Я понимаю, что тут ничего не понятно. Но что именно непонятно? постарайся задать вопрос, ответом на который будет не пересказ текста

Да я не знаю как решать через модули. Понял, как объяснить на 8 при нечётных n, и всё. Как на 8 при чётных n и на 5 я не знаю.

[Isaac New 3,552]

Да вот с индукцией большие цифры получаются. Всё застопорилось на выражении k^5 + 15k^3 + 60k^2 + 44k. И всё, дальше я не могу.

Ну так примени предположение, и у тебя степень понизится.

Да я не знаю как решать через модули. Понял, как объяснить на 8 при нечётных n, и всё. Как на 8 при чётных n и на 5 я не знаю.

8: я доказываю, что n(n^2-5n+26) делится на восьмёрку. Для этого я смотрю, на какую степень двойки делится n и доказываю, что оа оставшуюся делится второй множитель

5: Ну, пятёрку можно простым перебором сделать без попыток применять выскую науку. Что именно-то непонятно?

[IvPBay 459]

Ну так примени предположение, и у тебя степень понизится.

???

8: я доказываю, что n(n^2-5n+26) делится на восьмёрку. Для этого я смотрю, на какую степень двойки делится n и доказываю, что оа оставшуюся делится второй множитель

???

5: Ну, пятёрку можно простым перебором сделать без попыток применять выскую науку. Что именно-то непонятно?

Перебором чего?

[IvPBay 459]

На 8 доказал (логически - там по-любому получаются три чётных числа), осталось только доказать на 5.

[Isaac New 3,552]

???

???

Перебором чего?

Перебором остатков.

Просто примени предположение индукции - и у тебя будет новый многочлен, который ты должен доказать что делится на 120 при любом целом n

Две скобки. Доказываю, что их произведение делится на 8. В чём проблемы?

[Diplomate 3,115]

Isaac New, а твое первое доказательство — это какой класс школы? А то я что-то его не понял. Я так понял, это лучше без ММИ пробовать решать.

[IvPBay 459]

Да уже всё. Тему сдал (правда, не знаю, наскребут баллы или нет), надо быстрее - за преждевременную сдачу программы можно получить автомат.

[Isaac New 3,552]

Isaac New, а твое первое доказательство — это какой класс школы? А то я что-то его не понял.

Лично для меня быстрее без. А я не знаю, когда в школьной программе индукция и остатки. Вроде бы в углублённых учебниках есть, но не каждый учитель будет такое давать, ибо в ЕГЭ этой штуки нет, а учителя и так хронически не успевают. Лично меня весь седьмой класс учили этому. Но и остатки, и делимость считаются базовой частью внешкольной математики и научиться такому никогда не поздно. Если у тебя есть желание что-то про это почитать - можешь начать с википедии, статья "сравнения по модулю". Там посреди всей ахинеи про факториальные кольца - вполне читаемый текст проскальзывает

Я так понял, это лучше без ММИ пробовать решать.

Знаешь, лучше/хуже - главное, чтобы правильно и, по возможности, удобно

[MaslovRG 6,935]

Индукция в моем физико-математическом была в 10 классе.