Ας πούμε ότι είστε σε ένα πάρτι με άλλα εννέα άτομα και όλοι σφίγγουν το χέρι όλων των άλλων ακριβώς μία φορά. Πόσες χειραψίες γίνονται;

Αυτό είναι το «πρόβλημα της χειραψίας» και είναι ένα από τα αγαπημένα μου. Ως δάσκαλος μαθηματικών, μου αρέσει γιατί υπάρχουν τόσοι πολλοί διαφορετικοί τρόποι με τους οποίους μπορείτε να φτάσετε στη λύση και η ποικιλομορφία και η διασύνδεση αυτών των στρατηγικών απεικονίζουν όμορφα τη δύναμη της δημιουργικής σκέψης στα μαθηματικά.

Μια λύση έχει ως εξής: Ξεκινήστε με το κάθε άτομο να σφίγγει το χέρι του άλλου. Δέκα άτομα, με εννέα χειραψίες το καθένα, παράγουν 9 × 10 = 90 συνολικά χειραψίες. Αλλά αυτό μετράει κάθε χειραψία δύο φορές — μία φορά από την οπτική γωνία κάθε δονητή — επομένως ο πραγματικός αριθμός χειραψιών είναι $latex frac{90}{2} = 45$. Ένα απλό και υπέροχο επιχείρημα μέτρησης για τη νίκη!

Υπάρχει επίσης ένας εντελώς διαφορετικός τρόπος επίλυσης του προβλήματος. Φανταστείτε ότι οι καλεσμένοι φτάνουν ένας κάθε φορά, και όταν φτάνουν εκεί, δίνουν τα χέρια με όλους τους παρευρισκόμενους. Το πρώτο άτομο δεν έχει χέρια να κουνήσει, επομένως σε ένα πάρτι ενός ατόμου δεν υπάρχουν συνολικά μηδενικές χειραψίες. Τώρα φτάνει το δεύτερο άτομο και δίνει τα χέρια με το πρώτο άτομο. Αυτό προσθέτει μία χειραψία στο σύνολο, επομένως σε ένα πάρτι δύο ατόμων, υπάρχουν 0 + 1 = 1 συνολικά χειραψίες. Όταν το τρίτο άτομο φτάνει και δίνει τα χέρια με τους δύο πρώτους καλεσμένους, αυτό προσθέτει δύο χειραψίες στο σύνολο. Η άφιξη του τέταρτου ατόμου προσθέτει τρεις χειραψίες στο σύνολο, και ούτω καθεξής.

Αυτή η στρατηγική μοντελοποιεί την ακολουθία των χειραψιών αναδρομικά, πράγμα που σημαίνει ότι κάθε όρος στην ακολουθία ορίζεται σε σχέση με αυτούς που προηγούνται. Πιθανότατα είστε εξοικειωμένοι με την ακολουθία Fibonacci, την πιο διάσημη αναδρομική ακολουθία όλων. Ξεκινά 1, 1, 2, 3, 5, 8, 13, 21 και συνεχίζει με κάθε επόμενο όρο ίσο με το άθροισμα των δύο προηγούμενων.

Όπως θα δούμε παρακάτω, η αναδρομή είναι ένα ευέλικτο και ισχυρό πλαίσιο σκέψης για ένα ευρύ φάσμα μαθηματικών ιδεών. Και παρόλο που οι αρχαίοι Ινδοί μελετητές όπως ο Hemachandra πιστώνονται ότι γνώριζαν για αυτά τα είδη ακολουθιών ήδη από το 1150, εξακολουθούν να προσφέρουν ενδιαφέρουσες προκλήσεις για τους μαθηματικούς σήμερα.

Ας δούμε πώς η αναδρομική σκέψη βοηθά στο πρόβλημα της χειραψίας. Αν αφήσουμε το $latex a_n$ να ισούται με τον αριθμό των χειραψιών στο an n-person party, μπορούμε να αναπαραστήσουμε αυτήν την αναδρομική σχέση με τον ακόλουθο τύπο:

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

