Diskussionen zum Übergangsmarathon - Seite 8

08.08.2017, 19:28

HAL 9000

Formelmäßig läuft meine Rechnung ähnlich ab. Allerdings überzeugt mich deine Argumentation nicht ganz:

1) Von welchem Halbkreis redest du? Bzw., was meinst du mit "Startpunkt" ?

2) Wieso darfst du in deinem Modell die einzelnen Wahrscheinlichkeiten einfach summieren? Vermutlich basierend auf disjunkten Ereignissen, aber welche meinst du da?

08.08.2017, 19:41

Mathema

Auf diesen Beitrag antworten »

Also ich hatte mir das so vorgestellt (bin aber auch kein Fachmann auf diesem Gebiet):

1) Ich wähle einen beliebigen Punkt auf dem Kreis. Dann zeichne ich einen Durchmesser durch den Punkt. Dann habe ich zwei Halbkreise. Wenn der Mittelpunkt des Kreises nicht in dem Vieleck aus meinen $\begin{eqnarray*} n \end{eqnarray*}$ Punkten liegen soll, dann müssen doch alle anderen Punkte in einem Halbkreis liegen. Sobald ich einen Punkt aus dem anderen Halbkreis wähle und wieder mit meinem ersten Punkt verbinde, liegt der Mittelpunkt des Kreises ja im Vieleck.

Das heißt wenn ich einen Punkt festgelegt habe, muss ich nur noch $\begin{eqnarray*} n-1 \end{eqnarray*}$ Punkte auf den Kreisbogen werfen und sie müssen (mit WSK 1/2) eben einen Halbkreis treffen.

Stimmt das bis hierhin?

08.08.2017, 19:56

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Mathema
1) Ich wähle einen beliebigen Punkt auf dem Kreis.

Damit geht es schon los. Was meinst du mit diesem Satz? Wird hier ein Punkt auf dem Kreis gewählt, bevor die $\begin{align*} n \end{align*}$ Punkte festgelegt werden? Oder meinst du, daß einer der $\begin{align*} n \end{align*}$ Punkte ausgezeichnet wird?

[ Die Lösung $\begin{align*} 1 - \frac{n}{2^{n-1}} \end{align*}$ bestätige ich. ]

08.08.2017, 20:00

Mathema

Auf diesen Beitrag antworten »

Ja sorry - ich meine ein Punkt (von den $\begin{eqnarray*} n \end{eqnarray*}$ ) auf der Kreislinie wird ausgezeichnet (so daß eben noch $\begin{eqnarray*} n-1 \end{eqnarray*}$ verbleiben).

08.08.2017, 20:39

HAL 9000

Auf diesen Beitrag antworten »

Hmm, ich war wohl oben etwas unfair, denn an sich klappt die Argumentation von Mathema. Vielleicht muss sie nur noch etwas detaillierter erläutert werden:

1) Wir betrachten die größte Winkellücke in der Konfiguration, und bei festgelegtem Orientierungssinn (z.B. mathematisch positiv) sei Punkt $\begin{align*} k \end{align*}$ der erste nach dieser Lücke.

2) Für festes $\begin{align*} k \end{align*}$ berechnen wir nun die Wahrscheinlichkeit, dass diese größte Winkellücke mindestens einen Halbkreis umfasst. Die anderen $\begin{align*} (n-1) \end{align*}$ Punkte (alle außer k) müssen dafür in dem anderen Halbkreis liegen, und die Wahrscheinlichkeit dafür ist mit der Argumentation von Mathema gleich $\begin{align*} \frac{1}{2^{n-1}} \end{align*}$ .

3) Das in 2) klappt für alle $\begin{align*} k=1,\ldots,n \end{align*}$ , und die Ereignisse sind disjunkt, also ist die Wahrscheinlichkeit der Vereinigung gleich $\begin{align*} \frac{n}{2^{n-1}} \end{align*}$ .

Anzumerken ist, dass dieselbe Argumentation auch für Winkellücken der Größe $\begin{align*} p>\frac{1}{2} \end{align*}$ Vollkreise klappen würde, d.h., mit Wahrscheinlichkeit $\begin{align*} n(1-p)^{n-1} \end{align*}$ gibt es eine solche Winkellücke in der Konfiguration. Für $\begin{align*} p<\frac{1}{2} \end{align*}$ klappt das so allerdings nicht, der Grund dafür liegt in 2): Ein positiver Anteil der dort berechneten Wahrscheinlichkeit $\begin{align*} (1-p)^{n-1} \end{align*}$ umfasst Fälle, wo innerhalb dieser Punktkonfiguration eine größere Lücke klafft, als die an deren Ende ja annahmegemäß Punkt k stehen soll... Vielleicht ist in dem Fall noch was mit Siebformel zu machen, muss ich mal noch eruieren. Augenzwinkern

