DS HA1 beautified

\section{Ameisenkolonie} \hfill \textbf{9 Punkte}

Sei $2000000 \leq n \leq 3000000$ die Anzahl der Ameisen in der Kolonie mit

n n n n n \equiv 3 (mod 19) \equiv 1 (mod 20) \equiv 2 (mod 21) \equiv 1 (mod 22) \equiv 0 (mod 23) ⟹ n ⟹ n ⟹ n ⟹ n ⟹ n \in [3]_{\equiv 19} \in [1]_{\equiv 20} \in [2]_{\equiv 21} \in [1]_{\equiv 22} \in [0]_{\equiv 23}

Sei $A = [3]_{\equiv 19} \cap [1]_{\equiv 20} \cap [2]_{\equiv 21} \cap [1]_{\equiv 22} \cap [0]_{\equiv 23}$ .

Laut Definition, teilt der Divisor $m$ die Differenz zweier Zahlen derselben Äquivalenzklasse $[x]_{\equiv m}$ . Die Elemente von $A$ sind in $5$ Äquivalenzklassen enthalten. Somit teilen jeweils die Divisoren \numlist{19;20;21;22;23} die Differenz zweier Zahlen aus $A$ ; die kleinstmögliche solche Zahl ist das kleinste gemeinsame Vielfache von \numlist{19;20;21;22;23}: $kgV (19, 20, 21, 22, 23) = kgV (19, 2^{2} \cdot 5, 3 \cdot 7, 2 \cdot 11, 23) = 19 \cdot 2^{2} \cdot 5 \cdot 3 \cdot 7 \cdot 11 \cdot 23 = 2018940 = M$ Also teilt $M$ die Differenz zweier Zahlen aus $A$ . Das nächst kleinere und nächst größere Element von $A$ sind: $n_{0} - kgV (19, 20, 21, 22, 23) = 2582141 - 2018940 = 563201 < 2000000$ und \ $n_{0} + kgV (19, 20, 21, 22, 23) = 2582141 + 2018940 = 4601081 > 3000000$ .

Somit hat $A$ im Bereich $2000000 \leq n \leq 3000000$ nur ein Element.

Somit sind genau $2582141$ Ameisen in der Kolonie und keine andere Anzahl ist möglich.

n \equiv 1 (mod 22) ⟹ \exists k \in Z ∣ n = 22 k + 1 ⟹ \exists k \in Z ∣ n = 11 \cdot \in Z 2 k + 1 ⟹ n \equiv 1 (mod 11)

Das System $m_{1} = 11$ , $m_{2} = 19$ , $m_{3} = 20$ , $m_{4} = 21$ , $m_{5} = 23$ ist paarweise relativ prim, da paarweise kein gemeinsamer Primfaktor existiert $11$ , $19$ , $2^{2} \cdot 5$ , $3 \cdot 7$ und $23$ . Laut chinesischem Restsatz kann jede natürliche Zahl $< 19 \cdot 20 \cdot 21 \cdot 11 \cdot 23 = M = 2018940$ eindeutig durch ihre Reste modulo \numlist{19; 20; 21; 11; 23} dargestellt werden.

n n n n n n \equiv a_{i} (mod m_{i}) \equiv 1 (mod 11) \equiv 3 (mod 19) \equiv 1 (mod 20) \equiv 2 (mod 21) \equiv 0 (mod 23) ⎭ ⎬ ⎫ M = 11 \cdot 19 \cdot 20 \cdot 21 \cdot 23 = 2018940 M_{i} M_{1} M_{2} M_{3} M_{4} M_{5} =^{M} /_{m_{i}} =^{2} ╱_{73} = 19 \cdot 20 \cdot 21 \cdot 23 = 183540 =^{1} ╱_{2} = 11 \cdot 20 \cdot 21 \cdot 23 = 106260 =^{1} ╱_{2} = 11 \cdot 19 \cdot 21 \cdot 23 = 100947 = \frac{M}{21} = 11 \cdot 19 \cdot 20 \cdot 23 = 96140 = \frac{M}{23} = 11 \cdot 19 \cdot 20 \cdot 21 = 87780

\frac{1 234 568}{2} \frac{1}{2} \frac{ab}{c d} \frac{1 + 2}{3}

M_{i} \cdot t_{i} M_{1} \cdot 9 M_{2} \cdot 8 M_{3} \cdot 3 M_{4} \cdot 11 M_{5} \cdot 2 \equiv 1 (mod m_{i}) \equiv 1 (mod 11) \equiv 1 (mod 19) \equiv 1 (mod 20) \equiv 1 (mod 21) \equiv 1 (mod 23)

\begin{multline*} \implies \text{Lösung: } n_{0} := \sum_{i = 1}^{5} a_{i} \cdot M_{i} \cdot t_{i} = 1 \cdot 183\,540 \cdot 9 + 3 \cdot 106\,260 \cdot 8 + 1 \cdot 100\,947 \cdot 3 \\ + 2 \cdot 96\,140 \cdot 11 + 0 \cdot 87\,780 \cdot 2 = 6\,620\,021 \end{multline*}

$n_{0} mod M = 6620021 mod 2018940 = 563201$ ist die kleinste positive Lösung des obigen Systems.

Wir suchen eine weitere eine Lösung $n_{2}$ für das obige System im Bereich $2000000 \leq n_{2} \leq 3000000$ :

n_{2} = n_{1} + M = 563201 + 2018940 = 2582141 2000000 \leq 2582141 \leq 3000000 25821412582141 \equiv 3 (mod 19) \equiv 1 (mod 20) 25821412582141 \equiv 2 (mod 21) \equiv 1 (mod 22) 2582141 \equiv 0 (mod 23)

Somit ist $n_{2} = 2582141$ eine mögliche Anzahl von Ameisen ist der Kolonie.

Laut Definition, teilt der Divisor $m_{i}$ die Differenz zweier Zahlen derselben Äquivalenzklasse $[x]_{\equiv m}$ . Die Elemente von $A$ sind in $5$ Äquivalenzklassen enthalten. Somit teilen die Divisoren \numlist{19;20;21;22;23} die Differenz zweier Zahlen aus $A$ ; die kleinstmögliche solche Zahl ist das kleinste gemeinsame Vielfache von \numlist{19;20;21;22;23}. $kgV (19, 20, 21, 22, 23) = kgV (19, 2^{2} \cdot 5, 3 \cdot 7, 2 \cdot 11, 23) = 19 \cdot 2^{2} \cdot 5 \cdot 3 \cdot 7 \cdot 11 \cdot 23 = 2018940$

Also teilt $2018940$ die Differenz zweier Zahlen aus $A$ .

Wir bestimmen einen möglichen Wert $n_{0} \in A$ für $2000000 \leq n_{0} \leq 3000000$ . Die in Algorithmus \ref{alg:Ameisenkolonie} aufgelistete Berechnung hilft uns, einen geeigneten Kandidaten zu finden, für die mathematische Beweisführung ist er jedoch nicht notwendig.

Wir behaupten $n_{0} = 2582141 \in A$ , wobei $2000000 \leq 2582141 \leq 3000000$ gilt.

25821412582141 \equiv 3 (mod 19), \equiv 1 (mod 20), 25821412582141 \equiv 2 (mod 21), \equiv 1 (mod 22) 2582141 \equiv 0 (mod 23)

$\Rightarrow n_{0} \in [3]_{\equiv 19} \cap [1]_{\equiv 20} \cap [2]_{\equiv 21} \cap [1]_{\equiv 22} \cap [0]_{\equiv 23} \Rightarrow n_{0} \in A$

Da $2018940$ die Differenz zweier Zahlen aus $A$ teilt, sind das nächst kleinere und nächst größere Element von $A$ : \ $n_{0} - kgV (19, 20, 21, 22, 23) = 2582141 - 2018940 = 563201 < 2000000$ und \ $n_{0} + kgV (19, 20, 21, 22, 23) = 2582141 + 2018940 = 4601081 > 3000000$ .

Somit hat $A$ im Bereich $2000000 \leq n \leq 3000000$ nur ein Element.

Somit sind genau $2582141$ Ameisen in der Kolonie und keine andere Anzahl ist möglich.

\begin{algorithm} \KwResult{2582141 ist der kleinste mögliche Wert für $n$ } \For{ $n = 2000000$ \textbf{to} $3000000$ }{ \If{ $n mod 19 = 3$ \textbf{and} $n mod 20 = 1$ \textbf{and} $n mod 21 = 2$ \textbf{and} $n mod 22 = 1$ \textbf{and} $n mod 23 = 0$ }{ \Return $n$ } } \caption{Ein Algorithmus der einen Wert im Bereich $2000000 \leq n \leq 3000000$ findet, der in den Äquivalenzklassen $[3]_{\equiv 19}$ , $[1]_{\equiv 20}$ , $[2]_{\equiv 21}$ , $[1]_{\equiv 22}$ und $[0]_{\equiv 23}$ enthalten ist.} \label{alg:Ameisenkolonie} \end{algorithm}

Wir zeigen, dass das linke Konvergenzsystem genau dann gilt, wenn das rechte Konvergenzsystem gilt:

Zu Zeigen: n n n n n \equiv 3 (mod 19) \land \equiv 1 (mod 20) \land \equiv 2 (mod 21) \land \equiv 1 (mod 22) \land \equiv 0 (mod 23) ⟺ n n n n n \equiv 1 (mod 11) \land \equiv 3 (mod 19) \land \equiv 1 (mod 20) \land \equiv 2 (mod 21) \land \equiv 0 (mod 23)

Wir zeigen zunächst die rechte Richtung der Biimplikation. Wir nehmen die 5 Konvergenzen des linken Systems an und zeigen die 5 Konvergenzen des rechten Systems:

Annahmen: (A 1) : n \equiv 3 (mod 19) (A 2) : n \equiv 1 (mod 20) (A 3) : n \equiv 2 (mod 21) (A 4) : n \equiv 0 (mod 23) (A 5) : n \equiv 1 (mod 22) Zu Zeigen: (Z 1.1) : n \equiv 3 (mod 19) (Z 2.1) : n \equiv 1 (mod 20) (Z 3.1) : n \equiv 2 (mod 21) (Z 4.1) : n \equiv 0 (mod 23) (Z 5.1) : n \equiv 1 (mod 11)

Offensichtlich folgen aus $(A 1)$ , $(A 2)$ , $(A 3)$ und $(A 4)$ die gleichen Konvergenzen $(Z 1.1)$ , $(Z 2.1)$ , $(Z 3.1)$ und $(Z 4.1)$ . Aus $(A 5)$ folgen wir nun $(Z 5.1)$ :

\begin{multline*} n \equiv 1 \pmod{22} \implies \exists\, k \in \mathbb{Z} \mid n = 22k + 1 \\ \implies \exists\, k \in \mathbb{Z} \mid n = 11 \cdot \underbrace{ 2k }_{\in\, \mathbb{Z} } + 1 \implies n \equiv 1 \pmod{11} \end{multline*}

Wir haben alle Teilziele gezeigt und somit auch die rechte Richtung der Biimplikation gezeigt.

Jetzt zeigen wir die linke Richtung der Implikation. Wir nehmen die 5 Konvergenzen des rechten Systems an und zeigen die 5 Konvergenzen des linken Systems:

Annahmen: (A 11) : n \equiv 3 (mod 19) (A 12) : n \equiv 1 (mod 20) (A 13) : n \equiv 2 (mod 21) (A 14) : n \equiv 0 (mod 23) (A 15) : n \equiv 1 (mod 11) Zu Zeigen: (Z 11.1) : n \equiv 3 (mod 19) (Z 12.1) : n \equiv 1 (mod 20) (Z 13.1) : n \equiv 2 (mod 21) (Z 14.1) : n \equiv 0 (mod 23) (Z 15.1) : n \equiv 1 (mod 22)

Offensichtlich folgen aus $(A 11)$ , $(A 12)$ , $(A 13)$ und $(A 14)$ die gleichen Konvergenzen $(Z 11.1)$ , $(Z 12.1)$ , $(Z 13.1)$ und $(Z 14.1)$ .

Aus $(A 12)$ folgt:

\begin{multline*} n \equiv 1 \pmod{20} \implies \exists\, l \in \mathbb{Z} \mid n = 20l + 1 \\ \implies \exists\, l \in \mathbb{Z} \mid n = 2 \cdot \underbrace{ 10l }_{\in\, \mathbb{Z}} + 1 \implies n \equiv 1 \pmod{2} \end{multline*}

Also folgt die Annahme: $(A 16) : n ist ungerade$

Wir zeigen mit Kontraposition, dass wenn $(Z 15.1)$ nicht erfüllt wäre, dies Annahmen widerspricht. Wir betrachten die Restklasse modulo $22$ in einer Fallunterscheidung:

Fall 1: $n mod 22 \in {0, 2, 3, 4, 5, 6, 7, 8, 9, 10}$ : Es folgt $n \neq \equiv 1 (mod 11)$ , was $(A 15)$ widerspricht.

