| 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 |
|
