1. Ξεκινώντας από τον παρακάτω πίνακα, μεταθέτουμε όσες φορές και με όποια σειρά θέλουμε ολόκληρες γραμμές ή στήλες. Πόσους διαφορετικούς πίνακες μπορούμε να πάρουμε; (δύο πίνακες είναι διαφορετικοί αν διαφέρουν στον αριθμό μίας τουλάχιστον θέσης)
1 2 3 4 5 6 7
7 1 2 3 4 5 6
6 7 1 2 3 4 5
5 6 7 1 2 3 4
4 5 6 7 1 2 3
3 4 5 6 7 1 2
2 3 4 5 6 7 1
2. Οι πρέσβεις τεσσάρων χωρών και οι σύμβουλοί τους, ένας για τον καθένα, συνεδριάζουν γύρω από ένα στρογγυλό τραπέζι 12 θέσεων, αριθμημένων από 1 έως 12. Οι πρέσβεις κάθονται πάντα σε ζυγές θέσεις, ενώ οι σύμβουλοι πάντα δίπλα στον πρέσβη τους. Με πόσους διαφορετικούς τρόπους μπορούν οι οχτώ να καθίσουν γύρω από το τραπέζι; (δύο τρόποι είναι διαφορετικοί αν διαφέρουν στη θέση ενός τουλάχιστον ατόμου)
3. Σε μια λίμνη βρίσκονται μια σειρά από νούφαρα, αριθμημένα 1,2,3,..,11,.. Ένας βάτραχος που θα βρεθεί κάποια στιγμή στο νούφαρο κ, αμέσως μετά πηδάει με ίσες πιθανότητες στο νούφαρο κ+1 ή το νούφαρο κ+2. Αν ο βάτραχος ξεκινάει από το νούφαρο 1, ποια είναι η ακριβής πιθανότητα να πηδήσει κάποια στιγμή στο νούφαρο 11;
Πρόβλημα 3
Ο βάτραχος βρίσκεται στο νούφαρο 1. Παρατηρούμε ότι για να πάει στο νούφαρο 2 οι πιθανότητες είναι ½. Για να πάει στο νούφαρο 3 οι πιθανότητες είναι είτε να πάει κατευθείαν από το νούφαρο 1 (πιθ.1/2) ή από το νούφαρο 2 (πιθ.1/2*1/2=1/4). Συνολικά για το νούφαρο 3 είναι ½+1/4=3/4.
Παρατηρούμε ότι από την εκάστοτε θέση χ που βρίσκεται ο βάτραχος οι πιθανότητες να βρεθεί δύο θέσεις μακρύτερα δίνονται από τον τύπο Π(χ+2)=1/2*Π(χ)+1/2*Π(χ+1)=Π(χ)*(Π(χ+1)/2.
Π(2)=1/2
Π(3)=3/4
Εφαρμόζοντας τον αναδρομικό τύπο για να φτάσουμε μέχρι το νούφαρο 11 καταλήγουμε
Π(11)=683/1024=0,666…
Πρόβλημα 2.
Οι διπλωμάτες μπορούν να καθίσουν στις καρέκλες με 6!/4!*2=15 τρόπους.
Για λόγους ευκολίας των παρακάτω σκέψεων αριθμούμε τις καρέκλες 0,1,2,3…11 χωρίς όμως να αλλάζει κάτι ως προς την εφαρμογή της λύσης (αντί του 1-12).
Οι 15 τρόποι αυτοί μπορούν να αναλυθούν σε τέσσερις περιπτώσεις.
Α. Η περίπτωση αυτή περιλαμβάνει 2 τρόπους.
Δύο από τους διπλωμάτες να καθίσουν στις θέσεις 0 και 6 και οι υπόλοιποι δύο στη μα πλευρά του ημικύκλιου που ορίζουν οι θέσεις 0-6. Οι τρόποι που μπορούν να καθίσουν οι συνεργάτες είναι 5. Αν λάβουμε υπόψη μας και την περίπτωση του άλλου ημικυκλίου τότε συνολικά έχουμε 5*2=10 τρόπους να καθίσουν οι 8.
Β. Η περίπτωση αυτή περιλαμβάνει 4 τρόπους
Δύο διπλωμάτες να καθίσουν στις θέσεις 0 και 6 και οι υπόλοιποι δύο εκατέρωθεν. Εδώ, έχουμε συνολικά 34 τρόπους να καθίσουν οι 8.
Γ. Η περίπτωση αυτή περιλαμβάνει 8 τρόπους
Ένας διπλωμάτης να καθίσει σε μια από τις θέσεις 0 ή 6.Εδώ, οι τρόποι που μπορούν να καθίσουν οι 8 είναι 52.
Δ. Η περίπτωση αυτή περιλαμβάνει 1 τρόπο.
Οι θέσεις 0 και 6 είναι άδειες. Εδώ οι 8 μπορούν να καθίσουν με 9 τρόπους.
Συνολικά πλέον έχουμε 10+34+52+9=105
Πρόβλημα 1.
Παρατηρούμε ότι ενώ η διάταξη της κάθε σειράς και στήλης μπορεί να αλλάξει αυτό που δεν αλλάζει είναι η σύνθεσή. Δηλαδή δεν μπορούμε να συναντήσουμε δύο ίδιους αριθμούς σε μια στήλη ή σειρά.
Επιπλέον παρατηρούμε ότι στην αρχική μας διάταξη αν κρατήσουμε την πρώτη σειρά σταθερή. Το σύνολο των τρόπων που προκύπτουν είναι 6!. Αν επιχειρήσουμε να φέρουμε μια άλλη σειρά στη διάταξη (1,2,3,4,5,6,7) θα παρατηρήσουμε ότι ναι μεν όλες οι σειρές αλλάζουν αλλά οι διατάξεις παραμένουν οι 6 που είχαμε και πριν. Αυτό συμβαίνει γιατί ο αριθμός των αλλαγών που κάνουμε για να φέρουμε μια σειρά στη διάταξη που επιθυμούμε επηρεάζει κατά τον ίδιο τρόπο τις υπόλοιπες διατάξεις. Σε ένα παράδειγμα με 4χ4 η σκέψη γίνεται πιο καθαρή.
1234
4123
3412
2341
Αν επιχειρήσουμε το 3412 να το «κάνουμε» 1234 αυτομάτως όλες οι διατάξεις στις σειρές αλλάζουν φέρνοντας τα δύο ψηφία από μπροστά πίσω και έχουμε
3412
2341
1234
4123
όμως βλέπουμε ότι οι διατάξεις παραμενουν ως έχουν. Στην περίπτωσή μας η πρώτη σειρά μπορεί να δώσει 7! διατάξεις. Από τα παραπάνω ξέρουμε ότι η κάθε διάταξη συνδυάζεται με άλλες 6 αποκλειστικά. Συνεπώς 7!*6!=3.628.800. Γενικά για ν αριθμούς το σύνολο των τρόπων δίνεται από ν!*(ν-1)!
3. Ο βάτραχος μπορεί να φθάσει στο νούφαρο 11 με τους εξής τρόπους:
1. Με 11 μονά βήματα. Πιθανότητα (1/2)^11 =1/2048
2. Με 9 μονά και 1 διπλό βήμα. Πιθανότητα (1/2)^9*1/2*10=20/2048
3. Με 7 μονά και 2 διπλα βήματα. Πιθανότητα (1/2)^7*(1/2)^2*36=144/2048
4. Με 5 μονά και 3 διπλά βήματα. Πιθανότητα (1/2)^5*(1/2)^3*56=448/2048
5. Με 3 μονά και 4 διπλά βήματα. Πιθανότητα (1/2)^3*(1/2)^4*35=560/2048
6. Με 1 μονό και 4 διπλά βήματα. Πιθανότητα (1/2)*(1/2)^4*6=192/2048
Συνολική πιθανότητα: 1365/2048=66,65% περίπου
Θα πρέπει η απάντηση στο πρόβλημα 2 να συμπληρωθεί με τον πολλαπλασιασμό του 105 με το 4! εφόσον ζητάμε τους τρόπους που κάθονται και κάθε τρόπος είναι διαφορετικός αν διαφέρει σε ένα τουλάχιστον άτομο. Υπό αυτά τα δεδομένα οι τρόποι είναι 105*4!=2520.
1. Υπάρχουν 7! διαφορετικοί τρόποι να διαταχθούν οι γραμμές και για καθέναν από αυτούς υπάρχουν 7! διαφορετικοί τρόποι να διαταχθούν οι στήλες. Όμως κάθε συνδυασμός ξαναπροκύπτει από έναν διαφορετικό συνδυασμό γραμμής-στήλης, δηλαδή από 7 συνδυασμούς.
Άρα τελικά ο ζητούμενος αριθμός συνδυασμών είναι 7! * 7! / 7 = 3.628.800
2. Οι πρέσβεις μπορούν να κάτσουν με C(6,4)=15 τρόπους, αδιακρίτως ποιος πρέσβης κάθεται σε ποια θέση. Από αυτούς τους τρόπους οι 6 έχουν τους πρέσβεις σε διαδοχικές ζυγές θέσεις (4-0), οι 6 έχουν τους πρέσβεις σε 3 διαδοχικές ζυγές και μία αποκομμένη (3-1) και οι 3 τους έχουν σε δύο ζευγάρια διαδοχικών ζυγών θέσεων (2-2).
Αν λάβουμε υπόψιν μας και το ποιος πρέσβης κάθεται σε ποια θέση, τότε έχουμε συνδυασμούς (4-0): 4!*6=144, συνδυασμούς (3-1): 4!*6=144 και συνδυασμούς (2-2): 4!*3=72.
Όταν οι θέσεις των πρεσβευτών είναι της περίπτωσης (4-0) τότε οι σύμβουλοι μπορούν να καθίσουν με C(5,4)=5 τρόπους ανάμεσά τους, όταν είναι της περίπτωσης (3-1) τότε οι σύμβουλοι μπορούν να καθίσουν με C(4,3)*2=8 τρόπους ανάμεσά τους και όταν είναι της περίπτωσης (2-2) τότε οι σύμβουλοι μπορούν να καθίσουν με C(3,2)*C(3,2)=9 τρόπους ανάμεσά τους.
Άρα για πρέσβεις και συμβούλους μαζί έχουμε 144*5=720 συνδυασμούς περίπτωσης (4-0), 144*8=1152 συνδυασμούς περίπτωσης (3-1) και 72*9=648 συνδυασμούς περίπτωσης (2-2). Συνολικά έχουμε 720+1152+648 = 2520 συνδυασμούς.
3. Η πιθανότητα να βρεθεί ο βάτραχος στο 1ο νούφαρο είναι Ρ1=1.
Η πιθανότητα να βρεθεί στο 2ο νούφαρο είναι Ρ2= (1/2)Ρ1.
Η πιθανότητα να βρεθεί στο 3ο νούφαρο είναι Ρ3= (1/2)Ρ2 + (1/2)Ρ1.
Η πιθανότητα να βρεθεί στο 4ο νούφαρο είναι Ρ4= (1/2)Ρ3 + (1/2)Ρ2.
…
…
…
Η πιθανότητα να βρεθεί στο 11ο νούφαρο είναι Ρ11= (1/2)Ρ10 + (1/2)Ρ9.
Όλα αυτά απλοποιούνται εύκολα και προκύπτει ότι P11= 683/1024 ~ 0,667.
3. Απο απροσεξία, θεωρησα οτι τα βήματα είναι 11, ενώ στη πραγματικότητα είναι 10. Με αντίστοιχο σκεπτικό, υπολογίζω τη πιθανότητα σε 811/1024
3. Νεα διορθωση.
(1/2)^10+(1/2)^9*9+(1/2)^8*28+(1/2)^7*35+(1/2)^6*15+(1/2)^5=683/1024
Κωστή, Πάνο, είστε απαράδεκτα ασυναγώνιστοι, αλλά δεν περίμενα και τίποτε καλύτερο από εσάς!??
Στράτο, ήμουν έτοιμος να πιστέψω ότι το στιγμιαίο ολίσθημα ήταν του βατράχου ?, αλλά δεν μου το επέτρεψαν οι δύο προηγούμενοι. Εσύ το απέφυγες πάντως τελικά και μπράβο!
Δίνω μόνο δυο κάπως διαφορετικές προσεγγίσεις στους δύο από τους τρεις γρίφους:
Πρέσβεις
Θεωρούμε προσωρινά τους πρέσβεις μη διακριτούς μεταξύ τους.
Οι θέσεις των πρέσβεων είναι 6 και από αυτές χρησιμοποιούνται οι 4. Μένουν κενές 2 ζυγές θέσεις, οι οποίες μπορεί να είναι μεταξύ τους διαδοχικές (6 επιλογές) ή απέναντι (3 επιλογές) ή τίποτε από τα δύο (6 επιλογές). Με δεδομένες τις θέσεις των πρέσβεων, εύκολα προκύπτει ότι οι αντίστοιχες για κάθε περίπτωση επιλογές θέσεων των τεσσάρων συμβούλων είναι 5, 9 και 8. Επομένως υπάρχουν 6×5+3×9+6×8 = 105 συνδυασμένες επιλογές.
Οι πρέσβεις όμως είναι διακριτοί και κάθε μία από τις παραπάνω 105 συνδυασμένες επιλογές αντιστοιχεί σε 4!=24 διαφορετικές διατάξεις των πρέσβεων.
Συνεπώς οι ζητούμενοι διαφορετικοί τρόποι είναι 105×24 = 2520.
Νούφαρα
Ονομάζουμε Ρ(ν) την πιθανότητα να προσγειωθεί κάποια στιγμή ο βάτραχος στο νούφαρο ν. Εξ ορισμού, η πιθανότητα να μην προσγειωθεί ποτέ ο βάτραχος στο νούφαρο ν είναι η μισή της πιθανότητας να προσγειωθεί κάποια στιγμή στο νούφαρο ν-1. Επομένως:
1-Ρ(ν)=Ρ(ν-1)/2 => Ρ(ν)=1-Ρ(ν-1)/2
Ξεκινώντας από Ρ(1)=1, έχουμε:
Ρ(2)=1/2, Ρ(3)=3/4,…, Ρ(11)=683/1024