09.08.2017, 08:31

Leopold

Auf diesen Beitrag antworten »

@ Mathema / HAL 9000: Clevere Lösung! Kompliment!

Ich versuche einmal, die Lösung zu formalisieren.

Wie in der Gaußschen Zahlenebene können wir einen Punkt auf dem Kreis durch sein Argument bestimmen. Als Ergebnisraum nehmen wir daher

$\begin{align*} \Omega = \left[ 0, 2 \pi \right)^n \end{align*}$

Ein $\begin{align*} n \end{align*}$ -Tupel $\begin{align*} \omega = \left( x_1, \ldots, x_n \right) \in \Omega \end{align*}$ beschreibt eine zufällige Punktekonstellation auf dem Kreis. Die Wahrscheinlichkeit eines Ereignisses $\begin{align*} C \end{align*}$ ist gemäß Gleichverteilung

$\begin{align*} P(C) = \frac{1}{(2 \pi)^n} \int_C \dd \omega \end{align*}$

Für jede Punktekonstellation $\begin{align*} \omega \end{align*}$ ordnen wir dem $\begin{align*} k \end{align*}$ -ten Punkt bei positiver Orientierung den Halbkreis $\begin{align*} H_k(\omega) \end{align*}$ zu, der bei $\begin{align*} x_k \end{align*}$ beginnt:

$\begin{align*} H_k(\omega) = \begin{cases} \left[ x_k, x_k + \pi \right) , & 0 \leq x_k \leq \pi \\ \left[ x_k, 2\pi \right) \cup \left[ 0, x_k - \pi \right), & \pi < x_k < 2 \pi \end{cases} \end{align*}$

Das Ereignis, daß der Mittelpunkt des Kreises nicht im Innern des Sehnen- $\begin{align*} n \end{align*}$ -Ecks liegt, ist

$\begin{align*} A = \bigcup_{k=1}^n A_k \ \ \text{mit} \ \ A_k = \left\{ \, \omega \in \Omega \, \left| \ \forall \, i \neq k: \, x_i \in H_k(\omega) \, \right. \right\} \end{align*}$

Die $\begin{align*} A_k \end{align*}$ sind bis auf Nullmengen disjunkt und besitzen aus Symmetriegründen dieselbe Wahrscheinlichkeit. Daher folgt:

$\begin{align*} P(A) = n \cdot P(A_1) \end{align*}$

Nach dem Prinzip von Cavalieri ist aber $\begin{align*} A_1 \end{align*}$ volumengleich mit dem Quader $\begin{align*} \left[ 0 , 2 \pi \right) \times \left[ 0 , \pi \right)^{n-1} \end{align*}$ , also

$\begin{align*} \int_{A_1} \dd \omega = 2 \pi \cdot \pi^{n-1} = 2 \pi^n \end{align*}$

Somit gilt

$\begin{align*} P(A) = n \cdot P(A_1) = n \cdot \frac{2 \pi^n}{(2 \pi)^n} = \frac{n}{2^{n-1}} \end{align*}$

EDIT
Und wer bringt jetzt seine Lösung in den eigentlichen Thread? Verwirrend mit diesen zwei Threads ...

09.08.2017, 17:26

Auf diesen Beitrag antworten »

Ich hatte bei der Aufgabe 61 den Kreis durch ein Quadrat ersetzt und dachte,
dass für n=3 auch wieder 25% rauskommen müssten.
Aber ich komme immer auf 24%
Das kommt mir komisch vor,weil sich am Prinzip doch nichts geändert hat

09.08.2017, 19:04

Mathema

Auf diesen Beitrag antworten »

Zitat:

Original von xb
Aber ich komme immer auf 24%

Ja - das ist auch verkehrt. Aber so können wir das nur zur Info nehmen, oder was erwartest du nun?

Zitat:

Und wer bringt jetzt seine Lösung in den eigentlichen Thread?

Ich schlage vor derjenige, der eine neue Aufgabe hat. Wäre ja nur ein Copy&Paste - wobei sogar noch Auswahl besteht. Ein schöner Aufschrieb übrigens - das würde ich wohl so nie hinbekommen. Aber das unterscheidet wohl dann den Hobbymathematiker (so würde ich mich bezeichnen) vom Fachmann (so würde ich euch bezeichnen). Hast du eine neue Aufgabe? Oder HAL? Ich knobel gerade selber noch einer Aufgabe, die wäre dann aber geklaut (ok, das war die davor auch, aber ich suche erst selbst noch die Lösung). Ansonsten hatte ich gestern nur noch ein (wie ich finde ganz nettes) Integral berechnet, aber ich weiß nicht, ob das was für diesen Thread ist und kommt da doch eher trocken daher.

Zitat:

Hmm, ich war wohl oben etwas unfair,

Ach ja? Wo das?

