Problem 1873

Solution:

Aus der Voraussetzung folgt, dass die kleinste der Zahlen $a_{1}, a_{2}, \ldots, a_{2022}$ mindestens $1$, die zweitkleinste mindestens $2$ ist, usw. bis zur $2022$-ten, die mindestens $2022$ sein muss. Wenn wir nun die Zahlen $a_{1}, \ldots, a_{2022}$ sukzessive der Größe nach durch $1,2, \ldots, 2022$ ersetzen, so wird die Summe aus dem Aufgabentext nicht größer. Wir sehen also, dass wir uns auf den Fall einschränken dürfen, dass $(a_{1}, a_{2}, \ldots, a_{2022})$ paarweise verschiedene positive ganze Zahlen sind. Nun ersetzen wir $2022$ durch eine beliebige positive ganze Zahl $k$ und behaupten, dass der kleinste Wert $s(k)$, den die Summe
$$\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{k}}{k}\right\rfloor$$
annehmen kann, wenn $a_{1}, a_{2}, \ldots, a_{k}$ paarweise verschiedene positive ganze Zahlen sind, genau $\left\lfloor\log_{2}(k)\right\rfloor$ beträgt.

- Untere Schranke: Da $m$ offenbar monoton steigend ist, genügt es zu zeigen, dass $m\left(2^{t}\right) \geq t$ gilt. Der Fall $t=0$ ist klar, für $t>0$ verwenden wir vollständige Induktion und setzen daher $m\left(2^{t-1}\right) \geq t-1$ als bekannt voraus. Es seien $a_{1}, a_{2}, \ldots, a_{2^{t}}$ beliebige paarweise verschiedene positive ganze Zahlen. Dann ist das Maximum $a_{i}$ dieser Zahlen mindestens $2^{t}$. Falls $i>2^{t-1}$, so gilt nun
$$\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t}}}{2^{t}}\right\rfloor \geq \left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t-1}}}{2^{t-1}}\right\rfloor+\left\lfloor\frac{a_{i}}{i}\right\rfloor \geq m\left(2^{t-1}\right)+1 = t-1+1 = t$$
Falls jedoch $i \leq 2^{t-1}$, so ist die Menge $X=\{1,2, \ldots, 2^{t-1}\} \setminus \{a_{1}, a_{2}, \ldots, a_{2^{t-1}}\}$ nicht leer. Sei $b \in X$ beliebig. Dann gilt $a_{i} \geq 2^{t} = 2^{t-1} + 2^{t-1} \geq b+i$, also gilt
$$\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t}}}{2^{t}}\right\rfloor \geq \left\lfloor\frac{a_{1}}{1}\right\rfloor+\cdots+\left\lfloor\frac{b+i}{i}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t-1}}}{2^{t-1}}\right\rfloor \geq m\left(2^{t-1}\right)+1 = t-1+1 = t$$

- Obere Schranke: Wir setzen
$$a_{i}=\begin{cases} i-1, & \text{falls } i \text{ keine Zweierpotenz ist,} \\ 2^{s+1}-1, & \text{falls } i=2^{s}. \end{cases}$$
Dann sind $a_{1}, a_{2}, \ldots, a_{k}$ paarweise verschiedene positive ganze Zahlen und es gilt
$$\left\lfloor\frac{a_{i}}{i}\right\rfloor=\begin{cases} 0, & \text{falls } i \text{ keine Zweierpotenz ist,} \\ 1 & \text{andernfalls.} \end{cases}$$
also folgt $\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{k}}{k}\right\rfloor=\left\lfloor\log_{2}(k)\right\rfloor$.

Angewandt auf die konkrete Situation der Aufgabenstellung erhalten wir, dass der kleinste Wert, den die angegebene Summe annehmen kann, gleich $\left\lfloor\log_{2}(2022)\right\rfloor=11$ ist.