Matematyka.pl

Udowodnij, że w dowolnym kopcu liczba wierzchołków zewnętrznych ( liści ) jest równa albo o 1 większa od liczby wierzchołków zewnętrznych ( pewnie krawędzi ).

A więc rozrysowałem to sobie ładnie i wyciągnąłem wniosek:

że dla \(\displaystyle{ 2k}\) liści potrzeba \(\displaystyle{ 2k-1}\) krawędzi ich łączących, natomiast przy \(\displaystyle{ 2k+1}\) liści potrzeba \(\displaystyle{ 2k}\) krawędzi ich łączących, gdzie \(\displaystyle{ k \in \mathbb{Z}}\), ale nie wiem za bardzo jak mam to udowodnić

Że: \(\displaystyle{ 2k>2k-1}\) oraz \(\displaystyle{ 2k+1>2k}\)

??

józef92 pisze:liczba wierzchołków zewnętrznych (...) jest równa albo o 1 większa od liczby wierzchołków zewnętrznych

Coś tu chyba nie gra.

No na końcu cytowanego fragmentu wewnętrznych, ale łatwo się domyśleć

Jeżeli miało być wierzchołków wewnętrznych, to nie chodzi o krawędzie, a o wszystkie wierzchołki, które nie są liśćmi. Przy czym wtedy teza nie jest prawdziwa. Dopiero gdy zażądamy, aby kopiec był zupełny, wtedy jest to prawda i podejrzewam, że o takie coś chodziło.
Co się tyczy samego dowodu, to narysuj dowolny kopiec i policz liście. Reszta "udowodni się sama"
Możesz też próbować pokazywać indukcyjnie, że po odcięciu dowolnego liścia albo nie zmieniliśmy liczby wierzchołków zewnętrznych, albo zmniejszyliśmy liczbę wierzchołków zewnętrznych o 1, ale przy tym przybył nam dodatkowy liść.

Afish, widzę to, teraz kwestia zapisania tego formalnie Nie wiem naprawdę jak to "sformalizować"....

Tak na szybko, mogą być błędy.
Jeżeli kopiec ma wysokość \(\displaystyle{ h}\) i na ostatnim poziomie jest \(\displaystyle{ k}\) wierzchołków, wtedy cały kopiec ma \(\displaystyle{ 2^{h-1}-1 + k}\) wierzchołków. Rozpatrzmy dwa przypadki: \(\displaystyle{ k}\) jest parzyste, lub jest nieparzyste. Ja zajmę się przypadkiem parzystości, nieparzysty zrobisz sam, jest analogiczny. Na przedostatnim poziomie jest \(\displaystyle{ 2^{h-2}}\) wierzchołków, z czego \(\displaystyle{ \frac{k}{2}}\) to wierzchołki wewnętrzne. Zatem liści jest \(\displaystyle{ 2^{h-2} - \frac{k}{2} + k = 2^{h-2} + \frac{k}{2}}\). Teraz wierzchołków wewnętrznych jest \(\displaystyle{ 2^{h-1}-1+k - \left(2^{h-2} + \frac{k}{2}\right) = 2^{h-1} - 1 + k - 2^{h-2} - \frac{k}{2} = 2^{h-2} + \frac{k}{2} - 1}\), czyli o jeden mniej od liści. Teraz policz to samo dla drugiego przypadku i gotowe.

Ostatnie równanie dobrze wyprowadziłeś? )

Tak.

k nieparzyste przyjmie postać 2k+1, teraz nie dziele tego tak jak w przypadku k parzystego. Po prostu 2k+1. Wyszło ok