Problemele etapelor

Ediţia a III-a - Problema etapei 6

Data: 15 martie 2012 | Autor: China Girls | 1 comentariu

Problema Etapei este în general o problemă cu grad înalt de dificultate, dar tipică și exemplară, fără a cere tehnici speciale de rezolvare, și deci abordabilă indiferent de cunoștințele posedate. Problema Etapei nu este neapărat originală, dar nu este larg cunoscută.

Propuneri bine cântarite pentru viitoare Probleme ale Etapei sunt binevenite (prin intermediul resursei Forum). Soluțiile remarcabile pot selecționate de către administrator pentru a prezentate împreună cu soluția oficială (credite de rigoare către autori).

Bile în Tot Atâtea Cutii

În $n$ cutii, numerotate $C_{1}, C_{2},..., C_{k-1}, C_{k}, C_{k+1},..., C_{n-1}, C_{n}$ , se găsesc în total $n$ bile. Avem voie să facem următoarele operații

dacă în cutia $C_{1}$ se găsește cel puțin o bilă, putem muta o bilă din cutia $C_{1}$ în cutia $C_{2}$ ;
dacă în cutia $C_{n}$ se găsește cel puțin o bilă, putem muta o bilă din cutia $C_{n}$ în cutia $C_{n-1}$ ;
dacă în cutia $C_{k}$ $,$ $2\leqslant k\leqslant n-1$ , se găsesc cel puțin două bile, putem muta simultan o bilă din cutia $C_{k}$ în cutia $C_{k-1}$ și o altă bilă din cutia $C_{k}$ în cutia $C_{k+1}$ .

Demonstrați că, într-un număr finit de operații, putem obține câte o bilă în fiecare cutie (indiferent de configurația inițială a celor $n$ bile în cele $n$ cutii).

Etapa 06, China Girls, martie 2012

Autentifică-te pe site pentru a putea lăsa un comentariu.

Comentariu:

Paul Olaru - 18 martie 2012

Solutie:
C1 si Cn nu au nici o bila.
Celelalte cutii au un numar par sau impar de bile. Definim o functie iterativa astfel:Cutiile cu numar par de bile pot trimite jumatate din ele in cele imediat in stanga nepastrand niciuna, iar cele cu numar impar vor pastra cate una. In momentul in care o cutie are o singura bila sau niciuna nu i se va schimba starea decat daca va mai primi una din cutia vecina.
Putem ilustra aceasta functie iterata pe un exemplu: 5 bile in 5 cutii.
C1 are 2 bile, C2 niciuna, C3 are 3 bile, C4 si C5 niciuna. Putem ilustra drept 20300.
Aplicam:21110-12110-20210-11210-12020-20120-11120-11201-12011-20111-11111.
Alta cu 7 cutii, asezarea originala e 2003020, deci:
2003020-1111201-1112011-1120111-1201111-2011111-1111111
Reducem la extrema de 3 cutii:
210-120-030-111
Putem avea o analogie: Apa sub actiunea gravitatiei dintr-un set de forme ajunge la un moment dat un volum uniform.