Brilliant Induction – Η δύναμη της μαθηματικής επαγωγής

Η μαθηματική επαγωγή είναι ένα από τα πιο κομψά και ισχυρά εργαλεία της μαθηματικής απόδειξης. Στην απλή της μορφή, θέλουμε να δείξουμε ότι μια πρόταση ισχύει για κάθε θετικό ακέραιο $n$. Ξεκινάμε αποδεικνύοντας την πρόταση για $n=1$ και στη συνέχεια δείχνουμε ότι αν ισχύει για κάποιο $n-1$, τότε ισχύει και για το $n$.

Μια πιο γενική εκδοχή χρησιμοποιεί την υπόθεση της επαγωγής (γνωστή και ως “IHOP”), ενώ ακόμη πιο ισχυρή διατύπωση βασίζεται στην ελάχιστη κακή περίπτωση: υποθέτουμε ότι υπάρχει ένα ελάχιστο n για το οποίο η πρόταση είναι ψευδής και αποδεικνύουμε ότι οδηγούμαστε σε αντίφαση. Έτσι καταλήγουμε ότι δεν υπάρχει κανένα τέτοιο n.

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

🔹 Πρόβλημα:
Μπορεί για κάθε θετικό ακέραιο $n$ να υπάρξει μια πεπερασμένη διάταξη σημείων στο επίπεδο με την ιδιότητα ότι κάθε σημείο απέχει απόσταση 1 ακριβώς από $n$ άλλα σημεία της διάταξης;

Το πρόβλημα αυτό συνδέεται με τη θεωρία των γεωμετρικών γραφημάτων και περιστρέφεται γύρω από το πόσα σημεία μπορούμε να τοποθετήσουμε έτσι ώστε το πλήθος των γειτόνων σε απόσταση 1 ανά σημείο να είναι συγκεκριμένο. Για μικρές τιμές n είναι εύκολο να βρεθούν τέτοιες διατάξεις, όμως για μεγαλύτερες τιμές υπάρχουν θεωρητικά όρια που σχετίζονται με γνωστά γεωμετρικά προβλήματα, όπως το «πρόβλημα του kissing number» στο επίπεδο.