Ο αριθμός τηγανίτας,ο βιαστικός σερβιτόρος και ένα δυσεπίλυτο μαθηματικό προβλημα.

                      "Βρίσκεις πάντα αυτό για το οποίο δεν ψάχνεις."

                                            

                                     Ο νόμος του Μaryann,από τους νόμους του Μέρφυ

   Το 1975,ο μαθηματικός Jacob Goodman,καθηγητής στο City College της Νέας Υόρκης δίπλωνε και στοίβαζε τις σιδερωμένες πετσέτες για να βοηθήσει την σύζυγο του.Όταν ολοκλήρωσε την στοίβα,το αποτέλεσμα δεν τον ικανοποίησε, αποφάσισε να τις ξαναστοιβαξει κατά φθίνουσα σειρά μεγέθους από κάτω προς τα πάνω,όμως δεν υπήρχε χώρος για να φτιάξει μια δεύτερη στοίβα.Έκανε λοιπόν το εξής:ξεκινώντας από πάνω αναποδογύρισε μικρές στοίβες από πετσέτες όσες φορές χρειάστηκε για να προκύψει η φθίνουσα διάταξη.Αναρωτήθηκε λοιπόν πως θα μπορούσε το πρόβλημα αυτό να γενικευτεί και να το δημοσιεύσει στον περιοδικό American Mathematical Monthly.Ο Goodman αναδιατύπωσε το πρόβλημα αλλάζοντας τις "πετσέτες" με "τηγανίτες" και το δημοσίευσε με το ψευδώνυμο Harry Dweighter,αναγραμματισμός του harried waiter (βιαστικός σερβιτόρος).

 Το διατύπωσε ως "βιαστικός σερβιτόρος" περίπου έτσι:

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

                                         

   Το πρόβλημα ονομάστηκε η ταξινόμηση της στοίβας με τις τηγανίτες(Pancake sorting)  και μέχρι σήμερα παραμένει ένα ανοικτό πρόβλημα.Αν δοθεί μια τυχαία διατεταγμένη στοίβα από τηγανίτες, πως μπορούμε να τις διατάξουμε από κάτω προς τα πάνω κατά φθίνουσα διάταξη μεγέθους επιφανείας με όσο το δυνατό λιγότερες κινήσεις με μια σπάτουλα. Μια κίνηση (spatula flip) θεωρείται οταν με την σπάτουλα να πιάσουμε ένα σωρό από τηγανίτες από το πάνω μέρος της στοίβας και να το αναποδογυρίσουμε.(Δείτε το βιντεο στο τέλος της ανάρτησης).Ο αριθμός των ελάχιστων κινήσεων για την ταξινόμηση ν τηγανίτων ονομάζεται αριθμός τηγανίτας  Pν.

  Ο μέγιστος αριθμός κινήσεων που απαιτούνται για την ταξινόμηση ν τηγανιτών ανήκει στο διάστημα (15ν/14,18ν/11) αλλά η ακριβής τιμή δεν έχει βρεθεί.Το πρόβλημα έχει εφαρμογή στον παράλληλο προγραμματισμό στην επιστήμη των υπολογιστών.Για το συγκεκριμένο πρόβλημα έχει δημοσιευσει ο X.Παπαδημητρίου καθηγητής στη θεωρία των υπολογιστών του πανεπιστήμιου του Μπέρκλεϊ καθώς και ο Βill Gates όταν ακόμα ήταν φοιτητής.

 Στο σύνδεσμο:

 http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf

Δείτε το βίντεο:

                               

Περισσότερα στους συνδέσμους:

http://plus.maths.org/content/os/issue54/features/colvatter/index http://www.math.uiuc.edu/~west/openp/pancake.html

 http://www5.wittenberg.edu/sites/default/files/media/computer_science/forms/ArmstrongThesis.pdf

https://www.sciencenews.org/article/pancake-sorting

http://canadam.math.ca/2009/pdf/cibulka.pdf

 http://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman

 Μια παραλλαγή του προβλήματος

http://www.sciencedirect.com/science/article/pii/0166218X94000093