Ansonsten könnten wir natürlich einfach abwarten, ob jemand anderes noch eine neue Aufgabe stellt.

10.08.2017, 19:26

Auf diesen Beitrag antworten »

Ich habe jetzt mal meine Lösungsidee der Aufgabe 62 hingeschrieben
Aber diese scheint nur bei einer ungeraden Zahl von Mittelpunkten zu funktionieren

Das wäre mein Zwischenergebnis bei 4 Mittelpunkten

$\begin{eqnarray*} x_1=2x_{M4}-2x_{M3}+2x_{M2}-2x_{M1}+x_1 \end{eqnarray*}$
$\begin{eqnarray*} y_1=2y_{M4}-2y_{M3}+2y_{M2}-2y_{M1}+y_1 \end{eqnarray*}$

11.08.2017, 08:48

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000, aus Übergangs-Marathon Mathematik, zu Aufgabe 63
Ob es für allgemeine $\begin{align*} n,m \end{align*}$ auch eine schöne griffige explizite Formel für $\begin{align*} f_n(m) \end{align*}$ gibt, bleibt noch zu erforschen. Augenzwinkern

Ein Versuch. Leere Summe sind als 0, leere Produkte als 1 zu interpretieren.

$\begin{align*} f_n(m) \ = n^m + \sum_{k=1}^{m-1} \frac{m-k}{k} \cdot {{m+k-1} \choose {m}} \cdot n^{m-k} \end{align*}$

11.08.2017, 08:55

Leopold

Auf diesen Beitrag antworten »

Nachtrag zu Aufgabe 62

[attach]45064[/attach]

Es geht auch ganz ohne Koordinaten allein mit Anhängen von Vektoren.

11.08.2017, 15:29

Auf diesen Beitrag antworten »

Hier mal meine Idee zur Aufgabe 63
(Hatte ich damals durch probieren herausgefunden)

11.08.2017, 18:21

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Nachtrag zu Aufgabe 62
Es geht auch ganz ohne Koordinaten allein mit Anhängen von Vektoren.

Aber das funktioniert offenbar auch nur bei einer ungeraden Anzahl von Mittelpunkten
Es stellt sich also die Frage wie man die Aufgabe mit einer geraden Anzahl von Mittelpunkten lösen kann
Oder habe ich irgendwo falsch gerechnet?

11.08.2017, 19:05

HAL 9000

Auf diesen Beitrag antworten »

Für eine gerade Anzahl $\begin{align*} 2n \end{align*}$ von Punkten ist die Situation anders, das kann man mit ein wenig Vektorrechnung erkennen: Es gibt dann unendlich viele Lösungen genau dann wenn

$\begin{align*} M_1+M_3+\ldots M_{2n-1} = M_2+M_4+\ldots+M_{2n} \end{align*}$ .

Ist diese Bedingung nicht erfüllt, gibt es keine Lösung.

12.08.2017, 06:54

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Es gibt dann unendlich viele Lösungen genau dann wenn
$\begin{align*} M_1+M_3+\ldots M_{2n-1} = M_2+M_4+\ldots+M_{2n} \end{align*}$

Erstaunlich
Ich glaube ohne den mathematischen Beweis wäre da niemand darauf gekommen,dass das so ist

Hier nochmal die Aufgabe 62
Man kommt auch nur mit 2 Vektoren zu einem Eckpunkt

12.08.2017, 07:28

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von xb
Erstaunlich
Ich glaube ohne den mathematischen Beweis wäre da niemand darauf gekommen,dass das so ist

Weshalb, glaubst du, habe ich eine Aufgabe mit 5 Punkten gestellt? smile

Im Anhang eine dynamische Zeichnung für sechs Seitenmitten (zu öffnen mit Euklid). Die ersten fünf Mittelpunkte sind frei wählbar, der sechste nicht mehr. Dafür gibt es dann unendlich viele geschlossene Polygonzüge mit den vorgegebenen Mittelpunkten. Man kann nämlich den ersten Eckpunkt frei wählen.

12.08.2017, 11:19

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Weshalb, glaubst du, habe ich eine Aufgabe mit 5 Punkten gestellt? smile

Ah.Wirklich sehr fair und entgegenkommend smile

Es ist aber so,dass es bei der Aufgabe 62 mehr als nur eine Lösung gibt
Das stellt sich natürlich die Frage wieviele Lösungen gibt es den bei 2n+1 Mittelpunkte
Weiß das außer HAL noch jemand?

12.08.2017, 12:28

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von xb
Es ist aber so,dass es bei der Aufgabe 62 mehr als nur eine Lösung gibt

Nein, es gibt da nur eine Lösung. Vielleicht meinst du es ja so, dass es mehr als nur eine Möglichkeit gibt, diese eine Lösung zu konstruieren. Augenzwinkern