Fall 2: $n mod 22 \in {11, 13, 14, 15, 16, 17, 18, 19, 20, 21}$ : Bezogen auf die Konvergenz modulo 11, sind diese Werte konvergent zu den Restklassen in Fall 1. Es folgt $n \neq \equiv 1 (mod 11)$ , was $(A 15)$ widerspricht.

Fall 3: $n mod 22 = 12$ :

\exists m \in Z ∣ n = 22 m + 12 ⟹ \exists m \in Z ∣ n = 2 \in Z (11 m + 6) ⟹ n \equiv 0 (mod 2)

Es folgt, $n$ ist gerade, was $(A 16)$ widerspricht.

Wir haben alle Teilziele gezeigt und somit die linke Richtung der Biimplikation gezeigt.

Also ist das rechte Konvergenzsystem äquivalent zum linken Konvergenzsystem. Es genügt also zu Zeigen, dass das linke Konvergenzsystem nur eine Lösung im Bereich $2000000 \leq n \leq 3000000$ hat.

Fall 1: $n$ ist gerade:

Aus $(A 12)$ folgt die Fallunterscheidung:

\begin{multline*} n \equiv 1 \pmod{20} \implies \exists\, l \in \mathbb{Z} \mid n = 20l + 1 \\ \implies \exists\, l \in \mathbb{Z} \mid n = 2 \cdot \underbrace{ 10l }_{\in\, \mathbb{Z}} + 1 \implies n \equiv 1 \pmod{2} \end{multline*}

Also ist $n$ Element der Äquivalenzklasse ungerader Zahlen $[1]_{\equiv 2}$ , wobei laut Definition $2$ die Differenz zweier ihrer Elemente teilt.

Laut $(A 15)$ ist $n$ auch Element der Äquivalenzklasse $[1]_{\equiv 11}$ , wobei $11$ die Differenz zweier ihrer Elemente teilt.

Somit ist $n$ Element der Schnittmenge $[1]_{\equiv 2} \cap [1]_{\equiv 11}$ , und die Zahlen $2$ und $11$ teilen die Differenz zweier Elemente dieser Schnittmenge. Da $2$ und $11$ teilerfremd sind, muss die Differenz auch durch $kgV (2, 11) = 22$ teilbar sein.

$n$ muss also ungerade sein. Aus $(A 15)$ folgt:

n \equiv 1 (mod 11) ⟹ \exists m \in Z ∣ n = 11 m + 1

n = 20 m + 1 = 11 l + 1

Wir zeigen $(Z 15.1)$ mit einer Fallunterscheidung:

$n \equiv 1 (mod 20)$ und $n \equiv 1 (mod 11)$ folgt $n \equiv (mod 22)$ .

Fall 1 $n \equiv 1 (mod 22)$ :

Aus $(A12)$ folgt $$ \exists\, l \in \mathbb{Z} \mid n = 20l + 1 \implies \exists\, l \in \mathbb{Z} \mid 2 \cdot \underbrace{ 10l }_{\in\, \mathbb{Z}} + 1 \implies n \equiv 1 \pmod{2}

Offensichtlich folgen aus den angenommenen Konvergenzen modulo $19$ , $20$ , $21$ und $23$ , die Konvergenzen selbst.

Sei $n \in [3]_{\equiv 19} \cap [1]_{\equiv 20} \cap [2]_{\equiv 21} \cap [1]_{\equiv 22} \cap [0]_{\equiv 23}$ .

Offensichtlich gilt:

n n n n \equiv 3 (mod 19) \land \equiv 1 (mod 20) \land \equiv 2 (mod 21) \land \equiv 0 (mod 23) ⟺ n n n n \equiv 3 (mod 19) \land \equiv 1 (mod 20) \land \equiv 2 (mod 21) \land \equiv 0 (mod 23)

Wir müssen also zeigen, dass $n \equiv 1 (mod 22) ⟺ n \equiv 1 (mod 11)$ gilt.

\begin{multline*} n \equiv 1 \pmod{22} \implies \exists\, k \in \mathbb{Z} \mid n = 22k + 1 \\ \implies \exists\, k \in \mathbb{Z} \mid n = 11 \cdot \underbrace{ 2k }_{\in\, \mathbb{Z} } + 1 \implies n \equiv 1 \pmod{11} \end{multline*}

n \equiv 1 (mod 11) ⟹ \exists k \in Z ∣ n = 11 k + 1 ⟹ \exists : - - -

Anton's Digital Garden

Explorer