Funksjoner på de ikkenegative heltall

[Gustav]

Hvor mange funksjoner [tex]f:\, \mathbb{N}_0\to \mathbb{N}_0[/tex] fra de ikkenegative heltall til de ikkenegative heltall fins det som oppfyller

[tex]f(0)=2011[/tex]
[tex]f(1) = 111[/tex] og
[tex]f(\max(x+y+2, xy)) = \min(f(x+y), f(xy+2))[/tex] for alle x,y i [tex]\mathbb{N}_0[/tex]

(Med [tex]\mathbb{N}_0[/tex] menes altså unionen av de naturlige tall og {0} )

[Bernt Ivar]

Setter vi x = 0 får vi:
[tex]f(y+2) = \min(f(y), f(2))[/tex]
Ved å sette inn y = 0, får vi at f(2) < 2012.

Sett nå f(2)=k

Viss k < 112 får vi:
[tex]f(3) = \min (f(1),f(2))=k[/tex]
[tex]f(4) = k[/tex]
osv ved induksjon er f(n)=k for alle n > 1.

Dersom k > 111 får vi tilsvarende at f(oddetal) = 111, f(partal)=k.
Men då vil [tex]f(12)=f(3*4) = \min(f(7),f(14)) = 111 [/tex] altså har vi motsigelse.

Dermed finst det 112 slike funksjonar, ettersom funksjonen er bestemt av f(2) som kan ta alle verdiar frå 0 til 111.

[Fibonacci92]

Jeg får at:

[tex]x = 1:[/tex]

[tex]f(y+3) = min(f(y+1), f(y+2))[/tex]

Dette forteller oss at funksjonen er unikt bestemt av [tex]f(1)[/tex] og [tex]f(2)[/tex].

Videre har vi at hvis vi setter [tex]x = y = 0[/tex]:

[tex]f(2) \leq min(f(2), f(0))[/tex]

som betyr at [tex]f(2) \leq f(0) = 2011[/tex]

Da har vi at dersom [tex]f(2) \leq f(1)= 111[/tex]:

[tex]f(x) = f(2) = n[/tex] for [tex]x \neq 1,0[/tex]
[tex]f(1) = 111[/tex]
[tex]f(0) = 2011[/tex]

[tex]0 \leq n \leq 111[/tex]

og dersom [tex]f(2) \g f(1)= 111[/tex]:

[tex]f(x) = f(1) = 111[/tex] for [tex]x \neq 2,0[/tex]
[tex]f(2) = n[/tex]
[tex]f(0) = 2011[/tex]

[tex]111 \leq n \leq 2011[/tex]

som gir oss 2012 løsninger unikt bestemt av[tex] f(2)[/tex].

"Dersom k > 111 får vi tilsvarende at f(oddetal) = 111, f(partal)=k."

Hvordan får du dette Bernt Ivar?

[Bernt Ivar]

x=0:

[tex]f(y+2)=\min(f(y),f(2))[/tex]

for y=2 får vi:

[tex]f(4)=\min(f(2),f(2))=f(2)[/tex]

Tilsvarande får eg også det du får, at f(partal)=111, og dermed har vi motsigelse, så dessse løysingane funker ikkje. Eg skreiv kun opp1 eksempel, ettersom det er nok.

[Fibonacci92]

Klart:)

Overså at vi kunne hente informasjon om [tex]f(2) [/tex]fra

[tex]f(4) = min(f(2),f(2))[/tex]

Trodde jeg hadde brukt alle x,y som gir [tex]f(2)[/tex]

[Gustav]

Riktig løsning, ja!