Home › Archief › Nationale en Regionale Olympiades › Canada › CanMO › 1976 › macht van 2

macht van 2

Tags:

Opgave - CanMO 1976 vraag 5

Bewijs dat een natuurlijk getal de som is van minimum twee opeenvolgende getallen als en slechts als dat getal geen macht van 2 is.

Oplossing

Ingediend door Manu

Voor natuurlijke getallen $m, n$ met $m\le n$ is de som $N$ van de $(n-m+1)$ opeenvolgende natuurlijke getallen vanaf $m$:

$N = m + (m+1)+\ldots+(n-1)+n = \frac{1}{2} (m+n) (n-m+1)$

$N$ is een macht van $2 $
$\Leftrightarrow \exists a,b \in \mathbb{N} \colon m+n = 2^a \wedge n-m+1 = 2^b$
$ \Leftrightarrow \exists a,b \in \mathbb{N} \colon 2n+1 = 2^a+2^b \wedge 2m-1 = 2^a-2^b (*)$
$ \Leftrightarrow \exists a \in \mathbb{N} \colon 2n+1 = 2^a+2^0 \wedge 2m-1 = 2^a-2^0$
$ \Leftrightarrow m=n$

(*) $\colon 2n+1 = 2^a+2^b$ kan immers alleen maar voor $(a,b) = (0,b)$ of $(a,0)$ of $(\frac{1}{2},\frac{1}{2})$. Maar opdat ook $2m-1 = 2^a-2^b$ blijft alleen over $(a,b) = (a,0)$.

Voor andere getallen is het wel mogelijk:
Stel $n=p2^k$ waarbij $p$ oneven is.
Neem het grootste getal en stel dat gelijk aan $m+n$ en het kleinere gelijk aan $n-m+1$
omdat $m+n-(n-m-1)=2m+1$ oneven is, is het duidelijk dat $m$ natuurlijk is, aangezien $|p-2^k|$ ook oneven is en dan is snel te zien dat $n$ dat ook is.