Πρώτοι αριθμοί: Από τα Μαθηματικά του Δημοτικού, στη σύγχρονη έρευνα

 

Οι πρώτοι αριθμοί είναι αυτοί που έχουν ακριβώς δύο διαιρέτες: τον εαυτό τους και το 1. Οι αρχικοί αριθμοί που είναι πρώτοι είναι οι: 2, 3, 5, 7, 11, 13.

Ο πρώτοι... πρώτοι αριθμοί

Τα δομικά στοιχεία των φυσικών αριθμών

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

Παραδείγματα:

\(15 = 3 \cdot 5\)

\(210 = 2 \cdot 3 \cdot 5 \cdot 7\)

\(396 = 2^2 \cdot 3^2 \cdot 11\)

 

✅Η παραπάνω γραφή ονομάζεται ανάλυση αριθμού σε γινόμενο πρώτων παραγόντων ή πρωτογενής ανάλυση του αριθμού.

 

Πώς γίνεται η ανάλυση ενός αριθμού σε γινόμενο πρώτων παραγόντων;

Παράδειγμα: Θέλουμε να αναλύσουμε το 360 σε γινόμενο πρώτων παραγόντων. Θα χρησιμοποιήσουμε τη μέθοδο των διαδοχικών διαιρέσεων.

👣 Βήμα  1. Εξετάζουμε, σύμφωνα με τα κριτήρια διαιρετότητας, ποιος είναι ο μικρότερος πρώτος αριθμός που διαιρεί το 360. Βρίσκουμε ότι είναι το 2 και το γράφουμε στα δεξιά.

👣 Βήμα 2. Διαιρούμε το 360 με το 2 και γράφουμε από κάτω το πηλίκο, που είναι το 180.

👣 Βήμα 3. Συνεχίζουμε την ίδια διαδικασία για το 180. Το 180 διαιρείται κι αυτό με το 2. Διαιρούμε με το 2 και γράφουμε από κάτω το πηλίκο, που είναι το 90.

👣 Βήμα 4. Διαιρούμε το 90 με το 2 και γράφουμε από κάτω το πηλίκο, που είναι το 45.

👣 Βήμα 5. Το 45 τώρα δεν διαιρείται με το 2. Πηγαίνουμε στον επόμενο πρώτο αριθμό, που είναι το 3. Βρίσκουμε ότι το 45 διαιρείται με 3.

👣 Βήμα 6. Διαιρούμε το 45 με το 3 και γράφουμε από κάτω το πηλίκο, που είναι το 15.

👣 Βήμα 7. Το 15 διαιρείται με το 3. Διαιρούμε το 15 με το 3 και γράφουμε από κάτω το πηλίκο, που είναι το 5.

👣 Βήμα 8. Το 5 τώρα δεν διαιρείται με το 3. Πηγαίνουμε στον επόμενο πρώτο αριθμό, που είναι το 5.

👣 Βήμα 9. Το 5 προφανώς διαιρείται με το 5. Γράφουμε από κάτω το πηλίκο, που είναι το 1.

👣 Βήμα 10. Μόλις βρούμε πηλίκο το 1, η διαδικασία τελειώνει!

👣 Τελευταίο βήμα: Γράφουμε τον αριθμό 360 ως το γινόμενο των πρώτων αριθμών που έχουμε γράψει στην τελευταία στήλη:

360 = 2 · 2 · 2 · 3 · 3 · 5 = 2^3 · 3^2 · 5 

 

 👉Περισσότερα παραδείγματα μπορείτε να παρακολουθήσετε σε αυτό το βίντεο.

 

Εφαρμογές των πρώτων αριθμών στην Κρυπτογραφία

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

