олимпиадного типа задачка

[avva]

Доказать, что если n>=3, то nⁿⁿⁿ - nⁿⁿ (словами: степенная лесенка из четырёх n минус степенная лесенка из трёх n) делится на 1989.

Несложная и совершенно неглубокая, но вчера скоротала мне автобусную поездку — решал её в уме. И то неплохо.

Comments

[yappie.livejournal.com]

ого =)) это какой уровень должен быть, чтобы в уме доказывать.

[castleghost.livejournal.com]

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

[avva.livejournal.com]

Она только кажется сложной.

[little-orange.livejournal.com]

Бывают же такие люди!!!! *восхищенно*

[istaksiuatl.livejournal.com]

как это не странно, решения олимпиадных задачек невероятно прочищает голову. мы вот не так давно с другами решали на ходу задачки из олимпиады по математической лингвистике для старших классов каких-то чудо-школ. Там было задание, у нас на него ушло часа два, без преувеличений - японская таблица умножения. В русской транскрипции написаны примеры(на японском, естественно) и надо вычленить по логике словообразования, какое число какое. (абракадабраХкадабраабра=макабра))) И что вы думаете? Решили! А потом идешь - и чувствуешь себя каким-то просто СУПЕРМЕНОМ.

[yappie.livejournal.com]

это ли не есть уровень подготовки?

[yappie.livejournal.com]

да уж, безусловно кажется =)

[castleghost.livejournal.com]

Он самый. Просто я подумал, что вы про уровень интеллекта (IQ который).

[arno1251.livejournal.com]

Видимо, доказательство должно быть по индукции? Но вот с отправной точкой не получается что-то.
Итак,
3^3 = 27
27^3 = 19683
19683^3=7625597484987
7625597484987 - 19683 = 7625597465304
Но это число не делится на 1989. Получается 3833885100 и 1404 в остатке.

Может быть, в степенной лесенке порядок операций должен быть "справа налево"? :)

[yappie.livejournal.com]

=)

[tt-rex.livejournal.com]

n - целое?

[nidd.livejournal.com]

здороово. мне понравилось. только вот придумывать такие задачки гоорааааздо сложнее чем их решать. Шарыгина теперь нет :(

[avva.livejournal.com]

Может быть, в степенной лесенке порядок операций должен быть "справа налево"? :)

Конечно, это всегда имеется в виду. Ведь при порядке "слева направо" лесенка не нужна, её можно схлопнуть в степень порядка по правилу (a^b)^c = a^(b*c). Поэтому, когда есть лесенка, всегда подразумевается порядок a^(b^c).

[avva.livejournal.com]

Ага.

[arno1251.livejournal.com]

М-да... с возведением тройки в степень 7625597484987 возникли некоторые проблемы...

[avva.livejournal.com]

:)

Ne delitsja na 1989 ni pri kakih n

[(Anonymous)]

Prikolist vy Avva. Ochen' legko dokazat', chto ne delitsja ni pir kakih celyh n. Izdevaetes' na narodom?

[avva.livejournal.com]

Что, неужели ни при каких целых n, даже при n=1989? ;)

Делится, делится. Для всех n>=3. Вы ошиблись где-то в лёгком доказательстве.

impho

[chhwe.livejournal.com]

Обратите внимание, что не всегда верно 1989<=nⁿⁿⁿ - nⁿⁿ даже если n целое и больше трёх или равно трём. Тогда, очевидно, nⁿⁿⁿ - nⁿⁿ никак не может делиться на 1989 нацело и доказать Ваше утверждение становится невозможным.

[flaass.livejournal.com]

Вспомнил еще про 1989: придумать треугольник, который можно разрезать на 1989 равных треугольников.

Re: impho

[avva.livejournal.com]

Нет, это, конечно, всегда верно. Вы, возможно, неправильно понимаете, как считается nⁿⁿⁿ; см. один из предыдущих комментариев.
Для любого n>=3 nⁿⁿⁿ - совершенно астрономическое по своим размерам число, и, конечно, намного намного больше nⁿⁿ. Собственно, даже для n=2 разница больше 1989, хотя, действительно, не делится на 1989.

Сколько автобусных останок?

[(Anonymous)]

Сколько автобусных останок?
Гипотеза - 5
1989 = 9*13*17 - 1 остановка
делимость на 9 - 0 остановок
делимость на 13,17 - 2*2 остановок
Итого 5.
Угадал?

[dimrub.livejournal.com]

Сделал 9, застрял на 13 и 17. Подозреваю, что надо перебирать остатки. Неужели? :)

[bachelor.livejournal.com]

Не могу вспомнить, как мы когда-то в 8 классе на олимпиадах подобные задачки решали. Сейчас - рекуррентный спуск по функции Эйлера всех множителей (9,13,17), и они, по сути, схлопываются на третьем кругу (не до конца, правда - все равно небольшой перебор нужен. Были б лесенки повыше - даже автобус бы не понадобился). Извиняюсь за шифровку - кто это знает, тому решать нечего, а другим не хочу портить удовольствие.

Но что ж мы тогда делали? Неужели теорему Ферма на олимпиаде выдодили? Да, довыдавливал я из себя олимпиады - ничего не помню...

[avva.livejournal.com]

Я тоже не помню, если честно ;)

[avva.livejournal.com]

Нужна теорема Ферма ;) см. мою субботнюю запись.

мифический человеко-месяц

[chhwe.livejournal.com]

Был в отъезде, сорри, не сразу смог ответить.

Обратите внимание, что я говорил о 1989 и о трёх. Бывают случаи, когда 15 -- простое число и для его разложения на простые множители достаточно очень несложного квантового компьютера.

Вряд ли, конечно, жюри математической олимпиады зачтёт такое решение (см. заголовок постинга), но с моей точки зрения, оно вполне правомерно -- задача довольно некорректно поставлена: предлагается доказать утверждение очевидно неверное при некоторых не очень патологических условиях.

[(Anonymous)]

а доказательство где? =)

--pf (http://www.m14m.net/pf)

[(Anonymous)]

Ah. (http://www.livejournal.com/users/avva/1220725.html#cutid1) Never mind.

--pf (http://www.m14m.net/pf)

[dimrub.livejournal.com]

Да-да, я так и предполагал, но до конца так и не допер.

бег пардон

[chhwe.livejournal.com]

извините за флейм, но когда я вижу числа, записанные цифрами в позиционных системах счисления, трудно бывает удержаться от деструктивной математики

вот что (http://www.livejournal.com/users/chhwe/15851.html) я имел в виду, простите великодушно