zadania indukcja

[anilahcim]

Proszę o pomoc w rozwiązaniu zadań:

1. Sadzamy \(\displaystyle{ 2n}\) dzieci do \(\displaystyle{ n}\) wagoników po dwoje. Na ile sposobów można to zrobić?

2. Udowodnić indukcyjnie, że suma kątów wewnętrznych dowolnego \(\displaystyle{ n}\)-kąta wynosi \(\displaystyle{ (n-2)\pi}\).

3. Udowodnić, że aby połamać czekoladą o wymiarach \(\displaystyle{ p}\) na \(\displaystyle{ r}\) aby były same kawałki \(\displaystyle{ 1}\) na \(\displaystyle{ 1}\) potrzeba \(\displaystyle{ p \cdot r-1}\) złamań oraz że ta liczba nie zależy od sposobu łamania.

[Glo]

1. Ile par dzieci można utworzyć? Oczywiście każde dziecko jest rozróżnialne od pozostałych . Gdy znamy ilość par, można ustalić ich kolejność. Dla czterech dzieci, a więc dwóch wagonów, wybranie pierwszej pary determinuje drugą parę, więc kolejność jest jedna jedyna i już policzona podczas wybierania par. Natomiast gdy mamy trzy lub więcej wózków, należy zauważyć, że mamy np. opcje:

\(\displaystyle{ (1,2)-(3,4)-(5,6)\\
(1,2)-(5,6)-(3,4)}\)

gdzie każdy nawias to jeden wózek a cyfra oznacza dane dziecko. Zliczanie par nie da nam dwa razy wyniku \(\displaystyle{ (1,2)}\), bo to ta sama para. Dla sześciu dzieci dla każdej ustalonej pierwszej pary istnieją dwie dalsze drogi usadzenia dzieci. Ogólnie, dla \(\displaystyle{ 2n}\) dzieci istnieje \(\displaystyle{ (n-1)!}\) dalszych dróg, bo wszystkie poza pierwszą parą należy poprzestawiać na wszystkie możliwe sposoby. Tak więc, ostatecznie, wynikiem jest iloczyn liczby par i ilości permutacji \(\displaystyle{ (n-1)}\) elementów.

2. Sprawdzamy, czy nasze twierdzenie jest prawdziwe dla \(\displaystyle{ n=3}\). Założenie indukcyjne: zakładamy, że nasze wyrażenie jest prawdziwe dla \(\displaystyle{ n=k}\). Teraz aby dowód uznać za zakończony, potrzebne jest, aby twierdzenie okazało się prawdziwe dla \(\displaystyle{ n=k+1}\), czyli aby było:

\(\displaystyle{ S_{k+1}=(k-1)\pi}\)

Weźmy \(\displaystyle{ (k+1)}\)-kąt wypukły i połączmy dwa wierzchołki oddzielone wspólnym sąsiadem. Zostaje nam \(\displaystyle{ k}\)-kąt oraz trójkąt. Suma miar \(\displaystyle{ k}\)-kąta, z założenia indukcyjnego, jest \(\displaystyle{ (k-2)\pi}\), natomiast suma kątów trójkąt jest równa \(\displaystyle{ \pi}\). Tak więc suma kątów \(\displaystyle{ (k+1)}\)-kąta jest równa sumie kątów \(\displaystyle{ k}\)-kąta oraz trójkąta, to jest \(\displaystyle{ (k+1)\pi}\), czyli tyle ile chcieliśmy, co kończy dowód.