Twierdzenie: "Rysując na płaszczyźnie n prostych podzielimy płaszczyznę na nie więcej niż \(2^n\) części. Udowodnij to twierdzenie, stosując indukcję."
Ogólnie nie mam problemu z dowodem indukcyjnym, gdy mam podane obie strony równania. W tym wypadku nie wiem jednak za co się zabrać. Stworzyć sobie sztucznie lewą stronę: \(P_n \le 2^n\), ale co w związku z tym? Ktoś ma jakiś pomysł? Z góry dziękuję za odpowiedzi.
Udowodnij twierzedzenie stosując indukcję.
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
radagast
- Guru
- Posty: 17549
- Rejestracja: 09 lis 2010, 07:38
- Lokalizacja: Warszawa
- Podziękowania: 41 razy
- Otrzymane podziękowania: 7435 razy
- Płeć:
Jeśli poprowadzimy 0 prostych to mamy 1 część (\(2^0=1 \ge 1\) OK)
założenie indukcyjne: istniej liczba \(n\) taka, że jeżeli narysujemy na płaszczyźnie \(n\) prostych, podzielimy płaszczyznę na nie więcej niż \(2^n\) części.
teza: jeżeli narysujemy na płaszczyźnie \(n+1\) prostych, podzielimy płaszczyznę na nie więcej niż \(2^{n+1}\) części.
dowód:każdą z \(2^n\) części z założenia indukcyjnego n+1-sza prosta podzieli na co najwyżej dwie części. Zatem uzyskamy co najwyżej \(2 \cdot 2^n=2^{n+1}\) części.
CBDO
założenie indukcyjne: istniej liczba \(n\) taka, że jeżeli narysujemy na płaszczyźnie \(n\) prostych, podzielimy płaszczyznę na nie więcej niż \(2^n\) części.
teza: jeżeli narysujemy na płaszczyźnie \(n+1\) prostych, podzielimy płaszczyznę na nie więcej niż \(2^{n+1}\) części.
dowód:każdą z \(2^n\) części z założenia indukcyjnego n+1-sza prosta podzieli na co najwyżej dwie części. Zatem uzyskamy co najwyżej \(2 \cdot 2^n=2^{n+1}\) części.
CBDO