Guten Abend, ich bin bei der Recherche nach einem Algorithmus auf ein interessantes Rätsel gestoßen. Das Rätsel kommt aus einem Vorlesungsskript der Hochschule Fulda. Darin stehen einige interessante Rätsel und einige habe ich auch gelöst. Hier mal der Link: http://www2.hs-fulda.de/~grams/Problemloesen/ProblemloesenBegleitmaterial.pdf Licht aus! , Spielerei mit Schachbrett und Wieviele Taxis? sind mir mit etwas grübeln und probieren irgendwann klar geworden. Nur die Aufgabe "Kein Teiler!" lässt mich nicht ruhen. 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? Für mein Seelenheil bitte ich darum.
Angehängte Dateien:
-
Kein_Teiler.png
58 KB
Hi,
ich denk das beweist sich leichter über einen Widerspruch.
Man nimmt an, das M={n+1,...,2n} nicht die größte Menge mit den
genannten Eigenschaften ist. Dann muss es ein x<=n geben das nicht
Element von M ist und kein Element aus M teilt. Jetzt zeigt man, dass es
so ein x nicht gibt. Fertig.
Grüße
Flo
:
Bearbeitet durch User
Das es besagtes x nicht gibt kann man so zeigen:
Für x>1 (1 teilt jedes b aus M, also kann man x=1 gleich ausschließen)
muss gelten: ggT(x,b) = 1 für alle b aus M.
Substituiert man b mit c=b-x gilt auch ggT(x,c+x) für alle c aus
{1...n}.
Nun ist natürlich ggT(x,c+x)=ggT(x,c). Für c=x erhält man ggT(x,x)=x<>1
und damit einen Widerspruch zur Annahme.
Oder so ähnlich.
Grüße
Flo
Hmm, ok. Vielen Dank schonmal. Hatte mich auf den Beweis durch vollständige Iduktion versteift. Werde mir das noch mal näher zu Gemüte führen. Sieht aber ganz gut aus. Vielleicht beweißt ja noch der ein oder andere seine mathematischen Fähigkeiten. :-P
Ich weiß nicht ganz ob ich das Rätsel kapiert hab, aber die Lösung
M={n+1,...,2n} versteh ich nicht.
jede Primzahl < n, die nicht Teil der Primzahlzerlegung von n ist, kann
n nicht teilen
Es wird aber die Menge mit der größten Mächtigkeit gesucht. Die Anzahl der Primzahlen der von dir beschriebenen Menge ist kleiner n. Und somit nicht die Menge mit der größten Mächtigkeit...
Dennis K. schrieb: > ich bin bei der Recherche nach einem Algorithmus auf ein interessantes > Rätsel gestoßen. > Kein_Teiler.png Ach, werden die Hausaufgaben jetzt Rätsel genannt, damit das hier: Beitrag "Einheitlicher Umgang mit faulen Schülern etc.?" nicht greift? Gruss Harald
Ok, neuer Ansatz: Wenn ich beweise, dass nie Menge n+1 nicht die Bedingung erfüllt, dann kann ich es auf diese Weise mit einem Widerspruch belegen, oder?
Harald Wilhelms schrieb: > Ach, werden die Hausaufgaben jetzt Rätsel genannt, damit das hier: > Beitrag "Einheitlicher Umgang mit faulen Schülern etc.?" > nicht greift? > Gruss > Harald Wenn du meine anderen Posts verfolgt hättest, wüsstest Du, dass ich meinen Titel schon habe... Danke für den zudringlichen Post.
Florian Rist schrieb: > Man nimmt an, das M={n+1,...,2n} nicht die größte Menge mit den > genannten Eigenschaften ist. Dann muss es ein x<=n geben das nicht > Element von M ist und kein Element aus M teilt. Jetzt zeigt man, dass es > so ein x nicht gibt. Fertig. Geht leider nicht. Damit beweist Du nur, dass es keine größere Menge als M gibt, die M enthält.
Hallo dumidi dum, kann sehr gut sein, dass mein Beweisversuch falsch ist, aber deinen Einwand versteh ich noch nicht. Kannst du das noch etwas erläutern. Grüße Flo
Ok, ich versuch es mal.
Mit Widerspruchsbeweis.
In einer Teilmenge aus n+1 Elementen aus der Menge M={1, .. 2n} gibt es
2 Zahlen, bei denen eine die andere teilt.
Zerlegung in gerade und ungerade:
ai = 2^ki mi
m ist eine ungerade Zahl zwischen 1 und 2n-1.
Da es aber nur n verschiedene ungerade Anteile gibt muss eine Zahl ein
Vielfaches einer anderen sein.
:
Bearbeitet durch User
Dennis K. schrieb: > http://www2.hs-fulda.de/~grams/Problemloesen/ProblemloesenBegleitmaterial.pdf Nette Aufgaben, Danke dafür :-) > > [..] Wieviele Taxis? [..] Angenommen es gibt keine freien Nummern, Ok... Dann bin ich aber ins grübeln geraten. Wie ist es in der Realität? Wie geht man mit folgenden Annahmen um: -Taxen behalten ihre Taxileben lang ihre Nummer, auch wenn Taxen mit niedrigeren Nummern das Zeitliche segnet. -Neue Taxen erhalten die niedrigste zur Zeit freie Nummer Wie hoch ist der Anteil der Taxen, die -nicht nach ihrem Ableben sofort ersetzt werden, -die spontan erworben werden. Hätte es bei einer größeren Stichprobenmenge einen ausgedünnten oberen Nummernbereich gegeben?
Habe auch angenommen, dass die Taxinummern fortlaufend ohne Lücken sind. Und dann mit Normalverteilung einen Wert bestimmt. Wie das im richtigen Leben mit den Taxen funktioniert kann ich nicht sagen...
Florian Rist schrieb: > Kannst du das noch etwas erläutern. Kann ich versuchen. Florian Rist schrieb: > Man nimmt an, das M={n+1,...,2n} nicht die größte Menge mit den > genannten Eigenschaften ist. Dann muss es ein x<=n geben das nicht > Element von M ist und kein Element aus M teilt. Ich brösel mal ein wenig auf: Also: Annahme M={n+1,...2n} ist nicht die größte Menge mit der genannten Eigenschaft. D.h. es gibt eine Menge N mit der genannten Eigenschaft (alles Teilerfremd) und |N| > |M|. Dann (das ist richtig) muss es ein x<=n geben, dass nicht Element von N (oder meinst Du jetzt auch M, hilft beides nicht) ist und .... dann hört es auf. Dein Beweis kann funktionieren wenn Du weißt, dass M Teilmenge von N ist. Aber über die 'größte Menge' weißt Du nix. Analogie aus dem 8 Damenproblem: So köntest Du auch beweisen, dass 7 Damen das Maximum an Damen die sich nicht schlagen können auf einem Schachbrett wäre. Du nimmst eine Konfig mit 7 Damen und beweist dass Du keine mehr dazustellen kannst. Das funktioniert aber nicht als Beweis, da Du Dich erstmal in die Ecke manövriert hast, d.h. Du zeigst ein lokales Maximum, musst aber das globale zeigen.
Hallo dumdi dum, danke für deine Erklärungen. Ich hab's geschnallt. Du hast natürlich recht. Vereinfacht gesprochen ist das Problem, dass ich nicht weiß, ob ich nicht vielleicht durch entfernen eines Elements aus M und hinzufügen von zwei neuen Elementen ein neues und mächtigeres M (mit den best. Eigenschaften) bekomme. Grüße Flo PS: Zum Taxiproblem: http://blog.zeit.de/mathe/allgemein/zweiter-weltkrieg-mathematik-mathe-blog/
Yalu X. schrieb am 10.07.2014... Dennis K. schrieb am 20.06.2016... Dennis, bist du Schweizer?
Dennis K. schrieb: > Dann sag es doch... Ich habe die Lösung damals nicht gepostet, weil ich den Fuldaer Studenten der den Spaß beim Lösen der Aufgabe nicht nehmen wollte. Mittlerweile gibt es die Aufgaben von 2015, so dass gegen die Veröffentlichung der Lösung nichts mehr sprechen würde. Ich werde also heute Abend in meinem Altpapierkarton mal nach dem Schmierzettel mit der Lösung suchen. Da der Thread jetzt aber schon ein paar Tage alt ist, könnte es durchaus sein, dass der Zettel zwischenzeitlich in den Altpapiercontainer gewandert ist. Da auch dieser regelmäßig geleert wird, hat der Lösungszettel evtl. schon sein zweites Leben als Recycling-Klopapier genossen. Möglicherweise ist das Klopapier sogar schon benutzt und Richtung Kläranlage gespült worden. Vielleicht ist der zurückbleibende Klärschlamm auch schon zur Düngung eines Kartoffelackers verwendet worden. Geh also heute Abend doch einfach mal zu McDondald's und schau dir die Pommes vor dem Verzehr genau an, vielleicht entdeckst du darin irgendwelche mathematischen Symbole :) Wenn dir die Lösung wirklich wichtig ist, kann ich heute Abend, statt den Zettel zu suchen, auch versuchen, die Lösung aus dem Gedächtnis zu rekonstruieren, was erfolgsversprechender sein dürfte. Was ist aber mit deinem Beitrag vom 08.07.2014 14:17? Das sieht doch sehr gut aus. Ich weiß nicht, ob ich das damals überlesen hatte, denn sonst hätte ich ja selber nichts mehr zu posten brauchen, zumal mein Beweis komplizierter war, wenn ich das richtig in Erinnerung habe.
Dumdi D. schrieb: > Analogie aus dem 8 Damenproblem: So köntest Du auch beweisen, dass 7 > Damen das Maximum an Damen die sich nicht schlagen [...]. > Du nimmst eine Konfig mit 7 Damen und beweist dass Du > keine mehr dazustellen kannst. Frauenfeindlicher Witz in 3,2,1,... Yalu X. schrieb: > Da auch dieser regelmäßig geleert wird, hat der > Lösungszettel evtl. schon sein zweites Leben als Recycling-Klopapier > genossen. Ja das macht immer Spaß am Klo. Während dem drücken mathematische Rätsel auf dem Klopapier lösen. Blöd nur, wenn man nach dem Abwischen nochmal was nachlesen will :( Yalu X. schrieb: > Geh also heute Abend doch einfach mal zu McDondald's und schau dir die > Pommes vor dem Verzehr genau an, vielleicht entdeckst du darin > irgendwelche mathematischen Symbole :) Nein das sind immer nur so wirre Sätze. Man sollte nicht neben einem Hobbydichter wohnen.
John D. schrieb: > Yalu X. schrieb am 10.07.2014... > Dennis K. schrieb am 20.06.2016... > > Dennis, bist du Schweizer? Nein... Warum? Yalu X. schrieb: > Ich habe die Lösung damals nicht gepostet, weil ich den Fuldaer > Studenten der den Spaß beim Lösen der Aufgabe nicht nehmen wollte. > > Mittlerweile gibt es die Aufgaben von 2015, so dass gegen die > Veröffentlichung der Lösung nichts mehr sprechen würde. Ich werde also > heute Abend in meinem Altpapierkarton mal nach dem Schmierzettel mit der > Lösung suchen. Na, es würde mich halt schon die elegante Lösung interessieren, die du dir zurecht gelegt hast. Vielleicht findest du sie ja?
Dennis K. schrieb: > Vielleicht findest du sie ja? Leider nicht, es ist einfach schon zu lange her. > Na, es würde mich halt schon die elegante Lösung interessieren, die du > dir zurecht gelegt hast. Wie ich oben schon geschrieben habe, war mein Beweis nicht sehr elegant. Der Ansatz war in etwa folgender: Das sich mindestens n Zahlen aus {1, 2, ... 2n} finden lassen, die sich gegenseitig nicht teilen, zeigt man leicht anhand des Beispiels {n+1, n+2, ... 2n}. Es muss also nur noch gezeigt werden, dass es keine Teilmenge mit mehr als n Elementen gibt, die diese Bedingung immer noch erfüllt. Der Beweis erfolgt mit vollständiger Induktion: Für n=1 ist die Sache klar: Aus der Menge {1, 2} wird die Bedingung nur duch die Teilmengen {}, {1} und {2} erfüllt. Die beiden größten davon enthalten gerade 1 Element. Unter der Annahme, dass die Behauptung für n richtig ist, ist nun zu zeigen dass sie auch für n+1 gilt. Die Induktionsannahme lautet also: Es gibt höchstens n Zahlen aus {1, 2, ... 2n} die sich gegenseitig nicht teilen. Für n+1 ist die Menge, aus der die Teilmengen betrachtet werden {1, 2, ... 2n, 2n+1, 2n+2}. Eine Teilmenge dieser Menge, die die Bedingung erfüllt, kann auf Grund der Induktionsannahme nicht mehr n Elemente aus {1, 2, ... 2n} plus die zwei neu hinzugekommenen Elemente 2n+1 und 2n+2 enthalten. Eine Teilmenge kann also höchstens dann mächtiger als n+1 sein, wenn darin auch beide neuen Elemente 2n+1 und 2n+2 enthalten sind. insbesondere 2n+2=2(n+1) kann aber nur dann in der Teilmenge enthalten sein, wenn n+1 und alle Teiler davon nicht in ihr enthalten sind. Und jetzt kommt der Punkt wo ich nicht mehr genau weiß, wie ich das damals gelöst habe: Es kann jetzt nämlich gezeigt werden, dass, wenn man aus der Menge {1, 2, ... 2n} das Element n+1 und alle seine Teiler weglässt, es nicht mehr möglich ist, darin n Elemente zu finden, die sich nicht gegenseitig teilen. Damit ist gezeigt, dass die Behauptung auch für n+1 gilt, und der Beweis durch vollständige Induktion ist komplett. Wie ich diesen letzten Schritt gezeigt habe, weiß ich leider nicht mehr. Mir fallen dafür mehrere Möglichkeiten ein, die aber direkt oder indirekt alle auf die Faktorisierung der Zahlen in eine ungerade Zahl und eine Zweierpotenz hinauslaufen, wie du es in deinem Beweis gemacht hast. Nur braucht man dann keine vollständige Induktion mehr, da der Beweis ohne sie viel einfacher wird. Schon an diesem langen Text erkennt man meine Schwierigkeiten, den (nicht einmal vollständigen) Beweis zu skizzieren, weswegen vollkommen klar ist, dass er dem deinen an Eleganz um Kilometer hinterherhinkt :)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.