Interessantes Rätsel < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Kein Teiler
Bilden sie möglichst große Teilmengen der Zahlen von 1 bis 100 derart, dass unter den Zahlen keine ist, die eine andere dieser Zahlen teilt. Stellen sie eine Hypothese über den größtmöglichen Umfang (die größte Mächtigkeit) dieser Mengen auf. Versuchen sie diese Hypothese zu beweisen. Verallgemeinern sie ihre Aussage, indem sie für eine beliebig gewählte Zahl n die Zahlen von 1 bis 2n und deren Teilmengen betrachten. |
Die größte Teilmenge, die gebildet werden kann ist meiner Meinung nach
die Menge n.
Für die Beispiel Menge der Zahlen bis 100 wären das die Zahlen 51 bis
100.
Dies entspricht der Menge n.
Also für n = 50 und 2n = 100.
Mit weiterem probieren kam ich dann auf den Ansatz, dass es mit
vollständiger Induktion zu beweisen ist. Also für n = 1 bildet die Zahl
2 die größte Teilmenge und ist damit n Elemente groß.
bei n = 2 ist die größte Teilmenge 2 Elemente groß. Bestehend aus den
Zahlen 3 und 4.
Usw. Leider leuchtet mir nicht ein, wie ich das mathematisch
aufschreiben kann, so daß es einem auch einleuchtet, wenn man es liest.
Schau ich auf meine Zahlenmengen, so leuchtet mir nicht ein, dass das
immer so fortzuführen ist.
So jetzt die Frage:
Weiß jemand, wie ich das mit vollständiger Induktion schriftlich
festhalten kann?
Oder auch mit einem anderen Beweisverfahren.
Vielen Dank schon mal.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:http://www.mikrocontroller.net/topic/338316#new
|
|
| |
|
Hiho,
an der Lösung ist gar nichts ungewöhnlich, sie lässt sich sogar leicht als maximale Menge begründen.
Klar ist: In der Menge [mm] $\{n+1,n+2,\ldots,2n\}$ [/mm] teilt kein Element das andere.
Nimmt man nun ein weiteres Element aus [mm] $k\in\{1,\ldots,n\}$ [/mm] hinzu, muss man mindestens das Element 2k entfernen, d.h. jede weitere Menge mit der Eigenschaft ist mindestens genauso groß wie [mm] $\{n+1,n+2,\ldots,2n\}$
[/mm]
Gruß,
Gono.
|
|
|
| |
|
Die Begründung ist mir schon bewusst.
Nur wie ist die mathematische Darstellung dazu?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Do 10.07.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
