Problem wiewiórek

mol_ksiazkowy · Post autor: **mol_ksiazkowy** » 3 sie 2006, o 19:36

Na dziesięciu drzewach rozmieszczonych na okręgu siedzi dziesięć wiewiórek (po jednej na każdym). Od czasu do czasu dwie wiewiórki przeskakują naraz na sąsiednie drzewa. Czy wiewiórki mogą zebrać się na jednym drzewie...?

soliter · Post autor: **soliter** » 3 sie 2006, o 21:35

ponumerujmy drzewa kolejno liczbami ze zbioru \(\displaystyle{ \{n\in\mathbb{N}_{+}:n\le 10\}}\)
zalozmy, ze 10 wiewiorek weszlo na drzewo \(\displaystyle{ \mathbb{D}_{1}}\)
niezmiernie latwo zauwazyc, ze liczba wiewiorek, ktore wykonaly nieparzysta liczbe posuniec, jest nieparzysta (mowa o wiewiorkach z drzew o parzystych numerach)
zatem wiewiorki skoczyly lacznie 2k+1 razy

Sir George · Post autor: **Sir George** » 4 sie 2006, o 13:28

soliter: dobre rozwiązanie...!

mol_książkowy: i fajne zadanko...

Ja robiłem je tak: ponumerowałem drzewa liczbami od 1 do 10 (podobnie jak soliter). Następnie każdemu rozmieszczeniu wiewiórek na drzewach przyporządkowałem sumę liczb oznaczających drzewa, na których siedzą wiewiórki (jeśli na danym drzewie siedzie więcej niż jedna wiewiórka, to liczbę oznaczającą drzewo bierzemy w sumie z krotnością równą liczbie wiewiórek).
Z warunków zadania widać, że jeśli dokładnie dwie wiewiórki przeskakują na sąsiednie drzewa, to parzystość sumy odpowiadająca nowej sytuacji pozostaje bez zmiany (jest to tzw. niezmiennik).
Sytuacja końcowa (wszystkie wiewiórki na jednym drzewie) odpowiada sumie parzystej (równej dokładnie 10k). Sytuacja początkowa natomiast odpowiada sumie 55. Stąd widać, że nie jest możliwe spełnienie zadość tezie zadania...