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

[maxal]

Перестановка $\pi$ чисел $1,2,\dots,n$ строится так:
для каждого $k=1,2,\dots,n$ из ряда чисел $1,2,\dots,n$ выбирается $\lceil\frac{n}{k}\rceil$-е по счету ранее невыбранное число, и $\pi_k$ полагается равным этому числу.
Например, для $n=7$ получается перестановка $\pi=(7,4,3,2,5,6,1)$.

Доказать, что для любого $n$ перестановка $\pi$ является инволюцией, т.е. $\pi\cdot\pi = id.$

[Руст]

А разве это не вытекает из $[\frac{n}{[n/k]}]$. Только я использовал [] из за незнания как ставить скобки, употреблённые автором.

[Brukvalub]

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

А разве это не вытекает из $[\frac{n}{[n/k]}]$. Только я использовал [] из за незнания как ставить скобки, употреблённые автором.

Может быть, имеется в виду равенство $[\frac{n}{[n/k]}]=k$ ?

[Руст]

Да. Лучше ввести обозначение f(k) минимальное число, для которого
$kf(k)\ge n, \ f(k)\not =f(i),i<k$.
Тогда легко понять, что f(f(k))=k.

[maxal]

Brukvalub писал(а):

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

А разве это не вытекает из $[\frac{n}{[n/k]}]$. Только я использовал [] из за незнания как ставить скобки, употреблённые автором.

Может быть, имеется в виду равенство $[\frac{n}{[n/k]}]=k$ ?

Какое же это равенство? Подставьте, например, $n=4,\ k=3$.

[maxal]

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

Да. Лучше ввести обозначение f(k) минимальное число, для которого
$kf(k)\ge n, \ f(k)\not =f(i),i<k$.
Тогда легко понять, что f(f(k))=k.

Это всего лишь переформулировка. "Легко понять" - это не доказательство.

[Руст]

После этой переформулировки всё становится очевидным. Пусть на множестве P={1,2,...,n} установлено соответствие Галуа R={(k,m)|km>=n}. Тогда если имеется s элементов $(k,m)\in R,m<f(k)$, то имеется в точности s элементов $(r,f(k)),r<k$, что доказывает f(f(k))=k.

[Brukvalub]

maxal писал(а):

Brukvalub писал(а):

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

А разве это не вытекает из $[\frac{n}{[n/k]}]$. Только я использовал [] из за незнания как ставить скобки, употреблённые автором.

Может быть, имеется в виду равенство $[\frac{n}{[n/k]}]=k$ ?

Какое же это равенство? Подставьте, например, $n=4,\ k=3$.

Я и не утверждал, что это равенство-верное, а всего лишь попросил уточнить предыдущий пост Руста, поскольку он был мне непонятен, но напрашивалось именно такое его уточнение.

[maxal]

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

После этой переформулировки всё становится очевидным. Пусть на множестве P={1,2,...,n} установлено соответствие Галуа R={(k,m)|km>=n}.

Что это за "соответствие Галуа", как оно определяется в общем виде? И что чему тут "соответствует"?
Судя по данному определению R, это скорее отношение на множестве P чем соответствие.

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

Тогда если имеется s элементов $(k,m)\in R,m<f(k)$, то имеется в точности s элементов $(r,f(k)),r<k$, что доказывает f(f(k))=k.

Что-то я не понял, как это оно сразу доказывает f(f(k))=k. Поясни.
Я попробовал восстановить недостающие звенья доказательства, но полного доказательства на этом пути сходу все равно не получилось.

Введем обозначение

$$S(p,q) = \left|\{ m : (p,m)\in R,m<q\}\right| = \max\{0,q-\left\lceil\frac{n}{p}\right\rceil\}.$$

Тогда утверждение про "s элементов" можно переформулировать как $S(k,f(k))=S(f(k),k)$, что влечет тождество

$$k +\left\lceil\frac{n}{k}\right\rceil = f(k) + \left\lceil\frac{n}{f(k)}\right\rceil.$$

Теперь для доказательства того, что f() является инволюцией достаточно было бы показать, что уравнение для каждого y из P уравнение
$x+\left\lceil\frac{n}{x}\right\rceil = y$
имеет не более двух целочисленных решений относительно x. Но к сожалению, это не так. Например, для $n=601$ и $y=50$ получается 9 решений: $x=21, 22, \dots, 29.$

[Руст]

Подробно. Пусть $f(k)=-[-\frac nk ]+s$. Это значит, что существуют s элементов меньше k, что $f(i_1)=f(k)-1,f(i_2)=f(k-2),...,f(i_s)=f(k)-s$, а для других i<k выполняется f(i)>f(k). Это значит, что среди чисел m, таких, что mf(k)>=n ровно s чисел меньше k, а именно $i_1,i_2,...,i_s$, а для других чисел i<k, if(k)<n. Это эквивалентно $f(f(k))=-[-\frac{n}{f(k)}]+s=k$.

[maxal]

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

Это эквивалентно $f(f(k))=-[-\frac{n}{f(k)}]+s=k$.

Равенство $f(f(k))=-[-\frac{n}{f(k)}]+s$ понятно. А вот откуда $=k$ ?

[maxal]

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

Только я использовал [] из за незнания как ставить скобки, употреблённые автором.

Кстати,
1) чужие формулы можно выделять/копировать обычным образом, а потом модифицировать по нужде;
2) "потолок" делается как \lceil ... \rceil, например, \lceil \frac{n}{k} \rceil дает $\lceil \frac{n}{k} \rceil$

[Руст]

maxal писал(а):

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

Это эквивалентно $f(f(k))=-[-\frac{n}{f(k)}]+s=k$.

Равенство $f(f(k))=-[-\frac{n}{f(k)}]+s$ понятно. А вот откуда $=k$ ?

Мы уже установили, что среди чисел i<k ровно s удовлетворяют условию: if(k)>==n, что приводит f(f(k))=k.

[maxal]

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

maxal писал(а):

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

Это эквивалентно $f(f(k))=-[-\frac{n}{f(k)}]+s=k$.

Равенство $f(f(k))=-[-\frac{n}{f(k)}]+s$ понятно. А вот откуда $=k$ ?

Мы уже установили, что среди чисел i<k ровно s удовлетворяют условию: if(k)>==n, что приводит f(f(k))=k.

Какая конкретно связь у f() с пресловутым s? Я вижу два равенства:

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

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

где $s(k) = |\{ m : (k,m)\in R,\ m<f(k) \}| = |\{ r : (r,f(k))\in R,\ r<k \}|$.
Но как из этого следует $f(f(k))=k$ ?

[Руст]

maxal писал(а):

Какая конкретно связь у f() с пресловутым s? Я вижу два равенства:

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

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

где $s(k) = |\{ m : (k,m)\in R,\ m<f(k) \}| = |\{ r : (r,f(k))\in R,\ r<k \}|$.
Но как из этого следует $f(f(k))=k$ ?

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

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

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