Μια στοίβα με τηγανίτες

   
                                          

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

Jacob Goodman

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

                                    

  Ο μέγιστος αριθμός κινήσεων που απαιτούνται για την ταξινόμηση ν τηγανιτών ανήκει στο διάστημα (15ν/14,18ν/11) αλλά η ακριβής τιμή δεν έχει βρεθεί.Το πρόβλημα έχει εφαρμογή στον παράλληλο προγραμματισμό στην επιστήμη των υπολογιστών.Για το συγκεκριμένο πρόβλημα έχει δημοσιευσει ο  Χ.Παπαδημητριου καθηγητής στη θεωρία των υπολογιστών του πανεπιστήμιου του Μπέρκλεϊ καθώς και ο Β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