Προβληματισμοί

Η δυσκολία των προβλημάτων εκτιμάται με το σύστημα του Knuth  (βλ Τ.Α.Ο.C.P. είσαγωγή) με κλίμακα δυσκολίας 1-50. Βαθμό 50 δίνει ο Κnuth στο τελευταίο θεώρημα του Fermat (όταν ήταν ανοιχτό πρόβλημα) .
Tα προβλήματα δεν απαιτούνται προχωρημένα μαθηματικά  εκτός και αν αυτό δηλώνεται.
Ακολουθεί η αναδημοσιευσή ενός γνωστού προβλήματος (με καποια βοήθεια)

  Ιδέες για λύση, απείλες,χρηματικά έπαθλα κ.τ.λ. να στέλνονται adim@acm.org

Σοβαρότατες δυσκολίες φαίνεται να αντιμετωπίζει η Ελληνική (και διεθνής ) ακαδημαική κοινότητα απο το πρόβλημα του αμυγδαλόκηπου (που δημισιευτήκε στο περιοδικό Σynergy τευχος 0). Εξεταστικές περίοδοι χάθηκαν χωρίς καμία επιτυχία, κάποιοι επίκουροι καθηγητές παραιτήθηκαν για να έχουν τον απαραίτητο χρόνο να το μελετήσουν και ένας μεταπτυχιακός φοιτητής σε περιφεριακό πανεπιστήμιο συνελήθφη την στιγμή που κατέστρεφε με ανεξήγητη οργή τον αμυγδαλόκηπο του γείτονα του. Κάτω απο αυτές τις συνθήκες, αναδημοσιεύουμε το πρόβλημα σε σύντομη μορφή καθώς και κάποια ψήγματα βοηθείας.

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

Ιδού λοιπόν :

O Θησαυρός του αμυγδαλόκηπου (έκδοση διαίτης)

(Δυσκολία 35)

Έστω οτι επίλεγονται 2 ακεραιοι αριθμοί στο [3,100](χωρίς διάταξη).Υπολογίζεται το γινόμενο και το άθροισμα τους και δίνονται σε δύο ανθρώπους που, απο διαβολική σύμπτωση, ονομάζονται Κ.Γινόμενος και Ν.Άθροισμας.

Μεταξύ τους διαδραματίζεται ο εξής διάλογος:

-Γ:Δεν μπορώ να βρώ τους αριθμούς

-Α:Ούτε και εγώ,αλλα το ήξερα πως δεν θα μπορούσες

-Γ:Τώρα που μου το είπες αυτό μπορώ!

-Α:Αφού μπόρεσες και τους βρήκες, τους βρήκα και εγώ!

Φυσικά εσείς πρέπει να τους βρείτε χωρίς να διαθέτετε κανένα άλλο δεδομένο.

Διαφωτιστικό σχόλιο Νο1:Είναι φανερό πως υπάρχει μοναδικό ζευγος ακεραίων στο [3,100] για το οποίο θα μπορούσε να συμβεί ο δοσμένος διάλογος.Τόσο ο Γινόμενος όσο και ο Αθροισμάς αναλύουν τα

δεδομένα τους και κοιτούν μια λίστα απο πιθανά ζεύγη αριθμών.Καθε νέα πληροφορία έχει  σαν αποτέλεσμα ο αλλός να διαγράφει κάποια ζεύγη απο την λίστα του.Κάποιος βρίσκει τους αριθμούς αν διαγράψει ολές τις δυνατές επιλογές εκτός απο μια.Συνεπώς πρέπει να ερμηνευτεί τι πληροφορία δίνεται σε κάθε σημείο του διαλόγου απο τον έναν στον άλλο.

  Διαφωτιστικό σχόλιο Νο2:Αν και γενικά δεν απαιτούνται ειδικές μαθηματικές γνώσεις για την λύση του προβλήματος μια επανάληψη στο θεμελιώδες θεώρημα της αριθμοθεωρίας καθώς και στην εικασία του Goldbach ίσως βοηθήσει.Χρήση υπολογιστών (εξαντλητικών αλγορίθμων) μπορεί να γίνει αν και εμείς το λύσαμε και χωρίς Mathematica.

  Καλή αναζήτηση!