Οι επιστήμονες του χώρου χρησιμοποιούν κατά κόρον φυσικούς αριθμούς που είναι γινόμενο τεράστιων πρώτων αριθμών. Ας πάρουμε για παράδειγμα τον αλγόριθμο RSA, ο οποίος χρησιμοποιεί δύο μεγάλους πρώτους αριθμούς p και q. Αφού τους πολλαπλασιάσει, χρησιμοποιεί το γινόμενό τους n = p · q ως μέρος των κλειδιών κρυπτογράφησης και αποκρυπτογράφησης. Ο αριθμός n είναι δημόσιος και ονομάζεται «δημόσιο κλειδί», είναι δηλαδή, όχι μόνο γνωστός, αλλά και δημοσιευμένος σε κάποιο βιβλίο ανάλογο του τηλεφωνικού καταλόγου. Για να μπορέσει κανείς να «χακάρει» ένα σύστημα, θα πρέπει να έχει βρει την πρωτογενή ανάλυση του n, δηλαδή θα πρέπει να υπολογίσει τους πρώτους αριθμούς p και q από τους οποίους «αποτελείται». Στην πράξη, αυτοί οι πρώτοι αριθμοί έχουν τόσο πολλά ψηφία που, ακόμη και με χρήση υπολογιστικών συστημάτων τελευταίας τεχνολογίας που δουλεύουν νυχθημερόν, χρειάζονται δεκάδες χρόνια προκειμένου να υπολογιστούν!

❓Άραγε, η ανάπτυξη υπερσύγχρονης τεχνολογίας θα «προλάβει» τις εξελίξεις στην έρευνα της Θεωρίας Αριθμών;

Το πρόβλημα των τεσσάρων χρωμάτων

 

Το πρόβλημα των τεσσάρων χρωμάτων (four-color problem), είναι ένα "πολύχρωμο" πρόβλημα, που είναι πολύ εύκολο να εξηγηθεί και να κατανοηθεί, αλλά η πολύπλοκη απόδειξή του, που συνάρπαζε και απογοήτευε γενιές μαθηματικών, εξακολουθεί να προκαλεί τη μαθηματική κοινότητα, καθώς είναι το πρώτο θεώρημα στην ιστορία που αποδείχτηκε με χρήση ηλεκτρονικού υπολογιστή. Σε αυτή την ανάρτηση θα μάθουμε περί τίνος πρόκειται...

Παράδειγμα χάρτη χρωματισμένου με τέσσερα χρώματα

Ένα από τα μεγάλα επεισόδια στην ιστορία των μαθηματικών ξεκίνησε στις 23 Οκτωβρίου 1852. Σε μια επιστολή του προς τον Sir William Rowan Hamilton, ο Augustus De Morgan έγραψε: «Ένας μαθητής μου ζήτησε σήμερα να του εξηγήσω ένα γεγονός που δεν ήξερα ότι ήταν γεγονός -και δεν το ξέρω ακόμα».

Μέχρι σήμερα, αυτό το "γεγονός" συνεχίζει να συναρπάζει και να προκαλεί τους μελετητές. Ο φοιτητής ήταν ο Frederick Guthrie και το εν λόγω "γεγονός" προερχόταν αρχικά από τον αδελφό του, Francis. Αφού εξέτασε έναν χάρτη των βρετανικών κομητειών, αναρωτήθηκε αν ήταν πάντα δυνατό να χρωματιστεί ένας χάρτης χρησιμοποιώντας 4 ή λιγότερα χρώματα, διασφαλίζοντας ταυτόχρονα ότι οι περιοχές που έχουν κοινά σύνορα (περισσότερα από ένα γωνιακό σημείο) έχουν διαφορετικά χρώματα.

Φαινόταν ότι αυτό θα έπρεπε να είναι πάντα εφικτό. «Όσο περισσότερο το σκέφτομαι τόσο πιο προφανές φαίνεται», έγραψε ο De Morgan. Παρόλα αυτά, το πρόβλημα δεν ενθουσίασε τον Hamilton και οι προσπάθειες του De Morgan να προσελκύσει το ενδιαφέρον άλλων ερευνητών απέτυχαν επίσης.

Σύμφωνα με το Θεώρημα των τεσσάρων χρωμάτων, απαιτούνται τέσσερα χρώματα για να χρωματίσετε τη Δυτική Βιρτζίνια, την Πενσυλβάνια, το Οχάιο, το Κεντάκι, τη Βιρτζίνια και το Μέριλαντ -τρία για τους γείτονες της Δυτικής Βιρτζίνια και ένα τέταρτο για την ίδια τη Δυτική Βιρτζίνια.