Αυτό μας λέει ότι ο αριθμός των χειραψιών είναι ίσος n-person party ($latex a_n$) ισούται με τον αριθμό των χειραψιών σε (n − 1)-πάρτι ατόμου ($latex a_{n-1}$) συν n − 1 ακόμη χειραψίες, αποτυπώνοντας την ιδέα ότι όταν έρχεται ένα νέο άτομο προσθέτει έναν ορισμένο αριθμό νέων χειραψιών σε αυτές που έχουν ήδη πραγματοποιηθεί.

Στη συγκεκριμένη εκδοχή του προβλήματος της χειραψίας, θέλουμε να γνωρίζουμε $latex a_{10}$, τον αριθμό των χειραψιών σε ένα πάρτι 10 ατόμων, ώστε να διαπιστώσουμε ότι χρησιμοποιούμε την αναδρομική σχέση

$latex a_{10} = a_9 + 9$

Για να βρούμε την τιμή του $latex a_{10}$, πρέπει απλώς να γνωρίζουμε την τιμή του $latex a_9$ και να προσθέσουμε 9 σε αυτό. Πώς βρίσκουμε την τιμή του $latex a_9$; Με τη χρήση αναδρομής, φυσικά!

$latex a_9 = a_8 + 8$

Τώρα, για να βρούμε την τιμή του $latex a_8$, πρέπει να βρούμε την τιμή του $latex a_7$, που απαιτεί να γνωρίζουμε το $latex a_6$ και ούτω καθεξής. Σε αυτό το σημείο, μπορεί να ανησυχείτε ότι αυτό θα συνεχιστεί για πάντα σε ένα είδος άπειρης κατάβασης, αλλά μόλις φτάσουμε στο $latex a_1$ τελειώσαμε, γιατί γνωρίζουμε ότι δεν υπάρχουν συνολικά χειραψίες σε ένα πάρτι ενός ατόμου.

$latex a_1 = 0$

Αυτή η αρχική ή η τιμή "seed" είναι ένα βασικό χαρακτηριστικό μιας αναδρομικής ακολουθίας. Εγγυάται ότι αυτή η διαδικασία επιστροφής μέσω της ακολουθίας χρησιμοποιώντας την αναδρομική σχέση θα τελειώσει. Μόλις φτάσετε την τιμή του σπόρου, το backtracking σταματά και, στη συνέχεια, μπορείτε να προχωρήσετε στη λίστα για να λάβετε την τιμή που θέλετε.

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

$λάτεξ cdots$

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

Δουλεύοντας στη λίστα, βλέπουμε ότι υπάρχουν συνολικά 45 χειραψίες σε ένα πάρτι 10 ατόμων, κάτι που συμφωνεί με τον αρχικό μας υπολογισμό. Αν είστε κάτι σαν τους μαθητές μου, μπορεί να ρωτήσετε γιατί χρειαζόμαστε έναν άλλο τρόπο για να λύσουμε αυτό το πρόβλημα όταν γνωρίζουμε ήδη την απάντηση, ειδικά επειδή αυτή η δεύτερη προσέγγιση φαίνεται να διαρκεί περισσότερο.

Είναι μια καλή ερώτηση. Μια απάντηση είναι ότι η αναδρομική προσέγγιση μας δίνει μια εντελώς διαφορετική άποψη για το τι συμβαίνει σε αυτό το πρόβλημα, και διαφορετικές προοπτικές είναι χρήσιμες στα μαθηματικά, όπως είναι σε όλα τα πράγματα. Μας δίνουν διαφορετικές ευκαιρίες να κατανοήσουμε έννοιες και μας επιτρέπουν να χρησιμοποιούμε διαφορετικά εργαλεία, τα οποία μπορούν να βοηθήσουν όταν είμαστε κολλημένοι.

Συγκεκριμένα, η αναδρομή είναι χρήσιμη γιατί υπάρχει παντού στα μαθηματικά. Προκύπτει, για παράδειγμα, στις γραμμικές σχέσεις για τις οποίες όλοι μαθαίνουν στο μάθημα των μαθηματικών — αυτές που χαρακτηρίζονται από σταθερό ρυθμό μεταβολής και αντιπροσωπεύονται από γραμμές στο επίπεδο. Μια γραμμική συνάρτηση όπως το $latex f(x) = 3x + 5$ μπορεί να θεωρηθεί ως αναδρομικός τύπος:

