Mathe-Marathon Uni - Seite 7

Neue Frage »

tmo Auf diesen Beitrag antworten »

Vielleicht mal was für Tüftler:

Aufgabe 69

Man finde einen Ring der Charakteristik 0, der ein maximales Ideal enthält, derart dass ein unendlicher Körper der Charakteristik ist.

Vielleicht gebe ich direkt mal einen Tipp, um etwas zu motivieren:

Schon als Restklassenkörper ist gar nicht so einfach zu finden, aber man wird z.b. für via fündig. Vielleicht gibt das eine Idee, wie man den Ring konstruieren könnte.
tmo Auf diesen Beitrag antworten »

Die Aufgabe wurde ja bereits gelöst (siehe Diskussionen zum Thread "Mathe-Marathon Uni" ff., falls jemand Details will, gerne nachfragen), daher hab ich noch eine neue Aufgabe 70:

Und zwar untersuchen wir das Legendre-Symbol, genauer wollen wir versuchen aus einer endlichen Liste von Werten die Primzahl zu rekonstruieren.

Also folgendes Spiel:

Gegeben ist die Liste der ungeraden Primzahlen. Spieler A sucht sich aus der Liste seine Lieblingsprimzahl aus.

Dann ist der Spieler B an der Reihe. Ein Zug von ihm besteht daraus, dass er für ein beliebiges den Wert abfragt.

Sobald er die Primzahl kennt, hat Spieler B gewonnen.

Um die verräterischen Nullen in der Definition zu vermeiden, einigen sich beide Spieler vor dem Spiel auf eine (von p unabhängige) Abbildung

,

und Spieler A nennt im Fall dann immer den Wert für .

So nun die Aufgabe:

a) Zunächst einigen sich die Spieler auf für alle . Zeige, dass Spieler B in Zügen gewinnt.

b) Spieler A fühlt sich zurecht benachteiligt, daher probieren die Spieler mal die Abbildung für alle aus. Zeige, dass Spieler B in Zügen gewinnt. (Das ist nicht die beste Schranke).

c) Spieler A hat immer noch kein Spaß am Spiel. Finde daher für ihn ein , sodass Spieler B nie gewinnen kann (Und beweise dies natürlich). Mit "nie" ist hier "nicht nach endlich vielen Zügen" gemeint. Ausnahmsweise handelt es sich bei den Spielpersonen mal um normale Menschen, die wirklich eine endliche Lebenszeit und endliche Informationsaufnahme besitzen Augenzwinkern .

Gerne auch nur Lösungen für einzelne Aufgabenteile.
In a) und b) muss man eigentlich nur die Unzulänglichkeit der Abbildung geschickt ausnutzen, während in c) dann wirklich etwas zu beweisen ist, nachdem man die Unzulänglichkeiten von beseitigt hat.
RavenOnJ Auf diesen Beitrag antworten »

Dann mach ich erst mal a):

Die gedachte Primzahl sei . B erfragt die Werte zu . Für alle Primzahlen ergibt dies entweder 0, wenn , mit dem Mapping durch f also -1, oder es ergibt 1, da alle Quadrate quadratische Reste sind, falls kein Teiler des Quadrats ist. Insbesondere also wenn das Quadrat einer von verschiedenen Primzahl genommen wird. Es sind genau k Abfragen notwendig, die -1 bei der k-ten Abfrage liefert die gesuchte Primzahl.
tmo Auf diesen Beitrag antworten »

Kurze Erinnerung, dass hier noch b) und c) ausstehen. Wink In der c) darf der Dirichletsche Primzahlsatz, dass in arithmetischen Folgen unendlich viele Primzahlen vorkommen, natürlich verwendet werden.
tmo Auf diesen Beitrag antworten »

Würde an dieser Aufgabe hier mehr Interesse bestehen?

Oder hat jemand evtl. eine neue gute Aufgabe?

Dann würde ich nämlich mal auflösen und mit obiger Aufgabe weitermachen oder jemand anderes macht mit einer neuen Aufgabe weiter.
tmo Auf diesen Beitrag antworten »

Ich werde dann mal auflösen:

Zu b)

Zunächst folgende Überlegung: Findet Spieler B ein paar von Primzahlen derart, dass er von Spieler A hört, so ist klar, dass die gesuchte Primzahl ist.

Nun gibt es zu jeder Primzahl eine kleinere Primzahl mit . Denn wenn jede Primzahl quadratischer Rest wäre, so wäre jeder Zahl quadratischer Rest.

D.h. wenn die ausgewählte Primzahl ist, so wird Spieler B nach Abfrage der folgenden Zahlen das obige Paar gefunden haben:







Dies entspricht Zügen (Evtl. kann ich im Diskussionsthread darauf eingehen, wie man noch etwas verschärfen kann, wenn gewünscht).


Zur c)

Sowohl in a) als auch in b) war die entscheidende Idee natürlich, dass wir Widersprüche zur Multiplikativität des Legendre-Symbols suchen und somit die Primzahl identifizieren. Das Ziel muss also sein, ein zu finden, derart dass die Gesamtabfragefunktion multiplikativ ist.

tut's.

Die Gesamtabfragefunktion hat dann die selbe Form: , wobei hier nun möglich ist. ist offenbar multiplikativ.

Hinreichend dafür, dass Spieler B nicht gewinnen kann, ist nun folgende Aussage:

Zitat:

Ist eine beliebige Funktion, die multiplikativ im Sinne von für ist, so gibt es unendlich viele Primzahlen mit auf .


Beweis:
Seien dazu die ungeraden Primzahlen in . Wir wählen mit .

Nach dem chin. Restsatz und dem Dirichletschen Primzahlsatz gibt es unendlich viele Primzahlen mit

sowie und .

Für ein solches gilt in jedem Fall und wir erhalten:

und für .

Wegen der Multiplikativität erhalten wir auf .


Hat jemand eine neue Aufgabe? RavenOnJ wäre zuerst dran.
 
 
tmo Auf diesen Beitrag antworten »

Aufgabe 71:

Wir definieren eine Folge rekursiv durch:

.

Zu jedem zähle die Anzahl der Nullen unter den Folgengliedern .

Z.b. ist also und wegen ist .

Man finde für alle .

PS: Die Lösung findet sich in anderem Gewand schon in einer der Marathon-Diskussionen Augenzwinkern
Guppi12 Auf diesen Beitrag antworten »

Ich bin gespannt auf eine elegantere Lösung. Leider ist mir keine bessere Formulierung eingefallen(eigentlich braucht man sich nur das pascalsche Dreieck anschauen, dann sieht man es sofort, aber wie man das ordentlich in Worte fasst, naja..) :

Zitat:
Lösung 71

Es gilt

Beweis:

Vorbemerkung: Wenn ich im Folgendem von Bereich spreche meine ich dabei immer eine Menge von Folgenindizes. Ein Folgenglied aus dem Bereich bis soll also eines der Folgenglieder sein.


Es gilt



Daraus kann man ablesen, dass es für jedes Folgenglied aus dem Bereich bis jeweils Folgenglieder aus dem Bereich von bis gibt, deren Werte gleich , bzw. sind. Dies wird nun mit bezeichnet.

Damit beweisen wir nun mit vollständiger Induktion(über ) :

Im Bereich bis gilt:
Die Zahl taucht für alle genau -fach als Folgenglied auf. (Dies sind dann bereits alle Folgenglieder in dem Bereich wegen .)

Induktionsanfang: Im Bereich bis liegt nur das Folgenglied . Dieses ist gleich . Als Wahl für kommt auch nur in Frage. Die tritt also tatsächlich -fach als Folgenglied in diesem Bereich auf.

Induktionsschritt: Sei nun und

Fall 1:

Die Anzahl der Folgenglieder im Bereich bis mit Wert ergibt sich nach aus der Summe der Anzahlen der Folgenglieder im Bereich bis mit Werten bzw. .

Deren Anzahlen aufsummiert ergibt also nach Induktionsvoraussetzung .

Fall 2:

Im Bereich bis gibt es nach Induktionsvoraussetzung genau jeweils Folgenglied mit Wert bzw. und keine Folgenglieder, mit Wert oder . Nach gibt es dann auch genau jeweils ein Folgenglied im Bereich bis mit Wert bzw .
Induktion abgeschlossen.

Damit folgt nun sofort, dass für ungerade im Bereich bis überhaupt kein gerades Folgenglied liegt, geschweige denn eine .

Ist hingegen gerade, liegen im Bereich bis genau Nullen, wegen .


Guppi12 Auf diesen Beitrag antworten »

Aufgabe 72:

Sei die eulersche -Funktion und beliebig.

Zeige, dass ein (natürlich von abhängiges) existiert mit
tmo Auf diesen Beitrag antworten »

Lösung 72:

Ist die kleinste Primzahl mit , so gilt .

Zum Beweis der letzten Gleichheit beachte man, dass und nach Wahl die selben Primteiler haben und daher erhält man

tmo Auf diesen Beitrag antworten »

Mal was einfaches aus der elementaren Zahlentheorie:

Aufgabe 73

