Inverseaza reviziile

Diferente pentru preoni-2007/runda-3/solutii intre reviziile #5 si #4

Diferente intre #5 si #6
Diferente intre #3 si #4

Nu exista diferente intre titluri.

Diferente intre continut:

Fie $N$ = {$C * K + R$}, {$0 &le; r < K$}.
Se observa ca intr-o {$K$}-permutare nu conteaza decat resturile numerelor la impartirea cu $K$, si nu numerele propriu-zise. Deci putem privi o permutare in functie de cate resturi r sunt in permutare, pentru orice {$r$} de la $0$ la {$K-1$}. Se observa ca resturile de la $1$ la $R$ apar de exact {$C+1$} ori, in timp ce toate celelalte resturi apar de exact $C$ ori.

I. {$N &ge; 2 * K$}, sau, echivalent {$C &ge; 2$}. Se observa ca in primele $C$ numere din permutarea care constituie o solutie nu putem pune acelasi rest de cel putin $2$ ori. Observatia este evidenta, deoarece, cum avem relatia $sigma{~i~}$ congruent cu $sigma{~i+K~}$ ( mod {$K$} ), atunci restul care ar aparea de 2 ori in primele $C$ numere ar aparea de cel putin {$2*C$} ori ( pe primele {$C*K$} pozitii ), dar avem maxim {$C+1$} resturi disponibile egale, si cum {$2*C > C+1$}, am ajuns la o contradictie.

I. {$N &ge; 2 * K$}, sau, echivalent {$C &ge; 2$}. Se observa ca in primele $C$ numere din permutarea care constituie o solutie nu putem pune acelasi rest de cel putin $2$ ori. Observatia este evidenta, deoarece, cum avem relatia $sigma{~i~}$ congruent cu $sigma{~i+K~}$ ( mod {$K$} ), atunci restul care ar aparea de 2 ori in primele $C$ numere ar aparea de cel putin {$2*C$} ori ( pe primele {$C*K$} pozitii ), dar avem maxim {$C+1$} resturi disponibile egale, si cum {$2*C &ge; C+1$}, am ajuns la o contradictie.

II. {$K &le; N < 2*K$}. In acest caz, resturile de la $1$ la $R$ apar de $2$ ori fiecare, iar toate celelalte resturi apar o singura data. Cum doar pozitiile de la $R+1$ la $C$ au un rest unic in permutare ( toate celelalte resturi apar pe exact doua pozitii de forma $i$ si $i + K$ ) => pe aceste pozitii trebuie sa punem toate resturile care apar o singura data. Este evident si ca in primele $R$ pozitii trebuie sa punem resturile diferite doua cate doua, pentru ca fiecare rest apare de doua ori si trebuie pus pe doua pozitii.
Din ambele cazuri a rezultat ca pentru orice valori ale numerelor $N$ si $K$, o {$K$}-permutare trebuie sa respecte urmatoarele proprietati:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.