Το πρόβλημα έμεινε σε αδράνεια μέχρι το 1878, όταν ο Arthur Cayley ρώτησε τα μέλη της Μαθηματικής Εταιρείας του Λονδίνου αν κάποιος είχε βρει μια απόδειξη. Αμέσως μετά, άρχισαν να εμφανίζονται αποδείξεις. Η πρώτη, του δικηγόρου Alfred Kempe το 1879, ήταν αυτή που αποδείχθηκε η πιο σημαντική. Η απόδειξη ήταν πειστική και έγινε αποδεκτή ως σωστή για πάνω από μια δεκαετία. Δυστυχώς, η απόδειξη του Kempe -όπως και όλες οι άλλες που θα εμφανίζονταν τον επόμενο αιώνα- ήταν λανθασμένη. Ωστόσο, ήταν έξυπνη και περιείχε βασικές ιδέες που θα εμφανίζονταν στην τελική απόδειξη.

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

Για να κατανοήσουμε πώς ο Kempe και οι περισσότεροι μαθηματικοί έχουν δει αυτό το πρόβλημα, βοηθά να αναγνωρίσουμε ότι ένας χάρτης περιέχει πολλές πληροφορίες άσχετες με το πρόβλημα του χρωματισμού, όπως το σχήμα, το μέγεθος και την ακριβή θέση κάθε περιοχής. Το μόνο που έχει σημασία είναι ποιες περιοχές έχουν κοινά σύνορα, αν και απαιτούμε όλες οι περιοχές να συνδέονται μεταξύ τους -το Μίσιγκαν, με την ξεχωριστή άνω χερσόνησο, δεν εμποδίζει στην πραγματικότητα τον χάρτη των ΗΠΑ να είναι τετράχρωμος, αλλά θα μπορούσε, μαθηματικά.

Με αυτόν τον τρόπο, το πρόβλημα χρωματισμού χαρτών μετατρέπεται σε πρόβλημα χρωματισμού γραφημάτων: Χρωματίστε τις κορυφές έτσι ώστε οι γείτονες να έχουν διαφορετικό χρώμα. Ο ελάχιστος αριθμός χρωμάτων ονομάζεται χρωματικός αριθμός του γραφήματος. Μπορούμε να ρωτήσουμε για τον χρωματικό αριθμό οποιουδήποτε γραφήματος, αλλά τα γραφήματα που προέρχονται από χάρτες έχουν ειδικές ιδιότητες. Αυτά τα γραφήματα είναι απλά, δηλαδή δεν υπάρχουν ακμές που αρχίζουν και τελειώνουν στην ίδια κορυφή (που ονομάζονται βρόχοι) και δύο κορυφές μπορούν να ενωθούν μόνο με μία άκρη. Το γράφημα είναι επίσης επίπεδο, δηλαδή μπορεί να σχεδιαστεί έτσι ώστε να μην διασταυρώνονται ακμές.

Ένα πρόβλημα χρωματισμού χαρτών μπορεί να μετατραπεί σε πρόβλημα χρωματισμού γραφημάτων.

Μπορούμε τώρα να επαναδιατυπώσουμε το πρόβλημα του Francis Guthrie: Αποδείξτε ότι ο χρωματικός αριθμός κάθε απλού επίπεδου γραφήματος είναι το πολύ 4. Ακολουθεί ένα περίγραμμα του επιχειρήματος του Kempe, που περιγράφεται με σύγχρονους όρους χρησιμοποιώντας γραφήματα αντί για χάρτες. Ξεκίνησε παρατηρώντας ότι ένα γράφημα με μία κορυφή -ίσως ο χάρτης να είναι ένα μοναχικό νησί- απαιτεί μόνο ένα χρώμα. Στη συνέχεια χρησιμοποίησε ένα έξυπνο επιχείρημα για να χτίσει από εκεί και πέρα προς τα πάνω, υποστηρίζοντας ότι είναι δυνατόν να χρησιμοποιηθούν το πολύ τέσσερα χρώματα για να χρωματιστεί ένα γράφημα με δύο κορυφές, μετά τρεις κορυφές και ούτω καθεξής. Ορίστε πώς: Ας υποθέσουμε ότι μπορούμε να χρωματίσουμε όλα τα απλά επίπεδα γραφήματα με n κορυφές με το πολύ τέσσερα χρώματα —αυτό είναι ασήμαντο για n μικρότερο από 5— και τότε μας δίνεται ένα γράφημα με n+1 κορυφές. Πώς μπορούμε να δείξουμε ότι και αυτό θα χρωματίζεται το πολύ με τέσσερα χρώματα;

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

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

