Aufgabensammlung

Mathematikaufgaben, die mir über die Jahre begegnet sind und die ich schön finde.

Zahlentheorie

Bestimme alle \( n,k, a_1, \ldots, a_k \in \mathbb{Z}, \) sodass \[ \frac{n^{k+1} + 1}{(a_1n + 1)\cdots (a_kn+1)} \in \mathbb{Z} \] (Quelle: AIMO 2020)

Gibt es ein \( n \in \mathbb{N}, \) sodass \( n^7 - 77 \) eine Fibonacci-Zahl ist? (Quelle: Imre Leader)

Sei \( n = -1 \pmod {24}. \) Zeige, dass die Summe der Teiler \( \sigma(n) \) durch \( 24 \) teilbar ist.

Geometrie

Sei ein Würfel der Seitenlänge 1 im dreidimensionalen Raum gegeben. Beweise, dass sein Projektion/Schatten auf der x-y Ebene den gleichen Flächeninhalt hat wie die Länge seiner Projektion auf der z-Achse.

Mengenlehre

Gegeben sei eine Wohlordnung auf den reellen Zahlen. Ein Zug, der am Anfang leer ist, fährt diese entlang. Bei jeder Station steigt, falls möglich, eine Person aus, während \( \omega \) viele einsteigen. Welche Möglichkeiten gibt es für die Anzahl der Personen im Zug am Ende?

Kann man den dreidimensionalen Raum mit disjunkten Kreisen mit positivem Radius füllen?

Kombinatorik

In einem Aquarium schwimmen 1000 Fische mit Gewichten \(1,2, \ldots, 1000 \). Wenn Fisch \(A \) mit Gewicht \( a \) auf Fisch \( B \) mit Gewicht \( b = a-1 \) trifft, wird \( B \) von \( A \) gefressen. Gesucht ist \[ P( \text{Fisch mit Gewicht 1 überlebt}). \] (Quelle: AIMO 2020)

Gibt es eine Menge \( S \in \mathbb{N}_0 \) mit der Eigenschaft, dass \(a + 2b = n \) für jedes \( n \in \mathbb{N}_0 \) genau eine Lösung \( (a,b) \in S \times S \) hat?

Betrachte Polynome mit Koeffizienten aus \( \{ 0,1,2,3 \}. \) Wie viele von diesen erfüllen \( P(2) = n \) für festes \( n \) ?

Definiere für \( S \in \mathbb{N}_0, n \in \mathbb{N} \) die Funktion \[ r_s(n) = |\{ (s_1, s_2) \in S \times S: s_1 \neq s_2, s_1 + s_2 = n \}|. \] Frage: Gibt es eine Partition von \( \mathbb{N}_0 \) in die Mengen \( A, B \) sodass \( r_A(n) = r_B(n) \forall n \in \mathbb{N} \) ?
Ist es möglich, dass 100 Geraden in der Ebene genau 2023 Schnittpunkte haben?
Gegeben sei ein Graph, in dem alle Knoten Grad 3 haben. Gibt es eine Färbung der Kanten in 2 Farben, sodass von keinem Knoten nur gleichfarbige Kanten ausgehen? (Quelle: MO Landesrunde 2020)

Lösung 1 (Quelle: Hossein Gholizadeh)

Es gibt immer ungerade viele Knoten ungeraden Grades. Füge einen Knoten \( v \) hinzu und verbinde ihn mit jedem anderen Knoten. Nun hat jeder Knoten geraden Grad und wir finden einen Eulerkreis. Gehe diesen entlang und färbe die Kanten abwechselnd. Nach dem Entfernen von \( v \) und den mit ihm verbundenen Kanten hat der Graph die geforderte Eigenschaft.
Zeige, dass man einen Graphen \( G \) immer in zwei Teilgraphen teilen kann, wobei der Grad jeder Knote, wenn man nur die Kanten zu Knoten in der jeweiligen Teilmenge betrachtet, gerade ist.

Lösung 1

