Submitted by jonas on
De winnaar van de breinbreker van maart-april is Mathias Jolie. Als prijs ontvangt mathias een jaarabonnement op het tijdschrift Pythagoras en op het tijdschrijft Wiskunde & Onderwijs. Proficiat en veel leesplezier!
We kregen ook nog een juiste inzending van Yannick Neyt. Bedankt voor de inzending en veel succes met de breinbeker van mei-juni.
Oplossing
We zoeken een permutatie $\{a_1,\cdots,a_{2^n}\}$ van $\{1, 2,\cdots,2^n\}$ met de eigenschap dat als $a_i<a_k<a_j$ dan $k\neq \frac{i+j}{2}$. We bewijzen via inductie dat zo'n permutatie bestaat. Het geval $n=1$ is triviaal: elke permutatie voldoet.
Stel nu dat $\{x_1,\cdots,x_{2^{n-1}}\}$ een oplossing is voor het geval $n-1$. We stellen dan $y_i=2^n+1-x_i$ (dus $y_i>x_i\: \forall i$) en definiëren $a_i$ als $$\begin{cases} x_i \quad\text{als } i \text{ als oneven} \\ y_i \quad\text{als } i \text{ als even}. \end{cases}$$ We tonen nu aan dat $\{a_1,\cdots,a_{2^n}\}$ een goede permutatie is. Veronderstel dus dat $a_i<a_k<a_j$. We moeten aantonen dat $k$ niet het midden van $i$ en $j$ is.
- Als $i$ even en $j$ oneven is of omgekeerd, dan bestaat er geen midden van $i$ en $j$.
-
Zowel $i$ en $j$ zijn oneven: stel $i=2i'-1$ en $j=2j'-1$, dus $a_i=x_{i'}$ en $a_j=x_{j'}$. Noem $m=(i+j)/2$.
- $m=2m'-1$: dan is wegens inductie $x_{m'}<x_{i'}$ of $x_{m'}>x_{j'}$, dus $a_k\neq a_m$ en dus $k\neq m$
- $m=2m'$: dan is bij constructie $y_{m'}>x_{i'}$ en $y_{m'}>x_{j'}$, dus $k\neq m$
-
Zowel $i$ en $j$ zijn even: stel $i=2i'$ en $j=2j'$, dus $a_i=y_{i'}$ en $a_j=y_{j'}$. Noem $m=(i+j)/2$.
- $m=2m'-1$: dan is bij constructie $x_{m'}<y_{i'}$ en $x_{m'}<y_{j'}$, dus $k\neq m$
-
$m=2m'$: uit $y_{i'}<y_{m'}<y_{j'}$ volgt wegens constructie $x_{i'}>x_{m'}>x_{j'}$, strijdig met inductiehypothese