Supponiamo che tu sia a una festa con altre nove persone e che tutti stringano la mano a tutti esattamente una volta. Quante strette di mano avvengono?

Questo è il "problema della stretta di mano" ed è uno dei miei preferiti. Come insegnante di matematica, lo adoro perché ci sono tanti modi diversi per arrivare alla soluzione, e la diversità e l’interconnessione di queste strategie illustrano magnificamente il potere del pensiero creativo in matematica.

Una soluzione è questa: iniziare con ogni persona che stringe la mano a ogni altra persona. Dieci persone, con nove strette di mano ciascuna, producono 9 × 10 = 90 strette di mano totali. Ma questo conta ogni stretta di mano due volte, una volta dal punto di vista di ciascuno shaker, quindi il numero effettivo di strette di mano è $latex frac{90}{2} = 45$. Un argomento di conteggio semplice e adorabile per la vittoria!

C'è anche un modo completamente diverso per risolvere il problema. Immagina che gli ospiti arrivino uno alla volta e, quando arrivano, stringono la mano a tutti i presenti. La prima persona non ha la mano da stringere, quindi in un gruppo composto da una sola persona ci sono zero strette di mano totali. Ora arriva la seconda persona e stringe la mano alla prima persona. Ciò aggiunge una stretta di mano al totale, quindi in un gruppo di due persone ci sono 0 + 1 = 1 stretta di mano totale. Quando arriva la terza persona e stringe la mano ai primi due ospiti, si aggiungono due strette di mano al totale. L'arrivo della quarta persona aggiunge tre strette di mano al totale e così via.

Questa strategia modella ricorsivamente la sequenza delle strette di mano, il che significa che ogni termine nella sequenza è definito rispetto a quelli che lo precedono. Probabilmente hai familiarità con la sequenza di Fibonacci, la sequenza ricorsiva più famosa di tutte. Inizia con 1, 1, 2, 3, 5, 8, 13, 21 e continua con ogni termine successivo uguale alla somma dei due precedenti.

Come vedremo in seguito, la ricorsione è una struttura flessibile e potente per riflettere su un'ampia gamma di idee matematiche. E anche se si ritiene che antichi studiosi indiani come Hemachandra conoscessero questo tipo di sequenze già nel 1150, esse offrono ancora sfide intriganti per i matematici di oggi.

Vediamo come il pensiero ricorsivo aiuta con il problema della stretta di mano. Se lasciamo che $latex a_n$ sia uguale al numero di strette di mano in an n-persona, possiamo rappresentare questa relazione ricorsiva con la seguente formula:

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

Questo ci dice che il numero di strette di mano ad un ngruppo di due persone ($latex a_n$) è uguale al numero di strette di mano in un (n − 1) gruppo di persone ($latex a_{n-1}$) più n − 1 ulteriore stretta di mano, catturando l'idea che quando arriva una nuova persona si aggiunge un certo numero di nuove strette di mano a quelle già avvenute.

Nella nostra versione particolare del problema della stretta di mano, vogliamo conoscere $latex a_{10}$, il numero di strette di mano in una festa di 10 persone, per scoprire che utilizziamo la relazione ricorsiva

$lattice a_{10} = a_9 + 9$

Per trovare il valore di $latex a_{10}$, dobbiamo solo conoscere il valore di $latex a_9$ e aggiungervi 9. Come troviamo il valore di $latex a_9$? Usando la ricorsione, ovviamente!

$lattice a_9 = a_8 + 8$

Ora, per trovare il valore di $latex a_8$, dobbiamo trovare il valore di $latex a_7$, che richiede la conoscenza di $latex a_6$ e così via. A questo punto, potresti essere preoccupato che tutto ciò vada avanti all'infinito in una sorta di discesa infinita, ma una volta raggiunto $latex a_1$ abbiamo finito, perché sappiamo che non ci sono strette di mano totali in una festa tra una sola persona.

$lattice a_1 = 0$

Questo valore iniziale o "seme" è una caratteristica chiave di una sequenza ricorsiva. Garantisce che questo processo di backtracking attraverso la sequenza utilizzando la relazione ricorsiva finirà. Una volta raggiunto il valore iniziale, il backtracking si interrompe e puoi quindi avanzare nell'elenco per ottenere il valore desiderato.

$lattice 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$

$cdots in lattice$

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

Analizzando l'elenco, vediamo che ci sono 45 strette di mano totali in una festa di 10 persone, il che concorda con il nostro calcolo iniziale. Se sei come i miei studenti, potresti chiederti perché abbiamo bisogno di un altro modo per risolvere questo problema quando conosciamo già la risposta, soprattutto perché questo secondo approccio sembra richiedere più tempo.

È una bella domanda. Una risposta è che l'approccio ricorsivo ci offre una visione completamente diversa di ciò che accade in questo problema, e prospettive diverse sono utili in matematica, come in tutte le cose. Ci danno diverse opportunità di comprendere concetti e ci permettono di utilizzare diversi strumenti, che possono aiutarci quando siamo bloccati.

In particolare, la ricorsione è utile perché è ovunque in matematica. Si verifica, ad esempio, nelle relazioni lineari che tutti imparano durante le lezioni di matematica, quelle caratterizzate da un tasso di cambiamento costante e rappresentate da linee nel piano. Una funzione lineare come $latex f(x) = 3x + 5$ può essere pensata come una formula ricorsiva:

$lattice a_0 = 5$

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

Sebbene il modo più ovvio di pensare a $latex f(2)$ possa essere che $latex f(2) = 3 volte 2 + 5 = 11$, un altro modo è che $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Modellare ricorsivamente la caratteristica fondamentale delle funzioni lineari – il tasso di cambiamento costante – ci offre un altro modo di pensare a questa relazione. Lo stesso può essere fatto con funzioni esponenziali caratterizzate da cambiamento moltiplicativo costante.

Il pensiero ricorsivo funziona anche oltre le sequenze di numeri. Se hai mai risolto un sistema di equazioni, probabilmente hai applicato un approccio ricorsivo. Per risolvere il sistema

$lattice 2x + y = 10$

$lattice 3x – y = 5$

puoi prima sommare le due equazioni per eliminare il y variabile, che risulta nell'equazione $latex 5x = 15$. Risolvi questo per ottenere $latex x =$ 3, sostituisci per trovare $latex y = 4$ e il gioco è fatto. Questo approccio utilizza un algoritmo ricorsivo, in cui la soluzione di un sistema viene creata dalla soluzione a sistemi più piccoli e correlati. Ad esempio, per risolvere un sistema 3 × 3, elimini una variabile per trasformarla in un sistema 2 × 2, e poi di nuovo per trasformarla in un sistema 1 × 1. Questa singola equazione facile da risolvere è come il valore iniziale di questo processo ricorsivo. Segnala la fine del backtracking e da lì si risale la catena di equazioni, proprio come in una sequenza ricorsiva.

Esistono anche tecniche di dimostrazione ricorsiva. Ad esempio, una famosa formula in geometria è la formula della somma degli angoli di un poligono, che dice che la somma delle misure degli angoli interni di un nil poligono a lati è $latex (n-2) volte 180^{circ}$. Un modo per dimostrare questo risultato è iniziare con an n-gon e immagina cosa accadrebbe se rimuovessi un triangolo.

Rimuovendo un triangolo si trasforma il n-gon in un (n − 1)-gon, e rimuove anche 180 gradi di misura dell'angolo interno. Questa è una relazione ricorsiva: la somma dell'angolo interno per an n-gon è 180 gradi maggiore della somma dell'angolo interno per un (n − 1)-gon. Per stabilire il risultato generale, continua a rimuovere i triangoli finché non raggiungi il valore seme, cosa che in questa situazione accade quando hai rimosso tutti i triangoli tranne tre nvertici di -gon. A questo punto il poligono iniziale è stato ridotto a un triangolo, la cui somma degli angoli interni è pari a 180 gradi. Ora torna indietro, aggiungendo 180 gradi ad ogni passaggio, e otterrai la formula.

Tornando al nostro gruppo, il problema stesso della stretta di mano ci mostra cosa è possibile quando pensiamo in modo creativo e poi colleghiamo insieme quelle molteplici e diverse prospettive di un problema. Se giochiamo con il modello ricorsivo per la nostra sequenza di strette di mano:

$lattice a_1 = 0$

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

emerge un bel modello:

$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$

$cdots in lattice$

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

Ora abbiamo un modo nuovo e generale di pensare al problema: il numero di strette di mano in un n-persona partito è pari alla somma dei primi n − 1 intero positivo.

Ripensa al nostro approccio originale. In un n-persona, ogni persona stringerà la mano all'altra n − 1 persona. Il prodotto $latex n (n-1)$ conta ogni stretta di mano due volte, quindi il numero totale di strette di mano è $latex frac{n(n-1)}{2}$. Ma poiché i nostri diversi metodi contano la stessa cosa, devono produrre lo stesso risultato. In particolare, ciò significa:

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

Collegando diversi approcci al problema dell'handshake, otteniamo una formula chiusa per la somma dei primi n − 1 intero positivo. Ma otteniamo ancora di più: l'espressione $latex frac{n(n-1)}{2}$ implica una frazione, ma poiché è uguale a una somma di numeri interi, anch'essa deve essere un numero intero. Ciò dimostra un semplice fatto della teoria dei numeri: per ogni numero intero n, $latex frac{n(n-1)}{2}$ è un numero intero.

Questo stesso tipo di argomento continua ad alimentare la matematica moderna. Ad esempio, i ricercatori nei primi anni 2000 hanno dimostrato alcuni risultati sorprendenti sulle sequenze ricorsive note come sequenze di Somos mostrando che anch'esse contano qualcosa. Attraverso il potere delle connessioni creative, i matematici hanno scoperto ancora una volta dove potevano andare capendo dove erano stati.

esercizi

1. Trova una formula chiusa per la sequenza definita ricorsivamente come
$lattice a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. Alla fine della colonna, l'espressione $latex frac{n(n-1)}{2}$ è stata mostrata come un numero intero anche se l'espressione implica una frazione, perché $latex frac{n(n-1 )}{2}$ è il risultato del conteggio di qualcosa. Esiste anche un argomento di teoria dei numeri che mostra che questa espressione deve essere un numero intero. Che cos'è?

3. Trova i primi termini della sequenza ricorsiva
$lattice a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Trova i primi termini della sequenza ricorsiva
$lattice a_1 = 1$
$lattice a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$