Задача про функцию

EUgeneUS · 11/12/16 14051 уездный город Н

codeineDreaming
шаг 0: $f(1)=1$ (вычеркнули $1$ )
шаг 1: $f(2)=3$ (вычеркнули $2$ , $3$ и серии квадратов $2^{2^N}$ и $3^{2^N}$ )
четверку пропускаем - этот полный квадрат уже вычеркнут.
шаг 2: $f(5) = a_2$ (вычеркнули $5$ , $a_2$ и серии квадратов $5^{2^N}$ и $a_{2}^{2^N}$ )

какое число удобнее всего выбрать в качестве $a_2$ ?

(если откроете, Вам будет стыдно)

подсказка - оно идет за пятеркой :mrgreen:

codeineDreaming · 14/12/21 15

EUgeneUS в сообщении #1542968 писал(а):

codeineDreaming
шаг 0: $f(1)=1$ (вычеркнули $1$ )
шаг 1: $f(2)=3$ (вычеркнули $2$ , $3$ и серии квадратов $2^{2^N}$ и $3^{2^N}$ )
четверку пропускаем - этот полный квадрат уже вычеркнут.
шаг 2: $f(5) = a_2$ (вычеркнули $5$ , $a_2$ и серии квадратов $5^{2^N}$ и $a_{2}^{2^N}$ )

какое число удобнее всего выбрать в качестве $a_2$ ?

(если откроете, Вам будет стыдно)

подсказка - оно идет за пятеркой :mrgreen:

Хорошо, мне действительно стало стыдно :facepalm:

тогда я продолжу следующие шаги:
шаг 3: $f(7)=8$ (вычеркнули $7$ , $8$ и серии квадратов $7^{2^N}$ и $8^{2^N}$ )
шаг 4: $f(10)=11$ (вычеркнули $10$ , $11$ и серии квадратов $10^{2^N}$ и $11^{2^N}$ )
шаг 5: $f(12)=13$ (вычеркнули $12$ , $13$ и серии квадратов $12^{2^N}$ и $13^{2^N}$ )
ну и так далее
так ведь...?

EUgeneUS · 11/12/16 14051 уездный город Н

codeineDreaming в сообщении #1542969 писал(а):

так ведь...?

Да, верно. Девятку пропустили - это верно.

Так как мы на каждом шаге "вычеркивали" пару минимальных (это было важно) ещё невычеркнутых чисел, мы "вычернули" все по построению. То есть для каждого натурального числа $a$ задали $f(a)$ .
Осталось доказать, что каждое число "вычеркнуто" ровно один раз.

codeineDreaming · 14/12/21 15

EUgeneUS в сообщении #1542970 писал(а):

Осталось доказать, что каждое число "вычеркнуто" ровно один раз.

Ну первым делом я бы сказал, что, очевидно, если что-то и могло совпасть, то эти значения должны находиться в сериях типа $2^{2^n}$ и $2^{3\cdot{2^n}}$ $(8^{2^n})$ или $3^{2^n}$ и $3^{3\cdot{2^n}}$ $(27^{2^n})$ (то есть в основании разные степени одного и того же числа).
Рассмотрим всевозможные серии с основанием $2$ , для остальных серий рассуждения абсолютно аналогичные. (мне так удобнее рассуждать)
Заметим, что в основании серии может стоять только $2$ в нечётной степени $(2, 8, 32, 128, 512...)$ . Действительно, $2$ в любой чётной степени - какой-то полный квадрат ( $2^{2n} = (2^n)^2$ ), следовательно он будет получен в какой-то из серий.
Дальше можно опереться на основную теорему арифметики и сказать, что для каких-то серий вида $2^{\alpha\cdot{2^n}}$ и $2^{\beta\cdot{2^m}}$ , где $\alpha$ и $\beta$ - произвольные различные нечётные числа, разложения на множители, очевидно, будет разным при любых значениях $n$ и $m$ (случай, если $\alpha$ и $\beta$ взаимно простые совсем понятен, но если условно $\alpha = \beta^2$ , то в принципе тоже ясно, что разложения будут представлять из себя двойки в разных степенях)
Ну и из этого всего следует, что ни при каких значениях в двух сериях с основанием $2$ числа совпасть не могут (эти рассуждения работают для любого другого основания), следовательно в принципе совпадений быть не может.

Нормальное доказательство или лажа?

EUgeneUS · 11/12/16 14051 уездный город Н

codeineDreaming в сообщении #1542976 писал(а):

Нормальное доказательство или лажа?

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

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

вторым шагом нужно доказать, что в натуральных числах не выполняется равенство $a^{2^\alpha} = b^{2^\beta}$ , где $a\ne b$ - натуральные и не являются полными квадратами, а $\alpha$ и $\beta$ - произвольные натуральные.

codeineDreaming · 14/12/21 15

EUgeneUS в сообщении #1542982 писал(а):

codeineDreaming в сообщении #1542976 писал(а):

Нормальное доказательство или лажа?

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

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

вторым шагом нужно доказать, что в натуральных числах не выполняется равенство $a^{2^\alpha} = b^{2^\beta}$ , где $a\ne b$ - натуральные и не являются полными квадратами, а $\alpha$ и $\beta$ - произвольные натуральные.

спасибо большое за помощь!!!

EUgeneUS · 11/12/16 14051 уездный город Н

lel0lel в сообщении #1542965 писал(а):

Функция биективна

Кстати, не верно
Инъекция доказывается не сложно.
А вот сюръекция не обязательна. Контрпримером является построенная выше функция, которая никогда не принимает значение $2$ .

lel0lel · 20/04/10 1889

Да, не то написал. Сюръекции нет (если функция действует из $N$ в $N$ ), дважды применяя функцию получаем только квадраты, а не $\mathbb{N}$

lel0lel · 20/04/10 1889

Введём обозначения: $N^2$ -- множество квадратов натуральных чисел, $K$ -- множество чисел, не являющихся квадратами, таких что отображение $f$ переводит их в квадраты. Тогда $N=N^2+K+(N-N^2-K)$ , эти три слагаемых-множества не пересекаются друг с другом. Отображение $f$ импликация, иначе, если $x_1\ne x_2$ и $f(x_1)=f(x_2)$ , то $x_1^2=x_2^2$ , что неверно. Рассмотрим во что преобразуются наши три множества. Так как $f(f(x))=x^2$ и $f(x^2)=f(x)^2$ , то $f[N]=N^2+K, f[f[N]]=f[N^2+K]=N^2=N^4+K^2+f[K]$ . Так как отображение импликативно, то $K^2+f[K]$ это все квадраты в множестве $N^2$ , показатель степени которых имеет вид $2(2s+1)$ , обозначим это множество $B_2$ . Далее $f[N^2]=f[N]^2=N^4+K^2=N^8+K^4+f(K)^2+K^2$ , тогда $K^4+f[K]^2=B_4$ (все такие биквадраты в $N^2$ , степень которых имеет вид $4(2s+1)$ )Пусть $f^n$ это декартова степень отображения. Очевидно $f^{2m}[N]=N^{2^m}$ , $f^{2m+1}[N]=N^{2^{m+1}}+K^{2^m}$ . Причём $K^{2^m}+f[K]^{2^{m-1}}=B_{2^m}$ . Собственно, решение задачи можно провести так: выбираем бесконечное множество чисел $K$ , не являющихся квадратами, строим импликацию так, что $f[K]=B_2-K^2$ ; строим ещё импликацию так, что $f[N-K-N^2]=K$ ; строим ещё импликацию так, что $f[N^2]=N^4+K^2$ .