[Kombinatoryka] szyfry

[mol_ksiazkowy]

Każdą permutację A = (a1, ..,an) liczb 1, ... , n można zakodować za pomocą ciągu B = (b1, ..,bn), w którym \(\displaystyle{ b_i}\) jest równe liczbie wszystkich \(\displaystyle{ a_j}\) takich, że: (j < i oraz \(\displaystyle{ a_j > a_i}\)),

Przykład
Kodem permutacji A = (1, 5, 2, 6, 4, 7, 3) jest ciąg: B = (0, 0, 1, 0, 2, 0, 4). Czy taki szyfr jest jednoznaczny?...dac dowod lub podac \(\displaystyle{ A_1 A_2}\) o tym samym kodzie...!
Odszyfruj permut. majac jej kod: B=(0,0,1,3,4,1,1,3)....

[Sylwek]

Inaczej mówiąc, \(\displaystyle{ b_i}\) jest równe ilości liczb większych od \(\displaystyle{ a_i}\), które są w permutacji przed \(\displaystyle{ a_i}\), np. jak w przykładzie: \(\displaystyle{ a_4=6}\), wśród liczb \(\displaystyle{ a_1,a_2,a_3}\) jest 0 liczb większych od 6, zatem \(\displaystyle{ b_4=0}\).


Pokażę, że szyfr jest jednoznaczny. W tym celu pokażę, że każdej permutacji odpowiada jeden szyfr i każdy szyfr odpowiada jednej permutacji. W jedną stronę wynika to z algorytmu szyfrowania podanego w zadaniu.


W drugą stronę (pokażę algorytm odszyfrowania):
Mamy szyfr \(\displaystyle{ B=(b_1,\ldots,b_n)}\). Utwórzmy tablicę (\(\displaystyle{ T_1}\)):
\(\displaystyle{ \left[\begin{array}{ccccc}a_1&a_2&a_3&\ldots&a_n \\ &\_&\_&\_&\_ \end{array}\right]}\).

Gdzie pod każdą z liczb \(\displaystyle{ a_2,a_3,\ldots,a_n}\) będziemy po kolei wpisywali, czy jest większa (+) czy mniejsza (-) od \(\displaystyle{ a_1}\). Dokonujemy tego w następujący sposób:
* jeśli liczba \(\displaystyle{ b_i}\) ma większą wartość niż aktualna ilość wpisanych plusów (\(\displaystyle{ p}\)) - pod \(\displaystyle{ a_i}\) wpisujemy minus
* jeśli liczba \(\displaystyle{ b_i}\) ma mniejszą lub równą wartość w porównaniu do aktualnej ilości wpisanych plusów - pod \(\displaystyle{ a_i}\) wpisujemy plus.
Dowód poprawności tej metody jest prosty i intuicyjny - polecam chętnym zrobić.

Zatem \(\displaystyle{ a_1}\) jest równa ilości wpisanych minusów do \(\displaystyle{ T_1}\) (\(\displaystyle{ m_1}\)) powiększonej o 1 (gdyż jest dokładnie \(\displaystyle{ m}\) liczb mniejszych od \(\displaystyle{ a_1}\). Zostały nam do rozszyfrowania liczby z ciągu: \(\displaystyle{ (1,\ldots,a_1-1,a_1+1,\ldots,n)}\).

W następnym kroku budujemy tablicę (\(\displaystyle{ T_2}\)):
\(\displaystyle{ \left[\begin{array}{ccccc}a_2&a_3&a_4&\ldots&a_n \\ & \_ & \_ &\_ &\_ \end{array}\right]}\)
Wykonujemy najpierw operację: jeśli pod \(\displaystyle{ b_i}\) był wpisany minus, to zmniejszamy tą liczbę o 1 - gdyż już jednej liczby mniejszej od \(\displaystyle{ b_i}\) nie bierzemy pod uwagę: \(\displaystyle{ B=B_1 B_2}\). I postępujemy analogicznie - wówczas \(\displaystyle{ a_2}\) jest równe \(\displaystyle{ m_2+1}\) liczbie licząc od najmniejszej z ciągu liczb, które pozostały: \(\displaystyle{ (1,\ldots,a_1-1,a_1+1,\ldots,n)}\). Po tej operacji zostało nam n-2 liczb do rozszyfrowania. Znowu wykonujemy operację \(\displaystyle{ B_2 B_3}\) i tak dalej.

W ogólnym przypadku: \(\displaystyle{ a_i}\) jest równe \(\displaystyle{ m_i+1}\)-tej liczbie z ciągu pozostałych liczb licząc od najmniejszej.

Przeprowadzony dowód pokazuje, że szyfr jest jednoznaczny


Dla wiwatu rozszyfrujemy: \(\displaystyle{ B=(0,0,1,3,4,1,1,3)}\):

\(\displaystyle{ \left|\begin{array}{cccccccc} 0&0&1&3&4&1&1&3 \\ a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8 \\ x&+&+&-&-&+&+&+ \\ x & 0 & 1 & 2 & 3 & 1 & 1 & 3 \\ x & x & - & - & - & - & - & - \\ x&x&0&1&2&0&0&2\end{array}\right|}\)

I tak dalej.
Jak będziemy mieli całą tabelkę zrobioną, to po kolei odczytujemy wartość \(\displaystyle{ a_i}\) i wykreślamy ją z ciągu liczb \(\displaystyle{ (1,\ldots,n)}\) - a sposób "odczytywania" \(\displaystyle{ a_i}\) z bilansu plusów i minusów pokazałem wyżej.

P.S. Rozwiązaniem powyższego szyfru jest: \(\displaystyle{ (3,8,4,2,1,6,7,5)}\) - jakby ktoś próbował dokończyć powyższą tabelkę, to ma możliwość sprawdzenia wyniku