Problemele etapelor
Articolele din 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 cutii, numerotate , se găsesc în total bile. Avem voie să facem următoarele operații
- dacă în cutia se găsește cel puțin o bilă, putem muta o bilă din cutia în cutia ;
- dacă în cutia se găsește cel puțin o bilă, putem muta o bilă din cutia în cutia ;
- dacă în cutia , se găsesc cel puțin două bile, putem muta simultan o bilă din cutia în cutia și o altă bilă din cutia în cutia .
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 bile în cele cutii).
Etapa 06, China Girls, martie 2012
Comentariu:
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.