Εάν αφαιρέσουμε αυτήν την κορυφή και όλες τις άκρες που συνδέονται με αυτήν, αφήνουμε πίσω μας ένα γράφημα με n κορυφές —το οποίο ήδη γνωρίζουμε ότι μπορεί να χρωματιστεί χρησιμοποιώντας 4 χρώματα. Στην πραγματικότητα το κάνουμε ως το επόμενο βήμα. Τώρα, κοιτάξτε τις κορυφές δίπλα στην κορυφή που αφαιρέσατε. Εάν εμφανίζουν 3 ή λιγότερα χρώματα, μπορούμε να χρωματίσουμε την κορυφή που αφαιρέθηκε με ένα από τα υπόλοιπα χρώματα και τελειώσαμε: Μόλις δείξαμε ότι το γράφημα με n+1 κορυφές μπορεί να χρωματιστεί με 4 χρώματα. Και αν οι γειτονικές κορυφές περιλαμβάνουν και τα 4 χρώματα, ο Kempe επινόησε μια έξυπνη μέθοδο επαναχρωματισμού ορισμένων κορυφών για να ελευθερώσει ένα χρώμα για την κορυφή που αφαιρέθηκε, δείχνοντας πάλι ότι το γράφημα με n+1 κορυφές χρειάζεται μόνο 4 χρώματα.

Το 1890, ο μαθηματικός Percy Heawood εντόπισε το λάθος του Kempe. Υπήρχε μια ειδική περίπτωση στην οποία η έξυπνη μέθοδος του Kempe απέτυχε. Ο Heawood παρατήρησε ότι, αν και η δική του εργασία φαινόταν " μάλλον καταστροφική παρά εποικοδομητική", έδειξε ότι η τεχνική του Kempe μπορούσε να αποδείξει ότι κάθε χάρτης μπορεί να χρωματιστεί με 5 ή λιγότερα χρώματα - όχι όπως ακριβώς ο αρχικός στόχος, αλλά και πάλι εντυπωσιακός.

Ο Heawood διερεύνησε επίσης χάρτες που σχεδιάστηκαν σε πιο περίπλοκες επιφάνειες. Απέδειξε ότι ένας χάρτης σε ένα ντόνατ με g τρύπες μπορεί να χρειαστεί \( \frac{1}{2} \big( 7+\sqrt{1+48g} \big) \)   χρώματα (όπου αυτή η τιμή στρογγυλοποιείται στον πλησιέστερο ακέραιο). Όμως, σύμφωνα με αυτό που είχε αρχίσει να γίνεται συνήθεια, η απόδειξή του για τις γενικές επιφάνειες ήταν ελλιπής, και δεν είχαμε μια πλήρη απόδειξη μέχρι το 1968.

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

Αλλά ακόμη και όταν αποδείχθηκε το θεώρημα του Heawood για γενικές επιφάνειες, το πρόβλημα των τεσσάρων χρωμάτων παρέμεινε άλυτο. Χάρη σε δεκαετίες σκληρής δουλειάς, όμως, η απόδειξη ήταν ορατή. Σε ένα συνέδριο το 1976, 124 χρόνια αφότου ο Guthrie έθεσε το πρόβλημα, ο Wolfgang Haken ανακοίνωσε μια απόδειξη σε συνεργασία με τον Kenneth Appel και με τη βοήθεια του μεταπτυχιακού φοιτητή John Koch. Οι αντιδράσεις ήταν ανάμεικτες. "Περίμενα ότι το ακροατήριο θα ξεσπούσε σε ένα μεγάλο χειροκρότημα", έγραψε ο Don Albers, ο οποίος ήταν παρών στην ομιλία. "Αντίθετα, απάντησαν με ευγενικό χειροκρότημα!" Αυτό συνέβη επειδή η ομάδα, αντί να παράγει ένα επιχείρημα με μολύβι και χαρτί, βασίστηκε σε μεγάλο βαθμό σε έναν υπολογιστή.

