Μαθηματική επαγωγή και η εικασία του Goldbach

Η μαθηματική επαγωγή είναι ένα πολύ ισχυρό αποδεικτικό εργαλείο. Χρησιμοποιείται για να αποδείξουμε ότι μία πρόταση P(n) που εξαρτάται από κάποιον ακέραιο n ισχύει για όλους τους ακεραίους. Η στρατηγική είναι η εξής:

Εικόνα 1. 

• Αρχικά εξετάζουμε αν μία πρόταση ισχύει για κάποιον ελάχιστο ακέραιο n₀ (συνήθως αυτός είναι ο 1).
• Υποθέτουμε ότι ισχύει για κάποιον αυθαίρετο ακέραιο n > n₀ (αυτή είναι η επαγωγική υπόθεση)
• Χρησιμοποιώντας την επαγωγική υπόθεση (δηλ. ότι ισχύει για τον n), αποδεικνύουμε ότι ισχύει και για τον επόμενο ακέραιο n+1.

Η λογική της μαθηματικής επαγωγής παρομοιάζεται συχνά με το φαινόμενο του ντόμινο (Εικ. 1). Εφόσον το τουβλάκι n ρίχνει το επόμενό του (η ισχύς της πρότασης για τον n έχει ως αποτέλεσμα την ισχύ της και για τον n+1) και το τουβλάκι n είναι αυθαίρετο, τότε και το επόμενο τουβλάκι n+1 θα ρίξει το επόμενό του, (n+1)+1 κ.ο.κ.

Ένα αντιπαράδειγμα

Πολλές φορές δεν είναι τόσο σαφής η χρησιμότητα της επαγωγής και το πόσο ισχυρό εργαλείο είναι. Πολλοί πιστεύουν ότι αν κάτι ισχύει μέχρι κάποιο αρκετά μεγάλο n τότε θα ισχύει για όλους τους ακεραίους. Ένα αντιπαράδειγμα είναι το παρακάτω.

Θέλουμε να εξετάσουμε την ισχύ της πρότασης

Ο αριθμός f(n) = n² - n + 41 είναι πρώτος για κάθε n ≥ 1.

Πράγματι για n=1 έχουμε f(1) = 41, πού είναι πρώτος. Για n = 2 έχουμε f(2) = 43 που είναι πρώτος και για n = 3,4,\ldots,40 έχουμε αντίστοιχα

47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

που είναι όλοι πρώτοι.

Όμως για n = 41 έχουμε f(41) = 1681 = 41×41, συνεπώς η πρόταση δεν ισχύει.

Η εικασία του Goldbach

To 1742 ο Γερμανός μαθηματικός Christian Goldbach σε ένα γράμμα του στον ελβετό μαθηματικό Leonhard Euler έγραψε:

"Κάθε άρτιος αριθμός μεγαλύτερος του 2 μπορεί να γραφτεί ως το άθροισμα δύο πρώτων αριθμών. Θεωρώ ότι αυτό είναι ένα βέβαιο θεώρημα, μόνο που δεν μπορώ να το αποδείξω."

Η πρόταση αυτή έγινε γνωστή ως η εικασία του Goldbach και παρά το ότι από τότε έχουν περάσει περισσότερα από 250 χρόνια, κανένας δεν έχει καταφέρει να την αποδείξει ή να την απορρίψει (να βρει, δηλαδή, έναν αριθμό για τον οποίο δεν ισχύει). Αν εξετάσουμε κατά σειρά τους πρώτους 12 άρτιους βλέπουμε ότι πράγματι

4 = 2+2	10 = 3+7	16 = 7+9	22 = 11+11
6 = 3+3	12 = 5+7	18 = 7+11	24 = 11+13
8 = 3+5	14 = 7+7	20 = 7+13	26 = 13+13

Μάλιστα η εικασία του Goldbach έχει επαληθευτεί για όλους τους αριθμούς μέχρι κάποιον αριθμό της τάξης του 1,6×10¹⁸ (ίσως και παραπάνω ο υπολογιστής που τα υπολογίζει ακόμα τρέχει).

Είναι όμως δυνατό να βρεθεί ένας αριθμός για τον οποίο δεν ισχύει η εικασία του Goldbach, δεδομένου ότι ισχύει μέχρι έναν τόσο μεγάλο αριθμό της τάξης του 1,6×10¹⁸; Δε μιλάμε τώρα για το 41 αλλά για έναν τεράστιο αριθμό...

Ένα πιο πειστικό αντιπαράδειγμα

Θέλουμε να εξετάσουμε την ισχύ της πρότασης

Ο αριθμός S(n) = 991n² + 1 δεν είναι τέλειο τετράγωνο

Η πρόταση αυτή δεν ισχύει. Αν όμως αρχίσουμε να εξετάζουμε έναν-έναν τους αριθμούς S(n) δε μας φτάνουν ούτε 1000 ζωές για να βρούμε τον πρώτο αριθμό για τον οποίο δεν ισχύει, αφού ο μικρότερος αριθμός για τον οποίο η παραπάνω πρόταση είναι αναληθής είναι ο

n₀ = 12.055.735.790.331.359.447.442.538.767 > 1,2×10²⁸.

Για να κατανοήσουμε πόσο μεγάλος είναι αυτός ο αριθμός αρκεί να αναλογιστούμε το εξής:

Η ηλικία του σύμπαντος υπολογίζεται σήμερα από 13,5 ως 20 δισεκατομμύρια (σημερινά ηλιακά) χρόνια. Ας πάρουμε το μεγαλύτερο αριθμό από τους δύο.

Αν υπήρχε ένας άνθρωπος που εξέταζε αν η παραπάνω πρόταση ισχύει με ρυθμό έναν αριθμό το δευτερόλεπτο, τότε σήμερα δε θα είχε ξεπεράσει ούτε το 10¹⁸ (αριθμό κατά πολύ μικρότερο του 10²⁸).

Πηγή (δύο παραδειγμάτων): Journey into Mathematics: An Introduction to Proofs του J.J. Rotman

Μοναδικότητα (;) ανάλυσης σε γινόμενο πρώτων παραγόντων

Μπορούμε να "διασπάσουμε" (ή αναλύσουμε) κάθε θετικό (μη-πρώτο) ακέραιο σε γινόμενο δύο παραγόντων και στη συνέχεια να αναλύσουμε τους παράγοντες αυτούς σε άλλους δύο παράγοντες μέχρι να έχουμε ένα γινόμενο από παράγοντες που είναι όλοι πρώτοι αριθμοί.

Για παράδειγμα ο 60 μπορεί να αναλυθεί σε 4·15 αλλά επίσης 4=2·2 και 15=3·5 άρα τελικά

60 = 4·15 = 2·2·3·5 = 2²·3·5

Θα μπορούσαμε να ξεκινήσουμε αλλιώς:

60 = 6·10 = 2·3·2·5 = 2²·3·5. 

Πάλι δηλαδή φτάσαμε στην ίδια ανάλυση του 60 σε πρώτους παράγοντες. Το γεγονός ότι ενώ ξεκινήσαμε από διαφορετικές αναλύσεις του 60 και φτάσαμε τελικά στην ίδια ανάλυση σε πρώτους παράγοντες μας φαίνεται απόλυτα φυσιολογικό και προφανές. Είναι όμως τόσο προφανές;

Ας πάρουμε ακόμα ένα παράδειγμα, τον αριθμό 41369. Μετά από πολύ κόπο βρίσκουμε ότι 41369 = 41·1009, όπου οι 41 και 1009 είναι πρώτοι. Μπορούμε όμως να πούμε με απόλυτη βεβαιότητα ότι σίγουρα δεν υπάρχουν άλλοι δύο πρώτοι αριθμοί p και q, τέτοιοι ώστε pq = 41369;

Το σύνολο $\mathbb{Z}[\sqrt{6}]$

Αν το παράδειγμα με τον 41369 δεν ήταν αρκετά πειστικό, το επόμενο παράδειγμα ίσως είναι λίγο περισσότερο. Ας θεωρήσουμε το σύνολο $\mathbb{Z}[\sqrt{6}]$, που είναι μία επέκταση του συνόλου των ακεραίων και περιλαμβάνει τους αριθμούς της μορφής α+β√6, όπου οι α,β είναι ακέραιοι. Παρατηρούμε επίσης ότι το $\mathbb{Z}[\sqrt{6}]$ είναι κλειστό ως προς τη συνήθη πρόσθεση και πολλαπλασιασμό, δηλαδή το άθροισμα και το γινόμενο δύο αριθμών του $\mathbb{Z}[\sqrt{6}]$ είναι πάλι αριθμοί του $\mathbb{Z}[\sqrt{6}]$. Για παράδειγμα έχουμε

3+4√6 + 2-√6 = 5+3√6,
0+2√6 + 1-√6 = 1+√6.

Επίσης το γινόμενο δύο αριθμών του $\mathbb{Z}[\sqrt{6}]$ είναι πάλι αριθμός του $\mathbb{Z}[\sqrt{6}]$:

(3+4√6)(2-√6) = 6 - 3√6 + 8√6 - 24 = -18+5√6, 

(0+2√6)(1-√6) = -12+2√6

Να σημειωθεί ότι $\mathbb{Z}\subset\mathbb{Z}[\sqrt{6}]$ (είναι οι αριθμοί με β=0).

Τότε για τον αριθμό 6 έχουμε

6 = 2·3

αλλά και

6 = √6 √6

Δηλαδή έχουμε δύο διαφορετικές αναλύσεις; Είναι δυνατό;

Τουρνουά νοκ-άουτ

Μια και αυτή είναι η πρώτη ανάρτηση του blog, λέω να ξεκινήσουμε όμορφα και ομαλά

Ένα τουρνουά (ας πούμε) τένις διεξάγεται με το σύστημα νοκ-άουτ:

• σε κάθε γύρο οι αθλητές κληρώνονται σε ζευγάρια και παίζουν μεταξύ τους,
• αν το πλήθος των αθλητών σε κάποιο γύρο είναι περιττό, τότε κάποιος αθλητής περισσεύει. Αυτός περνά στον επόμενο γύρο χωρίς αγώνα.
• οι νικητές προχωρούν στο τουρνουά ενώ οι χαμένοι αποχωρούν.

Αν οι αθλητές αρχικά είναι 2011, πόσοι αγώνες θα γίνουν συνολικά στο τουρνουά;