Matematică care conectează unde mergem și unde am fost | Revista Quanta

Să spunem că ești la o petrecere cu alte nouă persoane și toți strâng mâna celorlalți exact o dată. Câte strângeri de mână au loc?

Aceasta este „problema strângerii de mână” și este una dintre preferatele mele. Ca profesor de matematică, îmi place pentru că există atât de multe moduri diferite în care poți ajunge la soluție, iar diversitatea și interconexiunea acelor strategii ilustrează frumos puterea gândirii creative în matematică.

O soluție este următoarea: începeți cu fiecare persoană strângând mâna fiecărei persoane. Zece persoane, cu nouă strângeri de mână fiecare, produc 9 × 10 = 90 de strângeri de mână în total. Dar aceasta numără fiecare strângere de mână de două ori - o dată din perspectiva fiecărui agitator - deci numărul real de strângeri de mână este $latex frac{90}{2} = 45$. Un argument simplu și minunat de numărare pentru câștig!

Există, de asemenea, o modalitate complet diferită de a rezolva problema. Imaginați-vă că oaspeții sosesc unul câte unul și, când ajung acolo, dau mâna tuturor celor prezenți. Prima persoană nu are mâinile de strâns, așa că într-o petrecere cu o singură persoană există zero strângeri de mână totale. Acum sosește a doua persoană și dă mâna cu prima persoană. Acest lucru adaugă o strângere de mână la total, astfel încât într-o petrecere de două persoane, există 0 + 1 = 1 strângere de mână totală. Când a treia persoană sosește și dă mâna primilor doi oaspeți, se adaugă două strângeri de mână la total. Sosirea celei de-a patra persoane adaugă trei strângeri de mână la total și așa mai departe.

Această strategie modelează recursiv secvența de strângeri de mână, ceea ce înseamnă că fiecare termen din secvență este definit în raport cu cei care vin înaintea lui. Probabil că ești familiarizat cu succesiunea Fibonacci, cea mai faimoasă secvență recursivă dintre toate. Începe cu 1, 1, 2, 3, 5, 8, 13, 21 și continuă cu fiecare termen ulterior egal cu suma celor doi anteriori.

După cum vom vedea mai jos, recursiunea este un cadru flexibil și puternic pentru a gândi la o gamă largă de idei matematice. Și chiar dacă cercetătorii indieni antici, precum Hemachandra, sunt creditați cu cunoștințele despre acest tip de secvențe încă din 1150, ei încă oferă provocări interesante pentru matematicieni de astăzi.

Să vedem cum gândirea recursiv ajută la problema strângerii de mână. Dacă lăsăm $latex a_n$ egal cu numărul de strângeri de mână la an n-partid persoană, putem reprezenta această relație recursivă cu următoarea formulă:

$latex a_n = a_{n-1} + n–1$

Acest lucru ne spune că numărul de strângeri de mână la o n- petrecerea persoanei ($latex a_n$) este egal cu numărul de strângeri de mână la un (n − petrecere de 1) persoană ($latex a_{n-1}$) plus n − încă 1 strângere de mână, surprinzând ideea că atunci când o persoană nouă sosește, adaugă un anumit număr de noi strângeri de mână celor care au avut deja loc.

În versiunea noastră specială a problemei strângerii de mână, dorim să știm $latex a_{10}$, numărul de strângeri de mână la o petrecere de 10 persoane, astfel încât să aflăm că folosim relația recursivă

$latex a_{10} = a_9 + 9$

Pentru a găsi valoarea lui $latex a_{10}$, trebuie doar să știm valoarea lui $latex a_9$ și să adăugăm 9 la aceasta. Cum găsim valoarea $latexului a_9$? Folosind recursiunea, desigur!

$latex a_9 = a_8 + 8$

Acum, pentru a găsi valoarea lui $latex a_8$, trebuie să găsim valoarea lui $latex a_7$, care necesită cunoașterea $latexului a_6$ și așa mai departe. În acest moment, s-ar putea să vă îngrijorați că acest lucru va continua pentru totdeauna într-un fel de coborâre infinită, dar odată ce ajungem la $latex a_1$ am terminat, pentru că știm că nu există nicio strângere de mână totală la o petrecere cu o singură persoană.

$latex a_1 = 0$

Această valoare inițială sau „sedinta” este o caracteristică cheie a unei secvențe recursive. Acesta garantează că acest proces de întoarcere prin secvență folosind relația recursivă se va încheia. Odată ce ați atins valoarea inițială, întoarcerea se oprește și apoi puteți merge înainte prin listă pentru a obține valoarea dorită.

$latex a_1 = 0$

$latex a_2 = a_1 + 1 = 0 + 1 = 1$

$latex a_3 = a_2 + 2 = 1 + 2 = 3$

$latex a_4 = a_3 + 3 = 3 + 3 = 6$

$latex cdots$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

Lucrând prin listă, vedem că există un total de 45 de strângeri de mână la o petrecere de 10 persoane, ceea ce este de acord cu calculul nostru inițial. Dacă sunteți la fel ca studenții mei, ați putea să întrebați de ce avem nevoie de o altă modalitate de a rezolva această problemă atunci când știm deja răspunsul, mai ales că această a doua abordare pare să dureze mai mult.

Este o întrebare bună. Un răspuns este că abordarea recursivă ne oferă o viziune complet diferită asupra a ceea ce se întâmplă în această problemă, iar perspective diferite sunt utile în matematică, așa cum sunt în toate lucrurile. Ele ne oferă diferite oportunități de a înțelege concepte și ne permit să folosim diferite instrumente, care ne pot ajuta atunci când suntem blocați.

