Σκεφθήκατε ποτέ, πόσο ύπουλο είναι αυτό το "κουλουράκι" που το
αποκαλούμε "μηδέν"; εδώ Και θα μπορούσατε να φανταστείτε ότι, στο
δυτικό κόσμο, άρχισε να χρησιμοποιείται η λέξη "εκατομμύριο" από
το 1362 μ.Χ.; Την έκφραση "εκατομμύριο" τη χρησιμοποιούσαν μόνο
ελάχιστοι μαθηματικοί. Οι άλλοι συνέχιζαν να τη περιγράφουν
"Χίλιες φορές το χίλια". Ακόμα και ο περίφημος Γερμανός
μαθηματικός Adam Riese (Αδάμ Ρήζε)
(Staffelstein 1492 – Annaberg 1559) χρησιμοποιούσε πολλές φορές τη
περιγραφή "Χίλιες φορές το χίλια" αντί της λέξεως "εκατομμύριο". Η λέξη
"δισεκατομμύριο" άρχισε να χρησιμοποιείται από το 19o αιώνα και μετά!!
Οι ανατολικοί λαοί όμως, ήξεραν πολύ πριν από μας, πώς να εκφράσουν
τους τεράστιους αριθμούς. Το 5o αιώνα μ.Χ. στην Ινδία οι Βραχμάνοι ιερείς
σκέφθηκαν να εκφράσουν μεγάλους αριθμούς προσθέτοντας κάθε φορά από
ένα "μηδέν". Οι Ινδοί λοιπόν είχαν φθάσει μέχρι τον αριθμό και την έννοια
των 100.000 εκατομμυρίων (100.000.000.000 = εκατό
δισεκατομμυρίων).
Εσείς, μέχρι που θα…φθάσετε, προσπαθώντας να λύσετε το πρόβλημα που
θα σας δώσω;
Πριν όμως σας δώσω το πρόβλημα, σας υπενθυμίζω ότι σύμφωνα με τη
θεωρία των μεταθέσεων δύο πράγματα μπορούν ν’ αλλάξουν τη θέση τους
δύο φορές, σύμφωνα με το σχήμα: 2!=1 x 2=2 και 2!= 2 x 1=2. Πέντε
πράγματα μπορούν ν’ αλλάξουν τη θέση τους 120 φορές, σύμφωνα με το
σχήμα: 5!=1 x 2 x 3 x 4 x 5=120. Δέκα πράγματα μπορούν ν’ αλλάξουν τη
θέση τους 3.628.800 φορές, σύμφωνα με το σχήμα:
10!=1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10=3.628.800 κ.ο.κ.
Σύμφωνα μ’ αυτό το σχήμα, γίνονται λοιπόν όλοι οι συγγενικοί
συλλογισμοί, σε προβλήματα όπου πρέπει να βρεθεί η απάντηση στο εξής
ερώτημα:
"Πόσοι συνδυασμοί είναι δυνατόν να γίνουν, αν…".
Και ιδού το πρόβλημα που πρέπει να λύσετε:
...Αν 15 πρόσωπα αποφασίσουν να πηγαίνουν κάθε ημέρα από μία
εκδρομή, και να συμμετέχουν σ’ αυτή κάθε φορά με άλλο
συνδυασμό τα διάφορα πρόσωπα της ομάδος των 15 ατόμων,
πόσος χρόνος θα χρειασθεί για να πραγματοποιήσουν κάθε δυνατό
συνδυασμό μεταθέσεων; (Κατ.5/Πρβ. Νο.13)
Δυστυχώς είμαι υποχρεωμένος να ζητήσω συγγνώμη από
τους Δ. Σκυριανόγλου, Η. Οικονομόπουλο, και τον
Ανώνυμο για την ταλαιπωρία που υπέστησαν από το
ανωτέρω πρόβλημα, τ' οποίο βρήκα έτσι διατυπωμένο
οδηγώντας τους λύτες σε άλλες κατευθύνσεις για τη λύση
του. Ο εξαίρετος φίλος του Blog Δ. Σκυριανόγλου, τον
οποίο ευχαριστώ, μου έστειλε την κατωτέρω διατύπωση
του προβλήματος που είναι και επίκαιρη λόγω της
25ηs Μαρτίου:
Δεκαπέντε μαθητές θέλουν να παρελάσουν την 25ηs Μαρτίου
παρατεταγμένοι σε μια σειρά. Για να μην αδικηθεί όμως κανείς
θέλουν να παρελάσουν με όλους τους δυνατούς συνδυασμούς,
ώστε όλοι να περάσουν από όλες τις θέσεις. Πόσες φορές θα πρέπει
να κάνουν παρέλαση, ώστε να το πετύχουν; (Κατ.5/Πρβ. Νο.13)
παρατεταγμένοι σε μια σειρά. Για να μην αδικηθεί όμως κανείς
θέλουν να παρελάσουν με όλους τους δυνατούς συνδυασμούς,
ώστε όλοι να περάσουν από όλες τις θέσεις. Πόσες φορές θα πρέπει
να κάνουν παρέλαση, ώστε να το πετύχουν; (Κατ.5/Πρβ. Νο.13)
Αναρτήσεις
29 σχόλια:
Μια διευκρίνιση:
Πόσα άτομα από τα 15 πάνε κάθε μέρα εκδρομή? Ή μήπως εννοείτε όλους τους δυνατούς συνδυασμούς ατόμων (δηλ. από 1 ως και 15? Ή μήπως ένα άτομο μόνο του δεν πάει εκδρομή?)
Αν από τα 15 άτομα τα n πάνε κάθε μέρα εκδρομή τότε οι διαφορετικοί συνδυασμοί των ατόμων είναι:
15 ανά n = 15!/(n! * (15-n)!)
Ο αριθμός αυτός ισούται με τον αριθμό των ημερών που θα χρειαστούν τα 15 άτομα ώστε να πάνε εκδρομή με όλους τους διαφορετικούς συνδυασμούς από n-άδες.
Αν μιλάμε για όλους τους δυνατούς συνδυασμούς ομάδων (με οποιοδήποτε αριθμό ατόμων) από 1 (ή 2 αν ένας μόνος του δεν πάει εκδρομή) έως και 15 τότε με τον τύπο που έδωσα παραπάνω κάνουμε τον υπολογισμό για όλα τα n και αθροίζουμε.
Αν μπορέσω σε λίγη ώρα θα έχω και ποσοτικές απαντήσεις για κάθε περίπτωση.
@Δημήτρης Σκυριανόγλου
Όλα τ' άτομα πάνε εκδρομή κάθε μέρα, όπως το αναφέρει η εκφώνηση.
Σχετικά με το "Σκάκι για Όλους" ενημερώστεμε εάν σταμάτησε ή όχι.
Συγνώμη αλλά εξακολουθώ να έχω απορίες:
Όταν λέτε ότι και τα 15 άτομα πάνε εκδρομή κάθε μέρα τι εννοείτε? Σε πόσες ομάδες χωρίζονται? Δώστε ένα παράδειγμα. Π.χ. τη μία μέρα μπορεί ο κάθε ένας να πάει μια εκδρομή μόνος του ενώ την άλλη να πάνε 5 άτομα σε μια εκδρομή 7 σε μια άλλη και 3 σε μια άλλη εκδρομή ή την τρίτη μέρα μπορούν να πάνε οι 10 μια εκδρομή και οι άλλοι 5 σε μια άλλη εκδρομή ενώ τέλος μια μέρα θα πάνε και οι 15 μαζί μια εκδρομή? Με άλλα λόγια ζητάτε όλους τους δυνατούς τρόπους που μπορούν να χωριστούν τα 15 άτομα? Δε μου είναι σαφές, συγνώμη...
Για το περιοδικό είναι γεγονός ότι αντιμετωπίζει κάποιες σοβαρές δυσκολίες, δε θα ήθελα όμως να επεκταθώ περισσότερο
@Δημήτρης Σκυριανόγλου
Ακριβώς, όλους τους δυνατούς συνδυασμούς των ατόμων. Συγνώμη για την ασάφεια. Ελπίζω να σας βοήθησα.
Θα το τολμήσω κι ας μην ξέρω τους γενικούς τύπους. Μήπως είναι (15!+14!+13!+...+2!+1) μέρες;
@ΗΛΙΑΣ ΟΙΚΟΝΟΜΟΠΟΥΛΟΣ
Όχι δεν είναι αυτή η λύση.
Με την ευκαιρία αυτή θα ήθελα να μου πείτε γιατί δεν μου απάντήσατε στα σχόλια που έκανα στα:
α)ο Σαμ Λόϋντ τα'χει 400;(07-03-2010)
β)Ένα μικρό Κουϊζ;(28-02-2010)
Το πρόβλημα έγγειται στο να βρούμε το πλήθος των συνδυασμών όταν χωρίζουμε n άτομα σε k ομάδες.Στη συνέχεια αθροίζουμε από k=1:15.
Από τα σχόλεια του προβλήματος υποθέτω θα προκύπτει κάποιος μεγάλος αριθμός,οπότε κάποιο κολπάκι θα χρησιμοποιείται για να βγάλουμε το τελικό νούμερο,πριν κολλήσει το calculator.
Έκανα έναν υπολογισμό και βρήκα:
86211885
είμαι σωστός (ή έστω κοντά)?
Γενικά, σύμφωνα με τον τρόπο υπολογισμού μου ισχύει:
C[1]=1
C[2]=2
C[3]=5
C[4]=15
C[5]=51
C[6]=188
C[7]=731
C[8]=2950
C[9]=12235
C[10]=51822
C[11]=223191
C[12]=974427
C[13]=4302645
C[14]=19181100
C[15]=86211885
Όπου C[N] το πλήθος όλων των δυνατών χωρισμών μιας Ν-αδας.
Επειδή όμως ο τρόπος υπολογισμού προέκυψε λίγο πειραματικά και λίγο διαισθητικά θα περιμένω την απάντηση του κ. Papaveri για να δώσω λεπτομέρειες (εφόσον, φυσικά, είμαι σωστός)
@Δημήτρης Σκυριανόγλου
Το πρόβλημα ζητάει τη χρονική διάρκεια που απαιτείται για όλες τις μεταθέσεις των 15 ατόμων. Πρέπει να είναι παραπάνω.
Λοιπόν, ας πάρουμε τα πράγματα από την αρχή για να δω αν έχω καταλάβει σωστά:
Αν έχουμε μόνο ένα άτομο τότε οι δυνατοί χωρισμοί είναι μόνο ένας:
C[1]=1
Αν έχουμε δύο άτομα Α και Β τότε οι δυνατοί συνδυασμοί είναι:
Α - Β (μια μέρα πάει εκδρομή ο κάθε ένας μόνος του) και
ΑΒ - (την άλλη μέρα πάνε και οι δύο μαζί εκδρομή). Άρα:
C[2]=2
Αν έχουμε τρία άτομα Α, Β και Γ τότε οι πιθανοί συνδυασμοί είναι:
Α - Β - Γ (ο καθένας μόνος του)
Α - ΒΓ
Β - ΑΓ
Γ - ΑΒ (ένας μόνος του και οι άλλοι σε ζευγάρια)
ΑΒΓ (πάνε και οι τρεις μαζί). Άρα:
C[3]=5
Αν καταλαβαίνω καλά π.χ. στην περίπτωση Ν=3 την πρώτη μέρα θα πάνε και οι τρεις εκδρομή μόνοι τους, τη δεύτερη ο Α μόνος και ο Β με το Γ, την τρίτη μέρα ο Β μόνος και ο Α με το Γ κ.ο.κ. άρα χρειάζονται συνολικά 5 μέρες όσοι είναι και οι συνδυασμοί. Εκτός και αν εννοείτε ότι κάθε μέρα διοργανώνεται μία μόνο εκδρομή οπότε για να πάει ο κάθε ένα εκδρομή μόνος του απαιτούνται 3 ημέρες.
Χμ.. Τώρα που το ξανακοιτάω μου ήρθε και μια άλλη ιδέα... Θα επανέλθω.
@Δημήτρης Σκυριανόγλου
Λύνεται με το τύπο των μεταθέσεων των συνδυατικών μαθηματικών.
Έκανα τη σκέψη να υπολογίσω όλες τις δυνατές μεταθέσεις μια 15άδας (σε μονάδες, δυάδες, τριάδες τετράδες κτλ) και να τις προσθέσω:
Σ(i=1 έως Ν) των (Ν ανά i)
Η λογική είναι ότι αρχικά θα πάει εκδρομή ο κάθε ένας μόνος του. Μετά σε όλες τις δυνατές δυάδες, μετά σε όλες τις δυνατές τριάδες κ.ο.κ.
Για Ν=15 προκύπτει ο αριθμός 32767, δηλ. ένα μικρό νούμερο και από όσο κατάλαβα ψάχνουμε για κάτι μεγάλο.
Ίσως θα ήταν καλό να εξηγήσετε με ένα παράδειγμα π.χ για Ν=3 ή Ν=4 ποιο ακριβώς είναι το ζητούμενο γιατί ομολογώ ότι εξακολουθώ να είμαι μπερδεμένος. Η λύση που έδωσα πριν αφορά το πρόβλημα: Με πόσους τρόπους μπορεί να χωριστεί μια Ν-άδα στοιχείων αλλά καταλαβαίνω ότι δεν είναι τελικά αυτό που ψάχνουμε.
@Δημήτρης Σκυριανόγλου
Σας στέλνω με e-mail τη λύση για να καταλάβετε τι θέλω.
Τώρα που βρήκα λίγο χρόνο να το ψάξω,βρήκα ότι μπορείς να χωρίσεις ν άτομα σε 2 ομάδες με 2^(ν-1)-1 τρόπους.Δεδομένου ότι το να τα χωρίσεις σε 1 ή σε ν ομάδες είναι 1 τρόπος μένουν άλλες ν-3 περιπτώσεις!
κ papaveri μας αναγκάζετε να γυρίσουμε πολύ παλιά :)
Βρήκα τρόπο να χωρίσουμε τα v σε 3 ομάδες.
Είναι ίσο με Σ (ν κ) x (ν-κ λ) όπου (ν κ) = ν!/κ!(ν-κ)! για κ από πρώτος ακέραιος μεγαλύτερος ή ισος του ν/3 έως ν και λ από πρώτος ακέραιος μεγαλύτερος ή ίσος του κ/2 έως το ελάχιστο μεταξύ κ και ν-κ.Θα προσπαθήσω να βρω αν απλοποιείται αλλά προς το παρόν έχω άλλες δουλειές να τελειώσω.Το πρόβλημα είναι ότι για να εφαρμόσεις το παραπάνω για ν=15 απαιτούνται 19 γινόμενα και αθροίσματα.
@Ανώνυμος
Αναμένω.
Για Σ(ν κ)= ν!/κ!*(ν-μ)! έχουμε:
Σ(ν κ)= 15!/3!*(15-3)!
Σ(ν κ)= 15!/3!*12!
Σ(ν κ)= 13*14*15/1*2*3
Σ(ν κ)= 2.730/6
Σ(ν κ)= 455 ομάδες των τριών ατόμων.
Ευχαριστώ που περιμένετε!
Πάντως δεν εννοούσα ομάδες των τριών ατόμων αλλά για 15 άτομα ανά τρεις ομάδες.Αυτά πχ μπορούν να χωριστούν με τους παρακάτω τρόπους:
13 1 1
12 2 1
11 3 1
11 2 2
10 4 1
10 3 2
9 5 1
9 4 2
9 3 3
8 6 1
8 5 2
8 4 3
7 7 1
7 6 2
7 5 3
7 4 4
6 6 3
6 5 4
5 5 5.
Το άθροισμα που έδωσα δεν είναι αυτό που αναγράφετε.
Aπό το να καθίσω να υπολογίσω τους παραπάνω συνδυασμούς για 3,4,5 κλπ ομάδες προτιμώ να ψάξω να βρω έναν τρόπο απλοποίησης,πχ λόγω κάποιας συμμετρίας που υπάρχει,ή χρησιμοποιώντας κάποια συμπληρωματικά σύνολα.Μια τέτοια απλοποίηση πετυχαίνεται εύκολα όταν τους 15 τους χωρίζουμε σε 2 ομαδες.
Τότε
14 1
13 2
12 3
11 4
10 5
9 6
8 7
και παίρνουμε το αποτέλεσμα που σας έδωσα.
Απλά για σήμερα δεν έχω χρόνο να ασχοληθώ αφού αύριο πρέπει να παραδώσω ένα άρθρο.
@Ανώνυμος
Δείτε την ανάρτηση, λόγω του ότι το αρχικό πρόβλημα οδηγούσε σε διαφορετική κατεύθυνση.
Σας ευχαριστώ. Και ζητώ συγγνώμη για την ταλαιπωρία
Τώρα βέβαια η λύση είναι εύκολη
15!=1307674368000
@Ανώνυμος
Πολύ σωστά! Να συμπλήρώσω κι' εγώ ότι οι ημερες αυτές εκφραζονται σε έτη:
Διαιρούμε τις 1.307.674.368.000 ημέρες με το 365 για να τις μετατρέψουμε σε έτη κι’ έχουμε:
1.307.674.368.000 :365=3.582.669.501 χρόνια, 1 μήνα και ≈7 ημέρες.
Είναι ζήτημα εάν θα υφίσταται ο πλανήτης Γη!!!
Βέβαια παραμένει το αρχικό πρόβλημα :)
Η διατύπωση του νέου προβλήματος προήλθε λίγο ανάποδα, δηλ. από τη λύση του αρχικού προβλήματος που μου έστειλε ο κ. Papaveri. Διαβάζοντας τη διατύπωση του νέου προβλήματος ξανά, θα αφαιρούσα την αναφορά "ώστε όλοι να περάσουν από όλες τις θέσεις" καθώς αυτό μπερδεύει λιγάκι (αν το πρόβλημα ήταν να περάσουν όλοι από όλες τις θέσεις θα αρκούσε απλώς μια ολίσθηση κάθε φορά και με 15 παρελάσεις θα είχαμε το επιθυμητό αποτέλεσμα).
Όσο για το αρχικό πρόβλημα εμμένω τελικά στη λύση που έδωσα στη 2η προσπάθειά μου, δηλ. το 86211885 που, αν τα έχω υπολογίσει σωστά, είναι όλοι οι διαφορετικοί δυνατοί συνδυασμοί με τους οποίους μπορούμε να χωρίσουμε μια ομάδα από 15 διαφορετικά άτομα. Το 15! (που είναι η λύση που είχε κατ' αρχήν ο κ. Papaveri στο μυαλό του) έχω την εντύπωση ότι δεν "κολλάει" καθόλου με το πρόβλημα.
ΥΓ κ. Papaveri δείτε παρακαλώ το τελευταίο σχόλιό μου στο πρόβλημα με τα πρόβατα. Το 721 που δόθηκε είναι φυσικά μια σωστή λύση αλλά πριν το 721 υπάρχει και το 301 :-) . Δείτε την ανάλυσή μου
Το θέμα για το αρχικό πρόβλημα είναι να βγάλουμε κάποιον γενικό τύπο,αντί να μετράμε μια μια τις μεταθέσεις.
Να υποθέσω ότι ο δικός σας είναι αναδρομικός.
@Ανώνυμος
Πράγματι κατέληξα σε κάποιον αναδρομικό τύπο ο οποίος προέκυψε λίγο διαισθητικά και λίγο μελετώντας τις περιπτώσεις για μικρά Ν όπου φαίνεται να επαληθεύεται. Δεν έχω όμως ακόμη κάποια αυστηρή μαθηματική απόδειξη.
Ο τύπος είναι:
C(N) = Σ(i=1 έως Ν-1)(C(i) * C(N-i)) + 1
Διαισθητικά αυτός ο τύπος λέει (περίπου) ότι: Για να υπολογίσω όλους τους τρόπους που μπορώ να διαχωρίσω Ν αντικείμενα χρειάζεται να υπολογίσω όλους τους τρόπους με τους οποίους μπορώ να χωρίσω i από αυτά τα αντικείμενα επί τους τρόπους που μπορώ να χωρίσω τα υπόλοιπα Ν-i και αυτό για όλα τα i από 1 έως Ν.
Το +1 που μπαίνει στο τέλος είναι για την περίπτωση όπου στην πραγματικότητα δεν έχουμε διαχωρισμό σε ομάδες αλλά όλα τα Ν αντικείμενα "χωρίζονται" σε μία ομάδα των Ν αντικειμένων.
Καθότι πληροφορικός ο ίδιος και επειδή ξέρω ότι το ιστολόγιο παρακολουθούν εκπαιδευτικοί αλλά και -πιθανώς- μαθητές δίνω το προγραμματάκι που έγραψα σε "ΓΛΩΣΣΑ" (στην ουσία εξελληνισμένη έκδοση της Pascal που χρησιμοποιείται για τη διδασκαλία του προγραμματισμού στο λύκειο (μέχρι πρότινος και στο γυμνάσιο)) για τους υπολογισμούς:
ΠΡΟΓΡΑΜΜΑ Δυνατοί_Χωρισμοί_Ναδας
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: C[20], N, i
ΑΡΧΗ
C[1] <- 1
ΓΙΑ N ΑΠΟ 2 ΜΕΧΡΙ 15
C[N] <- 0
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ (N - 1)
C[N] <- C[N] + C[i]* C[N - i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
C[N] <- C[N] + 1
ΓΡΑΨΕ 'C[', N, ']=', C[N]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΥΓ όπως βλέπω στην προεπισκόπηση δε διατηρείται η εσοχή προς τα μέσα στις γραμμές του προγράμματος έτσι γίνεται λίγο δυσανάγνωστο, ελπίζω να βγαίνει άκρη
Αν θέλετε να δείξετε ότι η λύση σας είναι σωστή,μπορείτε να το αποδείξετε με επαγωγή.
Θα μας προσφέρετε,τότε τη λύση και στο αρχικό πρόβλημα.
Ναι, η επαγωγή είναι μια ιδέα αλλά η εφαρμογή της δεν είναι και τόσο απλή! :-) Αν βρω χρόνο θα το εξετάσω.
Το βασικό μου θέμα είναι να κατανοήσω το μηχανισμό της λύσης. Έχω έναν τύπο που πειραματικά φαίνεται να δουλεύει αλλά δε μπορώ να εξηγήσω 100% γιατί είναι σωστός :-)
Λοιπόν, επειδή το πρόβλημα του χωρισμού μιας Ν-άδας για κάποιο λόγο με εξιτάρισε αποφάσισα να ασχοληθώ ώστε να αποδείξω τη λύση που πρότεινα... Η προσπάθεια αυτή τελικώς είχε διπλό αποτέλεσμα: α) Μου έδειξε ότι η αρχική λύση που έδωσα δεν είναι σωστή και β) με βοήθησε να καταλάβω καλύτερα το μηχανισμό λύσης του προβλήματος έτσι ώστε να παρουσιάσω τώρα μια νέα λύση η οποία πιστεύω ότι είναι και η σωστή κυρίως επειδή –σε αντίθεση με την προηγούμενη- μπορώ και να την εξηγήσω.
Όλα ξεκίνησαν όταν, στην προσπάθεια να καταλάβω το μηχανισμό της λύσης, εξέτασα ξανά όλες τις περιπτώσεις χωρισμού μιας 4-αδας και μιας 5-άδας. Εκεί ανακάλυψα ότι για Ν=5 οι δυνατοί χωρισμοί δεν είναι 51 όπως υπολόγισα αρχικά αλλά 52 (μου είχε ξεφύγει ένας!). Αυτό σήμαινε ότι ο τύπος που είχα βρει ήταν λάθος αλλά, από την άλλη, η αναλυτική καταγραφή όλων των δυνατών χωρισμών με βοήθησε να ανακαλύψω ένα pattern στο σχηματισμό των δυνατών χωρισμών, το οποίο υποπτευόμουν ότι υπήρχε αλλά δε μπορούσα να συγκεκριμενοποιήσω. Τελικά η οπτικοποίηση της λύσης μου έδειξε το σωστό δρόμο...
Έχουμε λοιπόν το εξής πρόβλημα:
Με πόσους διαφορετικούς τρόπους μπορούν να χωριστούν σε ομάδες Ν διαφορετικά αντικείμενα;
Για να γίνει κατανοητό το αντικείμενο του προβλήματος δίνω ένα παράδειγμα για Ν=3. Αν έχω 3 διαφορετικά αντικείμενα (Α, Β, Γ) αυτά μπορούν να χωριστούν σε ομάδες με 5 διαφορετικούς τρόπους (η ‘-‘ δηλώνει το διαχωρισμό των ομάδων)
Α-Β-Γ (τρεις ομάδες)
ΑΒ-Γ (δύο ομάδες)
Α-ΒΓ (δύο ομάδες)
ΑΓ-Β (δύο ομάδες)
ΑΒΓ (η τελευταία περίπτωση είναι λίγο εκφυλισμένη, είναι η περίπτωση όπου στην πραγματικότητα όλα τα αντικείμενα ομαδοποιούνται σε μία ομάδα)
Αν ονομάσουμε C(N) το πλήθος όλων των δυνατών χωρισμών μιας Ν-άδας από διαφορετικά αντικείμενα τότε γενικά ισχύει:
C(N) = Σ(από i=0 έως N-1)((N-1 ανά i) * C(i) για Ν=1,2,3.... (1)
Εξ ορισμού θέτουμε C(0) = 1 (που πρακτικά μπορεί να μη βγάζει νόημα αλλά μαθηματικά έχει την έννοια ότι το τίποτα (0) μπορεί να χωριστεί μόνο σε τίποτα δηλ με ένα τρόπο).
Έτσι για τις πρώτες τιμές του Ν, αναπτύσσοντας τον παραπάνω τύπο έχουμε:
C(1) = 1 * C(0) = 1
C(2) = 1 * C(0) + 1 * C(1) = 2
C(3) = 1 * C(0) + 2 * C(1) + 1 * C(2) = 5
C(4) = 1 * C(0) + 3 * C(1) + 3 * C(2) + 1 * C(3) = 15
C(5) = 1 * C(0) + 4 * C(1) + 6 * C(2) + 4 * C(3) + 1 * C(4) = 52
Παρατηρήστε τους συντελεστές σε κάθε εξίσωση. Βλέπετε κάτι, σας θυμίζουν κάτι; Για να το δούμε λίγο διαφορετικά:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Είναι φανερό νομίζω πλέον. Οι συντελεστές για το C(N) ισούνται με τους αριθμούς στη Ν-οστή γραμμή του τριγώνου του Pascal! (Για όσους τυχόν δε γνωρίζουν, στο τρίγωνο του Pascal κάθε νέα γραμμή δημιουργείται αθροίζοντας τους δύο από πάνω αριθμούς στην προηγούμενη ακριβώς γραμμή. Για περισσότερα δείτε εδώ:
http://users.sch.gr/geoman22/mathP/Pascal.htm αλλά και εδώ:
http://mathedutech.wordpress.com/tag/τρίγωνο-του-pascal/ )
Έτσι ο τύπος (1) μπορεί να γραφεί και ως:
C(N) = Σ(από i=0 έως N-1)((Pi) * C(i) για Ν=1,2,3.... (2)
όπου Pi είναι ο i-οστός όρος της Ν-οστής γραμμής του τριγώνου του Pascal.
Για να πω την αλήθεια όταν ανέλυσα πειραματικά το πρόβλημα για Ν=4 και Ν=5 ο αρχικός τύπου που κατέληξα ήταν αυτός, ο οποίος έχει μια κομψότητα (είναι σχετικά απλός, είναι αναδρομικός, εμπλέκει μέσα το φαινομενικά “άσχετο” τρίγωνο του Pascal) αλλά δε με βοηθούσε πολύ να καταλάβω γιατί είναι σωστός. Σκέφτηκα ότι οι συντελεστές αυτοί θα πρέπει να μπορούν να προκύψουν και αλλιώς δηλ. ως συνάρτηση του Ν και του i. Ήμουν μάλιστα σίγουρος (βλέποντας και το γραφικό ανάπτυγμα της λύσης για Ν=4 και 5, σαν αυτό που παρουσίασα για Ν=3 πιο πάνω) ότι οι συντελεστές αυτοί πρέπει να δηλώνουν κάποιο πλήθος συνδυασμών. Άρχισα λοιπόν να αναζητώ μια έκφραση του τύπου “Ν ανά i” και δεν άργησα να ανακαλύψω ότι οι συντελεστές προκύπτουν από τον τύπο (Ν-1 ανά i) για i=0,1,2,…N-1 !
Έτσι προέκυψε ο τύπος (1) αλλά, το κυριότερο, βοηθήθηκα να καταλάβω γιατί η λύση είναι σωστή και γιατί ισχύει αυτός ο τύπος. Η απόδειξη που θα παρουσιάσω είναι κατά κάποιο τρόπο αναδρομική και επαγωγική με την έννοια ότι θεωρεί πως για να υπολογίσω τους χωρισμούς μιας Ν-άδας ξέρω να υπολογίζω τους χωρισμούς για σύνολα με πλήθος αντικειμένων από 1 έως και Ν-1.
Ας θεωρήσουμε λοιπόν ότι έχουμε ένα σύνολο από Ν-1 διαφορετικά αντικείμενα τα οποία μπορούν να χωριστούν σε ομάδες με C(N-1) τρόπους. Στο σύνολο προσθέτουμε ακόμη ένα αντικείμενο οπότε το πλήθος των αντικειμένων γίνεται πλέον Ν. Με πόσους τρόπους μπορούν να χωριστούν τα αντικείμενα αυτά;
Κατ’ αρχήν το πρώτο που μπορούμε να κάνουμε είναι θεωρήσουμε το νέο στοιχείο ως μία ομάδα και να χωρίσουμε τα Ν-1 υπόλοιπα. Με πόσους τρόπους μπορούν να χωριστούν αυτά; Μα φυσικά με C(N-1) τρόπους. Άρα ο πρώτος όρος προκύπτει από το συνδυασμό της μίας ομάδας του ενός στοιχείου με τους C(N-1) τρόπους χωρισμού των υπόλοιπων Ν-1 στοιχείων: 1 * C(N-1). Να ο πρώτος όρος του αθροίσματος.
Το επόμενο βήμα είναι μαζί με το νέο Ν-οστό αντικείμενο να βάλουμε ένα από τα υπόλοιπα Ν-1. Αυτό θα δημιουργήσει μία ομάδα από 2 αντικείμενα ενώ τα υπόλοιπα Ν-2 μπορούν να χωριστούν με C(N-2) τρόπους. Πόσες όμως διαφορετικές ομάδες (δυάδες) μπορούμε να φτιάξουμε συνδυάζοντας το Ν-οστό αντικείμενο με ένα από τα Ν-1? Η απάντηση είναι: ((Ν-1) ανά 1) (=Ν-1)! Έτσι οι συνδυασμοί που προκύπτουν για αυτή την περίπτωση είναι: (Ν-1 ανά 1) * C(N-2). Να και ο δεύτερος όρος!
Κατόπιν μαζί με το νέο Ν-οστό αντικείμενο βάζουμε μαζί 2 αντικείμενα από τα υπόλοιπα Ν-1 φτιάχνοντας μια τριάδα. Τα υπόλοιπα N-3 αντικείμενα που απομένουν μπορούν να χωριστούν με C(N-3) τρόπους. Πόσες διαφορετικές τριάδες μπορούμε να φτιάξουμε συνδυάζοντας το Ν-οστό αντικείμενο με δύο αντικείμενα από τα Ν-1? Η απάντηση είναι: ((Ν-1) ανά 2)! Έτσι οι συνδυασμοί που προκύπτουν για αυτή την περίπτωση είναι: (Ν-1 ανά 2) * C(N-3). Να και ο τρίτος όρος!
Με την ίδια λογική εξαντλούμε τις περιπτώσεις προσθέτοντας κάθε φορά στην ομάδα του νέου Ν-οστού αντικειμένου ένα ακόμη αντικείμενο από τα Ν-1. Για την περίπτωση όπου η ομάδα του Ν-οστού αντικειμένου περιέχει i+1 αντικείμενα (δηλ. το Ν-οστό και i από τα υπόλοιπα Ν-1) τότε οι δυνατοί χωρισμοί είναι: (Ν-1 ανά i) * C(N-i).
Έτσι:
C(N) = Σ(από i=0 έως N-1)((N-1 ανά i) * C(Ν-1-i) για Ν=1,2,3.... (3)
Όμως επειδή (Ν-1 ανά i) = (N-1 ανά Ν-1-i) δηλ. οι συντελεστές του C(i) και C(N-1-i) είναι ίσοι η εξίσωση (3) γράφεται λίγο απλούστερα στη μορφή της (1):
C(N) = Σ(από i=0 έως N-1)((N-1 ανά i) * C(i) για Ν=1,2,3.... (1)
με C(0) = 1.
Εφαρμόζοντας τον τύπο (1) για τις τιμές του Ν από 1 έως και 15 παίρνουμε:
C[1]=1
C[2]=2
C[3]=5
C[4]=15
C[5]=52
C[6]=203
C[7]=877
C[8]=4140
C[9]=21147
C[10]=115975
C[11]=678570
C[12]=4213597
C[13]=27644437
C[14]=190899322
C[15]=1382958545
Ελπίζω να ήμουν κατανοητός :-) Αν υπάρχουν παρατηρήσεις είναι, φυσικά, ευπρόσδεκτες!
Δημοσίευση σχολίου