[Matx]#659: Funktion gesucht

[GJ Woeginger]

Bestimme alle Funktionen f, die die positiven ganzen
Zahlen in die positiven ganzen Zahlen abbilden und
die fuer alle positiven ganzen n die Ungleichung

2*f(n+1) > f(n) + f(f(n))

erfuellen.

___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

[Siegbert Steinlechner]

#



#




#




#




#




#



#

Wegen der geforderten Ganzzahligkeit denke ich, die einzige Möglichkeit
liegt in einem Polynom in n mit ganzzahligen Koeffizienten >=0:

f(n)=a0 + a1*n + a2*n^2 + a3*n^3+...

Schaut man sich dann die Ungleichung für Potenzen 2,3,4,... an, ist zu
sehen, dass die rechte Seite der gegebenen Ungleichung schneller mit n
wächst als die linke. Deshalb hat das Polynom höchstens den Grad 1.
Dies führt auf die Ungleichung

2*(a1*(n + 1) + a0) - a1*(a1*n + a0) - a1*n - 2*a0 > 0

und nach Vereinfachung mit der Annahme a1 ungleich 0 auf:

n - a1*n - a0 + 2 >0

Daraus folgen die möglichen Lösungen:

1.) a1=1, a0=0 => f(n)=n
2.) a1=1, a0=1 => f(n)=n+1

Der Fall a1=0 führt auf keine weitere Lösung.

Gruß
Siegbert

[totarefugium]

Siegbert Steinlechner wrote:
> Am 30.04.2012 15:13, schrieb GJ Woeginger:
>> Bestimme alle Funktionen f, die die positiven ganzen
>> Zahlen in die positiven ganzen Zahlen abbilden und
>> die fuer alle positiven ganzen n die Ungleichung
>>
>> 2*f(n+1)> f(n) + f(f(n))
>>
>> erfuellen.
>>


>

> Wegen der geforderten Ganzzahligkeit denke ich, die einzige Möglichkeit
> liegt in einem Polynom in n mit ganzzahligen Koeffizienten >=0:

Nein, auch eine aus Sinusfunktionen bestehende Reihe kann man so
komponieren, dass sie in geeigneter Weise ganzzahlige Punkte trifft,
auch wurden in der Aufgabenstellung keine zahlentheoretischen Funktionen
wie Modulodivision oder Gaussklammer ausgeschlossen...

> Daraus folgen die möglichen Lösungen:
>
> 1.) a1=1, a0=0 => f(n)=n
> 2.) a1=1, a0=1 => f(n)=n+1

Unter Benutzung der o.g. Sinusreihen, fände man auch

oo
f(n) = n - 1/2 + (1/pi)*SUM(sin(2*k*pi*n)/k)
k=1

und


oo
f(n) = 1/2 + n + (1/pi)*SUM(sin(2*k*pi*(1 + n))/k)
k=1

als Lösungen, sowie weitere mögliche Reihen.

MfG, Michael Taktikos

[Siegbert Steinlechner]

Hallo Michael,

dein Gedanke scheint zu sein, dass man zu den von mir angegebenen
Lösungen f(n)=n oder f(n) = n+1 Funktionen addieren darf, die an den
ganzzahligen Stellen n jeweils Null sind - scheint mir etwas akademisch,
ist aber akzeptiert. Trotzdem scheinen deine Lösungen nicht zu stimmen.
Die Summen ergeben für ganzzahlige n jeweils 0, dürfen also weggelassen
werden. Übrig bleiben dann die Lösungen f(n)=n-1/2 und f(n)=n+1/2. Das
sind aber keine gültigen Lösungen, die "die positiven ganzen Zahlen in
die positiven ganzen Zahlen abbilden".

Gruß
Siegbert

[Klaus-R. Loeffler]

GJ Woeginger <gwo...@figipc78.tu-graz.ac.at> wrote:

> Bestimme alle Funktionen f, die die positiven ganzen
> Zahlen in die positiven ganzen Zahlen abbilden und
> die fuer alle positiven ganzen n die Ungleichung
>
> 2*f(n+1) > f(n) + f(f(n))
>
> erfuellen.
>
> ___________________________________________________________

s
p
o
i
l
e
r
c
h
e
n

Da für jedes n gilt f(n+1) > f(n) oder f(n+1) > f(f(n)), kann das
Minimum von f an keiner Stelle n > 1 liegen; dieses Minimum existiert,
da die Folgenglieder positive ganze Zahlen sind, und liegt somit an der
Stelle 1.
Für n>1 ist damit f(n)>f(1)>=1.
Die entsprechende Überlegung liefert, dass das Minimum von f ueber
{2,3,4, ...} an der Stelle 2 liegen muss und an keiner anderen Stelle
angenommen wird.
Somit ist die Folge (f(n)) streng isoton; daraus folgt auch, dass fuer
alle positiven ganzen Zahlen gilt f(n) ≥ n und allgemeiner f(n+p)>= f(n)
+ p.

Gibt es positive, ganze Zahlen n, p mit f(n) ≥ n+p, so folgt
2 f(n+1) > f(n) + f(f(n)) ≥ f(n)+f(n+p) ≥ 2 f(n) + p, also f(n+1) -
f(n) ≥ (p+1)/2 .

Somit ist f(n+1) ≥ f(n) + (p+1)/2 ≥ n + p + (p+1)/2
= n+1 + p + (p-1)/2 .
Liegt also bei einem Folgeglied der Wert um mindestens p ueber dem
Index, so gilt das auch für das folgende Glied; somit gilt f(i+1)-f(i)
≥ f(n+1)-f(n) fuer alle Indizes i ≥ n.

2 f(n+1) - 2 f(n) > f(f(n)) - f(n) ≥ f(n+p) - f(n)
= summe(f(i+1)-f(i), i, n, n+p-1)
≥ (p-1) (f(n+1)-f(n)), und daher p ≤ 2 .

Ist fuer irgendein n nun f(n) = n+2, so folgt f(n+1) = n+3 und f(n+2) =
n+4.
Dann ist 2 f(n+1) = 2n+6 = n+2 + n+4 = f(n) + f(n+2) = f(n) + f(f(n))
mit Widerspruch zur vorgegebenen Ungleichung.

Damit muss fuer ein Anfangsstück oder die ganze Folge gelten f(n) = n,
und für ein Endstück oder die ganze Folge ist f(n) = n+1.

Nachrechnen zeigt, dass damit die vorgegebene Ungleichung allem Anschein
nach erfüllt wird.

Klaus-R.