zelfvermijdende wandeling
Opgave - CanMO 1979 vraag 5
Een wandeling bestaat uit een rij van stappen van lengte 1, noord-, oost-, zuid- of westwaarts. Een wandeling wordt $\emph{zelfvermijdend}$ genoemd als het nooit tweemaal door hetzelfde punt gaat. Zij $f(n)$ het aantal $n-$stappige zelfvermijdende wandelingen die bij de oorsprong beginnen.
Bepaal $f(1),f(2),f(3),f(4)$ en toon aan dat
$$2^n
- login om te reageren
Oplossing
$f(1) = 4$, want je kan in de 4 richtingen vertrekken.
$f(2) = 12$, want je kan nu bij elk van de vier mogelijkheden naar drie richtingen.
$f(3) = 36$, want je kunt weer telkens in drie richtingen verder.
Voor $f(4)$ hebben we het probleem dat de wandeling nu een vierkantje zou kunnen maken en dat mag niet. $f(4) = 100$, want dat is $3\cdot36-8$ (Die acht zijn de vier mogelijke vierkantjes in beide richtingen.)
Het is logisch dat $f$ nooit meer dan drie keer zo groot kan worden voor een $n$ die maar $1$ stijgt, want voor elke wandeling van $n-1$ stappen zijn er hoogstens 3 mogelijkheden bij $n$ (in elke richting 1). Daarom geldt (en omdat $f(1)=4$) dat:
$f(n)\leq 4\cdot3^{n-1}$ (gelijkheid treedt op voor $n$ gelijk aan $1$, $2$ of $3$)
Gebruik nu alleen twee opeenvolgende richtingen (noem de functie $g(n)$) : bv. noord en oost
$g(n) = 2^n$, want $g(1)=2$ en voor elk van de mogelijkheden voor $n-1$ zijn er twee voor $n$, de functie kan zichzelf nooit snijden.
Maar elk van deze mogelijkheden kan je ook maken met de vier richtingen dus:
$f(n)>g(n)=2^n$
Dus samen is
$2^n < f(n)\leq 4\cdot3^{n-1}$