Revizia anterioară Revizia următoare
 |    |
Solutii Runda 3
Buline
(problema usoara, clasa a 9-a)
Zero 2
(problema medie, clasa a 9-a)
Puteri
(problema grea, clasa a 9-a, problema medie, clasa a 10-a)
Balanta
(problema usoara, clasa a 10-a)
Expresii 2
(problema grea, clasa a 10-a)
Ograzi
(problema usoara, clasele 11-12)
KPerm
(problema medie, clasele 11-12)
Fie sigma o K-permutare cu N elemente => pentru orice i, 1 ≤ i ≤ N-K avem relatiile:
- sigmai + sigmai + ... sigmai+K-1 congruent cu 0 ( mod K )
- sigmai+1 + sigmai+2 + ... sigmai+K congruent cu 0 ( mod K )
Scazand cele doua relatii, obtinem sigmai congruent cu sigmai+K ( mod K ).
Fie N = C * K + R, 0 ≤ 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 ≥ 2 * K, sau, echivalent C ≥ 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 sigmai congruent cu sigmai+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.
II. K ≤ 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:
- pe primele K pozitii din permutare trebuie sa se gaseasca toate resturile 0, 1, ... K-1
- resturile de la 1 la R trebuie sa fie asezate pe primele R pozitii
- pe fiecare pozitie i incepand cu K+1 trebuie sa punem un numar care sa aiba restul din impartirea la K egal cu restul impartii numarului de pe pozitia i-K la K
Fie K par, K = 2p. Cum 0+1...+(2p-1) = p*(2p-1) si acest numar nu se divide cu 2p pentru ca 2p-1 este impar => pentru K par raspunsul este 0.
Pentru K impar, K = 2p+1, cum 0+1...+2p = p*(2p+1), care este dizibil la (2p+1), vom construi permutarea astfel:
- fixam ordinea primelor R resturi ( in total R! variante )
- fixam ordinea celorlalte K-R resturi ( in total ! variante )
- pentru fiecare rest din primele R sunt C+1 pozitii pe care trebuie sa il asezam. Pentru fiecare rest putem pozitiona numerele atasate in (C+1)! variante, si, cum sunt R resturi, avem [(C+1)!]{R} variante
- pentru toate celelalte resturi sunt C pozitii pe care trebuie sa le asezam. Pentru fiecare rest putem pozitiona numerele atasate in (C+1)! variante, si, cum sunt R resturi, avem [(C+1)!]{R} variante
Magazin
(problema grea, clasele 11-12)
Sponsori
Organizarea finalei preONI este posibila datorita generosilor nostri sponsori:
