# Problem 106
Let $[n] = \{1,\dots, n\}$ and let $I$ and $J$ be disjoint subsets of $[n]$ of the same size. We say that $(I,J)$ is _not worth checking_ if there is a bijection $\phi \colon I \to J$ with $\forall i\in I: \phi(i) > i$.

$A= \{a_1,\ldots,a_n\}$
$B = \{a_{i_1},\ldots,a_{i_m}\}$; $I=\{i_1,\ldots,i_m\}$ with $i_1 < i_2 < \ldots < i_m$.
$C = \{a_{j_1},\ldots,a_{j_m}\}$; $J=\{j_1,\ldots,j_m\}$ with $j_1 < j_2 < \ldots < j_m$.
$\phi(i_k) = j_k$ (Beispiel-$\phi$)

$(B,C)$ is not worth checking if there is a proof for $S(B)\ne S(C)$ which relies only on $I$ and $J$.

Claim 1: $(B,C)$ is not worth checking iff there is a bijection $\phi \colon I \to J$ with $\forall i\in I: \phi(i) > i$.

Claim 2: There is a bijection $\phi \colon I \to J$ with $\forall i\in I: \phi(i) > i$ iff $\forall k \in [m]\colon i_k < j_k$

# Problem 778

Feststellung:

$$
\sum_{x_1,x_2,x_3} x_1 \boxtimes x_2 \boxtimes x_3 = \sum_{z,x_3} (z \boxtimes x_3) \cdot \sharp\{x_1, x_2\mid x_1 \boxtimes x_2 = z\}
$$
Idee: Es sei
$$
f_x(M,R) := \sharp\{ (x_1,\ldots,x_R) \in M^R ~:~ x_1\boxtimes\cdots \boxtimes x_R = x\}.
$$
Dann gilt $F(M,R) = \sum_{x = 1}^M x \cdot f_x(M,R)$.

$$\forall 1\le x\le M: f_x(M,1) = 1$$
und
$$
f_x(I,R_1 + R_2) = \sum_{a\mathop\boxtimes b\mathop=x} f_a(I,R_1) \cdot f_b(I,R_2)
$$

$$f_x(I_1 \mathrel{\dot\cup} I_2,R_1 + R_2) = \sum_{a\mathop\boxtimes b\mathop=x} f_a(I_1 \mathrel{\dot\cup} I_2,R_1) \cdot f_b(I_1 \mathrel{\dot\cup} I_2,R_2)
%\sum_{(x, m) \in f(R_1, M)} \sum_{(y, n) \in f(R_2, M)} x \boxtimes y \cdot m \cdot n $$

$$f(I, R)$$

$$f(I_1 \mathrel{\dot\cup} I_2, R)$$
$$f(I, R_1 + R_2)$$

$M = 765432$

$Q_1 = (0-6)?????$
$Q_2 = 7(0-5)????$
$Q_3 = 76(0-4)???$
$Q_4 = 765(0-3)??$
$Q_5 = 7654(0-2)?$

$$f_x(I_1,\ldots,I_R) = \sharp\{ (x_1,\ldots,x_R) : x_1\boxtimes\cdots\boxtimes x_R=x \mathrel\land \forall i\colon~x_i\in I_i\}
$$
(too damn high)

**Ab hier löschen:**

$$\exists \tilde{h} \in o(\log(n)) \colon \,-\log\rho(n) \leq \left(\frac{\alpha + \beta}{2} - \sqrt{\alpha\beta}\right) \log(n) + \tilde{h}(n)$$

Es sei $c = \frac{\alpha + \beta}{2} - \sqrt{\alpha\beta}$ und es gelte $c<1$. Nach Lemma 4 gilt
$$
-\log\rho(n) \leq c \log(n) + o(\log(n)).
$$
Also gibt es ein $N_1 \in \mathbb N$ so, dass für alle $n \geq N_1$ gilt:
$$
-\log\rho(n) < c \log(n) + \frac{1-c}{2} \cdot \log(n).
$$
Weiterhin ist $\log(\gamma(n)\log(10)) \in o(\log(n))$. Also gibt es ein $N_2 \in \mathbb N$ so, dass für alle $n \geq N_2$ gilt:
$$
\log(\gamma(n)\log(10)) < \frac{1-c}{2} \cdot \log(n).
$$
Dann gilt für alle $n \geq \max(N_1, N_2)$:
\begin{align*}
-\log\rho(n) &< c \log(n) + \frac{1-c}{2} \cdot \log(n) \\
&= \log(n) - \frac{1-c}{2} \cdot \log(n) \\
&< \log(n) - \log(\gamma(n)\log(10)).
\end{align*}

# Problem 436
Es sei $Y_0, Y_1, \ldots,$ eine Folge von i.i.d. Zufallsvariablen mit $Y_i \sim U[0,1]$ (Gleichverteilung auf $[0,1]$).

Für $s \in [0,1)$ sei $k_s$ der minimale Index $k$, für den $\sum_{i=0}^k Y_i > 1 - s$ (das ist für jedes $s$ eine diskrete Zufallsvariable)

Es sei $X_s = Y_{k_s}$ der Wert, der $1-s$ überschreitet. Mit all dieser Notation ist der Wert, mit dem Louise das Spiel beendet gerade $X_0$.

Für ein $t < s$ ist es egal, ob im ersten Zug $Y_0 = t$ gezogen wird und danach bis $1-s$ gespielt wird, oder direkt nur bis $1-s-t$ gespiel wird. Deshalb gilt:
$$
\Pr(X_s \leq x \mid Y_0 = t) = \Pr(X_{s+t} \leq x)
$$

Achtung: Das ist super ungenau und da $\Pr(Y_0 = t) = 0$ gilt, ist völlig unklar, warum man darauf bedingen kann. Da müsste man einen W'theoretiker fragen.

Wir wollen jetzt die Verteilungsfunktion von $X_s$ bestimmen. Dafür zerlegen wir den W'raum zuerst in die Events $k_s = 0$ und $k_s \geq 1$.

\begin{align*}
\Pr(X_s \leq x) &= \Pr(Y_{k_s} \leq x) \\
&= \Pr(Y_{k_s} \leq x \wedge k_s = 0) + \Pr(Y_{k_s} \leq x \wedge k_s \geq 1)
\end{align*}
Da $k_s = 0$ genau dann gilt, wenn $Y_0 > 1-s$, ist
$$
\Pr(Y_{k_s} \leq x \wedge k_s = 0) = \Pr(1 - s < Y_0 \leq x) = \max(0, s + x - 1)
$$
Für die andere Seite komme ich auf
$$
\Pr(Y_{k_s} \leq x \wedge k_s \geq 1) = \int_{t = 0}^{1-s} \Pr(X_{s+t} \leq x)
$$
Vermutlich kommt man damit insgesamt auf eine Differentialgleichung, aber damit kenne ich mich nicht gut genug aus.

# Problem 774

Ansatz 1: Inclusion-Exclusion

Beispiel: n = 4
a&b + b&c + c&d - a&b,b&c - a&b,c&d - b&c,c&d + a&b,b&c,c&d
2 2 2 3 2,2 3 4

|**|*|*|-> (2,1,1) * 3 -> + 3 * z(2)^k * z(1)^k * z(1)^k
|**|**| -> (2,2)   * 1 -> - 1 * z(2)^k * z(2)^k
|***|*| -> (3,1)   * 2 -> - 2 * z(3)^k * z(1)^k
|****|  -> (4)     * 1 -> + 1 * z(4)^k

Problem: Summe über alle Partitionen -> wächst viel zu schnell

Ansatz 2:
$$
A_{i,j} = \begin{cases} 1 & i \& j \neq 0 \\ 0 & \text{sonst}
\end{cases}
$$

$A^n_{i,j}$ ist die Anzahl der conjunctive sequences der Länge $n+1$, welche mit $i$ beginnen und mit $j$ enden. Beweis per Induktion nach $n$.

Jede Permutation $\pi$ auf den bits der Zahlen induziert einen Graphenisomorphismus auf dem Graphen, dessen Adjazenzmatrix $A$ ist. Anstatt die Matrixeinträge zu multiplizieren, hoffen wir, die Äquivalenzklassen der zugehörigen Kanten unter allen solchen Permutationen betrachten zu können. Leider hat die Zahl $b=123456789$ ein sehr unregelmäßiges bitmuster und es gibt scheinbar wenige Permutationen, welche $\pi(k) \le b$ für $k\le b$ garantieren.

# Problem 757
A stealthy number is a natural number $n$, such that there are natural numbers $a,b,c,d$ with $n = ab = cd$ and $a+b = c+d+1$. The goal is to count the stealthy numbers up to $N = 10^{14}$.

Since $a + b = c + d + 1 \iff a = c + d + 1 - b$, we find
\begin{align*}
& &ab &= cd \\
\iff& &b(c+d+1-b) &= cd\\
\iff& &bc + bd + b - b^2 &= cd\\
\iff& &b &= cd - bc - bd + b^2 \\
\iff& &b &= (c - b)(d - b)
\end{align*}

Setting $x = c - b$ and $y = d-b$, we find that any solution has the form
\begin{align*}
b &= xy \\
c &= x + b = x + xy = x(y+1) \\
d &= d = y + b = y+xy = (x+1)y \\
a &= c + d + 1 - b = xy + x + y +1 = (x+1)(y+1) \\
N &= ab = x(x+1)y(y+1)
\end{align*}
and that every pair $(x,y)$ yields a solution.
Hence, it suffices to count the numbers of the form $x(x+1)y(y+1)$ less than $N$.
# Problem 759
Per Induktion können wir zeigen, dass
$$
f(n) = n \cdot p(n),
$$
wobei $p(n)$ die Anzahl an Einsen in der Binärdarstellung von $n$ ist.

Zu berechnen ist
\begin{align*}
S(N) = \sum_{n=1}^N f(n)^2 = \sum_{n=1}^N n^2\cdot p(n)^2 = \sum_{\ell=1}^{\lfloor \log_2(N) \rfloor} \ell^2 \cdot \sum_{\substack{n=1\\p(n)=\ell}}^N n^2
\end{align*}

Es sei $k = \lfloor \log_2(N) \rfloor$ und $[k] = \{0, 1, \ldots, k-1\}$
# Problem 752

$$
(1 + \sqrt{7})(\alpha(n-1) + \beta(n-1)\sqrt{7}) = (1 + \sqrt{7})(1 + \sqrt{7})^{n-1} = (1 + \sqrt{7})^n = \alpha(n) + \beta(n)\sqrt{7}
$$
Daraus folgt die Rekursionsgleichung
$$
\alpha(n) = \alpha(n-1) + 7\beta(n-1)
$$
und
$$
\beta(n) = \alpha(n-1) + \beta(n-1),
$$
Daher:
$$
\begin{pmatrix}\alpha(n) \\ \beta(n) \end{pmatrix} =
\begin{pmatrix}1&7\\1&1\end{pmatrix}\cdot
\begin{pmatrix}\alpha(n-1) \\ \beta(n-1) \end{pmatrix}
= \begin{pmatrix}1&7\\1&1\end{pmatrix}^n\cdot \begin{pmatrix}1\\1\end{pmatrix}
= S D^n S^{-1}\cdot \begin{pmatrix}1\\1\end{pmatrix}
$$
Explizite Formel::
$$
\alpha(n) = \frac{1}{2}\left((1-\sqrt{7})^n + (1+\sqrt{7})^n\right)
$$
und
$$
\beta(n) = \frac{1}{2\sqrt{7}}\left(-(1-\sqrt{7})^n + (1+\sqrt{7})^n\right)
$$
Mal anders
\begin{align*}
\alpha(n) &= \sum_{k=0}^{\left\lfloor\frac{n}2\right\rfloor} \binom{n}{2k}7^k \\
\beta(n) &= \sum_{k=0}^{\left\lfloor\frac{n}2\right\rfloor} \binom{n}{2k+1}7^k
\end{align*}

# Problem 739 -> unsolved
$$
a(i,k) = \begin{cases}
0, &\text{if } i < k\\
a(i-1,k) + a(i,k-1), &\text{if } 1 < k \le i \\
L(i), &\text{if } k=1
\end{cases}
$$

Sei $\alpha := \frac{1+\sqrt5}2$ und $\beta := \frac{1-\sqrt5}2$, dann gilt für die Lucas-Folge $(L(1),L(2),\ldots)$:
$$
L_0(k) := L(k) = \alpha^k + \beta^k
$$
weil wegen Eigenwerte. Dann ist im nächsten Schritt
$$
L_j(k) := \sum_{j < i \le k} L_{j-1}(i)
$$
wir wollen $L_n(n)$. Dann mal
$$
\begin{align*}
L_1(k) &= \sum_{1 < i \le k} (\alpha^k + \beta^k)
\\ &= \sum_{1 < i \le k} \alpha^i + \sum_{1 < i \le k} \beta^i
\\ &= \alpha^2 \cdot \frac{\alpha^{k-1}-1}{\alpha - 1} + \beta^2 \cdot \frac{\beta^{k-1}-1}{\beta - 1}
\\ &= \frac1{\alpha-1}\cdot\alpha^{k+1} - \frac{\alpha^2}{\alpha-1}\cdot 1
+ \frac1{\beta-1}\cdot\beta^{k+1} - \frac{\beta^2}{\beta-1}\cdot1
\end{align*}
$$
err
$$
L(k, t) = \sum_{1 < i \le k} \alpha^{i + t}
= \alpha^{2 + t} \cdot \frac{\alpha^{k-1}-1}{\alpha - 1}
$$

# Problem 375
Für einen Index $k$ sei $C_k$ die Anzahl der Paare $i,j$ mit $A(i,j) = S_k$. Dann gilt:
$$
M(N) = \sum_{i,j} A_{i,j} = \sum_k S_k \cdot \lvert\{i,j\mid A_{i,j} = S_k\}\rvert = \sum_k S_k \cdot C_k
$$

Ansatz: Bestimme für jedes $k$ das maximale Intervall $I_k$, in dem $S_k$ das Minimum ist.

Beispielfolge: $S=(4,7,2,3,5,1,6)$

Intervalle:
$S_0 = 4: I_0=[0,1], L_0=[0,0], R_0=[0,1]$
$S_1 = 7: I_1=[1,1], L_1=[1,1], R_1=[1,1]$
$S_2 = 2: I_2=[0,4], L_2=[0,2], R_2=[2,4]$
$S_3 = 3: I_3=[3,4]$
$S_4 = 5: I_4=[4,4]$
$S_5 = 1: I_5=[0,6]$
$S_6 = 6: I_6=[6,6]$

$C_i = \#L_i\cdot \#R_i$
$X_i = C_i \cdot S_i$

Algorithmisch: Sortiere (Wert, Index)-Paare aufsteigend nach Wert. Füge diese Paare sukzessive in eine nach Index sortierte Liste ein. Bestimme nach dem Einfügen jedes Elements seinen Vorgänger und Nachfolger in der Liste und berechne daraus $I_k$.
- Schritt 1: $[A_5=1]$
- Schritt 2: $[A_2=2, A_5=1]$
- Rechts vom eingefügten Element: $5-1 = 4$
- Links vom eingefügten Element: Nix gleich $0$
- Damit ist $I_2 = [0,4]$
- Schritt 3: $[A_2=2, A_3=3, A_5=1]$
- Links: $2+1=3$
- Rechts: $5-1=4$
- Damit ist $I_3=[3,4]$
- $\ldots$

Anstelle der sortierten Liste wollen wir einen nach Index balancierten Suchbaum, in dem das Einfügen und die Suche nach Vorgänger/Nachfolger in $O(\log n)$ gehen.

In der eigentlichen Aufgabe kommen fast alle Werte mehrfach vor, dafür ist $S$ aber periodisch.

Schlimmeres Beispiel: $4,(7,2,3,5,1,6),(7,2,3,5,1,6),(7,2,3,5,1,6),7,2,3$

Statt dessen trennen wir das Mittelstück am globalen Minimum:
Weniger schlimmeres Beispiel: $(4,7,2,3,5),(1,6,7,2,3,5),(1,6,7,2,3,5),(1,6,7,2,3)$

Ansatz:
- Berechne die $C_i$ und $X_i$ für Anfangs-, Mittel-, und Endstück.
- Multipliziere das Ergebnis für das Mittelstück mit der Anzahl seiner Wiederholungen
- Rechne alles zusammen
- Am Ende bleibt eine Anzahl $K$ von Indexpaaren $(i,j)$ übrig, die keinen Wert zugewiesen bekommen haben; diese entsprechen Intervallen, welche ein Mittelstück überspannen und damit als Minimum das globale haben. Also draufrechnen und profit.

# Problem 743

$$B(k, r) := A(k, rk)$$

Zu bestimmen ist: $B(10^8, 10^8)$. Wir bezeichnen mit $a$ die Anzahl Nullen/Zweien.

$$B(k, r) = \sum_{a = 0}^{\lfloor\frac{k}{2}\rfloor}\left(\frac{k!}{a!\cdot a! \cdot (k-2a)!}\right)2^{r(k-2a)}$$

$$B(k, r) = \sum_{a = 0}^{\lfloor\frac{k}{2}\rfloor} c_a(k,r)$$

wobei

\begin{align*}
c_a(k,r)
&= \left(\frac{k!}{a!\cdot a! \cdot (k-2a)!}\right)2^{rk-2ar}
\\&= \frac{(k-2a+1)(k-2a+2)}{2^{2r}a^2} \left(\frac{k!}{(a-1)!\cdot (a-1)! \cdot (k-2a+2)!}\right)2^{rk-2ar+2r}
\\&= \frac{(k-2a+1)(k-2a+2)}{2^{2r}a^2} c_{a-1}(k,r)
\end{align*}

mit $c_0 = 2^{rk}$
# Chris Rocks
Es sei $p(t)$ die Anzahl der Pfade von +100 bzw. -100 zu 0, die $t$ Schritte von der 0 (und 100 + $t$ Schritte zur 0) laufen und zuvor 0 nicht erreichen.
Weiterhin sei
$$
k(t) = \left(\frac{2}{3}\right)^{t}\left(\frac{1}{3}\right)^{t + 100}
$$
und
$$
f(t) = \left(\frac{1}{3}\right)^{t}\left(\frac{2}{3}\right)^{t + 100}
$$
Dann ist die Wahrscheinlichkeit, dass die Kröte nach genau $100 + 2t$ Schritten zum ersten Mal bei der 0 ankommt genau $p(t)k(t)$ und für den Frosch entsprechend $p(t)f(t)$.

Dann ist
\begin{align*}
&P(\text{K vor F}\mid\text{beide kommen an, zu verschiedenen Zeiten} ) \\
&= \frac{\sum_{t_1<t_2}p(t_1)p(t_2)k(t_1)f(t_2)}{\sum_{t_1\neq t_2}p(t_1)p(t_2)k(t_1)f(t_2)} \\
&= \frac{\sum_{t_1<t_2}p(t_1)p(t_2)k(t_1)f(t_2)}{\sum_{t_1 < t_2}p(t_1)p(t_2)\big(k(t_1)f(t_2) + k(t_2)f(t_1)\big)}.
\end{align*}
Es gilt:
$$
k(t_1)f(t_2) = \left(\frac{2}{3}\right)^{t_1}\left(\frac{1}{3}\right)^{t_1 + 100}\left(\frac{1}{3}\right)^{t_2}\left(\frac{2}{3}\right)^{t_2 + 100} = \frac{2^{t_1 + t_2 + 100}}{3^{2t_1 + 2t_2 + 200}} = k(t_2)f(t_1).
$$
Also ist
\begin{align*}
&\frac{\sum_{t_1<t_2}p(t_1)p(t_2)k(t_1)f(t_2)}{\sum_{t_1 < t_2}p(t_1)p(t_2)\big(k(t_1)f(t_2) + k(t_2)f(t_1)\big)} \\
&= \frac{\sum_{t_1<t_2}p(t_1)p(t_2)k(t_1)f(t_2)}{2 \sum_{t_1 < t_2}p(t_1)p(t_2)k(t_1)f(t_2)} = \frac{1}{2}.
\end{align*}
# Lobster Town

Sei $\ell$ die Länge des Lobsters (die eindeutig bestimmte Anzahl Knoten in einem längsten Pfad im Lobster). Sei $n$ die Anzahl Knoten des Lobsters. Sei $p(n)$ die Anzahl der Partitionen von $n\in\Bbb{N}$. Ein ZL ist ein Zusammenhängender Lobster. Dann gilt:

* Für $\ell=1$ gibt es genau einen ZL, genau dann wenn $n=1$.
* Für $\ell=2$ gibt es genau einen ZL, genau dann wenn $n=2$.
* Für $\ell=3$ gibt es genau einen ZL für jedes $n\ge3$, nämlich den Stern mit $n$ Knoten.
* Für $\ell=4$ gibt es $\lfloor\frac{n-2}{2}\rfloor$ ZL für jedes $n\ge 4$.
* Für $\ell=5$ gibt es $p(n) - n$ ZLs (für $n\ge5$)
* Für $\ell\ge6$ gibt es
\begin{align*}
\frac{1}{2}\left(
\sum_{n_1, \dots, n_{\ell-4}~\ge~0,\\ n_1 + \ldots + n_{\ell - 4} = n}(p(n_1) - 1)\cdot p(n_2)\cdot\ldots\cdot p(n_{\ell - 5})\cdot(p(n_{\ell - 4})-1) + \operatorname{symm}(n,l)\right)
\end{align*}
wobei $\operatorname{symm}(n,\ell)$ die Anzahl der spiegelsymmetrischen ZLs bezeichnet.
Für $\ell = 2k$ und $n$ gerade ist
$$
\operatorname{symm}(n,\ell) = \sum_{m_1, \ldots m_{k-2} ~\ge~0,\\
2m_1+ \ldots+ 2m_{k-2} = n} (p(m_1)-1) \cdot p(m_2) \cdot \ldots \cdot p(m_{k-2})
$$
Für $\ell$ gerade und $n$ ungerade ist die Anzahl 0.
Für $\ell = 2k + 1$ ist
$$
\operatorname{symm}(n,\ell) = \sum_{m_1, \ldots m_{k-1} ~\ge~0,\\
2m_1+ \ldots+ 2m_{k-2} + m_{k-1} = n} (p(m_1)-1) \cdot p(m_2) \cdot \ldots \cdot p(m_{k-1})
$$
Algorithmisch: definiere $\operatorname{PZ}(s, n)$ als
$$
\operatorname{PZ}(s, n) = \sum_{n_1, \dots, n_s~\ge~0,\\ n_1 + \ldots + n_s = n} p(n_1) \cdot \ldots p(n_s) = \sum_{n_1, m~\ge~0 \\ n_1 + m = n} p(n_1) \cdot \operatorname{PZ}(s - 1, m)
$$
Dann ist
\begin{align*}
&\sum_{n_1, \dots, n_{\ell-4}~\ge~0,\\ n_1 + \ldots + n_{\ell - 4} = n}(p(n_1) - 1)\cdot p(n_2)\cdot\ldots\cdot p(n_{\ell - 5})\cdot(p(n_{\ell - 4})-1) \\
&= \operatorname{PZ}(\ell-4, n) - 2\sum_{k=0}^n\operatorname{PZ} (\ell-5, k) +\sum_{k=0}^n (n-k+1) \operatorname{PZ}(\ell-6, k)
\end{align*}
Noch offen:
* $\operatorname{symm}(n,\ell)$ durch $\operatorname{PZ}(s,k)$ berechnen
* Von zusammenhängenden Lobsters auf Lobster-Wälder kommen ("Riddells Formula"?)

# Problem 745
Es sei $F(N,k)$ die Anzahl der Zahlen von $1$ bis $N$ mit $g(n) = k^2$. Insbesondere ist $F(N,1)$ die Anzahl der quadratfreien Zahlen $\leq N$.

Dann ist
$$
F(N,k) = F(\lfloor\frac{N}{k^2}\rfloor,1)
$$
und
$$
F(N,1) = N - \sum_{k=2}^{\lfloor \sqrt{N}\rfloor} F(N,k) = N - \sum_{k=2}^{\lfloor \sqrt{N}\rfloor} F(\lfloor\frac{N}{k^2}\rfloor,1)
$$
Außerdem gilt
$$
S(N) = \sum_{n=1}^N g(n) = \sum_{k=1}^{\lfloor \sqrt{N}\rfloor} k^2 \cdot F(N,k) = \sum_{k=1}^{\lfloor \sqrt{N}\rfloor} k^2 \cdot F(\lfloor\frac{N}{k^2}\rfloor,1)
$$
Zur Vereinfachung ist $f(n) = F(n,1)$. Dann gilt:
* $f(1)=1$
* $f(n) = f(n-1) + \delta_{g(n)=1}$
* $f(n) = n - \sum_{k=2}^{\lfloor \sqrt{n}\rfloor} f(\lfloor\frac{n}{k^2}\rfloor)$