12.08.2017, 12:42

Leopold

Auf diesen Beitrag antworten »

Ich glaube, xb geht daran, die Reihenfolge der Seitenmitten zu ändern (siehe seine letzte Graphik). Das wäre aber eine neue Fragestellung: Gegeben n ungeradzahlig viele Punkte. Wie viele Polygonzüge gibt es, so daß die n Punkte die Seitenmitten des Polygonzuges sind?

Man müßte jetzt festlegen, wann man Polygonzüge identifiziert. Da spielt dann die Geometrie der n Punkte eine Rolle. Im "chaotischen" Fall wären es n! Möglichkeiten (nein! stimmt gar nicht! zyklische Vertauschungen!). Was ist aber, wenn die Seitenmitten zum Beispiel die Ecken eines regelmäßigen Polygons bilden?
Das scheint mir keine einfache Frage der geometrischen Kombinatorik zu sein.

12.08.2017, 13:41

HAL 9000

Auf diesen Beitrag antworten »

Auf die Skizze habe ich nicht geschaut. Er hat von Aufgabe 62 gesprochen, und in der steht explizit

Zitat:

Original von Leopold
$\begin{align*} M_1 \end{align*}$ bis $\begin{align*} M_5 \end{align*}$ sind der Reihe nach die Seitenmitten eines geschlossenen Polygonzugs. Man bestimme den Polygonzug.

Insofern führen erlaubte Änderungen der Reihenfolge tatsächlich zu einer anderen Aufgabe, die man nicht mehr als "Aufgabe 62" referenzieren sollte. Augenzwinkern

12.08.2017, 18:49

Huggy

Auf diesen Beitrag antworten »

@xb

Deine Lösung zu Nr.64 ist natürlich richtig. Ich hatte schon befürchtet, dass die Sache zu einfach ist. Aus meiner Sicht muss man sich nur noch überlegen, dass die Schlussfolgerung auch dann noch richtig ist, wenn der Spieler A keine feste gemischte Strategie verfolgt, sondern seine Wahl von allen vorherigen Spielrunden abhängig macht.

12.08.2017, 19:00

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Ich hatte schon befürchtet, dass die Sache zu einfach ist

Nee ist nicht zu einfach.So kann ich wenigsten mitmachen

Zitat:

Original von Huggy
Aus meiner Sicht muss man sich nur noch überlegen, dass die Schlussfolgerung auch dann noch richtig ist, wenn der Spieler A keine feste gemischte Strategie verfolgt, sondern seine Wahl von allen vorherigen Spielrunden abhängig macht.

Da hatte ich mir auch Gedanken gemacht
Deshalb hier eine Zusatzüberlegung

Wenn man in die Gewinnfunktion nur $\begin{eqnarray*} b=\frac{7}{12} \end{eqnarray*}$
einsetzt bekommt man

$\begin{eqnarray*} G_A(a, \frac{7}{12})=-\frac{1}{12} \end{eqnarray*}$

Es scheint also egal zu sein welche Strategie A wählt

Aber B muss
$\begin{eqnarray*} p_B(1)=\frac{7}{12} \end{eqnarray*}$
erst mal hinkriegen

Hat A eine Möglichkeit sein Chancen zu verbessern,
wenn B eine "Unsicherheit " in seiner Strategie hat?

Also praktisch eine Standardabweichung

12.08.2017, 19:20

Huggy

Auf diesen Beitrag antworten »

Ich hätte so argumentiert: Wenn der Spieler B in jeder Spielrunde die Zahl 1 zufällig, aber mit der festen Wahrscheinlichkeit 7/12 wählt, dann ist der Erwartungswert des Gewinns für jede einzelne Spielrunde aus Sicht von B 1/12, egal ob A die Zahl 1 oder die Zahl 2 wählt. Deshalb ändert sich der Erwartungswert einer Folge von Spielrunden nicht, egal ob und wie A seine Strategie von Runde zu Runde ändert.

13.08.2017, 07:08

Auf diesen Beitrag antworten »

Ich habe die neue Aufgabe vom Schüler Marathon rübergeholt

Ist auch etwas schwierig für den Schüler Marathon

19.08.2017, 09:49

Auf diesen Beitrag antworten »

Nochmal die Aufgabe 62 mit den Polygonzügen

Die maximale Anzahl an Polygonzügen,wenn die Reihenfolge keine Rolle spielt müsste so aussehen

$\begin{eqnarray*} A=\frac{(n-1)!}{2} \end{eqnarray*}$

Man kann bei jedem Polygonzug beim Punkt M1 anfangen.Dann hat man 4*3*2*1 Möglichkeiten einen Polygonzug zu zeichnen (Vermutung)
Aber der Polygonzug 1 3 4 5 2 ist identisch mit 1 2 5 4 3

25.08.2017, 20:51

