Πέμπτη 11 Σεπτεμβρίου 2014

Πατάτες

Τρεις πατάτες τυχαίου μεγέθους και σχήματος βρίσκονται ακινητοποιημένες στον ευκλείδειο χώρο ($R ^{3}$). Μπορείτε να τις κόψετε και τις τρεις στη μέση (δημιουργώντας δηλαδή 2 κομμάτια ίσου όγκου από καθεμιά) με μία ($1$) απότομη μαχαιριά; Η μαχαιριά είναι δηλαδή ένα ευκλείδειο επίπεδο.

21 σχόλια:

  1. Σκεφτείτε το ανάλογο πρόβλημα μία διάσταση κάτω.
    Μπορούν πάντα να διχοτομηθούν 2 τυχαία υποσύνολα του $R^{2}$ από μία ευθεία;...

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Παρντόν, ένα τυχαίο ΠΕΠΕΡΑΣΜΕΝΟ υποσύνολο του $R^{2}$ εννοούσα, δηλαδή ένα κλειστό επίπεδο σχήμα πρακτικά.

      Διαγραφή
  2. Καταρχάς, ας παρατηρήσουμε ότι αν μετατοπίσουμε ένα τυχαίο επίπεδο παράλληλα προς τον εαυτό του, προς τη μια ή την άλλη κατεύθυνση, τότε θα υπάρξει κάποια θέση του που θα κόβει έναν στερεό όγκο (π.χ. μια πατάτα) ακριβώς στα δύο. Αρκεί να σκεφτούμε ότι αν η αρχική θέση του επιπέδου αφήνει ολόκληρο το στερεό στη μια του μεριά, ενώ η τελική θέση ολόκληρο στην άλλη του μεριά, τότε λόγω συνέχειας θα υπάρχει οπωσδήποτε ενδιάμεση θέση που θα αφήνει το μισό στερεό στη μια μεριά και το άλλο μισό στην άλλη. Επομένως, για κάθε τυχαία επιλεγμένη κατεύθυνση στο χώρο, η οικογένεια των κάθετων σε αυτή (και παράλληλων μεταξύ τους) επιπέδων θα περιέχει 3 επίπεδα που το καθένα τους κόβει και μια (τουλάχιστον) από τις 3 πατάτες ακριβώς στα δύο. Μένει να δείξουμε ότι υπάρχει μια 3-άδα τέτοιων επιπέδων που συμπίπτουν όλα μεταξύ τους.
    Ας φανταστούμε μια σφαίρα που περιέχει πλήρως στο εσωτερικό της τις 3 πατάτες. Κάθε προσανατολισμένη ακτίνα αυτής της σφαίρας καταλήγει σε ένα σημείο της επιφάνειάς της και παριστάνει μια κατεύθυνση στο χώρο. Επομένως, σύμφωνα με τα πιο πάνω, σε κάθε σημείο της επιφάνειας της σφαίρας μπορούμε να αντιστοιχίσουμε μια 3-άδα επιπέδων που διχοτομούν τις 3 πατάτες. Αν επιλέξουμε το ένα από αυτά ως επίπεδο αναφοράς, μπορούμε τώρα να δώσουμε τις θέσεις των άλλων 2 επιπέδων, ορίζοντας ως χ και ψ τις προσανατολισμένες αποστάσεις τους από το επίπεδο αναφοράς. Επομένως, σε κάθε σημείο της σφαίρας αντιστοιχίζουμε ένα ζευγάρι αριθμών χ,ψ και μπορούμε να απεικονίσουμε αυτό το ζευγάρι σε ένα καρτεσιανό σύστημα συντεταγμένων χΟψ.
    Αν πάρουμε δυο αντιδιαμετρικά σημεία της σφαίρας, έστω Β και Ν, είναι εύκολο να αντιληφθούμε ότι αυτά αντιστοιχούν σε ακριβώς αντίθετες μεταξύ τους κατευθύνσεις στο χώρο και επομένως τα σημεία αυτά θα αντιστοιχούν στην ίδια 3-άδα διχοτόμων επιπέδων. Επειδή όμως οι αποστάσεις χ, ψ που ορίσαμε είναι προσανατολισμένες, οι συντεταγμένες της καρτεσιανής απεικόνισης του Β θα είναι ακριβώς αντίθετες της αντίστοιχης του Ν. Αυτό σημαίνει ότι αν διαγράψουμε πάνω στη σφαίρα έναν πλήρη μεσημβρινό κύκλο, από Β προς Ν και από Ν προς Β, η αντίστοιχη καρτεσιανή εικόνα αυτού του κύκλου θα είναι μια κλειστή καμπύλη που περιλαμβάνει συμμετρικά ως προς Ο ζευγάρια σημείων, άρα θα περιέχει στο εσωτερικό της το Ο.
    Αν τώρα περιστρέψουμε τον πιο πάνω μεσημβρινό κύκλο κατά 180 μοίρες, γύρω από τη διάμετρο ΒΝ, τότε στο τέλος αυτής της ‘μισής’ στροφής, ο κύκλος θα επανέλθει στην αρχική του θέση, με αντιμετάθεση όμως των δύο ημικυκλίων που τον συναποτελούν. Επομένως, όλα τα σημεία της καρτεσιανής του απεικόνισης θα έχουν μετακινηθεί στα ακριβώς αντίθετά τους (συμμετρικά ως προς Ο των αρχικών) και η τελική εικόνα θα είναι η ίδια κλειστή καμπύλη, με ανεστραμμένες όμως τις θέσεις κάθε συμμετρικού ζευγαριού σημείων. Αυτό σημαίνει ότι σε κάποια στιγμή αυτής της μισής στροφής του μεσημβρινού κύκλου η κλειστή καμπύλη εκφυλίζεται σε μια σκέτη γραμμή που περνάει από την αρχή Ο. Εκείνη τη στιγμή επομένως και για το σημείο Ο της καρτεσιανής εικόνας, ισχύει χ=0, ψ=0 και τα 3 διχοτόμα επίπεδα ταυτίζονται σε ένα (q.e.d.).

    ΑπάντησηΔιαγραφή
  3. Η διαίσθησή μου με οδηγεί στο συμπέρασμα ότι το ζητούμενο δεν είναι πάντα δυνατόν. Δεν έχω χρόνο να καταλάβω την απόδειξη του Θανάση, αλλά αν τελικά έχει δίκιο θα πρέπει μάλλον να σταματήσω να εμπιστεύομαι τη διαίσθησή μου...

    ΑπάντησηΔιαγραφή
  4. Το ξανασκέφτηκα λίγο και άλλαξα στρατόπεδο...

    ΑπάντησηΔιαγραφή
  5. Papadim,υποκλίνομαι! Εξήγησες πολύ ωραία "με λόγια" ένα από τα φανταστικότερα θεωρήματα της Αλγεβρικής Τοπολογίας, το περίφημο Ham Sandwich Theorem (Θεώρημα του σάντουιτς με ζαμπόν :-) ) Mε εκπληκτικές εφαρμογές και λίαν αντιδιαισθητικό (ο swt το επιβεβαιώνει!) ,εφαρμογή ουσιαστικά δύο άλλων διάσημων τοπολογικών θεωρημάτων, του Θ. Borsuk-Ulam και του Θ. σταθερού σημείου. Δεν χρειάζεται να πλατειάσω άλλο, μπορεί κάποιος να αναζητήσει και να διαβάσει πολλά πράγματα, απλώς να πω πως το Ham Sandwich ονομάστηκε έτσι γιατί δείχνει τον τρόπο να μοιράσεις ένα τοστ με τρία υλικά στη μέση με ένα επίπεδο. Μάλιστα, δεν έχει σημασία αν τα υλικά είναι συνεχή ή ανακατεμένα ή οτιδήποτε.
    Στη γενική του μορφή ισχύει για n-διάστατο χώρο και λέει πως αν στο χώρο R^n υπάρχει σε υποσύνολα που διαθέτουν ένα μέτρο Λεμπέκ (Lebesgue) -Borel ,π.χ πρακτικά : μάζα, όγκο, εμβαδό κ.λ.π. υπάρχει πάντα ένα υπερεπίπεδο διάστασης n-1 που διχοτομεί τα υποσύνολα διάστασης n.
    Για μια αυστηρή μαθηματική απόδειξη:
    http://www.math.cornell.edu/~eranevo/homepage/TopMethNotes-2Margarita.pdf
    Μια εκπληκτική εφαρμογή είναι ας πούμε πως υπάρχει μια γραμμή που χωρίζει τον επίπεδο χάρτη της Ελλάδας στα δύο ,σε 2 ισεμβαδικές περιοχές και που έχουν ίδιο πλυθυσμό και ίδιο ας πούμε εισόδημα (ή τετραγωνικά δόμησης ή οποιοδήποτε άλλο Lebesgue μετρήσιμο χαρακτηριστικό)!
    Το θεώρημα είναι ένα θεώρημα "ύπαρξης". Δηλαδή υπάρχει τέτοιο υπερεπίπεδο πάντα, αλλά η ακριβής εύρεσή του είναι δύσκολη.

    ΑπάντησηΔιαγραφή
  6. Mια άλλη διαισθητική "απόδειξη" που σκέφτομαι, όχι κατ'ουσίαν πολύ διαφορετική από την εκπληκτική του Θανάση, είναι η εξής:
    Μπορούμε να φέρουμε σε οποιοδήποτε σημείο της επιφάνειας της 1ης πατάτας (που σημειωτέον, δεν χρειάζεται καν να είναι "κυρτη"!,δηλαδή ένα convex hull που λένε οι εγγλέζοι) ένα εφαπτόμενο επίπεδο. Όπως περιέγραψε ακριβώς ο Θανάσης (ουσιαστικά εφαρμογή του Θεωρήματος ενδιάμεσης τιμής για συνεχείς μεταβλητές) αν μεταφερθεί παράλληλα αυτό το επίπεδο κάποια στιγμή υποχρεωτικά θα διχοτομήσει το σύνολο (τον όγκο). Το ίδιο όμως κάνει και ένα ορθοκανονικό (κάθετο) επίπεδο στο αρχικό. Όταν γλυστρήσει κατάλληλα σίγουρα θα διχοτομήσει (με μια κάθετη στην αρχική μαχαιριά) κι αυτό τον όγκο. Υπάρχουν λοιπόν άπειρα (σε άπειρες διευθύνσεις του R^3) διχοτομούντα επίπεδα μεταξύ 2 πατατών . Αρα ένα οπωσδήποτε θα διχοτομεί και τη τρίτη .

    ΑπάντησηΔιαγραφή
  7. Να διορθώσω/ραφινάρω τη μαθηματική ορολογία μου,για χάρη της πιστότητας:
    To Χαμ-σάντουιτς λοιπόν λέει ότι μπορείς να χωρίσεις στα δύο d σύνολα στις d διαστάσεις με ένα (d-1)-διάστατο υπερεπίπεδο, αρκεί βεβαίως τα d-σύνολα να είναι Λεμπέκ (Lebesgue) μετρήσιμα και να έχουν πεπερασμένο μέτρο. Στην περίπτώσή μας ο όγκος για τις τρεις πατάτες.

    ΑπάντησηΔιαγραφή
  8. Γιώργη, ευχαριστώ! Η αλήθεια είναι ότι είχα πάρει γεύση από αυτό το σάντουιτς με ζαμπόν και παλιότερα, δεν μπόρεσα όμως τότε να το φάω ολόκληρο, γιατί με απώθησαν τα αφηρημένα του τοπολογικά μαθηματικά. Ήμουνα σίγουρος όμως, αφού το γνώριζα θετικά, ότι τρώγεται, και μάλιστα κομμένο ακριβώς στη μέση :-). Αυτά και για να μη μέμφεται ο Σωτήρης την συνήθως εξαιρετική του διαίσθηση :-).
    Στα σοβαρά τώρα, βρήκα καταπληκτική την ανάρτηση, όπως και τα τελευταία σχόλια του Γιώργου για το ευρύτερο πρόβλημα, τη γενίκευση σε χώρους πολλών διαστάσεων και τις προεκτάσεις του. Όσο με αφορά, σίγουρα θα μελετήσω ενδελεχώς τις πολύτιμες παραπομπές που έδωσε.
    Πάντως, η έμπνευσή σου, Γιώργο, να μεταφράσεις το ham sandwich στο πρόβλημα με τις πατάτες, για να το κάνεις προφανώς πιο εύπεπτο, ήταν ‘όλα τα λεφτά’ !!

    ΑπάντησηΔιαγραφή
  9. Θανάση,να σου πω. Εμπνεύστηκα τις πατάτες από ένα καρτούν που έβλεπε η κόρη μου στην τηλεόραση και έδειχνε έναν Σαμουράι,Νίντζα, κάτι τέτοιο τεσπά να πετάει μια πατάτα στον αέρα και να την κάνει...τσιπς με το σπαθί. :-)
    Παρεμπιπτόντως, να μια ωραία εφαρμογή applet για τη δυδιάσταστη περίπτωση, με εξήγηση του αλγορίθμου λύσης:
    http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/DanielleMacNevin/algorithm-pg3.html

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

    ΑπάντησηΔιαγραφή
  11. Nαι, σε ένα τουλάχιστον. Πού θέλεις να καταλήξεις όμως;

    ΑπάντησηΔιαγραφή
  12. Το "σε ένα τουλάχιστον" μου χαλάει το σενάριο.
    Θεώρησα διαισθητικά ότι όπως έχουμε ένα και μόνο κέντρο βάρους (έτσι δεν είναι? ) θα υπάρχει ένα και μόνο σημείο κέντρο όγκου, δηλαδή όλα τα επίπεδα που θα διέρχονται από αυτό το, ας το πούμε γεωμετρικό κέντρο, θα χωρίζουν το στερεό σε 2 ίσου όγκου μέρη. Αν είναι έτσι, αν υπάρχει ένα και μόνο κέντρο όγκου, υπάρχει κατάληξη αν όχι θέλει περισσότερη σκέψη . Η ερώτηση μου δεν έχει καμία σχέση με την λύση του Θανάση και την δική σου, παρά μόνο με την εκφώνηση του θέματος (και εκτός φακέλλου τοπογραφίας, καθώς μου είναι τελείως άγνωστο κεφάλαιο)

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Τοπολογίας (αντί τοπογραφίας) ήθελα να γράψω.

      Διαγραφή
    2. Και το σενάριο, με ευκλείδεια οπτική γωνία ήταν:
      Το επίπεδο που διέρχεται από τα κέντρα όγκου των πατατών, διχοτομεί και τις τρεις πατάτες, ή ότι άλλο ήθελε είναι.

      Διαγραφή
    3. Bεβαίως! To επίπεδο που διέρχεται από τα 3 κεντροειδή . Αν είναι δε ομογενή τα σώματα αυτά ταυτίζοντα και με τα κέντρα μάζας.

      Διαγραφή
  13. Το "ένα τουλάχιστον" το καταλαβαίνουμε από μια ειδική γενική περίπτωση τριών σφαιρών. Αν έχουμε 3 ανισομεγέθεις πλανήτες σε ευθυγράμμιση, δηλαδή τα 3 κέντρα τους είναι συνευθειακά, και αυτοί ορίζουν σε προβολή 3 ομόκεντρους κύκλους,βλέπουμε αμέσως πως υπάρχουν άπειρα επίπεδα που τους διχοτομούν. Όλοι οι μέγιστοι κύκλοι σε καθέναν (οι διάμετροι δηλαδή στην 2-διάσταστη προβολή των ομοκέντρων) κάνουν τη δουλειά.
    Η γενική περίπτωση τώρα είναι προφανώς ο 3ος πλανήτης να φύγει κάπου στο χώρο (ή ο αντίστοιχος κύκλος του σε προβολή να φύγει κάπου στο επίπεδο). Τότε μένει ένα μοναδικό επίπεδο (ή μία μοναδική κοινή διάμετρος των 2 πρώτων) που διχοτομεί και τον τρίτο. Αν υποπτεύομαι σωστά τη σκέψη σου (μα γιατί δεν την εκφράζεις όμως; Αν δεν εκφραστείς ΕΣΥ εδώ μέσα, ποιος θα εκφραστεί; Θα κόψουμε όλοι λάσπη στο τέλος...) όντως για ομογενείς σφαίρες ,το επίπεδο που κάνει τη δουλειά είναι αυτό που ορίζεται από τα 3 κ.βάρους (και όγκου ταυτόχρονα).
    Αλλά το εκπληκτικό σε αυτό το θεώρημα είναι πως ισχύει για οποιοδήποτε κατάλληλης διάστασης Lebesgue μετρήσιμο σύνολο. Ισχύει δηλαδή και για μεταβλητές πυκνότητες ,όπου το κ.όγκου ή κ.επιφάνειας δεν ταυτίζονται με το κ.μάζας. Ισχύει ακόμα και για διάσπαση όγκων! Yπάρχει ένα επίπεδο στο ηλιακό μας σύστημα που χωρίζει ακριβώς στα 2 τις μάζες του α)Ηλιου β)πλανητών και γ) αστεροειδών ! Ισχύει ακόμα και για εντελώς διαφορετικής -πώς να το πω;- "φύσης" σύνολα. Αυτό που έγραψα για την ευθεία γραμμή που μπορεί να χωρίσει στα 2 την Ελλάδα,ώστε τα 2 κομμάτια να έχουν ίδιο εμβαδό,ίδιο πλυθησμό και ίδιο ας πουμε μέσο εισόδημα, δεν ήταν πλάκα! Το έχουνε κάνει οι Αμερικάνοι και έχουν βρει αυτή τη γραμμή. :-)

    ΑπάντησηΔιαγραφή
  14. Σε ευχαριστώ για την αναλυτική απάντηση σου και ναι, σωστά κατάλαβες ότι το σκεπτικό μου ξεκίνησε από τρεις ομογενείς σφαίρες, εύκολη υπόθεση και μόνο με στοιχειώδη στερεομετρία, προχώρησε σε τρία ομογενή αλλά τυχαίου σχήματος στερεά , όπου και εκεί διαισθητικά τουλάχιστον θεωρώ ότι έχουμε σύμπτωση κέντρου βάρους και κέντρου όγκου , άρα λέω ότι τα 3 Κ.Β=Κ.Ο ορίζουν το επίπεδο που τα διχοτομεί και πάνω σε αυτό ήταν το ερώτημα μου.
    Και σίγουρα πολύ καλά κατάλαβες ότι γενικά είμαι επιφυλακτικός σαν άνθρωπος ειδικά σε περιβάλλον που δεν το γνωρίζω προσωπικά.
    Πάντως το "Αν δεν εκφραστείς ΕΣΥ εδώ μέσα, ποιος θα εκφραστεί; Θα κόψουμε όλοι λάσπη στο τέλος...)" όσο και υπερβολή να είναι μου άρεσε και κρατάω ένα $20 \%$ από αυτό και σίγουρα το πιστώνεσαι!
    Όσον αφορά το "Αυτό που έγραψα για την ευθεία γραμμή που μπορεί να χωρίσει στα 2 την Ελλάδα,ώστε τα 2 κομμάτια να έχουν ίδιο εμβαδό,ίδιο πλυθησμό και ίδιο ας πούμε μέσο εισόδημα, δεν ήταν πλάκα!", το αντιλαμβάνομαι πολύ καλά (έχω και το μπαγκράουντ της μεγάλης αρχιτεκτονικής εμπειρίας) αλλά και είχαμε ασχοληθεί εκτενώς με κάπως παραπλήσιο θέμα που είχες βάλει αρχικά, σημεία στο επίπεδο να τα χωρίσουμε στα δύο με μία γραμμή αλλά έχω ήδη μελετήσει αρκετά βιβλία σχετικά με αυτά που ασχολούμαστε εδώ και σε παρόμοιες ιστοσελίδες!
    Δεν δηλώνω πια παντελή άγνοια και αυτό είναι ένας ακόμα λόγος να είμαι προσεκτικός και επιφυλακτικός! :-)
    Να μην σε κουράζω άλλο, χαιρετώ και σε ευχαριστώ.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Υ.Γ. Τώρα είδα και την επιβεβαίωση στην ανάρτηση 7:26 μμ, ότι ισχύει και για σκέτα κεντροειδή που υπέθετα μεν αλλά δεν είμαι και σίγουρος και το πήγαινα πλαγίως, τόση ώρα έγραφα με βάση την ανάρτηση στις 7:11 μμ

      Διαγραφή
  15. Ευθύμη (και λοιποί ενδιαφερόμενοι ,εννοείται), mea culpa!
    Δεν ισχύει το σκεπτικό μας για τα κεντροειδή! Δεν είναι απαραιτήτως δηλαδή το επίπεδο που ενώνει τα 3 κεντροειδή το ζητούμενο! Aυτό το καταλαβαίνουμε σκεπτόμενοι στο 2-διάστατο ανάλογο του Θεωρήματος. Ας πάρουμε ένα τρίγωνο στο επίπεδο. Το κεντροειδές του είναι το σημείο τομής των διαμέσων. ΚΑΜΙΑ όμως άλλη ευθεία που διχοτομεί το εμβαδόν του τριγώνου δεν διέρχεται από το κεντροειδές. Η ευθεία λοιπόν που στη γενική περίπτωση διχοτομεί το εμβαδό 2 τριγώνων δεν διέρχεται υποχρεωτικά από τα 2 κεντροειδή. Άρα όντως η εύρεση δεν είναι τόσο απλή. Η παρανόησή μας ξεκίνησε νομίζω από τη λάθος σκέψη που κάναμε σχετικά με το εξής.Σε ένα ακανόνιστο εν γένει στερεό δε διέρχονται υποχρεωτικά
    όλα τα διχοτομούντα τον όγκο του επίπεδα από ένα σημείο. Και το κρισιμότερο είναι το εξής: δεδομένου ότι 3 τυχαία τέτοια επίπεδα έχουν ένα κοινό σημείο, δεν υποχρεώνει και όλα τα υπόλοιπα να διέρχονται από
    το σημείο αυτό (στη γενική πάντα περίπτωση) και δε σημαίνει ότι κάθε επίπεδο που περιέχει το σημείο αυτό διχοτομεί και αυτό το στερεό. Για την ειδική περίπτωση σφαιρών βεβαίως, υποχρεωτικά το επίπεδο θα ορίζεται από τα 3 κέντρα.

    ΑπάντησηΔιαγραφή