Δεν έβαλαν μια μηχανή να απαντήσει άμεσα στο ερώτημα, καθώς είναι δυνατά άπειρα επίπεδα γραφήματα και ένας υπολογιστής δεν μπορεί να τα ελέγξει όλα. Ωστόσο, όπως ο Kempe απέδειξε ότι κάθε γράφημα περιέχει μία από έξι ειδικές διαμορφώσεις κορυφών, οι Appel και Haken έδειξαν ότι κάθε γράφημα πρέπει να έχει μία από 1.936 ειδικές διαμορφώσεις. Η απόδειξη του θεωρήματος ισοδυναμεί με το να δείξουμε ότι χρειαζόμαστε μόνο τέσσερα χρώματα για να χρωματίσουμε οποιοδήποτε γράφημα που περιέχει αυτούς τους υπογράφους. Η διάσπαση των έξι ειδικών περιπτώσεων του Kempe σε 1.936 υποπεριπτώσεις τους έδωσε πιο λεπτομερή έλεγχο και έκανε κάθε περίπτωση ευκολότερο να ελεγχθεί -αν και ο συνολικός αριθμός ήταν πλέον πολύ μεγάλος για να μπορέσει ένας άνθρωπος να τον ελέγξει χωρίς βοήθεια. Στην πραγματικότητα, η ολοκλήρωση των υπολογισμών απαιτούσε πάνω από 1.000 ώρες εργασίας στον υπολογιστή.

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

Η απόδειξη του προβλήματος των τεσσάρων χρωμάτων ήταν, φυσικά, μόνο η αρχή της επανάστασης των υπολογιστών στα μαθηματικά. Το 1998 ο Thomas Hales χρησιμοποίησε έναν υπολογιστή για να αποδείξει την περίφημη εικασία του Johannes Kepler ότι ο πιο αποτελεσματικός τρόπος για να στοιβάζονται σφαίρες είναι αυτός που χρησιμοποιείται συνήθως για να στοιβάζονται πορτοκάλια σε ένα παντοπωλείο. Και πρόσφατα οι υπολογιστές βοήθησαν να βρεθεί ο "αριθμός του Θεού" - ο μέγιστος αριθμός στροφών που απαιτούνται για να λυθεί ένας κύβος του Ρούμπικ (20 στροφές ή 26 αν οι μισές στροφές μετράνε ως δύο). Αν και το πρόβλημα των τεσσάρων χρωμάτων για τους χάρτες έχει διευθετηθεί, πολλά βασικά ερωτήματα σχετικά με το χρωματισμό γραφημάτων παραμένουν αναπάντητα ή μόλις τώρα επιλύονται.

Η εργασία του Heawood με τις επιφάνειες έδειξε ότι μπορούμε να θέσουμε ερωτήματα χρωματικότητας για μη επίπεδα γραφήματα. Και στην πραγματικότητα, ο χρωματικός αριθμός ενός συγκεκριμένου γραφήματος δεν εξαρτάται από την επιφάνεια στην οποία σχεδιάζεται ο ισοδύναμος χάρτης. Για παράδειγμα, ένα γράφημα στον οποίο κάθε κορυφή συνδέεται με κάθε άλλη κορυφή ονομάζεται πλήρες γράφημα και ο χρωματικός αριθμός ενός πλήρους γραφήματος με n κορυφές είναι n. Έτσι, αν ένας μεγάλος γράφος (γράφημα) περιέχει έναν πλήρη γράφο με n κορυφές, τότε γνωρίζουμε ότι ο χρωματικός αριθμός του μεγάλου γραφήματος είναι τουλάχιστον n.

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

