writeup.tex

%! Author = baulu
%! Date = 06.03.2022

% Preamble
\documentclass[11pt]{article}

\usepackage[german]{babel}

% Packages
\usepackage{amsmath}
\usepackage[left=5cm,right=2cm,vmargin=2.5cm,footnotesep=0.5cm]{geometry}
\usepackage{amssymb}
\usepackage{fancyhdr}
\usepackage{tcolorbox}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{gensymb}

\pagestyle{fancy}

% Document
\begin{document}

    \setlength{\parindent}{0pt}

    \setlength{\headheight}{14pt}

    \rhead{Lukas Bilstein}
    \lhead{}

    \section*{Bundeswettbewerb Mathematik 2022 Runde 1}

    \subsection*{Aufgabe 1}

    Sei $k_n$ die Anzahl an Nüssen am n-ten Tag.

    Wir wissen das $k_0$, die Anzahl ohne zusätzliche Nüsse, gleich 2022 ist.

    Wir wissen weiterhin, dass $k_1 - k_0 = 2$, $k_2 - k_1 = 4$, $k_3 - k_2 = 6$, \ldots ist.

    Damit können wir folgende Formel aufstellen:

    \[
        k_n = k_{n-1} + 2n = 2022 + \varSigma^{n}_{i=1} (2i) = 2022 + 2 * \varSigma^{n}_{i=1} i
    \]

    Mithilfe der Summenformel ergibt dies:

    \[
        = 2022 + 2 * \frac{n(n+1)}{2} = 2022 + n(n+1)
    \]

    Damit wir die Nüsse gleichmäßig auf die 5 aufteilen könne, muss $k_n \equiv 0 (\text{ mod } 5)$ sein.

    Also muss gelten:

    \[
        2022 + n(n+1) \equiv 0 (\text{ mod } 5) \Leftrightarrow n(n+1) \equiv 3 (\text{ mod } 5)
    \]

    Wir unterscheiden nun 5 Fälle für n, nach modulo 5, und untersuchen $n(n+1)$:

    \bigskip

    \begin{tabular}{c c c}
        $n \text{ mod } 5$ & $(n+1) \text{ mod } 5$ & (n(n+1)) \text{ mod } 5 \\
        0 & 1 & 0 \\
        1 & 2 & 2 \\
        2 & 3 & $6 \equiv 1$ \\
        3 & 4 & $12 \equiv 2$ \\
        4 & 0 & 0 \\
    \end{tabular}

    Dabei fällt auf, dass es keinen Fall gibt, in dem $n(n+1) \equiv 3 (\text{ mod } 5)$ ist, wie es für die
    Aufteilung auf 5 notwendig wäre.

    Damit kann es niemals einen Tag n geben, an dem die Nüsse gleichmäßig auf alle 5 Eichhörnchen aufgeteilt werden
    können.

    $\blacksquare$

    \newpage

    \subsection*{Aufgabe 2}

    Sei n die Anzahl an Mitteldreiecken + 1, also die Anzahl an eingezeichneten Dreiecken inklusive dem Ursprünglichen.

    \bigskip

    Wir stellen zunächst fest, dass die Verbindung der Seitenmitten eines gleichseitigen Dreiecks
    wieder ein gleichseitiges Dreieck hervorbringt,
    da das Dreieck symmetrisch aufgebaut sein muss, nämlich genau die symmetrieachsen des äußeren gleichseitiges
    Dreiecks.
    Das einzige Dreieck, was dies erfüllt, ist wieder das gleichseitige Dreieck.

    Weiterhin liegen die Mitten der Seiten des inneren Dreiecks wieder auf den Verbindungen des äußeren Dreiecks
    mit den gegenüberliegenden Eckpunkten.

    \bigskip

    Seien $A_1$, $B_1$ und $C_1$ die Eckpunkte des äußersten Dreiecks, und $M$ der Mittelpunkt des Dreiecks
    (An dieser Stelle sei angemerkt, dass im gleichseitigen Dreieck Inkreis-, Umkreis- und Mittenschnittpunkt
    zusammen fallen;
    somit ist es egal, welchen dieser wir an dieser Stelle betrachten)

    Wir bezeichnen nun die Mitten jeweils mit $A_2$ (die Mitte von $[B_1C_1]$), $B_2$ (die Mitte von $[A_1C_1]$)
    und $C_2$ (die Mitte von $[A_1B_1]$)

    Die Mitten der Seiten $[A_2B_2]$, $[A_2C_2]$ und $B_2C_2$ bezeichnen wir analog mit $C_3$, $B_3$ und $A_3$.

    Dies setzen wir so lange fort, bis wir $A_n$, $B_n$ und $C_n$ eingezeichnet haben.

    \bigskip

    Wir können nun diese Anordnung von Dreiecken als Graphen $G_n$ ansehen.
    Dafür wollen wir zunächst eine Verbindungsvorschrift erstellen, die angibt, welche Knoten
    miteinander Verbunden sind.

    Mit folgenden Punkten ist jeder Knoten $X_i$ bis auf den Mittelpunkt verbunden, sofern diese
    Existieren:

    \begin{itemize}
        \item Allen anderen $Y_i$, da sie bereits ein Dreieck bilden
        \item Allen anderen $X_n$ und $M$, da diese alle auf einer Geraden liegen (die Verbindungsgerade einer Mitte und des gegenüberliegenden Eckpunktes)
        \item Allen $Y_{i+1}$, da diese die Mitten der Angrezenden Seiten sind
        \item Allen $Y_{i-1}$, da $X_i$ die Mitte einer Seite ist auf Ebene i-1, und damit mit diesen Verbunden ist (der X_{i-1} Punkt durch die Mitte-Ecke Verbidnung)
    \end{itemize}

    \bigskip

    Ein Dreieck in diesem Graphen zeichnet sich nun dadurch aus, dass
    wir drei Eckpunkte suchen, die verbunden sind, und nicht auf einer Geraden liegen.

    Drei Punkte liegen in unserem Graphen auf einer Geraden, wenn:

    \begin{itemize}
        \item Sie alle vom selben 'Typ' sind (z.B. alle vom Type $A_n$), und optional dem Mittelpunkt
        \item Sie der Form $X_i$, $Y_i$, $Z_{i-1}$ sind, also zwei Eckpunkte und dessen Mittelpunkt
    \end{itemize}

    \newpage

    Wir wollen dieses Problem nun mithilfe eines Computerprogramms lösen.
    Ich verwende in der finalen Implementierung python, da es keine Limitationen in vielen Bereichen hat.
    (Dabei ist vor allem die unbgrenzte Größe von Mengen und ganzzahlen wichtig)

    Wir beginnen aber zunächst aber mit einigen Definitionen.

    Wir nennen die Funktion, die entscheidet, ob zwei Knoten verbunden sind, 'connected', und die Funktion,
    ob drei Punkte auf einer Geraden liegen, 'on\_one\_line'.

    Wir können uns eine Menge $M_n$ aller Eckpunkte erzeugen, sie enhält alle $A_i$, $B_i$ und $C_i$
    mit $0 < i \le n$ und M.

    Wir können weiterhin eine Menge $G_n$ erzeugen, die alle Verbindungen als $\{X_n, Y_n\}$ darstellt, erzeugen.
    Diese Menge ist:
    \[\{\{x, y\} \vert x \in M_n \land y \in M_n \land connected(x, y)\}\]

    Aus dieser Menge können wir nun die Menge aller Dreiecke $D_n$ heraus konstruieren, auf folgende Weise
    (wobei x, y und z die Eckpunkte der Dreiecke sind):
    \[D_n = \{\{x, y, z\} \vert \{x, y\} \in G_n \land \{x, z\} \in G_n \land \{y, z\} \in G_n \land on\_one\_line(x, y, z)\}\]

    Damit haben wir alle Bausteine für ein Program, was uns die Gesamtanzahl an anzeichenbarer Dreiecke angibt.
    Die Anzahl ist einfach der Betrag von $D_n$.

    Folgender Pseudo-Code implementiert dies:

    \begin{tcolorbox}

        Funktion connected(X, Y)

        \{

            Falls (X[0] == Y[0]) $\rightarrow$ Wahr

            Falls (X[0] == `M` oder Y[0] == `M`) $\rightarrow$ Wahr

            Falls (Betrag(x[1] - Y[1]) $\le 1$) $\rightarrow$ Wahr

            Sonst $\rightarrow$ Falsch

        \}

        \bigskip

        Funktion on\_one\_line(X, Y, Z)

        \{

            Falls (Betrag($\{X[0], Y[0], Z[0]\} - \{'M'\}$) == 1) $\rightarrow$ Wahr

            s = [X[1], Y[1], Z[1]]

            s.sort()

            Falls (s[0] == s[1] == s[2] - 1) $\rightarrow$ Wahr

            Sonst $\rightarrow$ Falsch

        \}

        \bigskip

        n = Eingabe(`n: `)

        $K_n = \{A_i | i \in \mathbb{N} \land i \le n\} + \{B_i | i \in \mathbb{N} \land i \le n\} + \{C_i | i \in \mathbb{N} \land i \le n\} + \{`M`\}$

        $G_n = \{\{x, y\} | x \in K_n \land y \in K_n \land connected(x, y)\}$

        $D_n = \{\{x, y, z\} \vert \{x, y\} \in G_n \land \{x, z\} \in G_n \land \{y, z\} \in G_n \land on\_one\_line(x, y, z)\}$

        Ausgabe(Betrag($D_n$))

    \end{tcolorbox}

    \newpage

    Wir wollen nun diesen Code in python umsetzen (zu finden ab dem 09.03.2022 unter https://github.com/uuk0/BuMa2022/blob/main/runde\%201/Aufgabe2\_final.py)

    \lstset{language=Python}
    \lstset{frame=lines}
    \lstset{caption={Python code}}
    \lstset{label={lst:code_direct}}
    \lstset{basicstyle=\footnotesize}
    \begin{lstlisting}
    import itertools

    n = int(input("N:"))

    G = set()
    D = set()


    def connected(a, b):
        if ((a[0] == "M") or (b[0] == "M")):
            return True

        if (abs(a[1] - b[1]) <= 1):
            return True

        return False

    def on_one_line(a, b, c):
        if len({a[0], b[0], c[0]} - {"M"}) == 1:
            return True

        x, y, z = sorted((a[1], b[1], c[1]))
        if (x == y == z - 1):
            return True

        return False


    vertices = {("M", 0)}

    for i in range(1, n + 1):
        for c in ("A", "B", "C"):
            vertices.add((c, i))

    for a, b in itertools.combinations(vertices, 2):
        if connected(a, b):
            G.add((min(a, b, key=lambda e: e[1]), max(a, b, key=lambda e: e[1])))

    for a, b, c in itertools.combinations(vertices, 3):
        if on_one_line(a, b, c):
            continue

        a, b, c = sorted((a, b, c), key=lambda e: e[1])
        D.add((a, b, c))

    print(len(D))
    \end{lstlisting}

    \newpage

    Führt man obiges Program für verschiedene Werte für n aus, ergeben sich folgende Werte:

    \begin{tabular}{c c}
        n & $|D_n|$ \\
        1 & 4 \\
        2 & 23 \\
        3 & 90 \\
        \ldots & \ldots \\
        8 & 1985 \\
        9 & 2844 \\
        10 & 3919 \\
        \ldots & \ldots \\
    \end{tabular}

    \bigskip

    Somit sind die gesuchten Werte $n=9$ mit 2844 einzeichen-baren Dreiecken und insgesamt 8 Mitteldreiecke

    \newpage

    \subsection*{Aufgabe 3}

    Skizze: (für eine farbige Version siehe https://github.com/uuk0/BuMa2022/, Skizze 2)

    \includegraphics{"Aufgabe3_Skizze2_grayscale.jpg"}

    Um zu beweisen, dass die Gerade den Winkel in der Mitte teilt, wollen wir beweisen, dass die beiden Teilwinkel
    gleich groß sind.

    Wir bennen den $\angle QmP'$ mit $\alpha$.
    Dementsprechend ist der $\angle PmQ = 180 \degree - \alpha$.

    O.b.d.A. können wir $0 \degree < \alpha < 180 \degree$ setzen aufgrund der Achsensymmetrie zur Horizontalen.
    Sollte $\alpha > 180\degree$ sein, spiegeln wir die Skizze an der PP'' Achse und erhalten ein $\alpha < 180 \degree$

    Wir bezeichnen $\angle APQ$ mit $\beta_1$ und $\angle BPB$ mit $\beta_2$.
    Ziel wird es sein, zu beweisen, dass diese gleich groß sind.

    Wir halten fest, dass, wie schon in der Skizze angedeutet, $\angle PQP' = \angle PBP'' = 90 \degree$ ist (nach dem
    Satz des Thales).

    Das $\triangle PQm$ ist gleichschenklig, da es zwei Punkte auf einem Kreis und den Kreismittelpunkt als Eckpunkte besitzt.
    Damit ist $\angle QPm = \angle PQm = \frac{180 \degree - \angle PmQ}{2} = \frac{180\degree - 180 \degree + \alpha}{2} = \frac{\alpha}{2}$.

    Analoges gilt im $\triangle mQP'$, sodass $\angle mQP' = \angle QP'm = 90 \degree - \frac{\alpha}{2}$.

    Wir wollen nun $\angle PAB$ mit $\delta$ bezeichnen.
    Nach den Winkelregeln am Kreis ist $\angle BP''P = 180 \degree - \delta$
    (Vgl. z.B. https://learnattack.de/schuelerlexikon/mathematik/winkel-am-kreis, vorletzter Eintrag, wobei
    die Strecke $PB$ als Sehne dient, und wir die Punkte $A$ und $P''$ betrachten).

    \newpage

    Im Dreieck $\triangle PBP''$ gilt:
    \[180 \degree - \delta + 90 \degree + \angle P''PB = 180 \degree \Leftrightarrow \angle P''PB = \delta - 90 \degree\]

    An P gilt weiterhin:
    \[\frac{\alpha}{2} = \beta_2 + \angle P''PB = \beta_2 + \delta - 90 \degree \Leftrightarrow \beta_2 = 90 \degree - \delta + \frac{\alpha}{2}\]


    Im $\triangle APQ$ gilt:
    \[\delta + \beta_1 + 90 \degree - \frac{\alpha}{2} = 180 \degree \Leftrightarrow \beta_1 = 90 \degree - \delta + \frac{\alpha}{2}\]

    Nun fällt auf, dass der Winkel $\angle PP''B$ nur dann $= 180 \degree \delta$ ist,
    wenn B oberhalb der PP'' Achse liegt. Sollte B unterhalb liegen, wird der Winkel gleich $\delta$ selbst,
    aber $\beta_2$ ist jetzt nicht mehr $=\frac{\alpha}{2} - \angle BPP''}$, sondern
    $= \frac{\alpha}{2} + \angle BPP'' = \frac{\alpha}{2} + 90 \degree - \delta$, da nun $\angle BPP'' = 90 \degree - \delta$ direkt ist.

    Für $\beta_1$ ändert sich in diesem Fall nichts.

    \bigskip

    Damit ist bewiesen, dass in jedem Fall $\beta_1 = \beta_2$ und damit das die Gerade $PQ$ den Winkel $\angle APB$ in der Mitte teilt.

    $\blacksquare$

    \newpage





    \subsection*{Aufgabe 4}

    Wir stellen zunächst fest, dass der größte Teiler einer Zahl immer sie selbst ist.

    Das heist, sofern die Zahl selbst nicht durch drei Teilbar ist, ist $a_k = k$.

    Wir definieren nun $\phi(k) = \begin{cases}k & \text{wenn } k\text{ mod }3 \not \equiv 0 \\\phi(\frac{k}{3}) & \text{sonst}\end{cases}$

    Dabei stellt $\phi(k)$ gleichzeitig $a_k$ dar.

    \bigskip

    Wir stellen weiterhin fest, das jede dritte Zahl durch drei Teilbar ist, jede neunte durch neun,
    jede 27 durch 27, und so weiter.

    \bigskip

    Eine Eigenschaft der Zahlen im Dreiersystem ist, das sie alle 3 einen `roll-over` haben an der
    1-er stelle, alle $3^2$ an der $3^2$ Stelle, alle $3^3$ an der $3^3$ Stelle usw.

    Damit steht an der 1-er Stelle alle 3 eine 1, an der 3-er Stelle alle $3^2$, an der $3^2$ Stelle
    alle $3^3$, usw.

    \bigskip

    Weiterhin stellen wir fest, dass eine Summe von natürlichen Zahlen genau dann durch 3 teilbar ist,
    wenn $\Sigma(a_n\text{ mod }3) \equiv 0 (\text{mod }5)$

    Wir wissen, dass alle $a_n$'s der Form $a_{3i+1}$ genau 1 in dieser Summe mitbringt,
    und alle der Form $a_{3i+2}$ genau 2 beträgt.
    Damit kommt es auf auf die der Form $a_{3i}$ an.

    Analog trägt diese 1 bei in der Form $a_{9+1}$, und 2 in der Form $a_{9i+2}$.

    Wir können also nie ein $a_n \equiv 0 (\text{mod }3)$ finden.

    Damit gibt es 4 Fälle, in denen das neue $a_n$ die Summe $\equiv 0 (\text{mod }3)$ macht:

    \begin{tabular}{c c c c c}
        zuvor & 1 & 1 & 2 & 2 \\
        $a_n \text{ mod } 3$ & 1 & 2 & 1 & 2 \\
        danach & 2 & $3 \equiv 0$ & $3 \equiv 0$ & $4 \equiv 1$
    \end{tabular}

    \bigskip

    Sollte die Summe zuvor $\equiv 0 (\text{mod } 3)$ sein, übernimmt sie hier das modulo des neuen Terms.

    Damit gibt es genau zwei Fälle, in dem ein $s_n$ durch drei Teilbar ist, nämlich wenn
    genau dann, wenn entweder $s_{n-1} \equiv 1 (\text{mod } 3)$ ist und $a_n \equiv 2$ oder umgekehrt.

    In allen anderen Fällen entsteht eine nicht durch 3 teilbare Zahl.

    % Diese folge von unterschieden wird in der OEIS unter https://oeis.org/A060236 geführt.

    \bigskip

    Für die Anzahl an 1-er in der Dreierdarstellung einer Zahl:

    Multiplikation mit 3 $\Rightarrow$ nichts ändert sich, da eine 0 dazu kommt

    Multiplikation mit 3 mit angeschlossen + 1 $\Rightarrow$ 1x 1 mehr, da eine neue 1

    Multiplikation mit 3 mit angeschlossen + 2 $\Rightarrow$ nicht änder sich, da eine 2 dazu kommt.




\end{document}