Home › Archief › Internationale Olympiades › EGMO › 2018 › trivial a, harder b

trivial a, harder b

Tags:

Opgave - EGMO 2018 dag 1 vraag 2

Beschouw de verzameling \[A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.\]

    a)
    Bewijs dat elk geheel getal $x \ge 2$ geschreven kan worden als het product van één of meer (niet noodzakelijk verschillende) elementen van $A$.

    b)
    Voor elk geheel getal $x \ge 2$, definiëren we $f(x)$ als het kleinste gehele getal zodat $x$ geschreven kan worden als het product van $f(x)$ (niet noodzakelijk verschillende) elementen van $A$. Bewijs dat er oneindig veel paren $(x,y)$ van gehele getallen bestaan met $x \ge 2, y \ge $2 en $f(xy) < f(x)+f(y).$
    (Paren $(x_1,y_1)$ en $(x_2,y_2)$ zijn verschillend dan en slechts dan als $x_1 \neq x_2$ of $y_1 \neq y_2$)

Oplossing

Ingediend door Luka

a)

Merk op dat voor $k=i-1,$ $1+\frac 1k =\frac{i}{i-1}.$

Per inductie ziet men eenvoudig in dat

\[x = \prod_{i=2}^{x}\frac{i}{i-1}.\]

b)
Lemma 1:$f(xy) \le f(x) + f(y)$
Dit is waar, want je kan $xy$ schrijven als $x \cdot y$ en je kan $x$ vormen met $f(x)$ factoren (elementen uit $A$) en $y$ met $f(y)$ factoren, dus heb je hoogstens $f(x)+ f(y)$ factoren nodig om $xy$ te vormen.

Ten tweede is $f(2^n) = n$ want je neemt $n$ factors van $2$, wat $f$ maximaliseert aangezien $2$ de grootste factor mogelijk is. Hierdoor is $f(2^n+1) =n+1$, want je neemt $n$ factors van $2$ en $1$ factor van $\frac{2^n+1}{2^n}$.

Nu is $f(65) = 7$ en is $f(5) = 3$ en $f(13) = 5$, waardoor we $f(65) < f(5) + f(13)$ hebben. Er bestaat al $1$ paar waarvoor $f(xy) < f(x) + f(y)$.

De volgende oplossing is afkomstig van Tijs.
Stel dat er eindig zo'n getallen waren. Dit betekent dat voor alle paren $(a,b)$ waarvoor $f(ab) < f(a) + f(b)$ niet geldt, we hebben dat $f(ab) = f(a) + f(b)$ wegens Lemma $1$.
Neem vervolgens een maximale $x+y$ waarvoor $f(xy) < f(x) + f(y)$ (dit bestaat want er zijn maar een eindig aantal oplossingen), Kies nu een $k > \max\{x, y\}$ waardoor we

\[f(kxy) = f(k) + f(xy) < f(k) + f(x) + f(y) = f(kx) + f(y)\]

tegenspraak. Aangezien het paar $(5,13)$ voldoet, voldoen er een oneindig aantal paren dus.

Mijn oplossing voor b:
Neem $m = 2^n + 1$ met $n \equiv 2 \pmod 4$ voor $m,n \in \mathbb{Z}_{>0}$. Hierdoor is $5|m$, aangezien $ord_{5}(2) = 4$.

Hierdoor hebben we $f(m) \le f(5) + f(\frac{m}{5})$.

nu is $f(m) = n+1$ en $f(5) = 3$. We bewijzen dat $f(\frac{m}{5}) > n-2$

Stel uit het ongerijmde dat $f(\frac{m}{5}) \le n-2$.

Ten eerste hebben we dat als $2^a < x$, dat $f(2^a) < f(x)$, want $f(2^a)$ wordt 'geoptimaliseerd', i.e. het is het grootste getal dat met $a$ factoren kan gevormd worden uit $A$.
Hierdoor hebben we dat
\[f(\frac{m}{5}) = f(\frac{2^n+1}{5}) > f(\frac{2^n}{8}) = n-3\]

We hebben dus $f(\frac{m}{5}) = n-2$

Als er minder dan $n-3$ factoren van $2$ nodig zijn om $\frac{m}{5}$ te vormen, is het al verloren, want:

\[\frac{m}{5} \le 2^{n-4} \cdot \frac{a+1}{a} \cdot \frac{b+1}{b} \le 2^{n-4} \cdot \frac{3}{2} \cdot \frac{3}{2} < \frac{2^n+1}{5} = \frac{m}{5}\]

Als $f(\frac{m}{5})$ exact $n-2$ factoren van $2$ bevat, zou $2^{n-2} = \frac{2^n+1}{5}$, tegenspraak.

Bijgevolg zou $\frac{2^n+1}{5}$ gevormd moeten worden uit $n-3$ factoren van $2$, aangevuld met een ander element uit $A$, dus

\[\frac{2^n+1}{5} = 2^{n-3} \cdot \frac{a+1}{a} \iff a = \frac{5 \cdot 2^{n-3}}{2^n+1-5 \cdot 2^{n-3}} \ge 2\]

Noem $2^n+1 = b$ en $5 \cdot 2^{n-3} = c$.
Nu is \[b = 2^n+1 > 2^n = 16 \cdot \frac{2^{n-3}}{2} > 15 \cdot \frac{2^{n-3}}{2} = \frac{3}{2} \cdot 5 \cdot 2^{n-3} = \frac{3}{2} c\]

Maar we hebben ook dat
\[a = \frac{c}{b-c} \ge 2 \iff \frac{3}{2} c \ge b\]

tegenspraak.

Bijgevolg is $f(\frac{m}{5}) > n-2$ en is \[f(m) = n+1 < 3 + (n-2) < f(5) + f(\frac{m}{5})\]