Auf diesen Beitrag antworten »

Ein Hinweis zur Aufgabe 65

Die 2 Aufnahmen mit der Sonne wurde tatsächlich gemacht
Allerdings keine Aufnahme von mir

Das rechte Bild aus der Schweiz wurde mit einem Weißlichtfilter aufgenommen
Man beachte den Sonnenfleck

29.07.2021, 08:22

HAL 9000

Auf diesen Beitrag antworten »

Denkanstoß für Aufgabe 68: Für den Fall n=100 betrachte man die drei Zahlen 126,163,198 .

30.07.2021, 12:09

HAL 9000

Auf diesen Beitrag antworten »

Ein paar Hinweise zu Aufgabe 70, die wohl noch nicht allzu viel verraten:

1) Wenig überraschend dürfte sein, dass man das durch einen Induktionsbeweis bewältigen kann.

2) Man schaue sich das Verhalten von beiden Seiten der Ungleichung an, wenn man das $\begin{eqnarray*} x \end{eqnarray*}$ -Tupel um einen festen Offset $\begin{eqnarray*} t \end{eqnarray*}$ verschiebt, d.h., wenn man $\begin{eqnarray*} (x_1-t,\ldots,x_n-t) \end{eqnarray*}$ statt $\begin{eqnarray*} (x_1,\ldots,x_n) \end{eqnarray*}$ betrachtet.

05.08.2021, 18:05

HAL 9000

Auf diesen Beitrag antworten »

Hinweis zu Aufgabe 69:

Statt für $\begin{eqnarray*} n=2021 \end{eqnarray*}$ Nüsse kann man sich das Problem ja mal für kleinere, besser gesagt wirklich kleine $\begin{eqnarray*} n \end{eqnarray*}$ anschauen (sinnvollerweise natürlich $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ ): Dabei wird man feststellen, dass die Aussage für ungerade $\begin{eqnarray*} n \end{eqnarray*}$ wahr ist, für gerade $\begin{eqnarray*} n \end{eqnarray*}$ jedoch falsch. Bleibt noch das schwere Restproblem, das geeignet zu nutzen.

12.08.2021, 14:22

HAL 9000

Auf diesen Beitrag antworten »

Zu Aufgabe 70:

3) Die rechte Seite mit $\begin{eqnarray*} (x_1-t,\ldots,x_n-t) \end{eqnarray*}$ statt $\begin{eqnarray*} (x_1,\ldots,x_n) \end{eqnarray*}$ kann man als Funktion von $\begin{eqnarray*} t \end{eqnarray*}$ auffassen:

$\begin{eqnarray*} h(t) := \sum_{i=1}^n \sum_{j=1}^n g\left(\left|x_i+x_j-2t\right|\right) \end{eqnarray*}$

Bemerkenswert an dieser Funktion ist, dass sie stückweise ebenfalls konkav ist, und zwar auf allen Intervallen, deren Randpunkte benachbarte Zahlen aus der Menge

$\begin{eqnarray*} M = \left\{ \frac{x_i+x_j}{2} \bigm| i,j\in\{1,2,\ldots,n\} \right\} \end{eqnarray*}$

sind, und diese Konkavität trifft ebenfalls auf die beiden Außenintervalle $\begin{eqnarray*} \left(-\infty,\min M\right] \end{eqnarray*}$ und $\begin{eqnarray*} \left[\max M,\infty\right) \end{eqnarray*}$ zu. Zusammen mit der Eigenschaft, dass konkave Funktionen auf einem abgeschlossenen Intervall ihr Minimum auf dem Rand annehmen bedeutet dies, dass Funktion $\begin{eqnarray*} h \end{eqnarray*}$ ihr globales Minimum in einem Punkt aus $\begin{eqnarray*} M \end{eqnarray*}$ annimmt. In Hinblick auf die nachzuweisende Ungleichung reicht es somit

$\begin{eqnarray*} \sum_{i=1}^n \sum_{j=1}^n g\left(\left|x_i-x_j\right|\right) \leq h(t) \end{eqnarray*}$

für diesen worst-case $\begin{eqnarray*} t=\frac{x_i+x_j}{2} \end{eqnarray*}$ nachzuweisen.

Durch Umnumerierung kann man zudem o.B.d.A. $\begin{eqnarray*} i=n \end{eqnarray*}$ erreichen, sowie im Fall $\begin{eqnarray*} i\neq j \end{eqnarray*}$ auch o.B.d.A. $\begin{eqnarray*} j=n-1 \end{eqnarray*}$ (im anderen Fall $\begin{eqnarray*} i=j \end{eqnarray*}$ ist hingegen offenbar $\begin{eqnarray*} j=n \end{eqnarray*}$ ). Sieht man sich damit dann die Doppelsummen näher an, ist man dem Induktionsschritt schon sehr nahe.

