Две задачки для школьников.

[maxal]

ИСН, нет проблем. Сообщения в темах немного перетасовал, чтобы тематика не повторялась в несвязанных темах.

[Коровьев]

Доказать элементарно (без привлечения сведений из теории чисел) что если простое число представимо в виде суммы двух квадратов целых чисел, то это представление, с точностью до порядка слагаемых, единственно.

[Sonic86]

Есть такая книжка Серпинского: Что мы знаем и чего не знаем о простых числах.
Если упростить немного для этой задачи то, что там написано, то будет такое решение:
Пусть $p$ - простое и $p=x^2+y^2$ и $p=u^2+v^2$ и $x\neq u$ и $y \neq v$. Тогда
$p^2=(x^2+y^2)(u^2+v^2)=(xu)^2+(xv)^2+(yu)^2+(yv)^2$
$p^2=(xu+yv)^2+(xv-yu)^2=(xu-yv)^2+(xv+yu)^2$
Среди этих разложений найдется разложение, в котором есть слагаемое, кратное $p$.
Действительно: $(xu+yv)(xv+yu)=uv(x^2+y^2)+xy(u^2+v^2)$.
Левая часть делится на $p$, значит, хотя бы 1 множитель делится на $p$.
С помощью этого факта легко найти, что разложения отличаются лишь порядком сомножителей.
Простота использована в факте делимости.
А вообще, где-то раньше Руст говорил, что эту задачу лучше решать с помощью теории групп (кольцо гауссовых целых),
а более простые доказательства являются лишь его усложениями и загромождениями (не цитата),
в чем я, конечно же, с ним согласен. В таком доказательстве смысла не видно, нет сути. Если это решение давать детям, то им, скорее всего, задача покажется неинтересной.
(Естественно, $p=4k+1$ или $p=2$).

[Коровьев]

Sonic86 писал(а):

А вообще, где-то раньше Руст говорил, что эту задачу лучше решать с помощью теории групп (кольцо гауссовых целых),

Sonic86 писал(а):

а более простые доказательства являются лишь его усложениями и загромождениями (не цитата),в чем я, конечно же, с ним согласен.

Sonic86 писал(а):

В таком доказательстве смысла не видно, нет сути. Если это решение давать детям, то им, скорее всего, задача покажется неинтересной.
(Естественно, $p=4k+1$ или $p=2$).

Вы перепутали задачку для школьников с серьёзной теоремой.
Серьёзно такие вопросы о представлении простых чисел разложимыми формами решаются в теории дивизоров. Для квадратичных полей она решена полностью.
В частности, /данная задачка/ для мнимого квадратичного поля $R(\sqrt{-1})$ число классов дивизоров равно единице, а посему разложение на простые множители в этом поле однозначно, и, как следствие, норма простого числа этого поля есть простое рациональное число единственным способом представимо ввиде суммы двух квадратов целых чисел...
Но если это решение дать специалистам, то им оно покажется банальным, а школьникам непонятным. Задача же данного форума, по моему глубокому уразумению, показать, как можно решить ту или иную, простую или сложную задачу.

Добавлено спустя 7 минут 30 секунд:

Задача 2.
Доказать что простое число
$p=4k+1$
представимо в виде суммы квадратов двух целых чисел.

[Sonic86]

Ага, простите, действительно перепутал. Но про эту сложную то что писал - правда, и все равно все задачи из этого района туда относятся (кстати, можно формулировать и без дивизоров, хотя может я и упрощаю)

Но решение-то я то написал, которое надо.

[Коровьев]