Τα κλειδιά του Bombe

(Δυσκολία 25 , Γενικευσή 30)

Το πρόβλημα αφηγείται ο Βλάσης Τζούλης

  Ο πατέρας μου ο Όμηρος Τζούλης γεννήθηκε το 1915. Έγινε δεκτός για σπουδές στα  μαθηματικό τμήμα του King's College, Cambridge το 1934. Σε ένα σεμινάριο του Max Newman πάνω στην μαθηματική λογική  γνώρισε τον σπουδαίο μαθηματικό και θεωρητικό της πληροφορικής Alan Mathison Turing. Ο πατέρας μου ενθουσιάστηκε απο τις προτοποριακές ιδέες του Turing, γρηγορα ομώς επεστρεψε στην μεγάλη μαθηματική του αγάπη την αριθμοθεωρία. Σας μεταφέρω την ιστορία για τα κλειδιά του Bombe όπως μου την είχε αφηγηθεί: “Όταν ξέσπασε ο πόλεμος, ένας φίλος μου μαθηματικός, ο W.G.Welchman ήρθε στο γραφείο μου μαζί με έναν άγνωστο, απρόσιτο άνθρωπο που συστήθηκε σαν αντισυντάγματαρχης Cornell.Ζήτησε την βοήθεια μου για ένα πολυ σημαντικό πρόγραμμα χωρίς όμως να μου δόσει περισσότερες πληροφορίες. Δεν μου μιλούσε με τον γνωστό μεταξυ μας τρόπο, ήταν φανερό πως το στρατιωτικό κλίμα τον είχε τρομοκρατήσει. Εγώ αρνήθηκα ευγενικά και του είπα πως επιθυμούσα να επιστρεψω στην πατρίδα για να μπορέσω να βοηθήσω τους δικούς μου ανθρώπους αν η Ελλάδα εμπλακεί στον πόλεμο. Μια απο τις επόμενες μέρες δυο νεαροί της στρατιωτικής αστυνομίας με επισκεύθηκαν στο γραφείο μου, μου ανακοίνωσαν πως μου είχε απαγορευθεί η έξοδος απο την χώρα και μου ζήτησαν να τους ακολουθήσω.

Με οδήγησαν στο Government Code and Cypher School στο Bletchley Park.Το κλίμα εκέι ήταν κάτι προτόγνωρο για εμένα.Στρατιωτικές φρουρές σε όλες τις εισόδους των κτιρίων, ακόμη και έξω απο μερικές πόρτες γραφείων.

