Permutari particulare

Filip Chindea · Post by **Filip Chindea** » Fri Jun 13, 2008 9:18 pm

Determinati \( n \in \mathbb{N}^{\ast} \) astfel incat exista \( \sigma \in S_n \) cu proprietatea ca \( S = \{ |\sigma(k) - k| \ : \ k \in \overline{1, n} \} \) are \( n \) elemente.

[TST V 2008, Problema 1, American Mathematical Monthly]

Post by **Beniamin Bogosel** » Sat Jun 14, 2008 10:42 am

Imi aduc aminte de problema asta din lista de probleme pentru pregatire de anul trecut de la lot. Nici atunci n-am reusit s-o rezolv.

Se poate obtine usor ca singurele numere \( k \) pentru care ar putea exista astfel de permutari sunt multiplii de 4 si multiplii de 4 +1.
Justificare: \( 0=\sum_{k=1}^n(\sigma(k)-k)\equiv_2 \sum_{k=1}^n|\sigma(k)-k|=\frac{n(n-1)}{2} \).

Am gasit exemple pentru 1,4,5,8,9. In cazul general nu am reusit...
Exemplele pe care le-am gasit, sunt toate cicli de lungime \( n-1 \). Banuiesc ca si in cazul general tot asa se intampla.

bae · Post by **bae** » Sat Jun 14, 2008 12:34 pm

Post by **Beniamin Bogosel** » Sat Jun 14, 2008 1:16 pm

bae wrote:
Beniamin Bogosel wrote:Imi aduc aminte de problema asta din lista de probleme pentru pregatire de anul trecut de la lot.
Parca trebuia ca problemele de la concursuri sa nu fie cunoscute dinainte de catre elevi. Ma rog, cel putin de catre majoritatea!

Si eu m-am mirat cand am vazut-o... Anul trecut am primit niste foi cu probleme chiar in prima zi de pregatire, si fiecare avea cate o copie. Problema asta era la combinatorica. Oricum, n-am reusit s-o rezolvam atunci, cel putin eu si colegii mei de camera. Daca a fost data pe post de problema 1 poate ca nu era chiar asa de grea...

bae · Post by **bae** » Sat Jun 14, 2008 1:24 pm

Filip Chindea · Post by **Filip Chindea** » Sat Jun 14, 2008 8:18 pm

Personal, am pierdut vreo ora cu exemplul (ma rog, daca gaseai in unul din cazuri celalalt trebuia sa fie clar, la modelul asta). Daca ma uit acum pare destul de natural (se obtine prin lipirea a doua "blocuri" si a ceea ce mai ramane):

\( n \equiv 0 \pmod{4}, \ n = 4k \) :

\( \left\{ \begin{array}{lcl} \sigma(j) = 4k - j + 1, & \forall j \in \overline{1, k}, & |\sigma(j) - j| \in \{4k - 1, 4k - 3, ..., 2k + 1 \}, \\ \sigma(4k - j) = j, & \forall j \in \overline{1, k}, & |\sigma(4k - j) - (4k - j)| \in \{ 4k - 2, 4k - 4, ..., 2k\}, \\ \sigma(4k) = 2k + 1, & & |\sigma(4k) - 4k| = 2k - 1, \\ \sigma(k + 1) = k + 1, & & |\sigma(k + 1) - (k + 1)| = 0, \\ \sigma(k + 1 + j) = 3k - j + 1, & \forall j \in \overline{1, k - 1}, & |\sigma(k + 1 + j) - (k + 1 + j)| \in \{ 2k - 2, 2k - 4, ..., 2\}, \\ \sigma(3k - j) = k + 1 + j, & \forall j \in \overline{1, k - 1}, & |\sigma(3k - j) - (3k - j)| \in \{ 2k - 3, 2k - 5, ..., 1\}. \end{array} \right. \)

Cazul \( n \equiv 1 \pmod{4} \) e "tema" (mi-e lene sa dau Copy-Paste

): mai ajustati cu vreun \( 1 \) sau vreo valoare particulara prin cateva locuri.

Post by **Beniamin Bogosel** » Sat Jun 14, 2008 8:55 pm

Sunt curios cate puncte se dadeau daca nu gaseai exemplul... Doar justificarea. Astfel de probleme mi se par cam artificiale. Trebuie ceva experienta, intr-adevar pentru a gasi astfel de exemple, dar in concurs, stiind ca ma sunt inca 2 probleme de rezolvat e destul de greu sa le gasesti.

Filip Chindea · Post by **Filip Chindea** » Sat Jun 14, 2008 9:20 pm

Baremul care se pare ca a fost aplicat, din cate se vede pe tabel (2 resp. 5 puncte) este destul de fair-play (singura idee la prima parte era de insumare (mod 2)): pâna la urma aici era "de munca".
Este adevarat, problemele din AMM de anul acesta au necesitat, pe langa idei efective, si ceva constructii. Poate sa para "artificial", mai degraba stresant sa trebuiasca sa refaci poate o cautare laborioasa a autorilor. Astfel de chestiuni par a fi o traditie, totusi: vezi constructia grafului fara un \( C_4 \) monocromatic de anul trecut, cazul de egalitate la inegalitatea nonstandard din 2006 etc.