MateClar
← Capitol

Manual · pagina 84

Exercițiul 20 · Altitudinea dronelor

Într-un grup de drone autonome care monitorizează o pădure, fiecare dronă are un ID unic (număr natural nenul). Pentru a evita coliziunile, dronele trebuie să își actualizeze altitudinea de zbor conform unui algoritm secret, bazat pe ID-ul lor. Funcția f:N∗→N∗f : \mathbb N^* \to \mathbb N^* reprezintă algoritmul prin care o dronă cu ID-ul nn își calculează noua altitudine f(n)f(n) (în metri). Algoritmul trebuie să respecte două reguli stricte:

păstrarea ordinii: dacă o dronă are un ID mai mare decât alta, ea va zbura întotdeauna la o altitudine strict mai mare (ff este strict crescătoare);

feedback-ul de siguranță: sistemul verifică integritatea datelor printr-o buclă dublă; dacă o dronă își recalculează altitudinea bazându-se pe noua altitudine deja calculată, suma dintre această „dublă procesare” și altitudinea simplă trebuie să respecte o relație liniară fixă, pentru a preveni erorile de calcul.

Determină funcția de altitudine f:N∗→N∗f : \mathbb N^* \to \mathbb N^*, știind că este strict crescătoare și verifică relația: f(f(n))+f(n)=2n+9f(f(n)) + f(n) = 2n + 9, ∀n∈N∗\forall n \in \mathbb N^*.

Funcția f:N∗→N∗f : \mathbb N^* \to \mathbb N^* (altitudinea, în metri, a dronei cu ID-ul nn) este strict crescătoare și verifică f(f(n))+f(n)=2n+9f(f(n)) + f(n) = 2n + 9, ∀n∈N∗\forall n \in \mathbb N^*. Determină funcția ff.

Scrie relația pentru n+1n + 1 și scade din ea relația pentru nn. Folosește apoi că, între numere naturale, „strict mai mare” înseamnă „mai mare cu cel puțin 11”.

  1. 1. Ce știm și ce idee folosim

    Nu cunoaștem formula lui ff. Știm trei lucruri: valorile sunt numere naturale nenule, ff este strict crescătoare, iar f(f(n))+f(n)=2n+9f(f(n)) + f(n) = 2n + 9. „Dubla procesare” din enunț este compunerea (f∘f)(n)=f(f(n))(f \circ f)(n) = f(f(n)) (manual, p. 80).

    Între numere naturale, „strict mai mare” înseamnă „mai mare cu cel puțin 11”. Așa că, pentru orice nn:

    f(n+1)−f(n)≥1,f(f(n+1))−f(f(n))≥1.\begin{aligned} f(n + 1) - f(n) &\ge 1, \\ f(f(n + 1)) - f(f(n)) &\ge 1. \end{aligned}

    Ideea: comparăm relația dată pentru n+1n + 1 cu cea pentru nn, ca să vedem cu cât cresc valorile de la un ID la următorul.

  2. 2. Scădem relația pentru nn din cea pentru n+1n + 1

    f(f(n+1))+f(n+1)=2(n+1)+9f(f(n))+f(n)=2n+9\begin{aligned} &f(f(n + 1)) + f(n + 1) \\ &\qquad = 2(n + 1) + 9 \\[6pt] &f(f(n)) + f(n) = 2n + 9 \end{aligned}

    Verifică-te

    Cât este diferența membrilor din dreapta, (2(n+1)+9)−(2n+9)\big(2(n + 1) + 9\big) - (2n + 9)?
    În stânga, grupăm termenii doi câte doi:
    f(f(n+1))−f(f(n))⏟≥ 1+f(n+1)−f(n)⏟≥ 1=2\begin{aligned} &\underbrace{f(f(n + 1)) - f(f(n))}_{\ge\, 1} \\ &\quad + \underbrace{f(n + 1) - f(n)}_{\ge\, 1} = 2 \end{aligned}
    Două numere naturale, fiecare cel puțin 11, au suma 22 doar dacă amândouă sunt egale cu 11. Deci f(n+1)−f(n)=1f(n + 1) - f(n) = 1 pentru orice n∈N∗n \in \mathbb N^*.

  3. 3. Forma lui ff și constanta

    Valorile f(1),f(2),f(3),…f(1), f(2), f(3), \dots cresc cu exact 11 la fiecare pas: formează o progresie aritmetică cu rația 11 (din capitolul 2). Deci f(n)=f(1)+(n−1)=n+cf(n) = f(1) + (n - 1) = n + c, unde c=f(1)−1c = f(1) - 1 este un număr natural.

    Ca să-l aflăm pe cc, punem această formă în relație. Întâi f(f(n))=f(n+c)f(f(n)) = f(n + c), adică (n+c)+c=n+2c(n + c) + c = n + 2c, deci:

    f(f(n))+f(n)=(n+2c)+(n+c)=2n+3c.\begin{aligned} f(f(n)) + f(n) &= (n + 2c) + (n + c) \\ &= 2n + 3c. \end{aligned}

    Verifică-te

    Relația cere 2n+3c=2n+92n + 3c = 2n + 9 pentru orice nn. Cât este cc?

  4. 4. Verificare și interpretare

    Deci f(n)=n+3f(n) = n + 3. Verificăm toate condițiile: valorile n+3≥4n + 3 \ge 4 sunt în N∗\mathbb N^*; funcția este strict crescătoare; f(f(n))=f(n+3)=n+6f(f(n)) = f(n + 3) = n + 6, iar (n+6)+(n+3)=2n+9(n + 6) + (n + 3) = 2n + 9.
    nnf(n)f(n)f(f(n))f(f(n))suma
    1144771111
    2255881313
    3366991515
    123456712345678910Oxy
    f(n)=n+3f(n) = n + 3

    Graficul lui ff este format din puncte izolate, pentru că domeniul este N∗\mathbb N^*; ele stau pe dreapta punctată y=x+3y = x + 3.

    În problemă: drona cu ID-ul nn zboară la n+3n + 3 metri. Drona 11 la 44 m, drona 22 la 55 m, … Un ID mai mare dă o altitudine mai mare, cum cere regula păstrării ordinii.
Răspuns
f:N∗→N∗f : \mathbb N^* \to \mathbb N^*, f(n)=n+3f(n) = n + 3.