Μπήκαμε σε ένα απο τα γραφεία που είχαν φρούρηση.Απο την πόρτα είχε ξυστεί το όνομα κάποιου εργαστηριού και εγραφε απλά "Bombe". Mέσα αναγνώρισαν τους  Turing και Welchman να είναι σκυμένοι πάνω απο κάτι που εμοιαζε με στατιστική ανάλυση. Ήξερα οτι τελικά θα σε επείθαν, είπε με τυπικό φλεγματικό χιούμορ ο Turing, καλοσηρθες στο Bletchley Park. Moυ εξήγησε πως σκοπός του προγράμματος ηταν η αποκρυπτογράφηση των μυνημάτων της Luftwaffe. Moυ μίλησε για το Enigma το κρυπτογραφικό μηχάνημα που χρησιμοποιούσαν οι Ναζί και το πώς θα μπορούσαν να αποκρυπτογραφήσουν τα μηνήματα του.Ηδη καποια βασική θεωρία είχε δημιουργηθεί απο Πολωνους μαθηματικούς. Έργαστικα και εγώ σκληρά μαζί τους και τελικά καταφέραμε να σχεδιάσουμε και να κατασκευάσουμε το θρυλικό Bombe, το μηχάνημα που τελικά έσωσε αμέτρητες ζωές στον πόλεμο. Οι ναζί είχαν καταλάβει πως έχουμε ενα ισχυρό όπλο ενάντια στο Enigma, δεν κατάφερναν όμως με τις παραμετρικές μεταβολές να μας καθυστερoύν αρκετά. Το σημαντικό ήταν που αυτοι δεν γνώριζαν με ποιόν μηχανισμό  αποκρυπτογραφούσαμε. Το 1941 ο Τυring με κάλεσε στο γραφείο του:Ηοmer, μου λεεί έχουμε ένα πρόβλημα. Γνωρίζεις πολύ καλά πως το Bombe είναι κλειδωμένο μαζί με τα σχέδια του και τις περιγραφές των αλγορίθμων στο ειδικό χρηματοκιβώτιο ασφαλέιας.Το πρόβλημα είναι πως υπάρχουν 5 Βρετανοί στρατηγοί πρέπει να έχουν πρόσβαση στο μηχάνημα όποτε το χρειάζονται για να αποσπασουν σημαντικές πληροφορίες.Ξερείς ομώς καλυτερα απο τον κάθε ένα πόσο ανασφαλές είναι να βγαίνει το μηχανημα απο το χρηματοκιβώτιο συνεχώς.Ηδη συλάβαμε αυτόν τον κατάσκοπο που είχε συστηθεί με το όνομα White και επιχείρησε να φωτογραφίσει το Bombe. Οι στρατηγοί αποφάσισαν το εξής: αν υπάρχουν 3 που ζητάνε το μηχανημα τοτε αυτο πρέπει να ξεκλειδώνει ενώ αν το ζητάνε λιγότεροι απο 3 πρέπει να περιμένουν.Φυσικά οι στρατηγοί ταξιδεύουν συνεχώς συντονίζοντας τις πολεμικές επιχειρήσεις και δεν είναι δυνατόν να έρχονται και καθε φορά όλοι στο Bletchley park για να ανοιξουν το χρηματοκιβώτιο κάθε φορά που το ζητάει μία τριάδα.Πρέπει συνεπώς κάθε τριάδα να έχει όλα τα κλειδία του χρηματοκιβωτίου.Χμμ του απάντησα.Πόσες κλειδαρίες έχει το χρηματοκιβώτιο?Ο κλειδαράς έιναι εδώ και περιμένει, μου ειπε, αρκεί να του πείς πόσες κλειδαριές χρειάζονται και πόσα αντικλείδια απο κάθε κλείδι και θα τα κατασκευάσει επι τόπου.Αν ήταν μόνο τρεις στρατηγοί θα ήταν εύκολο, του απανταώ: Θα βάζαμε 3 κλειδαρίες και τρια κλειδια (ΑΒΓ) και θα γίναμε στον κάθε στρατηγό απο δυο (ΑΒ,ΒΓ,ΓΑ) και έτσι κάθε δυάδα θα είχε και τα τρια κλειδιά ενώ κανένας μόνος του δεν θα είχε και τα τρία.Το καταλαβαίνεις το πρόβλημα Βλαση?" Αν και παιδί είχα καταλάβει το πρόβλημα και μου φαινόταν αρκετά απρόσιτο: Ποσα κλειδία θα έπρεπε να έχει το χρηματοκιβώτιο,και πώς  θα έπρεπε να μοιραστούν στους  στρατηγούς? Προσπάθησα να σκεφτώ αλλά  συνεχώς υπήρχε κάποια δυάδα που είχε όλα τα κλειδία η καποια τριάδα που της έλειπε κάποιο κλειδί. Θυμάμαι τον θαυμασμό μου προς τον πατέρα μου όταν μου είπε πως έλυσε το γενικό προβλημα (Ν στρατηγοί ,trunc(N/2)+1 να έχουν όλα τα κλειδία) σε μια νύχτα και μάλιστα με ελάχιστο αριθμό κλειδιών.Στο τέλος ο πατερας μου είπε "Θυμάμαι πως ο Turing είχε ενθουσιαστεί με αυτό το πρόβλημα και μου είχε πεί πως στο μέλλον, όταν η ειρήνη επικρατήσει ξανά, τέτοια προβλήματα θα εμφανίζονται πολύ πιο συχνά οταν όλοι θα είναι συνδεδεμένοι χρησιμοποιώντας κάποιες υλοποιήσεις των θεωρητικών μηχανων που είχε επινοήσει". Φυσικά δεν κατάλαβα τιποτέ για το τι ενοούσε. Γνωρίζετε κάποιον τρόπο λύσης του πρόβληματος των κλειδιών του Bombe? Μπορείτε να γενικεύσετε για Ν στρατηγούς?