12.04.2022, 12:41

Mathema

Auf diesen Beitrag antworten »

Zu Aufgabe 71:

Das war ich mit der Löschung. Zur Aufgabe eine Lösungsidee:

Die Folge $\begin{eqnarray*} a_n \end{eqnarray*}$ lässt sich schreiben als $\begin{eqnarray*} a_n=\frac{1}{2}\left(\left(2+\sqrt{3}\right)^n+\left(2-\sqrt{3}\right)^n\right) \end{eqnarray*}$ . Und somit:

$\begin{eqnarray*} a_p=\frac{1}{2}\left(\left(2+\sqrt{3}\right)^p+\left(2-\sqrt{3}\right)^p\right)=\frac{1}{2}\cdot 2\sum_{k=0, k \text{ gerade}}^p \binom{p}{k}2^{p-k}\sqrt{3}^k=\sum_{j=0}^{\frac{p-1}{2}} \binom{p}{2j}2^{p-2j}3^j\equiv 2^p=2\cdot 2^{p-1}\equiv 2 \pmod{p} \end{eqnarray*}$

12.04.2022, 13:08

HAL 9000

Auf diesen Beitrag antworten »

Du hattest letztens irgendwo geschrieben "das ging schnell"... Das Kompliment muss ich jetzt zurückgeben. smile

Die Gültigkeit der Hilfsaussage " $\begin{eqnarray*} \binom{p}{k} \end{eqnarray*}$ ist durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar für $\begin{eqnarray*} 1\leq k\leq p-1 \end{eqnarray*}$ " muss sich der Leser natürlich noch klar machen, und den Kleinen Fermat am Ende erkennen.

12.04.2022, 14:03

IfindU

Auf diesen Beitrag antworten »

Sehr cool Mathema!

Es ist schon bei der expliziten Darstellung nicht offensichtlich (für mich), dass die Teilbarkeit gilt. Gibt es eine Chance es direkt in der rekursiven Darstellung nachzuweisen, ohne die explizite herzuleiten?

12.04.2022, 15:16

HAL 9000

Auf diesen Beitrag antworten »

Wäre schön, wenn jemand sowas findet. Ich habe das Problem auch deshalb hier eingestellt, weil es eine der wenigen mir bekannten Behauptungen zu solchen Differenzenfolgen ist, der ich nur mit der expliziten statt der rekursiven Darstellung beikommen konnte.

Es hängt ja auch wirklich ganz stark von den Anfangswerten ab. Im verlinkten Thread wird ja auch über die verwandte Folge $\begin{eqnarray*} (b_n) \end{eqnarray*}$ mit derselben Iteration $\begin{eqnarray*} b_n = 4b_{n-1}-b_{n-2} \end{eqnarray*}$ aber den Anfangswerten $\begin{eqnarray*} b_0=0,b_1=1 \end{eqnarray*}$ gesprochen. Für die gilt die obige Behauptung nicht, nur eine etwas verwandte ("für Primzahlen $\begin{eqnarray*} p\equiv \pm 1\bmod 12 \end{eqnarray*}$ ist $\begin{eqnarray*} b_p-1 \end{eqnarray*}$ durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar, für $\begin{eqnarray*} p\equiv \pm 5\bmod 12 \end{eqnarray*}$ hingegen $\begin{eqnarray*} b_p+1 \end{eqnarray*}$ "), dafür aber sowas wie $\begin{eqnarray*} \operatorname{ggT}\left(b_m,b_n\right) = b_{\operatorname{ggT}\left(m,n\right)} \end{eqnarray*}$ . Augenzwinkern

12.04.2022, 20:10

IfindU

Auf diesen Beitrag antworten »

Ich fand schon vorher fast ausweglos mit der Rekursionsgleichung zu argumentieren. Wenigstens sah ich nicht wie ich ausnutzen kann, dass $\begin{eqnarray*} p \end{eqnarray*}$ prim ist. (Was ist dann an $\begin{eqnarray*} a_p \end{eqnarray*}$ so besonders?) und dann muss $\begin{eqnarray*} p \end{eqnarray*}$ auch noch ungerade sein, weil es für $\begin{eqnarray*} p =2 \end{eqnarray*}$ falsch ist.
Und jetzt hängt die Eigenschaft noch empfindlich von den Anfangswerten ab?

Pure Resignation/ Verzweiflung meinerseits. Hätte nicht einmal an einen Ansatz um das alles unter einen Hut zu bringen. Zum Glück gibt es die explizite Darstellung. Ob das noch Übergangsmarathon ist und nicht schon Hochschulmarathon?

Wenigstens kann ich die explizite Formel nur Herleiten, weil ich eine/die Herleitung der expliziten Darstellung für die Fibonacci-Folge kenne. Dass $\begin{eqnarray*} p | \binom{p}{k} \end{eqnarray*}$ würde ich einem super pfiffigen Prestudenten zutrauen, aber den kleinen Fermat? Big Laugh

