Autor |
Beitrag |
Kerstin
| Veröffentlicht am Montag, den 08. Mai, 2000 - 15:09: |
|
Wieviele Teilmengen von {1,2,...,n} enthalten keine zwei aufeinanderfolgende Zahlen? Wie beweise ich sowas??? Danke schonmal. |
Ralf
| Veröffentlicht am Dienstag, den 09. Mai, 2000 - 23:13: |
|
Am besten indem Du das Gegenereignis zählst. Klar? |
Armin Heise (Armin)
| Veröffentlicht am Mittwoch, den 10. Mai, 2000 - 20:07: |
|
Hallo Kerstin, die Aufgabe ist meiner Meinung nach extrem schwierig. Benutzen muß man auf jeden Fall: zu jeder Menge mit n Elementen gibt es 2 hoch n verschiedene Teilmengen. ( dies kann man per Induktion beweisen ) Nun muß man für kleine n die Anzahl der Teilmengen ohne direkt aufeinanderfolgende Zahlen zählen und versuchen, eine Regel aufzustellen, wie die Anzahl für beliebiges n ist. Diese kann man dann versuchen zu beweisen. Über die Aufgabe muß ich noch nachdenken. Bis demnächst. |
SpockGeiger
| Veröffentlicht am Mittwoch, den 10. Mai, 2000 - 20:26: |
|
Hi Von meinem Standpunkt aus hast Du, Adam, Dich geirrt, der Tipp mit der Komplement war sehr gut: Also betrachte ich mal alle Teilmengen mit 2 aufeinanderfolgenden Zahlen, nacheinader: Alle Teilmengen, in denen 1 und 2 enthalten ist, ist gerade die Anzahl aller Teilmegen der restlichen Elemnte, also: 2n-2 Nun alle Teilmengen mit 2 und 3, aber ohne 1, das haben wir bereits betrachtet: Das sind 2n-3 und so weiter... Also summe(i=2..n, 2n-i) = summe(i=0..n-2, 2i) = 2n-1-1 Zieht man das von der Gesamtzahl ab, ergibt das: 2n-1+1 viele Gruesse SpockGeiger |
habac
| Veröffentlicht am Donnerstag, den 11. Mai, 2000 - 14:27: |
|
Hi Spockgeiger Bei Deiner Methode wird aber die Teilmenge T={1,3,4} nicht ausgeschlossen, so dass Du bei der Grundmenge G={1,2,3,4} auf das Schlussresultat 9 kommst. Richtig wäre 8. Nach meinen Überlegungen sind die gesuchten Zahlen gerade die Fibonaccizahlen 1, 2, 3, 5, 8, ... |
Martin Ozimek (Spockgeiger)
| Veröffentlicht am Donnerstag, den 11. Mai, 2000 - 23:53: |
|
Hallihallo Erstmal Entschuldigung an Armin, Du hattest Recht, dass die Aufgabe gar nicht so trivial ist, ganz so schwer ist sie aber auch nicht. Deine Vermutung mit den Fibonacci-Zahlen war voellig richtig. Also: Die Anzahl aller Teilmengen der Menge der ersten n natuerlichen Zahlen, die keine 2 aufeinanderfolgenden Zahlen beeinhalten, ist fibonacci(n+2) Bezeichne diese Zahlen mit A(n) Beweis durch Induktion nach n: Induktionsanfang: klar! (nachrechnen) Induktionsschritt: Man nehme die Menge der serten n natuerlichen Zahlen. Keine 2 aufeinanderfolgenden Zahlen beinhalten alle Teilmengen aus der Menge der ersten n-1 natuerlichen Zahlen. Es ist ja klar, dass sich keine Eigenschaft veraendert, wenn das n-te Element nicht dazukommt. Also zunaechst mal A(n-1) Hinzu kommen alle Teilmengen, die das n-te Elemnt, aber nicht das n-1-te Element beinhalten, und bezueglich der ersten n-2 Elemnte die Bedingung erfuellen, also A(n-2) Also: A(n)=A(n-1)+A(n-2), gerade die Definition der Fibonacci-Zahlen, qed. viele Gruesse SpockGeiger |
Armin Heise (Armin)
| Veröffentlicht am Sonntag, den 14. Mai, 2000 - 20:39: |
|
Hallo Martin, vielen Dank für die Beschreibung von habac Gedanken. Armin |
|