Το πρόβλημα των 36 αξιωματικών
Δημοσιεύτηκε: Παρ Δεκ 09, 2011 4:40 am
Αναζητώντας κάτι άλλο έπεσα από λαθροτυχία (serendipity!) σε άρθρο των New York Times (26 Απριλίου 1959) και στην ακόλουθη μαθηματική ιστορία:
Κατα το σωτήριον έτος 1782, όταν ο Leonhard Euler βρισκόταν στην Αγία Πετρούπολη, θέλησε κάποιος αυλικός του Τσάρου να τοποθετήσει
αξιωματικούς 
διαφορετικών βαθμών και διαφορετικών μονάδων σε ένα 
τετράγωνο ... έτσι ώστε σε κάθε γραμμή και σε κάθε στήλη να μην υπάρχει επανάληψη βαθμού και να μην υπάρχει επανάληψη μονάδας. [Μία προφανής παραλλαγή του προβλήματος θα ήταν η τοποθέτηση 
ζαριών διαφορετικών χρωμάτων έτσι ώστε σε κάθε γραμμή και σε κάθε στήλη να μην υπάρχει επανάληψη ούτε χρώματος ούτε αριθμού.] Ζητήθηκε η βοήθεια του μεγάλου μαθηματικού, ο οποίος δεν κατάφερε να λύσει το πρόβλημα: επειδή όμως το έλυσε στην γενική του μορφή για αριθμούς διάφορους του 
... είκασε ότι το πρόβλημα ΔΕΝ έχει λύση για κανένα τετράγωνο της μορφής 
. [Ας παρατηρηθεί εδώ ότι προφανώς δεν υπάρχει λύση για το 
τετράγωνο (εύκολη άσκηση).]
Η εικασία αυτή του Euler (που έγινε έναν περίπου χρόνο πριν πεθάνει) καταρρίφθηκε το 1959 (δείτε και εδώ), και αυτό είναι το θέμα του παραπάνω άρθρου των New York Times: ακριβέστερα, υπάρχει λύση για κάθε
τετράγωνο, εκτός και αν 
(κάτι που ήταν ήδη γνωστό από το 1901, δικαιώνοντας μερικώς τον Euler) ή 
. Μία από τις πιο ενδιαφέρουσες πληροφορίες του άρθρου είναι η αποτυχία των ηλεκτρονικών υπολογιστών να βρουν λύση για 
και η εκτίμηση των ειδικών ότι ο τότε καλύτερος υπολογιστής θα χρειάζονταν 100 χρόνια μόνο για την περίπτωση αυτή!
Δεν γνωρίζω πόσο εύκολα μπορεί να προκύψει η μη ύπαρξη λύσης για, η απόδειξη πάντως του 1901 (από τον Gaston Tarry) πιάνει 34 σελίδες...
Γιώργος Μπαλόγλου
Κατα το σωτήριον έτος 1782, όταν ο Leonhard Euler βρισκόταν στην Αγία Πετρούπολη, θέλησε κάποιος αυλικός του Τσάρου να τοποθετήσει
αξιωματικούς διαφορετικών βαθμών και διαφορετικών μονάδων σε ένα τετράγωνο ... έτσι ώστε σε κάθε γραμμή και σε κάθε στήλη να μην υπάρχει επανάληψη βαθμού και να μην υπάρχει επανάληψη μονάδας. [Μία προφανής παραλλαγή του προβλήματος θα ήταν η τοποθέτηση ζαριών διαφορετικών χρωμάτων έτσι ώστε σε κάθε γραμμή και σε κάθε στήλη να μην υπάρχει επανάληψη ούτε χρώματος ούτε αριθμού.] Ζητήθηκε η βοήθεια του μεγάλου μαθηματικού, ο οποίος δεν κατάφερε να λύσει το πρόβλημα: επειδή όμως το έλυσε στην γενική του μορφή για αριθμούς διάφορους του ... είκασε ότι το πρόβλημα ΔΕΝ έχει λύση για κανένα τετράγωνο της μορφής . [Ας παρατηρηθεί εδώ ότι προφανώς δεν υπάρχει λύση για το τετράγωνο (εύκολη άσκηση).]Η εικασία αυτή του Euler (που έγινε έναν περίπου χρόνο πριν πεθάνει) καταρρίφθηκε το 1959 (δείτε και εδώ), και αυτό είναι το θέμα του παραπάνω άρθρου των New York Times: ακριβέστερα, υπάρχει λύση για κάθε
τετράγωνο, εκτός και αν (κάτι που ήταν ήδη γνωστό από το 1901, δικαιώνοντας μερικώς τον Euler) ή . Μία από τις πιο ενδιαφέρουσες πληροφορίες του άρθρου είναι η αποτυχία των ηλεκτρονικών υπολογιστών να βρουν λύση για και η εκτίμηση των ειδικών ότι ο τότε καλύτερος υπολογιστής θα χρειάζονταν 100 χρόνια μόνο για την περίπτωση αυτή!Δεν γνωρίζω πόσο εύκολα μπορεί να προκύψει η μη ύπαρξη λύσης για
, η απόδειξη πάντως του 1901 (από τον Gaston Tarry) πιάνει 34 σελίδες...Γιώργος Μπαλόγλου
]