12.04.2022, 21:00

Mathema

Auf diesen Beitrag antworten »

Ich habe auch keine Ahnung, wie man nur aus der Rekursion argumentieren könnte (was ja nicht heißen muss, dass dieses nicht geht). Falls so ein Beweis existiert, würde mich das natürlich auch sehr interessieren.

Ja - meine beiden Kongruenzzeichen müssten in einem sauberen Beweis natürlich noch begründet werden. Die Teilbarkeitsaussage fand ich recht offensichtlich, den kleinen Fermat habe ich ja noch angedeutet. smile

Mit "Übergang" sind ja auch interessierte Wettbewerbsteilnehmer wohl gemeint - zumindest postet HAL hier ja auch ab und an IMO Aufgaben. Und das Lösen von linearen Differenzengleichungen 2. Ordnung durch Lösen der charakteristischen Gleichung und den kleinen Fermat findet man z. B. ja auch im Buch von Engel.

13.04.2022, 06:49

HAL 9000

Auf diesen Beitrag antworten »

Für das hier

Zitat:

Original von HAL 9000
$\begin{eqnarray*} b_n = 4b_{n-1}-b_{n-2} \end{eqnarray*}$ aber den Anfangswerten $\begin{eqnarray*} b_0=0,b_1=1 \end{eqnarray*}$ [...]

für Primzahlen $\begin{eqnarray*} p\equiv \pm 1\bmod 12 \end{eqnarray*}$ ist $\begin{eqnarray*} b_p-1 \end{eqnarray*}$ durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar, für $\begin{eqnarray*} p\equiv \pm 5\bmod 12 \end{eqnarray*}$ hingegen $\begin{eqnarray*} b_p+1 \end{eqnarray*}$

muss man übrigens schon stärkere Geschütze auffahren (zumindest ist mir nichts besseres eingefallen):

Zunächst bekommt man mit der Standardmethode die explizite Darstellung $\begin{eqnarray*} b_n = \frac{1}{2\sqrt{3}}\left[ (2+\sqrt{3})^n - (2-\sqrt{3})^n \right] \end{eqnarray*}$ . Die Binomische Expansion liefert hier $\begin{eqnarray*} b_n = \sum_{k=0}^{\left\lfloor \frac{n-1}{2} \right\rfloor} \binom{n}{2k+1} 2^{n-2k-1} 3^k \end{eqnarray*}$ .

Für Primzahlen $\begin{eqnarray*} n=p>3 \end{eqnarray*}$ bedeutet das $\begin{eqnarray*} b_p \equiv 3^{\frac{p-1}{2}}\bmod p \end{eqnarray*}$ . Laut Kleinem Fermat können wir zunächst nur $\begin{eqnarray*} \left(3^{\frac{p-1}{2}}-1\right)\left(3^{\frac{p-1}{2}}+1\right) = 3^{p-1}-1\equiv 0\bmod p \end{eqnarray*}$ folgern, d.h., es kommen nur $\begin{eqnarray*} \pm 1 \end{eqnarray*}$ als Reste in Frage. Nun ist $\begin{eqnarray*} 3^{\frac{p-1}{2}}\equiv \left(\frac{3}{p}\right)\bmod p \end{eqnarray*}$ (Legendre-Symbol), d.h. wir bekommen 1 genau dann, wenn 3 quadratischer Rest modulo $\begin{eqnarray*} p \end{eqnarray*}$ ist. Laut Quadratischem Reziprozitätsgesetz bekommen wir nun

$\begin{eqnarray*} \left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)\cdot (-1)^{\frac{3-1}{2}\cdot \frac{p-1}{2}} = \left(\frac{p}{3}\right)\cdot (-1)^{\frac{p-1}{2}} \end{eqnarray*}$ .

Gehen wir nun für $\begin{eqnarray*} p>3 \end{eqnarray*}$ die vier möglichen Fälle $\begin{eqnarray*} p\bmod 12 \end{eqnarray*}$ durch, bekommen wir als Werte für $\begin{eqnarray*} \left(\frac{3}{p}\right) \end{eqnarray*}$ :

$\begin{eqnarray*} p\equiv 1\bmod 12:\quad 1\cdot 1 = 1 \end{eqnarray*}$
$\begin{eqnarray*} p\equiv -1\bmod 12:\quad (-1)\cdot (-1) = 1 \end{eqnarray*}$
$\begin{eqnarray*} p\equiv 5\bmod 12:\quad (-1)\cdot 1 = -1 \end{eqnarray*}$
$\begin{eqnarray*} p\equiv -5\bmod 12:\quad 1\cdot (-1) = -1 \end{eqnarray*}$