Induktion über die Anzahl an Knoten. Nehme einen Graphen mit \( n+1 \) Knoten, und nehme einen Knoten \( v \) mit ungeradem Grad heraus (wenn keiner existiert, sind wir fertig). Der Graph \( G \) hat jetzt \(n \) Knoten, und betrachte den Graphen, der von den Nachbarknoten von \( v \) erzeugt wird, und drehe alle Nachbarschaften um (verbinde nicht verbundene Knoten, und lösche alle existierenden Kanten). Wir erhalten \( G' \) mit \( n \) Knoten, und nun wenden wir die Induktionshypothese darauf an, und erhalten \( G' = X \cup Y. \) \( v \) hat ungeraden Grad und damit o.B.d.A. gerade viele Nachbarn in \( X. \) Wir fügen \( v \) also zu \( X \) hinzu, damit haben jedoch alle Nachbarn von \( v \) nun ungeraden Grad innerhalb von \( X. \) Wir drehen aber wieder alle Kanten von \( G' \) so um, dass er wieder zu \( G \) wird, was genau bewirkt, dass all diese Knoten geraden Grad in \( X \) haben, und sich die Parität des Grades aller Knoten in \( Y \) nicht ändert.
Gegeben ist ein Quadratgitter aus NxN Kästchen; N sei eine ungerade Zahl größer oder gleich 3. Die Raupe Nummersatt sitzt in dem Kästchen genau in der Mitte des Gitters. Jedes der übrigen Kästchen enthält einen Stammbruch. Über die Verteilung der Zahlen ist nur bekannt, dass sich in keinen zwei Feldern die gleiche Zahl befindet. Nummersatt möchte durch dieses Zahlenmeer einen Weg nach draußen finden. Sie kann dabei von einem Kästchen stets nur zu einem entlang einer Seite angrenzenden Kästchen weiterwandern und muss jede Zahl fressen, durch deren Kästchen ihr Weg führt. Nummersatt kann insgesamt nicht mehr als 2 fressen. Wann kann Nummersatt dem Gitter entfliehen? (Quelle: Bundesrunde 2003)

Es gibt ein Schloss, das aus einem 3x3-Feld an an- und ausgeschalteten Lichtern besteht. Wenn man ein Licht betätigt, dann ändert sich der Zustand aller Lichter in dessen Spalte und Reihe. Zeige, dass es genau 32 Zustände gibt, aus denen man das Schloss öffnen kann.
Beweise mit einer kombinatorischen Deutung, dass für die Fibonacci-Zahlen mit \( F_0 = 1, F_1 = 1 \) gilt, dass \[ F_{2n} = \sum_{i = 0}^n {2n-i \choose i} \]

Lösung 1

Beide Seiten der Gleichung können interpretiert werden als die Anzahl Möglichkeiten, \( 2n \) Treppen hinunterzulaufen, wobei man immer nur 1 oder 2 Schritte machen darf.
Es seien \( n \) Punkte im \( \mathbb{R}^2 \) gegeben, die paarweise höchstens den Abstand 1 haben. Wie viele Punkte kann es höchstens geben, die Abstand echt größer als \( \frac{1}{\sqrt{2}} \) haben?

Lösung 1 (Quelle: Victor Souza)

Betrachte den Graphen mit den \( n \) Punkten als Knoten und verbinde zwei Punkte, wenn sie Abstand echt größer als \( \frac{1}{\sqrt{2}} \) haben. Zeige mit Elementargeometrie, dass dieser Graph keinen \( K_4 \) als Teilgraphen haben kann. Dann hat der Graph nach dem Satz von Turan höchstens \( \frac{n^2}{3} \) Kanten, und ein Beispiel zu konstruieren, das diesen Wert annimmt, ist nicht sehr schwer.
Sei \( G \) ein endlicher Graph mit \( n \) Knoten, und \( J \) die \( n \times n \)- Matrix mit einer 1 in jedem Eintrag. Wann kann \( J \) als Polynom in der Nachbarschaftsmatrix von \( G \) geschrieben werden?

Lösung 1

Genau dann, wenn \( G \) regulär und zusammenhängend ist. (beweis todo)

Analysis

Finde eine überall surjektive Funktion, d.h. eine Funktion die jedes reelle Intervall \( (a,b) \) auf \( \mathbb{R} \) abbildet. (Quelle: Imre Leader)

Lösung 1
Die Conway base-13 function

Lösung 2 (Quelle: Robbie Bennett)

Wir konstruieren eine Funktion \( (0,1) \to (0,1) \) mit der gewollten Eigenschaft. Diese ist für \( x = \sum_{r = 1}^{\infty} x_r10^{-r}, \) wobei wir im Zweifelsfall die Dezimaldarstellung nehmen, die mit Nullen endet, wie folgt: \[ f: x \mapsto \begin{cases} \sum_{p \text{ prim} }^{\infty} (10^{-n_p} \sum_{i = 1}^{\infty} x_{p^i}(-1)^{i}) \mbox{ falls die innere Summe immer konvergiert } \\ 0 \mbox{ falls nicht, für irgend ein } p \end{cases} \] Hierbei ist \( p \) die \( n_p\) -te Primzahl. Jetzt können wir im Intervall \(k,m \in \mathbb{N} \) so wählen, dass \( (k \cdot 10^{-m}, k \cdot 10^{-m} + 10^{-m-1}) \subseteq (a,b). \) Wenn die \(i \)-te Nachkommastelle von \( y \) die Zahl \( y_i \) ist, können wir eine Zahl im Intervall \( (k \cdot 10^{-m}, k \cdot 10^{-m} + 10^{-m-1}) \) so wählen, dass die Nachkommastellen der Primpotenzen der \( i\) -ten Primzahl, wobei wir nur die nach der \(m \)-ten Stelle verändern, in der alternierenden Summe aufsummiert \( y_i \) ergeben.

Beweise: Wenn \(a_i \to a, \) dann gilt \[ \lim_{n \to \infty} \frac{1}{n} \sum_{i = 1}^n a_i = a \]

Gibt es ein Polynom von \( \mathbb{R}^2 \) nach \( \mathbb{R}^+ \) (die positiven reellen Zahlen), das surjektiv ist?

Beweise für eine Menge Mittel \( b_k, \) für die \[ \begin{align} \sum_{k=1}^n |b_k| &\to \infty \tag{1} \\ \frac{|\sum_{k=1}^n b_k|}{\sum_{k=1}^n|b_k|} &\geq \beta > 0 \tag{2} \end{align} \] gilt, dass für jede Folge \( x_k \to a \) auch \[ \frac{\sum_{k=1}^n b_kx_k}{\sum_{k=1}^n b_k} \] gegen \( a \) konvergiert. Finde auch Gegenbeispiele, wenn eine der beiden Bedingungen verletzt ist. (Quelle: Jürgen Prestin)
Finde eine geschlossene Form für \[ a_n = \sqrt{2 + \sqrt{2 + \ldots + \sqrt{2}}}. \]
Beweise, dass \( tan^{-1}(x) \) keine gebrochenrationale Funtion ist.
Konvergiert die harmonische Summe, wenn man nur alle \( n \) ohne die Stelle 7 betrachtet?
Sei \( \sum a_n \) divergent. Konstruiere ein \( b_n \), dessen Partialsummen ebenfalls divergieren, aber \( \frac{a_n}{b_n} \to 0 \) gilt.
Lösung 1 (Quelle: Conor Doherty)

Seien \( A_i \) die \(i \)-ten Partialsummen der \(a_i \). Die Folge \( b_n = \sqrt{A_n} - \sqrt{A_{n-1}} \) erfüllt beide Bedingungen.

Algebra

Konstruiere eine unendliche Gruppe mit nur endlichen Untergruppen.

Sei \( G \) eine Gruppe und \( H \) eine Untergruppe von ihr. Beweise: Wenn nicht \( |G| \; | \; |G:H|! \), dann enthält \( H \) eine nichttriviale normale Untergruppe.

Sei \( G \) eine Gruppe mit endlich vielen Elementen der Ordnung 2. Beweise, dass \( G \) entweder keine, oder ungerade viele Elemente der Ordnung 2 hat.

Sei \( G \) endlich erzeugt. Zeige, dass die Anzahl der Untergruppen mit Index \( n \) endlich ist.
Sei \( |G| = p^n \) für \( p \) prim. Zeige, dass es für jede echte Untergruppe \( H \) mindestens ein \( g \in G \backslash H \) gibt, sodass \( gHg^{-1} = H. \)

Lösung

Unendlicher Abstieg. Falls \( Z(G) \) keine Untergruppe von \( H \) ist, sind wir fertig. Falls schon, ist \( \frac{H}{Z(G)} \leq \frac{G}{Z(G)} \) ein kleineres Beispiel, da das Zentrum einer \( p \)- Gruppe immer nichttrivial ist.

Für welche \( n \) ist das Polynom \( x^n + 64 \) irreduzibel?

Lösung (Quelle: Bulgaria IMO TST)

Einfach zu sehen, dass wenn 3 oder 4 Teiler von \( n \) sind, wir eine Faktorisierung finden. Behauptung: Falls nicht, ist das Polynom irreduzibel.

Für Kinder

Eine Zahl ist selbstbeschreibend, wenn die erste Stelle angibt, wie viele Nullen sie hat, die zweite, wie viele Einsen, und so weiter. Zum Beispiel ist 2020 selbstbeschreibend. Finde alle selbstbeschreibenden Zahlen unter 10000.

Du hast eine Karte der Stadt, in der du dich gerade befindest, und du legst sie auf den Boden. Gibt es einen Punkt auf der Karte, der direkt überhalb dem Punkt in der Wirklichkeit liegt, dem er entspricht?