Студенческая олимпиада киевского мехмата 2013

[Keter]

dm в сообщении #693504 писал(а):

7. An integer is called good if it is the $k$-th power of an integer for some $k\ge 2$. Is finite or infinite the set of all integers that are not sums of two good integers? (Andriy Bondarenko)

Не понимаю смысла этой задачи.. Ведь существует очень много чисел $a \ne b^2+c^2.$ А это уже по идеи означает, что множество натуральных чисел, которые не являются суммой двух хороших, бесконечно.

[xmaister]

Keter в сообщении #693819 писал(а):

Не понимаю смысла этой задачи.. Ведь существует очень много чисел $a \ne b^2+c^2.$ А это уже по идеи означает, что множество натуральных чисел, которые не являются суммой двух хороших, бесконечно

Сказано, $k\ge 2$

[Keter]

xmaister, ну всё правильно. При k=2 суммой двух квадратов могут не быть бесконечно много чисел, так как ими не являются числа вида $4n+3.$ Этого достаточно, для того чтобы ответить на вопрос задачи infinite.

[Cash]

Недостаточно, поскольку некоторые из этих чисел, например, $35$, можно выразить суммой двух кубов.
$7=2^3+(-1)^3$
$31=3^3+2^2$
$15 = 2^4+(-1)^3$
и т.д.

[Keter]

Cash, ну и? Подразумевается, что таких чисел крайне мало.

[Cash]

Да,ладно...
Еще накидал...

-- Пн мар 11, 2013 00:38:26 --

Много чисел, не представимых в виде $a^2-b^3$?

[Keter]

Cash, бесконечно.

-- 11.03.2013, 00:08 --

Cash в сообщении #693879 писал(а):

Недостаточно, поскольку некоторые из этих чисел, например, $35$, можно выразить суммой двух кубов.
$7=2^3+(-1)^3$
$31=3^3+2^2$
$15 = 2^4+(-1)^3$
и т.д.

Да, но все эти числа будут подмножеством бесконечного множества чисел $4n+3.$ И по мере увеличения $n$ их плотность вроде уменьшается. Значит, при их исключении бесконечное множество останется.

Конечно, Вы полностью правы. И я задумался как строго это доказать.

[nnosipov]

Cash в сообщении #693886 писал(а):

Много чисел, не представимых в виде $a^2-b^3$?

Вопрос, интересный сам по себе. Например, в таком виде нельзя представить любое число вида $-4c^2-1$, где целое $c$ не имеет простых делителей вида $4k+3$. Есть и другие подобные примеры.

[Keter]

nnosipov, только сейчас заметил Ваше сообщение.

nnosipov в сообщении #693712 писал(а):

dm в сообщении #693504 писал(а):

7. An integer is called good if it is the $k$-th power of an integer for some $k\ge 2$. Is finite or infinite the set of all integers that are not sums of two good integers?

Суммой двух квадратов не представляется любое число вида $4n+3$. А различных сумм вида $a^k+b^l$, где $k>2$ или $l>2$, мало. Поэтому "infinite".

Я похоже рассуждал. Но всё таки, как строго доказать, что "различных сумм вида $a^k+b^l$, где $k>2$ или $l>2$, мало." Ведь на таких олимпиадах именно это и требуется?

[nnosipov]

Оценим сверху количество $k$-х степеней $>1$, которые не превосходят $N$. Имеем $N \geqslant a^k \geqslant 2^k$, откуда $k \leqslant \log{N}$ и $a \leqslant N^{1/k}$. Поэтому оценка сверху --- это величина порядка $N^{1/2}\log{N}$. Если же начинать не с квадратов, а с кубов, то --- $N^{1/3}\log{N}$. В итоге всевозможных сумм двух точных степеней, одновременно не являющихся квадратами, будет порядка $N^{1/2+1/3}\log^2{N}=o(N)$.

А вот что делать с разностью степеней, пока не понимаю. Я невнимательно прочитал условие задачи и думал, что речь идёт о натуральных числах.

[Keter]

nnosipov, речь идёт о натуральных числах. Спрашивается: finite or infinite множество натуральных чисел, которые не являются суммой двух хороших?

-- 11.03.2013, 16:51 --

nnosipov в сообщении #694124 писал(а):

Я невнимательно прочитал условие задачи и думал, что речь идёт о натуральных числах.

Еще раз перечитал. Вы всё правильно поняли. Вот официальный источник: http://putnam.ho.ua/mechmat/2013/mm13sm.pdf
Там "...является степенью натурального..." и "...множество натуральных..."

[nnosipov]

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