bitstrings
Opgave - VWO 1991 vraag 4
Een woord van lengte $n$ dat bestaat uit enen en nullen noemen we een bitstring van lengte $n$. (bv. 000 is een bitstring van lengte 3, 01101 is een bitstring van lengte 5)
Beschouw de rij $s(1),s(2),...$ van bitstrings van lengte $n>1$ (bv. $000$ is een bitstring van lengte 3, $01101$ is een bitstring van lengte 5) die als volgt geconstrueerd wordt:
- $s(1) = 00..001$,
- $s(k+1)$ wordt als volgt verkregen: verwijder het meest linkse cijfer van $s(k)$. Als dit getal met een $1$ erachter nog niet voorkomt, plaats dan die $1$ erachter, als dat wel al voorkomt, plaats er dan een $0$ achter in de plaats.
Bewijs dat de bitstrings $s(1),s(2),...,s(2^n)$ alle verschillend zijn.
Bijvoorbeeld:
$s(1) = 001 \rightarrow s(2) = 011 \rightarrow s(3) = 111 \rightarrow s(4) = 110 \rightarrow s(5) = 101$
$\rightarrow s(6) = 010 \rightarrow s(7) = 100 \rightarrow s(8) = 000 \rightarrow s(9) = 001 \rightarrow ...$
- login om te reageren
Oplossing
Voor $n=1$ hebben we $s(1)=1$ en $s(2)=0$ dus het klopt.
Laat $n>1$.
Veronderstel dat $s(p)$ en $s(q)$ gelijk zijn, dat $0< p< q$ en dat $(a,b)$ het koppel getallen $(p,q)$ is waarvoor het grootste van de twee, $b$, van alle $q$ de kleinste is. Dus voor alle koppels $(p,q)$ geldt dat $q\geq b$.
Het is onmogelijk dat $s(a)$ en $s(b)$ beide eindigen op een $1$ omdat een $1$ alleen wordt toegevoegd als de resulterende bitstring nog niet bestaat.
Dus $s(a)$ en $s(b)$ eindigen allebei op een $0$.
Stel daarom $s(a)=s(b)=t0$ met $t$ een bitstring van lengte $n-1$.
Omdat $b$ minimaal is moeten $s(a-1)$ en $s(b-1)$ verschillend zijn, dus $s(a-1)=et$ en $s(b-1)=ft$ met $e\neq f$ en $e$, $f$ beide $0$ of $1$.
Omdat $s(a)$ eindigt op $0$ zijn er twee mogelijkheden:
We kunnen dus besluiten dat als een bepaalde bitstring $x$ twee keer voorkomt, dat dan $x=00..00$. $(*)$.
Dit betekent dat er zeker een $a\leq2^n$ is zodat $s(a)=00..00$. Zoniet zouden er van de eerste $2^n$ bitstrings zeker twee gelijk zijn wegens het duivenhokprincipe, maar wegens (*) dat kan niet. $(**)$
Vervolgens bewijzen we dat alle bitstrings voorkomen.
Merk op dat een bepaalde bitstring $x0$ (Met $x\neq00..00$) slechts kan voorkomen als zowel $1x$ als $0x$ al zijn voorgekomen, want wegens (*) is het onmogelijk dat $1x$ of $0x$ tweemaal voorkomt.
Dit betekent dat als een bitstring $x=x_1x_2\cdots x_n$ (met $x_i$ telkens gelijk aan $0$ of $1$ en $x\neq00..00$) niet voorkomt, ook $x_2x_3\cdots x_n0$ niet voorkomt.
Dus dan is ofwel $x_2=x_3=\cdots=x_n=0$, ofwel komt ook $x_3x_4\cdots x_n00$ niet voor.
Dan is opnieuw ofwel $x_3=x_4=\cdots=x_n=0$, ofwel komt $x_4x_5\cdots x_n000$ niet voor.
Enzovoort, tot uiteindelijk $x_n=0$ ofwel komt $00..00$ niet voor.
Dus vinden we uiteindelijk dat in elk geval de bitstring $00..00$ niet voorkomt.
Dit is in tegenstrijd met (**), dus onze veronderstelling dat de bitstring $x$ niet voorkomt is fout. Bijgevolg komt elke bitstring voor.
Aangezien er $2^n$ mogelijke bitstrings zijn en deze allemaal ergens voorkomen moeten deze voorkomen bij de bitstrings $s(1),\cdots s(2^n)$ omdat na $00..00$ hetzelfde blijft komen en omdat $00..00$ te laatste als $2^n$-de voorkomt wegens (**).
Bijgevolg zijn de bitstrings $s(1)$ tot $s(2^n)$ alle verschillend.