Τρίτη, 14 Ιανουαρίου 2014

Κυβάκια σουβλάκι!

"Υπήρχε περισσότερη φαντασία στο κεφάλι του Αρχιμήδη απ' ό,τι στο κεφάλι του Ομήρου"
             Βολταίρος
Ένα πολύ ωραίο πρόβλημα. 
ΠΡΟΕΙΔΟΠΟΊΗΣΗ: Η γεωμετρική αντιμετώπιση -που μοιάζει φυσική- μπορεί και να μην είναι τόσο ..φυσική!..μπορεί όμως και να είναι. :-)
Συγκολλώντας μοναδιαίους κύβους ($1 \times 1 \times 1$) κατασκευάζουμε ένα κυβοειδές (ορθογώνιο παραλληλεπίπεδο) διαστάσεων $300 \times 324 \times 375$.   Aπό πόσους μοναδιαίους κύβους περνάει  η διαγώνιος του κυβοειδούς; Πόσα δηλαδή κυβάκια $1 \times 1 \times 1$ διατρέχει η διαγώνιος;

28 σχόλια:

  1. Τοποθετούμε το κυβοειδές σε τρισδιάστατο ορθοκανονικό σύστημα χψζ και έστω (0,0,0) και (300,324,375) οι συντεταγμένες των δύο κορυφών / άκρων τής διαγωνίου.
    Στο δρόμο της από το ένα άκρο στο άλλο, η διαγώνιος θα συναντήσει, σε διαφορετικά σημεία και μια φορά το καθένα, όλα τα επίπεδα με χ=1,2,..,299 (πλήθος 299), όλα τα επίπεδα με ψ=1,2,..,323 (πλήθος 323) και όλα τα επίπεδα με ζ=1,2,..,374 (πλήθος 374). Υπάρχουν επομένως συνολικά 299+323+374=996 εσωτερικά σημεία τομής της διαγωνίου με τα επίπεδα αυτά. Σε αυτά προστίθενται και τα 2 άκρα της διαγωνίου, 998 συνολικά σημεία. Κάθε τμήμα της διαγωνίου που ορίζεται με άκρα 2 διαδοχικά τέτοια σημεία αντιστοιχεί και σε 1 μοναδιαίο κύβο.
    Επομένως, η διαγώνιος διατρέχει 997 μοναδιαίους κύβους..

    ΑπάντησηΔιαγραφή
  2. Νομίζω ότι θα πρέπει να ληφθεί υπόψη η περίπτωση η διαγώνιος να περνά ανάμεσα από κορφές χωρίς να τέμνει κάποια μοναδιαία κυβάκια.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

      Διαγραφή
  3. Καλησπέρα κι ευχαριστώ για τα πρώτα σχόλια!
    Eμπνευσμένη και to the point η ιδέα του papadim, αλλά φυσική και πολύ to the point και η παρατήρηση του swt! :-)

    ΑπάντησηΔιαγραφή
  4. To πρόβλημα έχει μια γενική λύση για τυχαίες ακέραιες διαστάσεις Ν Χ Μ Χ Κ ... ίσως αυτό βοηθάει στην αντιμετώπισή του.
    (εποπτικά θα βοηθούσε ίσως και η διερεύνηση του 2-διάστατου αντίστοιχου προβλήματος)

    ΑπάντησηΔιαγραφή
  5. Αυτό που αρχικά παρατηρώ είναι ότι το κυβοειδές μπορεί να χωριστεί σε 27 υποκυβοειδή διαστάσεων 100x108x125 με τη διαγώνιο να ταυτίζεται με τις διαγωνίους τριών εξ αυτών. Έχουμε ήδη λοιπόν 2 σημεία στα οποία η μετάβαση στα επόμενα x, y, z επίπεδα γίνεται ταυτόχρονα και άρα έχουμε ήδη 4 λιγότερα σημεία (6-2).

    ΑπάντησηΔιαγραφή
  6. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

    ΑπάντησηΔιαγραφή
  7. 300=2^3*3*5^2
    324=2^2*3^4
    375=3*5^3
    άρα η διαγώνιος περνάει 3 φορές από κοινό σημείο
    τομής και των τριών διευθύνσεων επιπέδων, άρα
    -4σημεία (όπως ήδη έχει παρατηρήσει ο swt)

    Συμπίπτουν ανά δύο διευθύνσεις τα επίπεδα
    375/324=125/108 =>375/125=3 φορές, έχει ήδη
    υπολογισθεί.
    375/300=5/4 =>375/5=75 φορές
    άρα 75-1-2 (που υπολογίσθηκε)=72 σημεία αφαιρετέα
    324/300=27/25 =>324/27=12 φορές,
    άρα 12-1-2(που υπολογίσθηκε)=9 σημεία αφαιρετέα
    συνολικά 4+72+9=85 σημεία που πρέπει
    να αφαιρεθούν

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Aπό ποιον αριθμό πρέπει ν'αφαιρεθούν;
      Ποιο είναι το αποτέλεσμα;

      Διαγραφή
    2. Τα επίπεδα που διαπερνά η διαγώνιος (με τα διπλοπεράσματα και τριπλοπεράσματα είναι 999-3(τα τρία τελευταία, ένα Χ, ένα Υ και ένα Ζ)=996. Πρέπει
      στο 996 να προσθέσουμε και το τελευταίο κυβάκι, άρα 996+1=997 (όπως είχε αναγραφεί από τον papadim, που το ίδιο είχα βρει και εγώ, οι αφαιρέσεις μου έλειπαν)
      Αποτέλεσμα 997-85=912
      (Η λύση έγινε με στερεομετρική προσέγγιση)

      Διαγραφή
    3. Και όταν λέω στερεομετρική-κατασκευαστική, το εννοώ απόλυτα. Κατασκεύασα κάναβο (108*100=1/3*324*1/3 *300 ) και έφερα την διαγώνιο. Στο κατακόρυφο επίπεδο που περνάει από την διαγώνιο βρίσκεται η διαγώνιος του κυβοειδούς.
      Περιστροφή της διαγωνίου του κανάβου, έτσι που να συμπέσει με τον άξονα των Χ.
      Κατασκευή της διαγωνίου του κυβοειδούς από το 0 στο 125(1/3 *375) στο άκρο της διαγωνίου της διαγωνίου του κανάβου και μετά έλεγχος των τομών του κανάβου με την διαγώνιο του σε σχέση με την με την διαγώνιο του στερεού κλπ, κλπ δεν περιγράφονται τα σχήματα, όπου όλα έγιναν φανερά και καθαρά, 3 τομές ανά κόμβο, τα διπλά σημεία κλπ, έ και μετά το μαθηματικοποίησα

      Διαγραφή
  8. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

    ΑπάντησηΔιαγραφή
  9. Διορθώνω:
    (Ν+Μ+Κ)-ΜΚΔ(Ν,Μ)-ΜΚΔ(Μ,Κ)-ΜΚΔ(Ν,Κ)+ΜΚΔ(Ν,Μ,Κ) και για την περίπτωσή μας 999-12-3-75+3 = 912.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Συνοψίζω το σκεπτικό και το αποτέλεσμα της προσέγγισής μου, σε συνέχεια του αρχικού μου σχολίου:
      Θα συμφωνήσω με τους φίλους ότι υπάρχουν όντως διελεύσεις τής διαγωνίου από κόμβους και ακμές του πλέγματος, οπότε και θα πρέπει να γίνουν αφαιρετικές διορθώσεις για τα διπλομετρήματα και προσθετικές για τα τριπλομετρήματα των σημείων.
      Νομίζω δηλαδή ότι έχουμε και εδώ μια εφαρμογή τής inclusion-exclusion principle.
      Για τη γενική περίπτωση κυβοειδούς Ν χ Μ χ Κ που πρότεινε ο Γιώργος, αν δε μου ξεφεύγει κάτι σημαντικό, νομίζω ότι ο αριθμός των διατρεχόμενων από τη διαγώνιο μοναδιαίων κύβων πρέπει να δίνεται από την παράσταση:
      (Ν+Μ+Κ)-ΜΚΔ(Ν,Μ)-ΜΚΔ(Μ,Κ)-ΜΚΔ(Ν,Κ)+ΜΚΔ(Ν,Μ,Κ) και για την περίπτωσή μας 999-12-3-75+3 = 912.

      Διαγραφή
  10. Πιο νηφάλια σήμερα (μετά την περιπλάνησή μου στην
    στερεομετρική απεικόνιση του θέματος) εύκολα περνάμε στην συνδυαστική γεωμετρία και στις ενώσεις-τομές συνόλων και στην γενίκευση των διαγραμμάτων Βέν, στην αρχή του
    εγκλεισμού-αποκλεισμού.
    Έτσι έχουμε : Ο αριθμός των κύβων που διατρέχει η διαγώνιος ισούται με το άθροισμα των επιπέδων-εδρών των κύβων που διαπερνά η διαγώνιος μείον τις τομές των τριών διαφορετικών επιπέδων ανά 2 συν τις τομές ανά τρία, από τις οποίες περνάει
    η διαγώνιοςήτοι: 300+324+375-75-12-3+3=912
    Υ.Γ Πολύ καλό θέμα!

    ΑπάντησηΔιαγραφή
  11. Κάνω ένα συγκεντρωτικό σχόλιο εδώ,για να μη γράφω διάσπαρτα εδώ κι εκεί.
    Αυτό το πρόβλημα μού αρέσει πολύ! Kυρίως για το μυστήριο-τρόπο τινά- που το περιβάλλει, με την έννοια πως παρότι κάποιος θα περίμενε να έχει να κάνει με γεωμετρικές μετρικές σχέσεις του ευκλείδειου χώρου , τελικά αποδεικνύεται πως είναι θέμα αριθμοθεωρητικών εννοιών και συναρτήσεων.
    Ο Ευθύμιος όμως , συνέδεσε με μαγικό τρόπο τους δύο "κόσμους" αφού οι στερεομετρικοί του υπολογισμοί (λεπτοί και δύσκολοι υποθέτω) επαλήθευσαν (και αμφιδρόμως επαληθεύτηκαν!) με την "μαθηματικοποίηση" όπως την αποκάλεσε- του σχολίου 11.19μ.μ. που ουσιαστικά εκφράζει την αριθμοθεωρητική φύση του προβλήματος για τους συγκεκριμένους αριθμούς. Συγχαρητήρια και Μπράβο Ευθύμιε!

    Papadim ή Θανάση ή Μπάμπη Σουγιά (αφού "όλα τα σφάζεις κι όλα τα μαχαιρώνεις":-) ) υποκλίνομαι ανυπόκριτα και με θαυμασμό μπροστά σου !!
    Aκριβώς αυτή η incllusion-exclusion λογική είναι το κλειδί της γενίκευσης αυτού του προβλήματος και ακριβώς ο τύπος που δίνεις
    $(Ν+Μ+Κ)-ΜΚΔ(Ν,Μ)-ΜΚΔ(Μ,Κ)-ΜΚΔ(Ν,Κ)+ΜΚΔ(Ν,Μ,Κ)$ είναι ο γενικός τύπος που ξεκλειδώνει κάθε τριάδα ακεραίων $Ν, Μ, Κ$ Μια πολύ ενδιαφέρουσα αριθμοθεωρητική συνάρτηση!
    Για να μην φαίνονται ξένες ιδέες σαν δικές μου, να πω πως στην πηγή που βρήκα ένα παραλλαγμένο θέμα (και την οποία δεν αναφέρω για να μην την "κάψω" :-) ) αναφέρεται πως "..δεδομένου ενός συνόλου $S$ από $n$ θετικούς ακέραιους έστω $G(s,k)$ για k<ή ίσο n, το αθροισμα των Μεγίστων Κοινών Διαιρετών κάθε υποσυνόλου $k$ στοιχείων από το $S$ , τότε μπορούμε να ορίσουμε την συνάρτηση συμπερίληψης -αποκλεισμού (inclusion-exclusion function) :
    $f(S)=G(S,1) -G(S,2) +G(S,3)-...- (-1)^n G(S,n)$ "
    Οπότε στην περίπτωσή μας αυτή δίνει τον τύπο του papadim!
    Kαι παρεμπιπτόντως ,έχει μεγάλο ενδιαφέρον ας πούμε πως αν το $S$ είναι το σύνολο των $n$ πρώτων θετικών ακεραίων τότε ισχύει:
    $f({1,2,...,n})=\sum_1^n \ \varphi (k)$ όπου $φ(n)$ η συνάρτηση totient function του Όϋλερ, που δίνει το πλήθος των μεταξύ τους πρώτων φυσικών αριθμών μικρότερων ή ίσων με $n$ .Και "μεταξύ τους πρώτοι" σημαίνει Μ.Κ.Δ=1 ..με απευθείας σύνδεση με το θέμα μας.
    Θα ήταν παράλειψή μου βεβαίως να μην ευχαριστήσω επίσης τον swt για τα εμπνευσμένα σχόλιά του!
    Ελπίζω να σάς άρεσε αυτό το θέμα.

    ΑπάντησηΔιαγραφή
  12. Φίλε Γιώργο, όχι απλά ωραίο αλλά εκπάγλου ομορφιάς το θέμα σου!!
    Σε ευχαριστώ θερμά για την επιλογή του, τα σχόλιά σου, τη γενίκευση της γενίκευσης και τις πολύ ενδιαφέρουσες συνάφειες και προεκτάσεις που αναφέρεις.
    Για να κάνω και μια σύνδεση με το προοίμιο της ανάρτησης, νομίζω ότι είχε και Όμηρο (ποίηση, έμπνευση) και Αρχιμήδη (θετική σκέψη και ανάλυση) στα καλύτερά τους.
    Η διαδικασία της συζήτησής του και η ανταλλαγή σχολίων μέχρι να φτάσουμε στο τελικό αποτέλεσμα ήταν μια παραδειγματική επιβεβαίωση της δύναμης και της αποτελεσματικότητας του συνεργατικού συναγωνισμού (co-opetition, όπως εύστοχα έχει ονοματισθεί από κάποιον σπουδαίο παιγνιοθεωρητικό).
    Πολλά μπράβο λοιπόν και στους αγαπητούς φίλους swt και Ευθύμιο!!

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Συμφωνώ απόλυτα, Θανάση, το "παιχνίδι" είχε κάτι από τον τελικό Ευρωμπάσκετ 1987 Ελλάδα-Σοβιετική Ένωση, σε μικρογραφία βέβαια μην διαπράξουμε και ύβριν, αναφέρομαι σε αυτό το παιχνίδι γιατί πέραν των άλλων έτυχε να είμαι στο γήπεδο.
      Φιλικά, Ευθύμης

      Διαγραφή
  13. Πολύ ωραίες οι λύσεις του Ευθυμίου και του Θανάση, όπως και οι γενικεύσεις του Θανάση και του Γιώργου. Χαίρομαι να συμμετέχω σε συζητήσεις γύρω από τα ωραία προβλήματα που επιλέγει ο Γιώργος, στενοχωριέμαι βέβαια λίγο, γιατί, ειδικά τις καθημερινές, δεν έχω όσο χρόνο θα επιθυμούσα να αφιερώσω.
    Με την ευκαιρία, εύχομαι μια καλή χρονιά σε όλους τους συμμετέχοντες, σχολιαστές και μη σχολιαστές.
    Σωτήρης

    ΑπάντησηΔιαγραφή
  14. Καλή χρονιά και σε σένα Σωτήρη, χαίρομαι που μαθαίνω το όνομά σου και βέβαια η "μπάλα" άλλαξε τρία ζευγάρια χέρια πριν καταλήξει 2 φορές στο "καλάθι"!
    Φιλικά, Ευθύμης

    ΑπάντησηΔιαγραφή
  15. Δηλαδή, αν καταλαβαίνω καλά εγώ είμαι ο Πολίτης κι ο Σωκράτης ο ..Βασιλακόπουλος; :-)
    (αα, προτιμώ να παίζω μέσα ,κι ας είμαι κι ο ταπεινός Καμπούρης!)

    ΑπάντησηΔιαγραφή
  16. Κάπως έτσι Γιώργο! :-)
    Με την προσθήκη Πολίτης μεν, αφού αυτός ήταν ο προπονητής, αλλά με "ίσκιο" και "χρώμα" Ιωαννίδη, "ισκιο" λόγω Άρη Θεσσαλονίκης (Ιωαννίδης-Γκάλης-Γιαννάκης) και "χρώμα" λόγω ...ζωηρού ταμπεραμέντου σε σχέση με τον ήρεμο και χαμηλών τόνων Πολίτη και για τον κ. Ρωμανίδη θα έλεγα και "Πολίτης" και "Βασιλακόπουλος", και "προπονητής" και διευθύνων του απέραντου και αξιόλογου αυτού ιστότοπου.
    Φιλικά, Ευθύμης

    ΑπάντησηΔιαγραφή
  17. ΑΠΟ ΤΟ ΜΕΡΙΚΟ ΣΤΟ ΓΕΝΙΚΟ
    ΚΑΙ ΑΠΟ ΤΟ ΜΕΡΙΚΟ ΚΑΙ ΓΕΝΙΚΟ ΣΤΟ ΕΙΔΙΚΟ

    Αν $A(0,0,0)$ και $B(324,300,375)$ οι συντεταγμένες των άκρων της διαγωνίου του κυβοειδούς να βρεθούν οι συντεταγμένες του σημείου $M$ όπου η διαγώνιος με κατεύθυνση από το $A$ στο $B$ εισέρχεται στον 456ο κύβο.

    ΑπάντησηΔιαγραφή
  18. Πολύ ενδιαφέρον το ερώτημά σου Ευθύμη, άλλα, επίτρεψέ μου την παρατήρηση, όχι τόσο ώστε να χάνουμε και τον ύπνο μας -:). Αρκετά πάντως για να ξυπνάει το μυαλό μας παρέα με τον πρωινό καφέ.

    Το μέσο της διαγωνίου ΑΒ είναι το σημείο (162, 150, 187,5). Το σημείο αυτό είναι ένα από τα σημεία ‘διπλής διέλευσης’ (δύο ακέραιες συντεταγμένες) και είναι το σημείο εξόδου από το κυβάκι Νο 456 και εισόδου στο Νο 457, αφού έχει πίσω του 456 κυβάκια και μπροστά του άλλα 456 κυβάκια, από τα 912 συνολικά.
    Επομένως το σημείο Μ εισόδου στο Νο 456 έχει ζ=187 και, βάσει κανόνα αναλογιών, θα έχει χ=(324/375)*187=161,568 και ψ=(300/375)*187=149,6.
    Άρα τελικά Μ=(161,568 - 149,6 – 187)

    ΑπάντησηΔιαγραφή
  19. Πολύ σωστά Θανάση, και δεν είχα πρόθεση να χάσει κανείς τον ύπνο του, εξάλλου η επιλογή του πιο εύκολου κύβου δείχνει και την πρόθεση μου!
    Επιφυλάσσομαι για κάτι δύσκολο στο μέλλον! :-)
    Άργησα να σου απαντήσω γιατί γύρισα αργά το μεσημέρι από την δουλειά μου.

    ΑπάντησηΔιαγραφή
  20. Στο δικό σου ύπνο αναφερόμουν, Ευθύμη, κρίνοντας από την ώρα που έδιωξες το σχόλιο με το πρόσθετο ερώτημα.
    Όσο για το ίδιο το ερώτημα, ήταν μια πολύ καλή εμπεδωτική άσκηση και μπράβο σου που το σκέφτηκες. Φυσικά, με χαρά θα υποδεχτώ και ό,τι άλλο, εύκολο ή δύσκολο, αποφασίσεις να προτείνεις στο μέλλον.

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

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