$latex a_0 = 5$

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

Αν και ο πιο προφανής τρόπος να σκεφτούμε για το $latex f(2)$ μπορεί να είναι ότι $latex f(2) = 3 φορές 2 + 5 = 11$, ένας άλλος τρόπος είναι ότι $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 $. Η αναδρομική μοντελοποίηση του θεμελιώδους χαρακτηριστικού των γραμμικών συναρτήσεων - του σταθερού ρυθμού μεταβολής - μας δίνει έναν άλλο τρόπο να σκεφτούμε αυτή τη σχέση. Το ίδιο μπορεί να γίνει με εκθετικές συναρτήσεις που χαρακτηρίζονται από συνεχή πολλαπλασιαστική αλλαγή.

Η αναδρομική σκέψη λειτουργεί και πέρα ​​από ακολουθίες αριθμών. Εάν έχετε λύσει ποτέ ένα σύστημα εξισώσεων, πιθανότατα έχετε εφαρμόσει μια αναδρομική προσέγγιση. Για να λύσουμε το σύστημα

$latex 2x + y = 10$

$latex 3x – y = 5$

μπορείτε πρώτα να προσθέσετε τις δύο εξισώσεις μαζί για να εξαλείψετε το y μεταβλητή, η οποία καταλήγει στην εξίσωση $latex 5x = 15$. Λύστε αυτό για να πάρετε $latex x =$ 3, αντικαταστήστε το για να βρείτε $latex y = 4$, και τελειώσατε. Αυτή η προσέγγιση χρησιμοποιεί έναν αναδρομικό αλγόριθμο, όπου η λύση σε ένα σύστημα χτίζεται από τη λύση σε μικρότερα, σχετικά συστήματα. Για παράδειγμα, για να λύσετε ένα σύστημα 3 × 3, εξαλείφετε μια μεταβλητή για να τη μετατρέψετε σε σύστημα 2 × 2 και στη συνέχεια ξανά για να τη μετατρέψετε σε σύστημα 1 × 1. Αυτή η εύκολη στην επίλυση μεμονωμένη εξίσωση μοιάζει με την αρχική τιμή αυτής της αναδρομικής διαδικασίας. Σηματοδοτεί το τέλος του backtracking, και από εκεί συνεχίζετε τον δρόμο σας προς τα πίσω στην αλυσίδα των εξισώσεων, ακριβώς όπως σε μια αναδρομική ακολουθία.

Υπάρχουν ακόμη και αναδρομικές τεχνικές απόδειξης. Για παράδειγμα, ένας διάσημος τύπος στη γεωμετρία είναι ο τύπος αθροίσματος γωνίας πολυγώνου, ο οποίος λέει ότι το άθροισμα των μέτρων των εσωτερικών γωνιών ενός nΤο πολύγωνο της όψης είναι $latex (n-2) επί 180^{circ}$. Ένας τρόπος για να αποδείξετε αυτό το αποτέλεσμα είναι να ξεκινήσετε με ένα n-Φανταστείτε τι θα γινόταν αν αφαιρούσατε ένα τρίγωνο.

Η αφαίρεση ενός τριγώνου στρέφει το n-μπαίνω σε ένα (n − 1)-gon, και αφαιρεί επίσης 180 μοίρες μέτρησης εσωτερικής γωνίας. Αυτή είναι μια αναδρομική σχέση: Το άθροισμα της εσωτερικής γωνίας για ένα nΤο -gon είναι 180 μοίρες μεγαλύτερο από το άθροισμα της εσωτερικής γωνίας για ένα (n − 1)-gon. Για να καθορίσετε το γενικό αποτέλεσμα, συνεχίστε να αφαιρείτε τρίγωνα μέχρι να φτάσετε στην τιμή του σπόρου, κάτι που σε αυτήν την περίπτωση συμβαίνει όταν έχετε αφαιρέσει όλα τα τρίγωνα εκτός από τρία n-κορυφές του gon. Σε αυτό το σημείο το αρχικό πολύγωνο έχει μειωθεί σε ένα τρίγωνο, του οποίου το άθροισμα της εσωτερικής γωνίας είναι γνωστό ότι είναι 180 μοίρες. Τώρα ανεβείτε ξανά, προσθέτοντας 180 μοίρες σε κάθε βήμα και θα λάβετε τον τύπο.