Решение верно, но есть куча других решений, у меня другое.
Сейчас не об этом.
Про задачку 2, возможно, позже.
"Лирическое отступоление".
Великий Куммер доказал-таки теорему Ферма, ту самую.
Но.
Выяснилось, что разложение на простые множители в большинстве полях алгеброических целых числах неоднозначно. В поле целых рациональных чисел со времён Евклида сие не подвергалось сомнению, но в полях целых алгеброических числах это оказалось неверным для большинства полей.
А Куммер доказал БТФ именно исходя из однозначности разложения. Пытаясь обойти это препятствие Кукммер и создал теорию дивизоров - делителей в переводе. Позже Дедекинд в своих кольцах развил эту теорию, назвав определённый класс чисел идеалами . Доказать полностью БТФ не удалось, но появилось мощное орудие в теории чисел, которое и позволило решить класс задач, не имевших до сих пор решения.
***
Задача 1 и задача 2 я поставил, чтобы получить практически элементарно теорему существования.
Задача 3.
Доказать, что существует бесконечное множество таких целых рациональных $a$, что уравнение
$x^2+ a^2$
принимает бесконечно большое число раз значение равное простому числу при целых$x$.
/Дирихле доказал это для арифметических прогрессий, но все попытки доказать это для конкретной функции большей степени ни к чему не привели./
Исходные данные.
1. Простое число $P=4k+1$ представимо в виде суммы квадратов двух целых чисел с точностью до порядка слагаемых единственным способом.
2. Сумма ряда обратных простых чисел $P=4k+1$ расходится.
/Это доказал Дирихле в своей теореме о простых числах в арифметической прогрессии. А бесконечность таких простых чисел - следствие этой теоремы./
3. Сумма ряда последовательных квадратов обратных целых чисел сходится.
И равна $\pi ^2/6$
4. Решение, на мой взгляд, довольно-таки простое. И короткое.

[Sonic86]

! Исходя из этого требуемое легко получается чисто логически от противного.
Пусть таких $a$ - конечное число $N$. Тогда ряд обратных величин всех простых вида $x^2+a^2$
ограничен сверху рядом из величин, обратных к квадратам и умноженным на $N$, то есть ограничен
величиной $frac{N \pi^2}{6}$. Но ряд по все таким простым бесконечен (это мы знаем).
Значит, предположение неверно.
Вот только каковы эти $a$ мы только отсюда так и не узнаем.
Поэтому, может быть, попробовать оценить плотность множества всех таких $a$?
Согласно интуиции, она должна быть равна 1.

[Коровьев]

Я приведу более расширенное доказательство.
Составим бесконечную матрицу из всех обратных простых данного вида.

\[ \left( \begin{array}{l} \begin{array}{*{20}c} {{\textstyle{1 \over {1^2 + x_{11}^2 }}}} & {{\textstyle{1 \over {1^2 + x_{12}^2 }}}} & {{\textstyle{1 \over {1^2 + x_{13}^2 }}}} & {...} \\ \end{array} \\ \begin{array}{*{20}c} {{\textstyle{1 \over {2^2 + x_{21}^2 }}}} & {{\textstyle{1 \over {2^2 + x_{22}^2 }}}} & {{\textstyle{1 \over {2^2 + x_{23}^2 }}}} & {...} \\ \end{array} \\ \begin{array}{*{20}c} {{\textstyle{1 \over {3^2 + x_{31}^2 }}}} & {{\textstyle{1 \over {3^2 + x_{32}^2 }}}} & {{\textstyle{1 \over {3^2 + x_{33}^2 }}}} & {...} \\ \end{array} \\ \begin{array}{*{20}c} {\begin{array}{*{20}c} {...} & {} \\ \end{array}} & {...} & {} & {...\begin{array}{*{20}c} {} & {...} \\ \end{array}} \\ \end{array} \\ \end{array} \right) \]

В $l$-той строке все обратные простые вида

\[{\textstyle{1 \over {l^2 + x_{lk}^2 }}}\]

в порядке убывания величин

\[ l<x_{kl} < x_{k(l + 1)} \]

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

\[ \sum\limits_{k = 1} {{\textstyle{1 \over {l^2 + x_{lk}^2 }}}} < \sum\limits_{k = 1} {{\textstyle{1 \over {x_{lk}^2 }}}} < \sum\limits_{n = 1}^\infty {{\textstyle{1 \over {n^2 }}}} = \frac{{\pi ^2 }}{6} \]