În special, recursiunea este utilă, deoarece este peste tot în matematică. Apare, de exemplu, în relațiile liniare despre care toată lumea învață la ora de matematică — cele caracterizate printr-o rată constantă de schimbare și reprezentate prin linii în plan. O funcție liniară precum $latex f(x) = 3x + 5$ poate fi considerată ca o formulă recursivă:

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

Deși cel mai evident mod de a ne gândi la $latex f(2)$ poate fi că $latex f(2) = 3 ori 2 + 5 = 11$, o altă modalitate este că $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Modelarea recurstivă a caracteristicii fundamentale a funcțiilor liniare — rata constantă de schimbare — ne oferă un alt mod de a gândi această relație. Același lucru se poate face cu funcțiile exponențiale caracterizate prin schimbare multiplicativă constantă.

Gândirea recursiva funcționează și dincolo de secvențe de numere. Dacă ați rezolvat vreodată un sistem de ecuații, probabil că ați aplicat o abordare recursivă. Pentru a rezolva sistemul

$latex 2x + y = 10$

$latex 3x – y = 5$

mai întâi puteți adăuga cele două ecuații împreună pentru a elimina y variabilă, din care rezultă ecuația $latex 5x = 15$. Rezolvați asta pentru a obține $latex x =$ 3, înlocuiți pentru a găsi $latex y = 4$ și ați terminat. Această abordare utilizează un algoritm recursiv, în care soluția unui sistem este construită de la soluție la sisteme mai mici, înrudite. De exemplu, pentru a rezolva un sistem 3 × 3, eliminați o variabilă pentru a o transforma într-un sistem 2 × 2 și apoi din nou pentru a o transforma într-un sistem 1 × 1. Această ecuație unică ușor de rezolvat este ca valoarea de bază a acestui proces recursiv. Semnalează sfârșitul returului și de acolo vă întoarceți în lanțul de ecuații, la fel ca într-o secvență recursivă.

Există chiar și tehnici recursive de demonstrare. De exemplu, o formulă celebră în geometrie este formula sumei unghiurilor poligonului, care spune că suma măsurilor unghiurilor interioare ale unui npoligonul cu laturi este $latex (n-2) ori de 180^{circ}$. O modalitate de a demonstra acest rezultat este să începeți cu un n-du-te și imaginează-ți ce s-ar întâmpla dacă ai elimina un triunghi.

Îndepărtarea unui triunghi transformă n-intru într-un (n − 1)-gon și elimină, de asemenea, 180 de grade de măsurare a unghiului interior. Aceasta este o relație recursivă: suma unghiului interior pentru an n-gon este cu 180 de grade mai mult decât suma unghiurilor interioare pentru un (n − 1)-gon. Pentru a stabili rezultatul general, continuați să eliminați triunghiuri până când ajungeți la valoarea semințelor, ceea ce în această situație se întâmplă când ați eliminat toate, cu excepția a trei n- vârfurile lui gon. În acest moment, poligonul inițial a fost redus la un triunghi, a cărui sumă unghiurilor interioare este cunoscută ca fiind de 180 de grade. Acum mergeți înapoi în sus, adăugând 180 de grade la fiecare pas și veți obține formula.

Revenind la petrecerea noastră, problema strângerii de mână în sine ne arată ce este posibil atunci când gândim creativ și apoi conectăm acele mai multe perspective diferite ale unei probleme. Dacă ne jucăm cu modelul recursiv pentru secvența noastră de strângeri de mână:

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

apare un model frumos:

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$latex cdots$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Avem acum un mod nou și general de a ne gândi la problemă: numărul de strângeri de mână într-un n- persoana partid este egala cu suma primei n − 1 numere întregi pozitive.

Gândește-te înapoi la abordarea noastră inițială. Într-un n- persoana petrecere, fiecare persoană va strânge mâna cu cealaltă n − 1 persoană. Produsul $latex n (n-1)$ numără fiecare strângere de mână de două ori, deci numărul total de strângeri de mână este $latex frac{n(n-1)}{2}$. Dar, deoarece metodele noastre diferite contează același lucru, ele trebuie să dea același rezultat. În special, aceasta înseamnă:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Prin conectarea diferitelor abordări ale problemei strângerii de mână, obținem o formulă închisă pentru suma primei n − 1 numere întregi pozitive. Dar obținem și mai mult: expresia $latex frac{n(n-1)}{2}$ implică o fracție, dar pentru că este egală cu o sumă de numere întregi, și ea trebuie să fie un număr întreg. Acest lucru demonstrează un fapt simplu al teoriei numerelor: pentru fiecare număr întreg n, $latex frac{n(n-1)}{2}$ este un număr întreg.

Același tip de argument continuă să alimenteze matematica modernă. Ca un exemplu, cercetătorii de la începutul anilor 2000 a dat rezultate surprinzătoare despre secvențele recursive cunoscute sub numele de secvențe Somos, arătând că și ele numără ceva. Prin puterea conexiunilor creative, matematicienii au descoperit din nou unde ar putea merge înțelegând unde au fost.

Exerciții

1. Găsiți o formulă închisă pentru secvența care este definită recursiv ca
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. La sfârșitul coloanei, expresia $latex frac{n(n-1)}{2}$ s-a arătat a fi un număr întreg, chiar dacă expresia implică o fracție, deoarece $latex frac{n(n-1) )}{2}$ este rezultatul numărării a ceva. Există, de asemenea, un argument al teoriei numerelor care arată că această expresie trebuie să fie un număr întreg. Ce este?

3. Găsiți primii termeni ai șirului recursiv
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Găsiți primii termeni ai șirului recursiv
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$