Σάββατο 1 Νοεμβρίου 2014

CombinatoriΧ

$1.$ Πέντε φίλοι,οι Αντώνης, Βίκτορας, Γιάννα, Δήμητρα και Ελένη θα λάβουν μέρος σε μια σκυταλοδρομία $5$ προβλημάτων. Αλλά ο Αντώνης δεν θέλει να λύσει το πρώτο πρόβλημα και η Δήμητρα δεν θέλει να λύσει το τελευταίο. Μ' αυτούς τους περιορισμούς,πόσες διαφορετικές πεντάδες λυτών μπορούν να συγκροτήσουν;
$2.$ Με κορυφές από τις κορυφές ενός κύβου,πόσες διαφορετικές πυραμίδες τριγωνικής βάσης μπορούν να σχηματιστούν;
Αναρτήθηκε από στις 1.11.14
Ετικέτες

14 σχόλια:

  1. papadim3 Νοεμβρίου 2014 στις 9:58 π.μ.

    Ζήτημα 1ο
    Αν δεν υπήρχαν οι περιορισμοί, θα υπήρχαν 5! = 120 διαφορετικές πεντάδες.
    Ανάμεσα σε αυτές, σε 4!=24 ο Αντώνης θα έλυνε το πρώτο πρόβλημα και σε 4!=24 η Δήμητρα θα έλυνε το τελευταίο.
    Επίσης, σε 3! = 6 πεντάδες ο Αντώνης θα έλυνε το πρώτο και η Δήμητρα το τελευταίο.
    Με εφαρμογή της αρχής inclusion – exclusion, οι πεντάδες που απομένουν είναι:
    120-2*24+6 = 78

    ΑπάντησηΔιαγραφή
  2. papadim3 Νοεμβρίου 2014 στις 10:26 π.μ.

    Οι 8 κορυφές ενός κύβου συνδυάζονται ανά 4 με C(8,4)=70 τρόπους. Σε 6 από αυτούς, οι 4 κορυφές βρίσκονται στην ίδια έδρα του κύβου και σε άλλους 6 βρίσκονται στο ίδιο διαγώνιο / διχοτόμο του κύβου επίπεδο. Οι περιπτώσεις αυτές δεν δίνουν τετράεδρο. Επομένως, μπορούν να σχηματιστούν 70-12=58 τετράεδρα.

    ΑπάντησηΔιαγραφή
  3. RIZOPOULOS GEORGIOS3 Νοεμβρίου 2014 στις 11:01 π.μ.

    Papadim, ως συνήθως...άψογος!

    ΑπάντησηΔιαγραφή
  4. papadim3 Νοεμβρίου 2014 στις 11:10 π.μ.

    Ευχαριστώ Γιώργη! Τα θέματά σου ως συνήθως ...νοστιμότατα!

    ΑπάντησηΔιαγραφή
  5. papadim3 Νοεμβρίου 2014 στις 3:01 μ.μ.

    Στο 1, τι γίνεται όμως αν και η Ελένη δεν ήθελε να λύσει το τρίτο;

    ΑπάντησηΔιαγραφή
  6. papadim3 Νοεμβρίου 2014 στις 3:50 μ.μ.

    Είναι κανονική Γιώργη, για όσους τυχόν θα ήθελαν να δοκιμαστούν σε μια πιο απαιτητική εφαρμογή της αρχής. Σε αυτούς δεν περιλαμβάνεσαι προφανώς εσύ, βασικός εισαγωγέας της μεθόδου εις την ημεδαπή! :-). Αποτελείς exclusion.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. RIZOPOULOS GEORGIOS3 Νοεμβρίου 2014 στις 4:18 μ.μ.

      Ok. Μπαίνει λοιπόν σαν υποερώτημα 1.β η ερώτηση του Θανάση: "Τι γίνεται αν ,εκτός του Αντώνη και της Δήμητρας ,και η Ελένη δεν θέλει να λύσει το 3ο πρόβλημα; "

      (Μου θυμίζει κάτι αριθμούς μικρότερους από ξέρω γω το 666 που δεν διαιρούνται με το 5, το 7, και το 12 inclusive αυτό... :-)

      Διαγραφή
  7. stratos3 Νοεμβρίου 2014 στις 6:54 μ.μ.

    Μία απλή διαδοχή σκέψεων είναι η εξής:
    Αν δεν υπήρχαν οι περιορισμοί Αντώνη και Δήμητρας, η Ελένη θα έλυνε το κάθε πρόβλημα σε 4!=24 πεντάδες.
    Με τον περιορισμό του Αντώνη (που δεν λύνει το πρώτο πρόβλημα), οι πεντάδες στις οποίες η Ελένη λύνει το πέμπτο πρόβλημα, μειώνονται από 24 σε 18 (αφαιρούνται δηλαδή οι 3!=6 πεντάδες, όπου ο Αντώνης θα έλυνε το πρώτο και η Ελένη το πέμπτο πρόβλημα).
    Ομοίως, με το περιορισμό της Δήμητρας, που δεν λύνει το πέμπτο πρόβλημα, οι πεντάδες της Ελένης στις οποίες λύνει το πρώτο πρόβλημα, μειώνονται επίσης σε 18.
    Απομένουν 78-18-18=42 πεντάδες στις οποίες ισχύουν οι περιορισμοί του Αντώνη και της Δήμητρας και στις οποίες η Ελένη λύνει κάποιο από τα προβλήματα 2, 3 ή 4.
    Λόγω συμμετρίας, η κάθε περίπτωση (επίλυση προβλήματος 2, 3 ή 4), εμφανίζεται σε 42/3=14 πεντάδες.
    Επομένως, ο περιορισμός της Ελένης, να μη λύσει το πρόβλημα 3, μειώνει τις πεντάδες σε 78-14=64

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. RIZOPOULOS GEORGIOS3 Νοεμβρίου 2014 στις 7:08 μ.μ.

      Στράτο, ωραίος!
      Ή (για να είναι και η λύση exclusively inclusive στα γούστα του Θανάση :-) )με την Αρχή Συμπερίληψης-Εξαίρεσης (Inclusion-exclusion) η Ένωση των τριών γεγονότων ισούται με τα 3 αθροίσματα των συνόλων μείον τις τομές ανά δύο σύν την τομή των τριών.
      5!-4!-4!-4!+3!+3!+3!-2!=64

      Διαγραφή
  8. papadim4 Νοεμβρίου 2014 στις 9:02 π.μ.

    Άψογα Στράτο, πολύ ωραία η εναλλακτική σου προσέγγιση!
    Περιληπτική - εξαιρετική φυσικά και η λύση σου Γιώργο!
    Να προσθέσω μόνο ότι σε περίπτωση που δύο ή περισσότεροι από τους μαθητές δε θέλουν να λύσουν ένα και το ίδιο θέμα, τότε οι εφικτές πεντάδες προκύπτουν μόνο από exclusion και όχι inclusion, αφού οι μη επιτρεπτές πεντάδες έχουν ένωση, αλλά όχι τομή ως αλληλοαποκλειόμενες. Π.χ. αν τόσο ο Αντώνης όσο και η Δήμητρα δεν ήθελαν να λύσουν το πρώτο πρόβλημα, τότε οι δυνατές πεντάδες θα ήταν 5! - 2*4! = 72 και όχι 78 όπως στο αρχικό ερώτημα.
    Περισσότερο ενδιαφέρον όμως, σε σχέση με τις ενώσεις και τις τομές των ενδεχομένων, έχουν οι μικτές περιπτώσεις, π.χ. τι γίνεται αν ο Αντώνης και η Δήμητρα δε θέλουν να λύσουν το πρώτο και η Ελένη δε θέλει να λύσει το τρίτο. Αλλά αυτό το ερώτημα ας μείνει ρητορικό :-), εκτός κι αν κάποιος ....

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. stratos4 Νοεμβρίου 2014 στις 9:24 π.μ.

      Νομίζω ότι και αυτή η περίπτωση μπορεί να λυθεί με ανάλογη προσέγγιση.
      Οι 4!=24 πεντάδες στις οποίες η Ελένη λύνει το πρώτο πρόβλημα παραμένουν ανεπηρέαστες από το γεγονός ότι ο Αντώνης και η Δήμητρα δεν το λύνουν. Απομένουν επομένως 72-24=48 πεντάδες στις οποίες η Ελένη λύνει κάποιο από τα 4 άλλα προβλήματα με τον Αντώνη και τη Δήμητρα να μη λύνουν το πρώτο. Λόγω συμμετρίας, η κάθε περίπτωση εμφανίζεται 48/4=12 φορές, δηλαδή σε 12 πεντάδες η Ελένη λύνει ένα από τα προβλήματα 2,3,4 ή 5, με Αντώνη και Δήμητρα να μη λύνουν το πρώτο.
      Αρα, απομένουν 72-12=60 πεντάδες στις οποίες Αντώνης και Δήμητρα δεν λύνουν το πρώτο και Ελένη το τρίτο.

      Διαγραφή
    2. stratos4 Νοεμβρίου 2014 στις 9:29 π.μ.

      Θανάση, νομίζω ότι η αναλυτική προσέγγιση που επικαλούμαι, εφθασε στα όρια της. Για πιο πολύπλοκες καταστάσεις νομίζω ότι μόνο με exclusion/inclusion προσέγγιση θα μπορούσαμε να δουλέψουμε. π.χ., αν το πρόβλημα ήταν "Ο Αντώνης δεν θέλει να λύσει το πρώτο και είτε η Δήμητρα δεν θέλει να λύσει το πέμπτο, είτε η Ελένη και η Γιάννα δεν θέλουν να λύσουν ένα από τα 2, ή 3", δεν νομίζω ότι μπορεί εύκολα να λυθεί αναλυτικά.

      Διαγραφή
  9. papadim4 Νοεμβρίου 2014 στις 9:40 π.μ.

    Και πάλι άψογος Στράτο!!
    Με την inclusion-exclusion θα είχαμε:
    5! - 3*4! + 2*3! = 120 - 72 + 12 = 60
    Οι εξαιρέσεις (-) είναι οι πεντάδες όπου ο Αντώνης ή η Δήμητρα λύνουν το πρώτο ή η Ελένη λύνει το τρίτο και οι συμπεριλήψεις (+) είναι οι πεντάδες όπου ο Αντώνης λύνει το πρώτο και η Ελένη το τρίτο ή η Δήμητρα λύνει το πρώτο και η Ελένη το τρίτο.

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

Εγγραφή σε: Σχόλια ανάρτησης (Atom)