\[ \sum\limits_{k = 1} {{\textstyle{1 \over {k^2 + x_{kl}^2 }}}} < \sum\limits_{k = 1} {{\textstyle{1 \over {k^2 }}}} \le \sum\limits_{n = 1}^\infty {{\textstyle{1 \over {n^2 }}}} = \frac{{\pi ^2 }}{6} \]

Далее.
Пусть число строк с бесконечным числом членов конечно. Сумма конечного числа конечных величин конечна.
Вычеркнув эти строки из матрицы мы получим матрицу с конечным числом столбцов, сумма всех членов которой должна расходиться.
Но это невозможно. /Сумма конечного числа конечных величин конечна./
Следовательно, исходное допущение неверно и число строк с бесконечным числом членов бесконечно.
*****
Разумеется, данная метода годна и для многих других мнимых квадратичных полей с тривиальными единицами. Что касаемо вещественных квадратичных полей, то там неясно, ибо в них простое число допускает бесконечно много представлений квадратичной формой из-за наличия нетривиальных единиц в этих полях.
К примеру, форма

\[ a^2 -5 b^2 \]

Допускает представление простого числа 11 бесконечными способами.

\[ N(4 + \sqrt 5 ) = N((4 + \sqrt 5 )(2 + \sqrt 5 )^{2n} ) = N(a_n + b_n \sqrt 5 ) = 11 \]

так как

