Όμορφο θέμα... εισαγωγικών

#1

Για κάθε θετικό ακέραιο

, αντιστοιχούμε μοναδικούς μη αρνητικούς ακεραίους $f(n),\ g(n)$ έτσι ώστε :

(α) $g(99) =1,\ g(100)=0$

(β) f(100)=1

(γ)

Βρείτε τις τιμές $f(99),\ g(101),\ f(2008)$ .

Waseda University entrance exam

Mikesar · #2

Ας κάνω μια προσπάθεια...

$f(99)+f(99+g(99))=f(100)\Leftrightarrow f(99)=0$

$f(102)=f(101)+f(101+g(101))\Rightarrow f(102)\geq f(101)=2$
$f(103)=f(102)+f(102+g(102))\Rightarrow f(103)\geq f(102)=2$
και επαγωγικά
$f(n)\geq2, \ n\geq102$

Είναι $101+g(101)\geq101\Rightarrow f(101+g(101))\geq2$ άρα
$f(102)=f(101)+f(101+g(101))\geq 2+2=4$
$f(103)=f(102)+f(102+g(102))\geq 4+2=6$
και επαγωγικά $f(n)\geq4+2(n-102), \ n\geq102$

Έστω $g(101)>0\Rightarrow g(101)\geq2$ (αν ήταν g(101)=1

θα ήταν $f(102)=f(101)+f(102)\Rightarrow f(101)=0$ )
Τότε
$f(102)=f(101)+f(101+g(101))\geq f(101)+4+2(g(101)-1)\geq 2+4+2=8$
$f(103)=f(102)+f(102+g(101))\geq 8+4+2g(101)\geq 12$
$f(104)=f(103)+f(103+g(103))\geq 12+4+2+2g(103)\geq 18$
και επαγωγικά $f(n)\geq8+2(n-102), \ n\geq102$

Κάθε φορά που κάνουμε αυτή τη διαδικασία μεγαλώνει και η ελάχιστη τιμή του $f(n), \ n\geq102$ , δηλαδή το f(n)

μπορεί να είναι απείρως μεγάλο, άτοπο.
Άρα g(101)=0

και

Με όμοιο τρόπο, εάν $g(102)>0\Rightarrow g(102)\geq2$ τότε το $f(n), \ n\geq103$ μπορεί να είναι απείρως μεγάλο, άτοπο. Άρα g(102)=0

.

Η ίδια διαδικασία μας δίνει ότι $g(n)=0, \ n\geq 101$ .

Άρα για $n\geq102$ είναι
$f(n+1)=f(n)+f(n+g(n))\Rightarrow f(n+1)=2f(n)$

Συνεπώς:
$f(2008)=2f(2007)=2^2f(2006)=...=2^{1906}f(102)=2^{1908}$

Συνοψίζοντας είναι $\boxed{f(99)=0}$ , $\boxed{g(101)=0}$ , $\boxed{f(2008)=2^{1908}}$

csar · #3

Με πρόλαβε στο τσακ ο Μιχάλης πριν αναρτήσω τη δική μου λύση.

Παρόλα αυτά, Μιχάλη, στην απάντησή σου δεν κατάλαβα γιατί είναι άτοπο να αυξάνει το κάτω φράγμα που βρήκες για την

. Αφού η

είναι αύξουσα και μη-φραγμένη, δεν είναι λογικό να βρεις μία αύξουσα ακολουθία κάτω φραγμάτων για κάθε τιμή της; Ίσως είναι πιο σαφές το παρακάτω:

Έχεις δείξει ότι $f(n)\geq 2$ για $n\geq 102$ ή ακόμα καλύτερα ότι $f(n)\geq 1$ για $n\geq 101$ . Στη συνέχεια θεωρώ μόνον $n\geq 101$ :
f(n+1) = f(n) + f(n+g(n))

,
και επειδή $n+g(n)\geq n\geq 101$ έπεται ότι $f(n+g(n))\geq1$ , δηλαδή $f(n+1)\geq f(n)+1>f(n)$ . Άρα η

είναι γνησίως αύξουσα.

Όμως και $f(n)\geq 1$ , άρα $f(n+1)\geq f(n+g(n))+1>f(n+g(n))$ . Όμως η

είναι γνησίως αύξουσα. Άρα η f(n+1)>f(n+g(n))

υποννοεί ότι n+1>n+g(n)

, δηλαδή

για $n\geq 101$ .

Συνεπώς ισχύει ότι για $n\geq 101$ , f(n+1) = f(n)+f(n) = 2f(n)

με

άρα τελικά $f(n) = 2^{n-100}$ .

Χρήστος

Mikesar · #4

csar έγραψε: Παρόλα αυτά, Μιχάλη, στην απάντησή σου δεν κατάλαβα γιατί είναι άτοπο να αυξάνει το κάτω φράγμα που βρήκες για την . Αφού η είναι αύξουσα και μη-φραγμένη, δεν είναι λογικό να βρεις μία αύξουσα ακολουθία κάτω φραγμάτων για κάθε τιμή της;

Αυτό που συμπεραίνω είναι ότι $f(n)\geq 2k+2(n-102), n\geq102,k\in\mathbb{N^*}$ όπου

οι φορές που κάνουμε την παραπάνω διαδικασία. Επειδή η διαδικασία μπορεί να γίνει άπειρες φορές το κάτω φράγμα της f(n)

για κάποιο σταθερό

τείνει στο άπειρο, γεγονός που είναι άτοπο.
Για παράδειγμα για n=102

, $f(102)\geq2k$ άτοπο για αρκετά μεγάλο

.

#5

Από εδώ:
http://www.artofproblemsolving.com/Foru ... 8&t=190059

Όμορφο θέμα... εισαγωγικών

Όμορφο θέμα... εισαγωγικών

Re: Όμορφο θέμα... εισαγωγικών

Re: Όμορφο θέμα... εισαγωγικών

Re: Όμορφο θέμα... εισαγωγικών

Re: Όμορφο θέμα... εισαγωγικών

Μέλη σε σύνδεση