"Quadratisches Reziprozitätsgesetz" ist wohl definitiv kein Schulstoff. Augenzwinkern

09.02.2024, 09:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
[quote]Aufgabe 74
[..]
$\begin{align*} \text{(2)} \ \ f' \left( - \frac{1}{4} \right) = - \frac{1}{4} \end{align*}$

Sicher, dass du dich da nicht verschrieben hast?

$\begin{eqnarray*} f'\left( - \frac{1}{2} \right) = - \frac{1}{4} \end{eqnarray*}$ würde mir mehr einleuchten, aber vielleicht habe ich ja was übersehen. verwirrt

EDIT: So ist es, hatte einen Fall übersehen ... ziehe damit meine Frage zurück. Augenzwinkern

Hammerhart, die Aufgabe. Bin beeindruckt, dass es immerhin 1,8% geschafft haben - möchte nicht wissen, wieviel es bei uns gewesen wären.

09.02.2024, 09:53

Leopold

Auf diesen Beitrag antworten »

Bist du auch für 483?

09.02.2024, 09:56

HAL 9000

Auf diesen Beitrag antworten »

So ist es, mit Funktion $\begin{eqnarray*} f\left(x\right) = \left(x+\frac{5}{8}\right)x\left(x-1\right) = x^3 - \frac{3}{8}x^2 - \frac{5}{8}x \end{eqnarray*}$ .

Stellt sich die Frage, ob die Korrektoren mit der bloßen Antwort f(8)=483 bzw. evtl. auch noch mit der Angabe der Funktionsgleichung zufrieden waren - oder ob sie eine logisch wasserdichte Erklärung haben wollten, dass dies auch wirklich die einzige Lösung ist, die (1)(2)(3) genügt. Das wäre schon eine Menge Schreibarbeit...

--------------------------------------------------------------------------------

Mein Anfang wäre so, dass ich erstmal ausgiebig über die Konsequenzen von (1) nachdenke:

Für genügend kleine reelle $\begin{eqnarray*} x \end{eqnarray*}$ (auch die ganzzahligen) ist stets $\begin{eqnarray*} f(x)<0 \end{eqnarray*}$ , analog $\begin{eqnarray*} f(x)>0 \end{eqnarray*}$ für genügend große $\begin{eqnarray*} x \end{eqnarray*}$ .

Es gibt demnach eine größte ganze Zahl $\begin{eqnarray*} u \end{eqnarray*}$ mit $\begin{eqnarray*} f(k)<0 \end{eqnarray*}$ für alle ganzen $\begin{eqnarray*} k<u \end{eqnarray*}$ sowie eine kleinste ganze Zahl $\begin{eqnarray*} v \end{eqnarray*}$ mit $\begin{eqnarray*} f(k)>0 \end{eqnarray*}$ für alle ganzen $\begin{eqnarray*} k>v \end{eqnarray*}$ , offenkundig gilt $\begin{eqnarray*} u-1<v+1 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} u\leq v+1 \end{eqnarray*}$ .

Laut dieser Definition ist $\begin{eqnarray*} f(u)\geq 0 \end{eqnarray*}$ , wegen (1) dann aber $\begin{eqnarray*} f(u)=0 \end{eqnarray*}$ , analog folgt $\begin{eqnarray*} f(v)=0 \end{eqnarray*}$ .

$\begin{eqnarray*} u=v+1 \end{eqnarray*}$ ist nicht möglich, denn $\begin{eqnarray*} f(v+1)=f(u)=0 \end{eqnarray*}$ widerspricht $\begin{eqnarray*} f(v+1)>0 \end{eqnarray*}$ , es ist daher $\begin{eqnarray*} u\leq v \end{eqnarray*}$ .

$\begin{eqnarray*} u=v \end{eqnarray*}$ widerspricht wegen $\begin{eqnarray*} f(u-1)\cdot f(u+1) < 0 \end{eqnarray*}$ Voraussetzung (1) , es ist damit $\begin{eqnarray*} u\leq v-1 \end{eqnarray*}$ .

Es gibt noch genau eine weitere reelle Nullstelle $\begin{eqnarray*} w \end{eqnarray*}$ von $\begin{eqnarray*} f \end{eqnarray*}$ , wobei (noch) nicht ausgeschlossen ist, dass diese mit $\begin{eqnarray*} u \end{eqnarray*}$ oder $\begin{eqnarray*} v \end{eqnarray*}$ zusammenfällt.

Hier fängt dann die Kleinarbeit an hinsichtlich der Betrachtung von $\begin{eqnarray*} w \end{eqnarray*}$ . Da kommen dann auch (2) und (3) ins Spiel.

« vorherige Seite 123456789 nächste Seite »

Neue Frage »

Antworten »

Diskussionen zum Übergangsmarathon - Seite 8

Verwandte Themen