System von Oder-Kongruenzen

28.02.2023, 19:45

Malcang

System von Oder-Kongruenzen

Hallo zusammen,

ich hoffe es ist ok, wenn ich einen neuen Thread starte. Vorarbeit wurde hier jede Menge geleistet, danke nochmal an HAL 9000.
Meine jetzige Frage baut darauf auf.
Zuerstmal tue ich mir sehr schwer, die korrekte Formulierung zu finden. Deshalb würde ich das einmal beschreiben wollen, was ich habe.
Ich habe einen Algorithmus, der mir eine Problemlösung für bestimmte Kongruenzen gibt. Beispielsweise sagt er mir nach ein zwei Durchläufen, dass er die Lösung für diejenigen $\begin{eqnarray*} k \end{eqnarray*}$ bestimmen kann, für die $\begin{eqnarray*} k\equiv 1\pmod 2 \end{eqnarray*}$ oder $\begin{eqnarray*} k\equiv 2\pmod 3 \end{eqnarray*}$ . Nun weiß ich also, dass ich mit dem bisherigen Stand $\begin{eqnarray*} \frac{2}{3} \end{eqnarray*}$ aller Fälle bearbeiten kann, nämlich $\begin{eqnarray*} k\mod 6\in\{1,2,3,5\} \end{eqnarray*}$ .
Im nächsten Durchlauf bekomme ich wieder eine Kongruenz dazu, welche ich vorher noch nicht hatte. Wenn es jetzt $\begin{eqnarray*} k\equiv 0\mod 2 \end{eqnarray*}$ wäre, hätte ich alles abgedeckt. Wenn es das aber nicht ist, sondern beispielsweise $\begin{eqnarray*} k\equiv 10 \pmod{12} \end{eqnarray*}$ , dann ist der Anteil auf $\begin{eqnarray*} \frac{9}{12} = \frac{3}{4} \end{eqnarray*}$ gestiegen.

Jetzt will ich darauf hinaus, dass dieser Anteil immer höher wird, da ja mit jedem Durchlauf eine noch nicht betrachtete Kongruenz dazukommt.
Der Satz der dabei am Ende rauskommen soll ist dann der:

Zitat:

Sei $\begin{eqnarray*} \epsilon>0 \end{eqnarray*}$ . Dann existiert eine natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ , sodass der Anteil der von Algorithmus (1) abgedeckten Fälle nach $\begin{eqnarray*} n \end{eqnarray*}$ -maligem Durchlauf mindestens $\begin{eqnarray*} 1-\epsilon \end{eqnarray*}$ beträgt.

Ich hänge gerade daran, den Beweis korrekt zu formulieren. Ich weiß zwar was dort passiert, aber ich bekomme das >>System von Oder-Kongruenzen<< nicht richtig formuliert.

Kann mir jemand einen Schubs geben?

Vielen Dank smile

Neue Frage »

Antworten »

System von Oder-Kongruenzen

Verwandte Themen