Η παρατήρηση αυτή δεν συνεπάγεται ότι αν ο χρωματικός αριθμός ενός γραφήματος είναι n, τότε περιέχει ένα πλήρες γράφημα με n κορυφές. Αλλά το 1943, ο Hugo Hadwiger υπέθεσε κάτι πολύ παρόμοιο. Πίστευε ότι αν ένα γράφημα χωρίς βρόχους έχει χρωματικό αριθμό n, τότε έχει μια διάταξη κορυφών που ονομάζεται K_n, όπου η διαγραφή ορισμένων κορυφών και ακμών και η ομαδοποίηση άλλων οδηγεί σε ένα πλήρες γράφημα με n κορυφές. Αναδιατυπωμένη, αυτή η εικασία δηλώνει ότι αν ένα γράφημα δεν έχει ένα δευτερεύον K_n, τότε μπορεί να χρωματιστεί με λιγότερα από n χρώματα. Η εικασία του Hadwiger, ένα από τα σημαντικότερα ανοιχτά προβλήματα στη θεωρία γραφημάτων, γενικεύει το θεώρημα των τεσσάρων χρωμάτων, καθώς ένα επίπεδο γράφημα δεν μπορεί να περιέχει έναK₅ minor.

Αν και ο χρωματισμός γραφημάτων ξεκίνησε με ένα ερώτημα στη χαρτογραφία, προβλήματα που δεν έχουν καμία σχέση με χάρτες ή χρώματα μπορούν επίσης να ενταχθούν στο πλαίσιο του χρωματισμού γραφημάτων. Για παράδειγμα, το sudoku είναι ένα πρόβλημα χρωματισμού γραφήματος μεταμφιεσμένο. Δείτε κάθε κελί ως κορυφή και τα εννέα ψηφία ως χρώματα. Κάθε κορυφή έχει 20 ακμές που βγαίνουν από αυτήν -μία προς κάθε κελί στη σειρά, στη στήλη και στο υποτετράγωνο 3x3. Αυτός ο γράφος με 81 κορυφές και 810 ακμές ξεκινά με έναν μερικό χρωματισμό (τις δεδομένες ενδείξεις). Το αντικείμενο του παιχνιδιού είναι να χρωματίσετε τις υπόλοιπες κορυφές.

Το Sudoku μπορεί να θεωρηθεί ως ένα πρόβλημα χρωματισμού γραφημάτων.

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

Ο μαθηματικός Paul Erdös συνήθιζε να μιλάει για το "The Book" -έναν φανταστικό τόμο που περιέχει τις πιο κομψές αποδείξεις κάθε θεωρήματος. Αναρωτιέται κανείς αν το "The Book" περιέχει μια αναγνώσιμη από τον άνθρωπο απόδειξη του θεωρήματος των τεσσάρων χρωμάτων, και αν ναι, αν θα τη δούμε ποτέ...

 

Πηγή: Quanta Magazine

Το Θεμελιώδες Θεώρημα του Απειροστικού Λογισμού

Τα ολοκληρώματα έχουν κάνει αισθητή την απουσία τους στα χρόνια του covid-19. To 2020 βγήκαν από την εξεταστέα ύλη των Πανελλαδικών, αν και πολλοί τυχεροί μαθητές είχαν προλάβει να τα διδαχθούν. Φέτος όμως βγήκαν πολύ νωρίς εκτός της διδακτέας ύλης. Λίγο πριν αρχίσουν λοιπόν οι φετινές Πανελλαδικές εξετάσεις, θέλω να αποτίσω έναν μικρό φόρο τιμής σε αυτά τα όμορφα μαθηματικά αντικείμενα και να παρουσιάσω το Θεμελιώδες Θεώρημα του Απειροστικού Λογισμού, μέσα από ένα βιβλίο που, όσο και να το μελετήσεις, ποτέ δεν είναι αρκετό!

Πηγή: Απειροστικός Λογισμός II, Σ.Κ. Ντούγιας, Leader Books, 2005

Ο τύπος ⭑ είναι γνωστός ως τύπος των Newton-Leibniz και δείχνει τη σχέση που υπάρχει μεταξύ του ορισμένου και του αόριστου ολοκληρώματος. 

Με το παρακάτω πόρισμα, που είναι άμεση συνέπεια του Θεμελιώδους Θεωρήματος του Απειροστικού Λογισμού, παίρνουμε μια μέθοδο υπολογισμού του ορισμένου ολοκληρώματος.

Πηγή: Απειροστικός Λογισμός II, Σ.Κ. Ντούγιας, Leader Books, 2005

*~∞~*~∞~*~∞~*

Αφιερωμένο στους μαθητές μου.

Εύχομαι καλή επιτυχία σε όλα τα παιδιά!!!

*~∞~*~∞~*~∞~*

"Amat victoria curam" ("Η νίκη αγαπά την προετοιμασία").

Gaius Victorius Catullus (1ος αιώνας π.Χ.) 

Πώς προέκυψαν τα Κριτήρια Διαιρετότητας σύνθετων αριθμών;

Διαβάσαμε στα Κριτήρια Διαιρετότητας των αριθμών από το 1 ως το 18 και των αριθμών από το 19 ως το 32 πώς ελέγχουμε αν ένας αριθμός διαιρείται με καθέναν από τους αριθμούς 1 έως και 32. Για αρκετούς από αυτούς τους αριθμούς, το κριτήριο διαιρετότητας προέκυψε άμεσα και αβίαστα, καθώς από πίσω "κρύβεται" το παρακάτω θεώρημα της Θεωρίας Αριθμών, μαζί με το πόρισμά του:

Θεώρημα

Αν Μ.Κ.Δ.(b,c)=1, τότε Μ.Κ.Δ.(a,bc) = Μ.Κ.Δ.(a,b)*Μ.Κ.Δ.(a,c)

Πόρισμα
Αν οι αριθμοί b και c, με Μ.Κ.Δ.(b,c)=1, διαιρούν τον a, τότε και  το γινόμενό τους bc διαιρεί επίσης τον a.

Δηλαδή, αν ένας αριθμός a διαιρείται από δύο αριθμούς b και c οι οποίοι είναι πρώτοι μεταξύ τους, τότε διαιρείται και από το γινόμενο των b και c.

Σελίδα από το χειρόγραφο βιβλίο του Φυραρίδη Ανέστη (1998), Θεωρία Αριθμών, Πανεπιστημιακό Τυπογραφείο Ιωαννίνων (Επανέκδοση 2007)

Το παραπάνω πόρισμα γενικεύεται και για περισσότερους από δύο αριθμούς:

Αν οι ακέραιοι b₁, b₂, ... b_n είναι πρώτοι μεταξύ τους ανά δύο και ο καθένας τους διαιρεί τον a, τότε και το γινόμενό τους  

b₁b₂…b_n  

διαιρεί επίσης τον a.   


Από το παραπάνω πόρισμα προκύπτει ένα σημαντικό και εύχρηστο Κριτήριο Διαιρετότητας για σύνθετους αριθμούς. Αρκεί ο σύνθετος αριθμός να μπορεί να γραφεί ως γινόμενο δύο ή περισσότερων αριθμών που είναι πρώτοι μεταξύ τους ανά δύο.


Παραδείγματα

1. Είδαμε εδώ ότι ένας αριθμός διαιρείται με το 6 αν διαιρείται ταυτόχρονα με το 2 και το 3. Αυτό ισχύει σύμφωνα με το παραπάνω πόρισμα, αφού 6 = 2*3 και Μ.Κ.Δ.(2,3)=1.

