experimente2

Algoritmul, pas cu pas

Operația pare complicată, dar are o citire foarte simplă: a înlocui două elemente adiacente cu xor-ul lor înseamnă a le lipi într-un singur număr. Aplicată repetat, ea nu face decât să grupeze elementele inițiale în blocuri consecutive, fiecare bloc devenind xor-ul elementelor sale. Așadar întrebarea „pot ajunge toate valorile egale?” devine: pot tăia șirul în cel puțin $2$ blocuri consecutive, toate cu același xor?

Fie $t = A_1 \oplus A_2 \oplus \dots \oplus A_n$ — xor-ul total. El nu se schimbă niciodată (xor-ul e asociativ), deci e un invariant. Dacă reușim $k$ blocuri egale cu o valoare $v$, atunci xor-ul tuturor blocurilor este $t$; cum xor-ul a $k$ copii ale lui $v$ este $v$ când $k$ e impar și $0$ când $k$ e par, obținem: ori $t = v$ (cu $k$ impar), ori $t = 0$ (cu $k$ par).