catanedelcu

Mai intai as dori sa consemn faptul ca am realizat ieri un record de "cea mai  mica audienta a problemei zilei " pe site . E vina mea ca am rezolvat-o prea devreme sau a lui lucipet, ca era intuitiva ?  Am vrut sa propun ieri un bonus asa cum se face de obicei dar n-am avut timp si nici idee de o problema originala.

Parmalat

1, 8, 2, 10, 3, 7, 4, 9, 5, 6,
sau
1, 6, 2, 10, 3, 7, 4, 9, 5, 8, sunt prea obosit pentru ca gasi si ordinea intre 8 si 6
se observa ca s7,s8 si s9 au innaintea coloanei formata din 4 cifrele 7 6 si 8 adica scade cu 1 si creste 2(idem pentru s6 s7 s8 inaintea coloanei 3 si pentru s4 s5 si s6 inaintea coloanei cu 2); facem acelasi algoritm si pentru coloana dinaintea lui 5,
sper ca mai multe sa se intealga si din excelul urmator

http://www.picpaste.com/Problema_Halloween.JPG

wmutex

Hmm... as putea sa jur ca-i o problema de permutari...

s_n: {1, ..., n} -->  {1, ..., n} bijectiva

si as putea sa jur ca-i vorba de permutari alternante, adica pentru o permutare s_n = [a_1, a_2, ..., a_n]:

a_i < a_(i+1) pentru i impar
a_i > a_(i+1) pentru i par

As putea depune toate aceste juraminte, dar mai stau un pic, poate vine cineva cu o idee mai buna... :D

wmutex

Notatie: in cele ce urmeaza _ (underscore) inseamna indice si [x] denota operatia de parte intreaga (cel mai mare intreg mai mic decat x). Conform definitiei, clasele de resturi modulo n (mod n) au intotdeauna reprezentare pozitiva (oricare ar fi m intreg m mod n se afla intre 0 si n-1 inclusiv).

Seriile s_n (n = 1,10) sunt considerate ca functii de pozitie: s_n(i) inseamna numarul de pe pozitia i din seria n (de fapt seriile sunt niste permutari). De exemplu:
s_7(4) = 5

Ele par generate dupa urmatoarele reguli:

s_1(1) = 1

s_[n](2*k - 1) = k;  n,k naturale;  n>2;  1 ≤ 2*k-1 ≤ 2*n
s_[n](2*k) = s_[n/2]((k-1-n) mod [n/2] + 1) + [(n+1)/2];  n>2;  n,k naturale;  1 ≤ 2*k ≤ n

Astfel se asigura o permutare alternanta a numereloe de la 1 la n in seria n.

Verificare:
s_1(1) = 1

s_2(1) = 1
s_2(2) = s_2(2*1) = s_1((1-1-2) mod 1 + 1) + 1 = s_1(1) + 1 = 2

s_3(1) = 1
s_3(2) = s_3(2*1) = s_1((1-1-3) mod 1 + 1) + 2 = s_1(-3 mod 1 + 1) + 2 = s_1(1) + 2 = 1 + 2 = 3
s_3(3) = 2

s_4(1) = 1
s_4(2) = s_4(2*1) = s_2((1-1-4) mod 2 + 1) + 2 = s_2(-4 mod 2 + 1) + 2 = s_2(1) + 2 = 1 + 2 = 3
s_4(3) = 2
s_4(4) = s_4(2*2) = s_2((2-1-4) mod 2 + 1) + 2 = s_2(-3 mod 2 + 1) + 2 = s_2(2) + 2 = 2 + 2 = 4

s_5(1) = 1
s_5(2) = s_5(2*1) = s_2((1-1-5) mod 2 + 1) + 3 = s_2(-5 mod 2 + 1) + 3 = s_2(2) + 3 = 2 + 3 = 5
s_5(3) = 2
s_5(4) = s_5(2*2) = s_2((2-1-5) mod 2 + 1) + 3 = s_2(-4 mod 2 + 1) + 3 = s_2(1) + 3 = 1 + 3 = 4
s_5(5) = 3

s_6(1) = 1
s_6(2) = s_6(2*1) = s_3((1-1-6) mod 3 + 1) + 3 = s_3(-6 mod 3 + 1) + 3 = s_2(1) + 3 = 1 + 3 = 4
s_6(3) = 2
s_6(4) = s_6(2*2) = s_3((2-1-6) mod 3 + 1) + 3 = s_3(-5 mod 3 + 1) + 3 = s_3(2) + 3 = 3 + 3 = 6
s_6(5) = 3
s_6(6) = s_6(2*3) = s_3((3-1-6) mod 3 + 1) + 3 = s_3(-4 mod 3 + 1) + 3 = s_3(3) + 3 = 2 + 3 = 5

s.a.m.d.

(continuare in comentariul urmator)

wmutex

(continuare din comentariul anterior)

Pentru s_10 avem

s_10(1) = 1
s_10(2) = s_10(2*1) = s_5((1-1-10) mod 5 + 1) + 5 = s_5(-10 mod 5 + 1) + 5 = s_5(1) + 5 = 1 + 5 = 6
s_10(3) = 2
s_10(4) = s_10(2*2) = s_5((2-1-10) mod 5 + 1) + 5 = s_5(-9 mod 5 + 1) + 5 = s_5(2) + 5 = 5 + 5 = 10
s_10(5) = 3
s_10(6) = s_10(2*3) = s_5((3-1-10) mod 5 + 1) + 5 = s_5(-8 mod 5 + 1) + 5 = s_5(3) + 5 = 2 + 5 = 7
s_10(7) = 4
s_10(8) = s_10(2*4) = s_5((4-1-10) mod 5 + 1) + 5 = s_5(-7 mod 5 + 1) + 5 = s_5(4) + 5 = 4 + 5 = 9
s_10(9) = 5
s_10(10) = s_10(2*5) = s_5((5-1-10) mod 5 + 1) + 5 = s_5(-6 mod 5 + 1) + 5 = s_5(5) + 5 = 3 + 5 = 8

Asadar,

s_10: 1, 6, 2, 10, 3, 7, 4, 9, 5, 8