Επιστρέφοντας στο πάρτι μας, το ίδιο το πρόβλημα της χειραψίας μας δείχνει τι είναι δυνατό όταν σκεφτόμαστε δημιουργικά και μετά συνδέουμε αυτές τις πολλές διαφορετικές οπτικές γωνίες ενός προβλήματος. Αν παίξουμε με το αναδρομικό μοντέλο για τη σειρά των χειραψιών μας:

$latex a_1 = 0$

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

προκύπτει ένα ωραίο μοτίβο:

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

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

Τώρα έχουμε έναν νέο και γενικό τρόπο να σκεφτούμε το πρόβλημα: Ο αριθμός των χειραψιών σε ένα n-πρόσωπο κόμμα ισούται με το άθροισμα του πρώτου n − 1 θετικοί ακέραιοι.

Σκεφτείτε ξανά την αρχική μας προσέγγιση. Σε μια n-πρόσωπο πάρτι, κάθε άτομο θα κάνει χειραψία με το άλλο n − 1 άτομα. Το προϊόν $latex n (n-1)$ μετράει κάθε χειραψία δύο φορές, επομένως ο συνολικός αριθμός των χειραψιών είναι $latex frac{n(n-1)}{2}$. Αλλά επειδή οι διαφορετικές μας μέθοδοι μετρούν το ίδιο πράγμα, πρέπει να αποδώσουν το ίδιο αποτέλεσμα. Συγκεκριμένα, αυτό σημαίνει:

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

Συνδέοντας διαφορετικές προσεγγίσεις στο πρόβλημα της χειραψίας, παίρνουμε έναν κλειστό τύπο για το άθροισμα του πρώτου n − 1 θετικοί ακέραιοι. Αλλά παίρνουμε ακόμη περισσότερα: η έκφραση $latex frac{n(n-1)}{2}$ περιλαμβάνει ένα κλάσμα, αλλά επειδή είναι ίσο με ένα άθροισμα ακεραίων, πρέπει επίσης να είναι ακέραιος. Αυτό αποδεικνύει ένα απλό γεγονός της θεωρίας αριθμών: Για κάθε ακέραιο n, $latex frac{n(n-1)}{2}$ είναι ένας ακέραιος αριθμός.

Αυτό το ίδιο είδος επιχειρημάτων συνεχίζει να τροφοδοτεί τα σύγχρονα μαθηματικά. Ως ένα παράδειγμα, ερευνητές στις αρχές της δεκαετίας του 2000 απέδειξε μερικά εκπληκτικά αποτελέσματα σχετικά με τις αναδρομικές ακολουθίες γνωστές ως ακολουθίες Somos, δείχνοντας ότι και αυτές μετρούν κάτι. Μέσω της δύναμης των δημιουργικών συνδέσεων, οι μαθηματικοί για άλλη μια φορά ανακάλυψαν πού θα μπορούσαν να πάνε καταλαβαίνοντας πού έχουν βρεθεί.

Ασκήσεις

1. Βρείτε έναν κλειστό τύπο για την ακολουθία που ορίζεται αναδρομικά ως
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. Στο τέλος της στήλης, η έκφραση $latex frac{n(n-1)}{2}$ εμφανίστηκε ως ακέραιος, παρόλο που η έκφραση περιλαμβάνει ένα κλάσμα, επειδή $latex frac{n(n-1 ) {2}$ είναι το αποτέλεσμα της μέτρησης κάτι. Υπάρχει επίσης ένα όρισμα θεωρίας αριθμών που δείχνει ότι αυτή η έκφραση πρέπει να είναι ακέραιος. Τι είναι αυτό?

3. Βρείτε τους πρώτους όρους της αναδρομικής ακολουθίας
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Βρείτε τους πρώτους όρους της αναδρομικής ακολουθίας
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$