2. Για να εξετάσουμε αν ένας αριθμός διαιρείται με το 12, αρκεί να εξετάσουμε αν διαιρείται ταυτόχρονα με το 3 και το 4. Αυτό ισχύει σύμφωνα με το παραπάνω πόρισμα, αφού 12 = 3*4 και Μ.Κ.Δ.(3,4)=1.
Προσοχή! Για να εξετάσουμε αν ένας αριθμός διαιρείται με το 12, γράφουμε το 12 ως 12 = 3*4 γιατί οι αριθμοί 3 και 4 είναι πρώτοι μεταξύ τους και όχι 12 = 2*6, αφού οι αριθμοί 2 και 6 δεν είναι πρώτοι μεταξύ τους. Για παράδειγμα, ο αριθμός 18 διαιρείται ταυτόχρονα από το 2 και από το 6. Δεν διαιρείται όμως και από το 12.

3. Είδαμε εδώ ότι ένας αριθμός διαιρείται με το 30 αν διαιρείται ταυτόχρονα με το 3 και το 10, δηλαδή αν τελειώνει σε 0 και το άθροισμα των ψηφίων του διαιρείται με το 3. Αυτό επίσης βασίζεται στο ανωτέρω πόρισμα, καθώς 30=3*10 και Μ.Κ.Δ.(3,10)=1. Εναλλακτικά, θα μπορούσαμε να πούμε ότι 30=5*6 και Μ.Κ.Δ.(5,6)=1. Επομένως, για να εξετάσουμε αν ένας αριθμός διαιρείται με το 30, αρκεί να εξετάσουμε αν διαιρείται ταυτόχρονα με το 5 και το 6. Ο έλεγχος αυτός όμως θα ήταν λίγο πιο χρονοβόρος, μιας και το κριτήριο διαιρετότητας του 6 απαιτεί να ελέγξουμε αν ο αριθμός διαιρείται ταυτόχρονα με το 2 και το 3.

Και δηλαδή αυτό το πόρισμα μας έχει λύσει τα χέρια; Ισχύει για κάθε σύνθετο αριθμό;

• Για το 8, το 16, το 27 ή το 32 δεν μπορεί να εφαρμοστεί αυτή η μέθοδος, αφού κανένας τους δεν μπορεί να γραφεί ως γινόμενο δύο ή περισσότερων αριθμών που είναι πρώτοι μεταξύ τους ανά δύο. Για την εύρεση των Κριτηρίων Διαιρετότητας των αριθμών αυτών, ακολουθήθηκε άλλο μονοπάτι...

Ο Gowers χρωματίζει αριθμούς...

Ο Timothy Gowers είναι ένας από τους σπουδαιότερους εν ζωή μαθηματικούς, ο οποίος για την έρευνά του που συνέδεσε τη Συναρτησιακή Ανάλυση με τη Συνδυαστική, κέρδισε το 1998 το μετάλιο Fields. Στο βίντεο που ανέβηκε σήμερα στο YouTube από το κανάλι Numberphile, o Gowers εξηγεί το Θεώρημα Van der Waerden από τη Θεωρία Ramsey της Συνδυαστικής, χρωματίζοντας αριθμούς... Αξίζει να το δείτε!

Το Θεώρημα Van der Waerden

Για οποιουσδήποτε θετικούς ακεραίους r και k υπάρχει θετικός ακέραιος Ν τέτοιος, ώστε αν οι ακέραιοι {1, 2, ... , Ν} χρωματιστούν, ο καθένας με r διαφορετικά χρώματα, τότε θα υπάρχουν τουλάχιστον k ακέραιοι, όροι αριθμητικής προόδου, της οποίας οι όροι είναι του ίδιου χρώματος.
Ο ελάχιστος τέτοιος Ν ονομάζεται αριθμός Van der Waerden.

Τουλάχιστον μία λύση...

Το Θεώρημα του Bolzano

Έστω μια συνάρτηση f, ορισμένη σ' ένα κλειστό διάστημα [α, β]. Αν ισχύουν τα εξής:

• η f είναι συνεχής στο [α, β] και
• f(α)⋅f(β) < 0,

τότε υπάρχει ένα τουλάχιστον x₀ στο ανοιχτό διάστημα (α, β) τέτοιο, ώστε

f(x₀) = 0  

Δηλαδή το Θεώρημα Bolzano μας εξασφαλίζει ότι υπάρχει μία τουλάχιστον λύση της εξίσωσης f(x) = 0 στο ανοιχτό διάστημα (α, β).