\[ N(((2 + \sqrt 5 )^{2n} ) = N^{2n}(2 + \sqrt 5 ) =[(2 + \sqrt 5 ) (2 - \sqrt 5 )]^{2n}= 1 \]

[Коровьев]

Цитата:

Я закончу дело взявши обязательство.
В.Высотский

Задача 2.
Доказать, что простое число вида 4k+1 представимо ввиде суммы двух квадратов.

Лемма. Без доказательства. /Оно довольно простое, исходя из Малой теоремы Ферма/
Сущеcтвует такое a, что a^2+1 делится на простое число $P$ вида 4k+1

Пусть
$a^2+1\equiv$ $0$ $(mod P)$
Имеем
$(x+ay)(x-ay)=x^2 -a^2y^2=x^2+y^2 -(1+a^2)y^2 \equiv x^2+y^2$$(mod P)$
Пусть в выражении $x+ay$ величины $x$ и $y$ независимо друг от друга пробегают все целые числа от $1$ до $[\sqrt P]+1$
$[\sqrt P]$ - означает целую часть числа.
Мы получим $([\sqrt P]+1)^2$ чисел.
Так как
$([\sqrt P]+1)^2>P$
то среди них найдутся сравнимые по модулю $P$ как минимум два числа. /Принцип ящиков и предметов/
$x_1+ay_1 \equiv c(mod P)$
$x_2+ay_2 \equiv c(mod P)$
Вычтем из первого второе. Получим
$(x_1-x_2)+a(y_1-y_2)=x_0+ay_0 \equiv 0(mod P)$
где $x_0$ и $y_0$ заведомо меньше по модулю $[\sqrt P]+1$
Следовательно
$(x_0+ay_0)(x_0-ay_0) \equiv x_0^2+y_0^2 \equiv 0(mod P)$
Иначе
$mP=x_0^2+y_0^2<[\sqrt P]^2+[\sqrt P]^2<2P$
Отсюда $m=1$
И окончательно получим
$x_0^2+y_0^2=P$

[Коровьев]

Довольно популярная задача на многих форумах про сложение кирпичей.
Кирпичи выкладываются по одному друг на друга со сдвигом в одну сторону. На сколько далеко от центра первого кирпича по горизонтали будет находиться край последнего кирпича, чтобы стопка не рухнула.
Эта задача была, говорят, у Перельмана и он доказывает, что сдвиг может быть на любое расстояние, вплоть до бесконечности. Но, говорят, в его решении есть ошибка. Я доказательства его не видел.
Однако попробовать найти решение можно.
*****
p.s. Ответ писать не надо. Нужно решение.

[ИСН]

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

[TOTAL]

Коровьев писал(а):

Ответ писать не надо. Нужно решение.

И ответ и решения зависят от того, сколько кирпичей всего положено. Если на первом кирпиче лежат $n$ кирпичей, то ответ будет больше по сравнению со случаем, когда на первом кирпиче лежат $5n$ кирпичей. Хотя нет, я перепутал, ведь первый кирпич сверху. Нет, первый кирпич не на самом верху. В этом и вся хитрость вопроса?

[Коровьев]

ИСН писал(а):

Классическое решение банально, ошибаться там негде. Гармонический ряд расходится.

А вот знаменитый Перельман похоже смог.
http://www.etudes.ru/ru/forums/topic.php?id=6

Цитата:

Yura
Ошибся Перельман, приведя это решение задачи в Занимательной математике. Кирпичи упадут. Между прочим, в одном из учебников по Теормеханике в разделе по вычислению координат центра тяжести приведено правльное решение .... (Самое забавное, что даже в Кванте в своё время было приведено решение Перельмана)

Цитата:

Yura
Это публикация в Кванте с ошибочными рассуждениями
http://kvant.mccme.ru/1984/07/garmonicheskij_ryad.htm
и мой комментарий
http://elektrik.pisem.net/photo/2mistake.png

http://elektrik.pisem.net/photo/2mistake.png
Пара верхних кирпичей сразу рухнет

[ewert]

Авторы "Кванта" действительно ошиблись, но совсем ненамного -- всего лишь в два раза. Последовательность сдвигов каждого кирпича относительно предыдущего (начиная с верхнего) должна быть такой:

$${L\over2},\ {L\over4},\ {L\over6},\ {L\over8},\ {L\over10},\ {L\over12},\ \dots\;. $$

Т.е. $a_k={L\over2k}$. Если теперь $x_n$ -- смещение центра масс стопки из $n$ кирпичей относительно центра кирпича, на котором эта стопка лежит, то:

$ x_1=a_1={L\over2}; $

$ x_2={1\over2}\big((a_1+a_2)+a_2\big)={1\over2}(a_1+2a_2)={L\over2}; $

$ x_3={1\over3}\big((a_1+a_2+a_3)+(a_2+a_3)+a_3\big)={1\over3}(a_1+2a_2+3a_3)={L\over2}; $

ну и т.д.; ни одна "надстопка" не рухнет. При этом смещение самого верхнего кирпича относительно самого нижнего (сумма всех $a_k$) -- это действительно частичная сумма расходящегося гармонического ряда.

Боюсь, что это решение оптимально: система

$$\begin{cases} a_1\leqslant{L\over2}; \\ {1\over2}(a_1+2a_2)\leqslant{L\over2}; \\ .\ .\ .\ .\ .\ .\ .\ \\ {1\over n}(a_1+2a_2+\dots+na_n)\leqslant{L\over2}; \\ a_1+a_2+\dots+a_n=\max \end{cases}$$

-- это задача линейного программирования, и максимум достигается в вершине, где все неравенства превращаются в равенства.

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

[Коровьев]

Не понятно

ewert писал(а):

При этом смещение самого верхнего кирпича относительно самого нижнего (сумма всех $a_k$) -- это действительно частичная сумма расходящегося гармонического ряда.

и

Цитата:

Т.е. по такой лесенке действительно можно забраться сколь угодно далеко. Но, между прочим -- не бесконечно далеко! Если стопка состоит из бесконечного количества кирпичей, то они не смогут высунуться дальше чем на полкирпича относительно самого нижнего.
Правда, при условии, что сдвиги монотонны.

Разве гармонический ряд /сдвиги/ не принадлежит монотонной функции $x^-^1$.
***
Вообще-то вместо обратного ряда натуральных чисел, можно взять обратный ряд простых чисел /и не только/, при этом, При этом смещение самого верхнего кирпича относительно самого нижнего /сумма всех смещений/-- это также в пределе сумма расходящегося ряда. Однако, центр тяжести частичных "стопок", относительно нижнего кирпича, уже не будет постоянным, а будет уменьшатся до какого-то предела.