Sei zusammengesetzt, d.h. mit natürlichen Zahlen .

Man zeige, dass der Exponent der Primzahl 2 in der Primfaktorzerlegung von gerade ist.
RavenOnJ Auf diesen Beitrag antworten »

Dann mach ich mal

Lösung 73

. Sei und . OBdA sei (für kann man genauso mit vertauschten Rollen von m und k argumentieren). Es ist klar, dass . Man kann nun schreiben:
. Der Term muss offensichtlich gerade sein, was nur möglich ist, wenn m=k, da r und s beide ungerade. Damit wird . Der Exponent zu 2 in der Primfaktorzerlegung ist also gerade.
Guppi12 Auf diesen Beitrag antworten »

So, hier etwas für Algebraiker Mit Zunge

Aufgabe 74

Seien positive ganze Zahlen.

Zeige, dass dann stets durch teilbar ist.
tmo Auf diesen Beitrag antworten »

Mir fehlt leider der Geistesblitz, daher muss ich die Nuss ins Wasser legen und langsam aufweichen lassen (Kleine Hommage an den verstorbenen Grothendieck Augenzwinkern )

Lösung 74

Klar ist:

Zunächst zeigen wir, dass die Aussage für gilt, wenn sie für teilerfremde Zahlen gilt.

Das ist ganz leicht

ist nach Voraussetzung durch n teilbar. Die Teilbarkeit durch m kriegt man durch Vertausch von m und n.

Somit müssen wir die Behauptung nur noch für Primpotenzen zeigen (Für Primzahlen selbst ist es trivial, das ist unser Induktionsanfang. Wir können den Induktionsanfang aber auch bei dem noch trivialeren Fall setzen):

Es ist


Wir müssen nun noch zeigen, dann sind wir mit Induktion fertig.

Ist a nicht durch p teilbar, so haben wir

Ist a durch p teilbar, so sind wegen für sowieso beide Seiten Null.
HAL 9000 Auf diesen Beitrag antworten »

Angeregt durch das wiederholte Auftauchen dieser Problemstellung erlaube ich mir mal, diese auszudehnen:

Zitat:
Aufgabe 75

Man bestimme alle reellen Zahlen mit folgender Eigenschaft:

Für alle stetigen Funktionen mit gibt es eine Stelle mit .
Leopold Auf diesen Beitrag antworten »

Im Anhang eine Euklid-Datei zum Spielen.
Guppi12 Auf diesen Beitrag antworten »

Zitat:
Aufgabe 75

Man bestimme alle reellen Zahlen mit folgender Eigenschaft:

Für alle stetigen Funktionen mit gibt es eine Stelle mit .


Lösung 75

Die gesuchte Menge ist .

Für sei und betrachte zu stetigem wie in der Voraussetzung . Gäbe es kein mit , dann hat keine Nullstelle, ist also wegen des Zwischenwertsatzes strikt positiv oder strikt negativ. O.B.d.A. sei strikt positiv. Daraus folgt im Widerspruch zur Voraussetzung an .

Sei nun umgekehrt kein Kehrwert einer ganzen Zahl. Es gibt ein maximales mit .
Ich gebe erstmal eine anschauliche Beschreibung der Funktion, die wir konstruieren. Danach definiere ich sie formal, aber ob das wirklich hilfreich ist, weiß ich nicht. Wir konstruieren eine Funktion mit . Ausgehend vom Punkt betrachten wir die Punkte . Umgekehrt betrachten wir ausgehend von die Punkte . Verbinden wir diese Punkte, erhalten wir den Graph einer stetigen Funktion, die den Voraussetzungen entspricht, aber für kein erfüllt, dass .

Etwas formaler: Sei mit für , wobei und
für für . Man rechnet leicht durch Einsetzen in die Übergangsstellen nach, dass wohldefiniert, stetig und .

Wenn nun , dann ist , also gilt:

. Der Fall ist analog.

Ich hoffe, es ist ok, dass ich einige Details weggelassen habe, hab das mit dem Handy eingetippt unglücklich
HAL 9000 Auf diesen Beitrag antworten »

Huch, hatte ich schon ganz vergessen. Die Lösung ist natürlich rundum gelungen, insbesondere die Zick-Zack-Gegenbeispielfunktion im zweiten Fall. Freude
Guppi12 Auf diesen Beitrag antworten »

Zitat:
Aufgabe 76
Man zeige, dass sich in jedem metrischen Raum jede offene Menge als nicht-redundante Vereinigung von Kugeln schreiben lassen kann.

Dabei heißt eine Vereinigungen nicht-redundant, falls für alle gilt .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »