matematikk.net

For hver [tex]n \geq 0[/tex], la [tex]S(n) = n - m^2[/tex], der [tex]m[/tex] er den største [tex]m[/tex] slik at [tex]m^2 \leq n[/tex]. Definer følgen [tex]\left{a_k\right}^\infty_{k=0}[/tex] med [tex]a_0 = A[/tex] og [tex]a_{k+1} = a_k + S(a_k)[/tex] for [tex]k \geq 0[/tex]. For hvilke [tex]A[/tex] er følgen til slutt konstant? (Putnam 1991)

Løsningsforslag:

At følgen til slutt blir konstant er det samme som at [tex]S(a_k)[/tex] blir null for en gitt [tex]k \geq 0[/tex]. Altså at [tex]a_k[/tex] er et kvadrat. Vi får da den trivielle løsningen [tex]A = p^2[/tex] for en [tex]p \in \mathbb{N_0}[/tex]. Hvis vi nå kan vise at følgen aldri blir et kvadrat hvis den ikke starter som et kvadrat (*), er vi i mål. Ser da på S(n) for naturlige n:

S(1) = 0
S(2) = 1
S(3) = 2
S(4) = 0
S(5) = 1
S(6) = 2
S(7) = 3
S(8) = 4
S(9) = 0
... etc.

Hvis vi nå velger A lik m, får vi følgen vår ved å se på argumentet til S i rad m i oppstillingen vår og så hoppe S(m) rader nedover og så se på argumentet til S i den raden vi havner på. Vi kan dermed "oversette" (*) til:
Hvis vi starter på et tall som ikke er null, og hvis vi hopper like mange plasser til høyre som tallet vi står på indikerer, vil vi aldri lande på en null.
0 1 2 0 1 2 3 4 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 0 ...

Ser så på en understreng av strengen vår, fra 1 til 2n og så 0 for en n:

1 2 3 --- 2n 0
1 2 3 --- 2n (2n+1)

Øverst er tallet og nederst er tallets posisjon i understrengen. Vi ser at nullen er i en odde posisjon, mens vi alltid vil havne på en like plassering i understrengen hvis vi starter i posisjon m og så går m skritt. Vi når uansett heller ikke bort til den neste nullen, som har posisjon 2n+5 i forhold til understrengen, så vi vil aldri havne på en null med mindre vi starter på den, altså er det kun kvadratiske A som "til slutt" gir oss en konstant følge.