schrijfwijze

Opgave - USAMO 1978 vraag 3

Je weet dat alle getallen van 33 tot en met 73 voorgesteld kunnen worden als som van natuurlijke getallen $a_1,a_2,...,a_k$ waarvoor $\frac1{a_1}+...+\frac1{a_k}=1$. Toon aan dat dan hetzelfde waar is voor alle natuurlijke getallen groter dan 73.

Oplossing

Stel dat $n$ een getal is dat voldoet, zodat $n=a_1+a_2+...+a_i$ en $\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_i}=1$.

Er geldt dat $$2n+2=2(a_1+a_2+...+a_i)+2=2a_1 +2a_2+..+2a_i+2$$ en $$\frac{1}{2a_1}+\frac{1}{2a_2}+...+\frac{1}{2a_i}+\frac{1}{2}=\frac{1}{2}\left(\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_i}\right)+\frac{1}{2}=\frac{1}{2}+\frac{1}{2}=1,$$ evenzo geldt dat
$$2n+9=2(a_1+a_2+...+a_i)+3+6=2a_1 +2a_2+..+2a_i+3+6$$ en
$$\frac{1}{2a_1}+\frac{1}{2a_2}+...+\frac{1}{2a_i}+\frac{1}{3}+\frac{1}{6}=\frac{1}{2}\left(\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_i}\right)+\frac{1}{3}+\frac{1}{6}=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1.$$

De getallen $2n+2$ en $2n+9$ kunnen dus ook voorgesteld worden als som van natuurlijke getallen $a_1,a_2,...a_k$ waarvoor $\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k}=1$.

We wisten dat $n\in\{33,34,...,73\}$ voldeed, per inductie geldt het ook voor de getallen $n'>73$:

  • als $n$ even is, kunnen we $n=2n'+2$ schrijven en weten we omdat $n'$ voldoet ook $n$ zal voldoen zoals reeds aangetoond (dit doen we voor $n'$ vanaf $36$ en zo voldoet het dus voor alle even getallen $>73$)
  • als $n$ oneven is, kunnen we $n$ schrijven als $2n'+9$, analoog door $n'$ vanaf $33$ in te vullen zien we dat het gevraagde ook zal gelden voor de oneven getallen $\ge75$.

Te beginnen met de getallen $74,75,76,...$ zien we nu dat het zal gelden voor alle volgende natuurlijke getallen, zodat het gevraagde bewezen is.