"H Γεωμετρία χρειάζεται έμπνευση όσο και η ποίηση"
Αλεξάντερ Πούσκιν
Σε μια γραπτή εξέταση-διαγωνισμό συμμετέχουν 5 μαθητές . Ο καθένας μπορεί να διαλέξει 2 θέματα, από ένα σύνολο 5 διαφορετικών θεμάτων. Κάθε θέμα όμως από τα 5 μπορεί να είναι επιλογή ακριβώς 2 μαθητών. Με πόσους διαφορετικούς τρόπους μπορεί να γίνει αυτό;
Θα έλεγα ότι προκύπτει λίγο γεωμετρικά
ΑπάντησηΔιαγραφήΑν φτιάξουμε 2 στήλες με 5 σημεία η καθεμία(θέματα και μαθητές) θα κατασκευάσουμε διαδοχικά το ζητούμενο
Έβγαλα από τη διαδικασία
C(5,2)*5*C(3,2)*4*C(3,2)*C(4,2)*2=4*5*3*3*2*3*4*4*5=21600
Γενικά κάθε φορά παίρνουμε τους συνδυασμούς που έχουν κοινό στοιχείο(αρχικά π.χ. ξεκινάμε με 2 ευθείες από ένα σημείο της μίας στήλης(άρα δεν ξανασχολούμαστε με αυτό) και ενώνουμε με ένα οποιοδήποτε ζέυγος από τα 5 σημεία της άλλης άρα
C(5,2)*5
Εν συνεχεία παίρνουμε ένα σημείο από τα 4(αφού μ ε το 1ο δεν ξανασχολούμαστε) και τραβάμε 2 ευθείες από αυτό σε ένα ζεύγος της απέναντι στήλης.Επιλέγουμε να δημιουργείται από τα 3 σημεία που δεν δεχτήκαν ευθεία στο προηγ. βήμα
Άρα C(3,2)*4 κ.ο.κ.(αλλάζουμε και τη φορά της διαδικασίας μετά)
Αυτή είναι η λογική
21600 συνδυασμοί είναι πολλοί. Πολλοί! :-)
ΔιαγραφήΓενικά καλά επιχειρείς να προσεγγίσεις το θέμα. Πολλά προβλήματα Συνδυαστικής λύνονται εποπτικά με γραφήματα. Κοίτα λίγο Θεωρία Γράφων (ή Γραφημάτων)[Graph theory] και τι σημαίνει κατευθυνόμενος γράφος και ειδικά "δίγραφος" (Bipartite Graph)και "κύκλοι"..και τα ξαναλέμε! :-) To πρόβλημα πάντως είναι αρκετά δύσκολο. Ακόμη κι όταν προσδιορίσεις τον ακριβή τύπο γραφήματος που το αντιπροσωπεύει(το ψιλομαρτύρησα ήδη) θέλει καλό μέτρημα!
Σκέφτηκα ότι θα μπορούσε να σχετίζεται με τον αριθμό των "λέξεων" που μπορούν να προκύψουν αναγραμματίζοντας τη λέξη "ΑΑΒΒΓΓΔΔΕΕ". Κάθε διαδοχικό ζευγάρι γραμμάτων θα αντιστοιχούσε στα θέματα καθενός από τους 5 μαθητές. Οι αναγραμματισμοί είναι 10!/2^5 = 113400. Από τις "λέξεις" αυτές όμως πρέπει να διατηρηθούν μόνο όσες δεν περιέχουν κάποιο ζευγάρι με το ίδιο γράμμα δύο φορές, (αφού δε γίνεται ένας μαθητής να πάρει το ίδιο πρόβλημα 2 φορές). Σ' αυτό το μέτρημα κολλάω όμως.
ΑπάντησηΔιαγραφήΊσως είναι εφικτή και μια πιο απλή σχετικά προσέγγιση του θέματος.
ΑπάντησηΔιαγραφήΑπό πλευράς μου, προσπάθησα να το αντιμετωπίσω γραφικο-συνδυαστικά, μέσω ενός αυτοσχέδιου δένδρου επιλογών, όπου καλούνται οι 5 μαθητές, με μια τυχαία σειρά, να επιλέξουν από 2 θέματα ο καθένας. Ο πρώτος στη σειρά από τους μαθητές, έστω Α, επιλέγει ελεύθερα 2 από τα 5 θέματα, άρα έχει 10 επιλογές. Για τις επιλογές του επόμενου, του Β, έχουμε 3 κλάδους - δυνατότητες:
α)τα ίδια 2 θέματα με τον Α (1 επιλογή) ή
β) 1 μόνο θέμα από τα 2 που επέλεξε ο Α και ένα από τα υπόλοιπα 3 (6 επιλογές) ή
γ)κανένα από τα 2 θέματα του Α, αλλά και τα 2 αποκλειστικά από από τα υπόλοιπα 3 (3 επιλογές).
Η ανάπτυξη του δένδρου ακολουθεί παρόμοια λογική και για τους επόμενους παίκτες, αφού βέβαια σε κάθε βήμα ελέγχεται ότι κανένα θέμα δεν επιλέγεται παρά μόνο από μέχρι 2 μαθητές, ενώ στην ολοκλήρωση του δένδρου κάθε θέμα έχει επιλεγεί από ακριβώς 2 μαθητές.
Τα γινόμενα του αριθμού των επιλογών και των 5 μαθητών κατά πλήρη κλάδο μου δίνουν το πλήθος των δυνατών τρόπων που προκύπτουν από τον κλάδο αυτόν.
Αν δεν έχω κάνει λάθη στους υπολογισμούς μου, από διπλομετρήματα ή παράλειψη επιλογών, μου προκύπτουν 6 πλήρεις κλάδοι που δίνουν συνολικά 60+60+480+360+360+720 = 2040 τρόπους.
Εφόσον το σκεπτικό (ή και το αποτέλεσμα) δεν έχει λάθη ουσίας, νομίζω ότι μπορώ να το αναπτύξω ολοκληρωμένο σε επόμενο σχόλιό μου. Αλλιώς, θα ακούσω τη συμβουλή του αγαπητού Γιώργου και σε πρώτη ευκαιρία θα βουτήξω στα βαθιά της gragh theory. :)
Ωραίος ο papadim!Η λογική του μου φαίνεται σωστή.Εγώ υπερεκτίμησα τους συνδυασμούς καθώς λανθασμένα έβγαλα γινόμενα.Π.χ. αρχικά πολ/σα το C(5,2) με 5 (ο αριθμός των μαθητών).Το θέμα είναι πως διαφοροποιούνται οι εκάστοτε διαδρομές και δεν ισχύουν το ίδιο για κάθε μαθητή(ανάλογα με το ποιος επιλέγει πρώτος-2ος.Άρα ο πολ/μος ήταν τελείως άστοχος).Και πάλι μπράβο!
ΑπάντησηΔιαγραφήΚαι με την δική μου μέτρηση οι δυνατοί τρόποι βγαίνουν
ΑπάντησηΔιαγραφή10*1*3*2*1 +10*6*(1*1*1+4*2*1+1*1*1)
+10*(3*(6*2*1+4*6*1)=60+900+1080=2040
Διόρθωση πληκτρολογικού λάθους
ΑπάντησηΔιαγραφή10*1*3*2*1 +10*6*(1*1*1+4*2*1+1*6*1)
+10*3*(6*2*1+4*6*1)=60+900+1080=2040
Ωραίες οι ιδέες και οι λύσεις! 2040 είναι όντως οι διαφορετικοί τρόποι . Συγχαρητήρια!
ΑπάντησηΔιαγραφήPapadim ,είσαι ήδη βουτηγμένος στα βαθιά ,μιας και η ωραία λύση σου δεν είναι παρά μια εφαρμογή των ιδιοτήτων των διγράφων (Τα δέντρα είναι δίγραφοι! (Βipartite graphs)
Kαταθέτω και γώ λοιπόν αναλυτικά το σκεπτικό που έχω υπ’όψι μου:
Mπορούμε να μοντελοποιήσουμε την κατάσταση με έναν δίγραφο, δηλαδή ένα κατευθυνόμενο (ή «κατευθυντικό») γράφημα με 10 κορυφές (Κ5,5 ο συνήθης συμβολισμός). 5 οι μαθητές και 5 τα θέματα. Πρέπει λοιπόν να μετρήσουμε τον αριθμό των επιμέρους διγράφων που δημιουργούνται μεταξύ των 2 συνόλων ώστε από κάθε κορυφή να φεύγουν 2 ακμές . Αν από μια κορυφή ξεκινά μια ακμή και την ακολουθήσουμε μεχρι την αντίστοιχη κορυφή απέναντι , ουσιαστικά αυτό που ψάχνουμε είναι να σχηματιζεται άρτιος κύκλος , δηλαδή να ξαναγυρνάμε στην αρχική κορυφή σε άρtiο αριθμό βημάτων (ένας δίγραφος είναι ένα «κατευθυντικό» γράφημα ).
Όλο λοιπόν το γράφημα πρέπει να διαμερίζεται σε άρτιους κύκλους (cycles).
Aφού όμως ,με βάση τα δεδομένα, η κάθε κορυφή έχει σθένος(βαθμό) 2, δεν υπάρχουν κύκλοι μήκους 2 (γιατί τότε θα υπήρχε σε κόμβο μόνο μία συγκλίνουσα ακμή) αλλά τουλάχιστον 4 . άρα έχουμε κύκλους μήκους 4 και μήκους 6 (4+6=10) ή κύκλους μήκους 10.
Στην περίπτωση λοιπόν κύκλου μήκους 10 έχουμε:
O 1ος (τυχαίος) μαθητής έχει 5 επιλογές για ένα από τα δύο θέματά του. Αυτό το θέμα μπορεί να επιλεχθεί από ακόμη 4 μαθητές οι οποίοι μπορούν να επιλέξουν από 4 πλέον θέματα τα οποία μπορούν να επιλεχθούν από 3 πλέον μαθητές κ.λ.π…
Άρα οι διαφορετικοί 10-κυκλοι που υπάρχουν είναι 5*4*3*2*… =5!*4!
Αλλά αυτός ο αριθμός υπερεκτιμά κατά παράγοντα 2 ,γιατί λαμβάνει υπ’όψι τη σειρά επιλογής των 2 θεμάτων, η οποία όμως δεν μας ενδιαφέρει. Δεν έχει σημασία σε κάποιο κύκλο μήκους 10 ποιο θέμα διαλέγει ο μαθητής πρώτο (δηλαδή ποια ακμή είναι πρώτη και ποια όχι) Άρα διαίρεση με το 2 και έχουμε 5!*4!/2 =1440 δυνατότητες .
Στην περίπτωση κύκλου μήκους 4 και μήκους 6 έχουμε:
Για τους κύκλους μήκους 6 (δηλαδή 3 μαθητές και 3 θέματα απέναντι) έχουμε C(5,3) *C(5,3) =100 διαφορετικούς τρόπους να διαλέξουμε ποιοι 3 μαθητές και ποια 3 θέματα είναι στον κύκλο.
Ανάλογα όμως όπως παραπάνω για τα δεκάρια ,υπάρχουν 2!*1!/2 διαφορετικοί 4-κυκλοι και 3!*2!/2 δυνατοί 6-κυκλοι, που δίνουν συνολικές δυνατότητες: 100*1*6=600
Σύνολο: 1440+600=2040
YΓ. Καλή γενική αναφορά για τα Bipartite graphs έχει η Βίκη (όχι δυστυχώς στα Ελληνικά, όπως βέβαια στο 90% των μαθηματικού περιεχομένου άρθρων…)
http://en.wikipedia.org/wiki/Bipartite_graph
Αγαπητέ Γιώργο, ευχαριστώ για τα θετικά σου σχόλια, όπως και για την ωραιότατη ανάλυση / λύση του προβλήματος που έδωσες, μέσω της θεωρίας των γράφων.
ΑπάντησηΔιαγραφήΥποθέτοντας πάντως ότι κάποιοι φίλοιίσως τη βρουν αρκετά επαγγελματική, ας μου επιτραπεί να παραθέσω συνοπτικά, αλλά κάπως ολοκληρωμένα, και τη δική μου ερασιτεχνική:
Μαθητής Α
Επιλογή: ελεύθερη, 2 από 5 θέματα
Τρόποι Α: 10
Μαθητής Β
Επιλογές
α. τα ίδια 2 θέματα με τον Α
β. 1 από τα 2 θέματα ίδιο με θέμα του Α και 1 από τα 3 υπόλοιπα
γ. 2 από τα 3 υπόλοιπα
Τρόποι
Βα-Α 1
Ββ-Α 6
Βγ-Α 3
Μαθητής Γ
Από κλάδο Βα
Επιλογή: 2 από τα 3 υπόλοιπα
Τρόποι Γ-Βα-Α 3
Από κλάδο Ββ
Επιλογές
α. το 2ο θέμα του Α και το 2ο θέμα του Β
β. 1 θέμα από τα 2 παραπάνω και 1 από τα 2 υπόλοιπα
γ. 2 από τα 2 υπόλοιπα
Τρόποι
Γα-Ββ-Α 1
Γβ-Ββ-Α 4
Γγ-Ββ-Α 1
Από κλάδο Βγ
Επιλογές
α. 2 από τα 4 θέματα που επέλεξαν οι Α και Β
β. 1 θέμα από τα 4 παραπάνω και το 5ο θέμα
Τρόποι
Γα-Βγ-Α 6
Γβ-Βγ-Α 4
Μαθητής Δ
Από κλάδο Γ-Βα-Α
Επιλογή: 1 από τα 2 που επέλεξε ο Γ και το 5ο θέμα
Τρόποι Δ-Γ-Βα-Α 2
Από κλάδο Γα-Ββ-Α
Επιλογή: και τα 2 από τα 2 που δεν επέλεξε κανείς από τους Α, Β, Γ
Τρόποι Δ-Γα-Ββ-Α 1
Από κλάδο Γβ-Ββ-Α
Επιλογή: 1 από 2 που επέλεξαν προηγούμενοι και το 5ο θέμα
Τρόποι Δ-Γβ-Ββ-Α 2
Από κλάδο Γγ-Ββ-Α
Επιλογή: 2 από 4 θέματα που επέλεξαν προηγούμενοι
Τρόποι Δ-Γγ-Ββ-Α 6
Από κλάδο Γα-Βγ-Α
Επιλογή: 1 από 2 θέματα που επέλεξαν προηγούμενοι και το 5ο θέμα
Τρόποι Δ-Γα-Βγ-Α 2
Από κλάδο Γβ-Βγ-Α
Επιλογή: 2 από 4 θέματα που επέλεξαν προηγούμενοι
Τρόποι Δ-Γβ-Βγ-Α 6
Μαθητής Ε
Από όλους τους πιο πάνω κλάδους απομένουν 2 μαθήματα που έχουν επιλεγεί από 1 φορά μόνο από τους προηγούμενους μαθητές, οπότε αυτά αναγκαστικά και θα πάρει ο μαθητής Ε.
Τρόποι Ε: 1 (ανά κλάδο).
Συνοπτικά και για τους 5 μαθητές
Κλάδος Ε-Δ-Γ-Βα-Α : 1*2*3*1*10 = 60 τρόποι
Κλάδος Ε-Δ-Γα-Ββ-Α : 1*1*1*6*10 = 60 τρόποι
Κλάδος Ε-Δ-Γβ-Ββ-Α : 1*2*4*6*10 = 480 τρόποι
Κλάδος Ε-Δ-Γγ-Ββ-Α : 1*6*1*6*10 = 360 τρόποι
Κλάδος Ε-Δ-Γα-Βγ-Α : 1*2*6*3*10 = 360 τρόποι
Κλάδος Ε-Δ-Γβ-Βγ-Α : 1*6*4*3*10 = 720 τρόποι
Συνολικά 2040 τρόποι
θα προτείνω και μια πιο απλή αφήγηση της παραπάνω λύσης:
ΑπάντησηΔιαγραφήΟι συνδυασμοί 2 μαθημάτων από 5 είναι 10. Σε σχέση με καθέναν από αυτούς, οι 6 από τους υπόλοιπους 9 είναι συγγενείς (1 κοινό μάθημα), ενώ οι 3 είναι ξένοι (κανένα κοινό μάθημα).
Επομένως, αν ζητήσουμε από τους μαθητές Α και Β να επιλέξουν ανεξάρτητα ο καθένας ζευγάρι μαθημάτων, στις 100 συνδυασμένες τους επιλογές, οι 10 θα έχουν το ίδιο ζευγάρι, οι 60 συγγενικά ζευγάρια και οι 30 ξένα ζευγάρια. Εξετάζουμε κάθε περίπτωση ξεχωριστά:
α) οι Α-Β επέλεξαν το ίδιο ζευγάρι
Αποκλείονται τα 2 μαθήματα του δις επιλεγμένου ζευγαριού και επομένως οι μαθητές Γ-Δ-Ε περιορίζονται στο να επιλέξουν από τα υπόλοιπα 3 μαθήματα με 3*2*1=6 τρόπους. Συνολικά 10*3*2*1=60 τρόποι
β) οι Α-Β επέλεξαν συγγενικά ζευγάρια
Αποκλείεται το κοινό μάθημα που επέλεξαν οι Α-Β και μένουν 2 μονά μαθήματα (προς επιλογή άπαξ) και 2 διπλά μαθήματα (προς επιλογή δις).
Αν ο Γ επιλέξει και τα 2 από τα 2 μονά (1 τρόπος), ο Δ θα επιλέξει και τα 2 από τα 2 διπλά (1 τρόπος) και ο Ε επιλέγει 2 από 2 μονά (1 τρόπος). Συνολικά 60*1*1*1=60 τρόποι
Αν ο Γ επιλέξει το 1 από τα 2 μονά και το 1 από τα 2 διπλά (4 τρόποι), ο Δ θα επιλέξει 1 από 2 μονά και 1 από 1 διπλό (2 τρόποι) και ο Ε επιλέγει 2 από 2 μονά (1 τρόπος). Συνολικά 60*4*2*1=480 τρόποι.
Αν ο Γ επιλέξει τα 2 από τα 2 διπλά (1 τρόπος), ο Δ θα επιλέξει 2 από 4 μονά (6 τρόποι) και ο Ε επιλέγει 2 από 2 μονά. Συνολικά 60*1*6*1=360 τρόποι
γ) οι Α-Β επέλεξαν ξένα ζευγάρια
Δεν αποκλείεται κανένα μάθημα που επέλεξαν οι Α-Β και μένουν 4 μονά μαθήματα και 1 διπλό.
Αν ο Γ επιλέξει τα 2 από τα 4 μονά (6 τρόποι), ο Δ θα επιλέξει 1 από 2 μονά και 1 από 1 διπλό (2 τρόποι) και ο Ε επιλέγει 2 από 2 μονά (1 τρόπος). Συνολικά 30*6*2*1=360 τρόποι
Αν ο Γ επιλέξει 1 από τα 4 μονά και 1 από το 1 διπλό (4 τρόποι), ο Δ θα επιλέξει 2 από 4 μονά (6 τρόποι) και ο Ε επιλέγει 2 από 2 μονά (1 τρόπος). Συνολικά 30*4*6*1=720 τρόποι
Γενικό σύνολο 60+60+480+360+360+720 = 2040 τρόποι