Ένα έξυπνο πρόβλημα συνδυαστικής λογικής από τον Ρώσο μαθηματικό Βίκτορ Πρασόλοφ που ανατρέπει τη διαίσθησή μας!
Μερικά προβλήματα φαίνονται απλά, αλλά κρύβουν μια μαθηματική παγίδα που τα κάνει ιδιοφυή. Το παρακάτω ερώτημα από τον διακεκριμένο μαθηματικό Βίκτορ Πρασόλοφ είναι ένα τέτοιο παράδειγμα:
Είναι δυνατόν να ζωγραφίσουμε 25 κελιά σε ένα τετραγωνισμένο χαρτί, έτσι ώστε το καθένα να έχει περιττό αριθμό γειτονικών ζωγραφισμένων κελιών;Δοκιμάστε πρώτα να το σκεφτείτε — και μετά διαβάστε τη μαθηματική ερμηνεία που κρύβεται πίσω από την (απροσδόκητη) απάντηση!
📐 Κατανόηση του προβλήματος:
-
Έχουμε ένα τετραγωνισμένο πλέγμα (grid).
-
Επιλέγουμε 25 κελιά για να τα ζωγραφίσουμε.
-
Θέλουμε κάθε ζωγραφισμένο κελί να έχει περιττό αριθμό γειτόνων που είναι επίσης ζωγραφισμένοι.
-
Οι γείτονες είναι μόνο όσοι έχουν κοινή πλευρά (όχι διαγώνιο).
🔍 Ανάλυση με βάση τη θεωρία γράφων:
Ας μετατρέψουμε την εικόνα σε έναν απλό άγραφτο γράφο:
-
Κάθε ζωγραφισμένο κελί = μια κορυφή.
-
Αν δύο ζωγραφισμένα κελιά είναι γειτονικά, συνδέονται με ακμή.
-
Ο αριθμός γειτονικών ζωγραφισμένων κελιών είναι ο βαθμός της κορυφής.
➡️ Άρα το πρόβλημα γίνεται:
Υπάρχει γράφος με 25 κορυφές, ώστε κάθε κορυφή να έχει περιττό βαθμό;
🧠 Το θεώρημα που δίνει την απάντηση:
Το Θεώρημα των Χειραψιών (Handshaking Lemma) λέει:
Το άθροισμα των βαθμών όλων των κορυφών σε έναν γράφο είναι άρτιος αριθμός (γιατί κάθε ακμή μετριέται δύο φορές, μία από κάθε άκρο της).
Αλλά...
-
Αν έχουμε 25 κορυφές με περιττό βαθμό, τότε το άθροισμα είναι το άθροισμα 25 περιττών αριθμών → περιττός αριθμός!
🎯 Αντίφαση! Δεν μπορεί το άθροισμα να είναι ταυτόχρονα περιττό (από τις συνθήκες) και άρτιο (από το θεώρημα).
✅ Συμπέρασμα:
Δεν είναι δυνατόν να ζωγραφίσουμε 25 κελιά έτσι ώστε το καθένα να έχει περιττό αριθμό ζωγραφισμένων γειτονικών κελιών.
Μια απλή, φαινομενικά αθώα ερώτηση μάς οδηγεί σε μια βαθιά αλήθεια της θεωρίας γράφων — και δείχνει τη δύναμη της μαθηματικής συνέπειας.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου