инволюция специального вида

[maxal]

Руст писал(а):

Мы установили, что среди пар чисел (i,j) с условием ij>=n ровно s (i,f(k)) i<k и ровно s (k,j),j<f(k), т.е. s(f(k))=s(k).

Нет. Выше я определял функцию $S(p,q)=|\{ m : pm\geq n,\ m<q\}|$. Ты фактически доказал, что $S(k,f(k))=S(f(k),k),$ и наше $s(k)=S(k,f(k))=S(f(k),k)$.
Но ни откуда не следует, что $s(k)=s(f(k))$. Понятно, что $s(f(k))=S(f(k),f(f(k)))=S(f(f(k)),f(k))$, но это не имеет ничего общего с $s(k)=S(k,f(k))=S(f(k),k)$.

Руст писал(а):

Что касается

$$f(k-s(k))=\lceil\frac{n}{f(k)}\rceil$$

, я об этом не говорил, и возможно это вообще неверно.

Я описался. Должно быть

$$f(k-s(k))=\lceil\frac{n}{k}\rceil.$$

[Руст]

При рассмотрении функции двух переменных S(p,q) теряется часть информации, связанной с f(k). Поэтому, ещё раз попытаюсь объяснить со старым s(k). По определению:
$f(k)=\lceil\frac nk \rceil +s(k).$
Но это значит ещё то, что существуют
$i_1,i_2,...,i_j<k, f(i_j)=f(k)-j, \forall i\not =i_1,...,i_s, i<k \ f(i)>f(k).$
Докажем теперь, что f(f(k))=k.
Это верно для k=1,f(k)=n. Пусть это верно для всех чисел меньше k. Это значит, что
$f(f(k)-j)=i_j<k, \forall j<f(k)-s,f(j)>k.$
А это и значит, что f(f(k))=k.

[maxal]

Ага теперь похоже на правду. Попробую придать сказаному чуть более строгий вид:

Руст писал(а):

По определению:
$f(k)=\lceil\frac nk \rceil +s(k).$
Но это значит ещё то, что существуют
$i_1,i_2,...,i_j<k, f(i_j)=f(k)-j, \forall i\not =i_1,...,i_s, i<k \ f(i)>f(k).$

Другими словами,

$$f(k)=t\quad\Longleftrightarrow\quad \exists s\geq 0\ :\ f(\{ k-1, \dots, k-s \} ) = \{ t-1, \dots, t-s \}\ \ \ \wedge\ \ \ \forall i<k-s\ :\ f(i)>t.$$

При этом можно утверждать, что $s=t-\lceil\frac nk \rceil$.

Руст писал(а):

Докажем теперь, что f(f(k))=k.
Это верно для k=1,f(k)=n. Пусть это верно для всех чисел меньше k. Это значит, что
$f(f(k)-j)=i_j<k, \forall j<f(k)-s,f(j)>k.$
А это и значит, что f(f(k))=k.

Другими словами, $f(\{ f(k)-1, \dots, f(k)-s \}) = \{ k-1, \dots, k-s \}$, что вкупе с $\forall j<f(k)-s=\lceil\frac nk \rceil\ :\ f(j)>k$ доказывает, что $f(f(k))=k$.

[maxal]

Доказать явную формулу:

Для каждой пары чисел $(p,q)$ такой что $p\cdot q\geq n,$ но $p(q-1)<n$ и $(p-1)q<n,$ имеем $f(p)=q$ и $f(q)=p$.
Для чисел $k$, не попадающих ни в одну из таких пар $(p,q)$, имеем $f(k)=k$.