1. Πόσοι 11-ψήφιοι θετικοί ακέραιοι σχηματίζονται από τα ψηφία 1 ή 2 σε κάθε θέση χωρίς να εμφανίζεται το ψηφίο 1 σε δύο διαδοχικές θέσεις;
2. Σε μια λίμνη βρίσκονται μια σειρά από νούφαρα, αριθμημένα 1,2,3,…
Ένας βάτραχος που θα βρεθεί κάποια στιγμή στο νούφαρο κ, αμέσως μετά πηδάει με ίσες πιθανότητες στο νούφαρο κ+1 ή το νούφαρο κ+2.
Αν ο βάτραχος ξεκινήσει από το νούφαρο 1, ποια είναι η πιθανότητα να βρεθεί κάποια στιγμή στο νούφαρο 11;
Δοκιμότερος θα ήταν ο τίτλος 11 εναντίον 12, αφού τα 11 νούφαρα είναι επανάληψη.
Η κυβέρνηση μιας χώρας έχει 12 υπουργούς. Κάθε υπουργός έχει 5 από τους άλλους υπουργούς φίλους και τους υπόλοιπους 6 εχθρούς. Πόσες τριάδες υπουργών είναι όλοι τους φίλοι ή όλοι τους εχθροί μεταξύ τους;
Πρόβλημα 1
Για να είμαστε σίγουροι ότι μπορεί να σχηματιστεί τέτοιος 11ψήφιος θα πρέπει να έχει το πολύ έξι ψηφία 1. Έτσι
Μπορεί να φτιαχτεί 11ψήφιος χωρίς κανένα 1=> 1
11 ψηφιος με 1 σε μια θέση => 11
11 ψήφιος σε δύο μη διαδοχικές θέσεις =>45
11 ψήφιος σε τρεις μη διαδοχικές θέσεις => 84
11 ψηφιος σε τέσσερις μη διαδοχικές θέσεις =>70
11 ψηφιος σε πέντε μη διαδοχικές θέσεις =>21
11 ψήφιος σε έξι μη διαδοχικές θέσεις => 1
Σύνολο 233
Πρόβλημα 2
Μπορούμε να βρούμε πρώτα τις τριάδες που δεν μας κάνουν.
Ο κάθε υπουργός μπορεί να φτιάξει μια τριάδα όπου θα έχει έναν φίλο και έναν εχθρό. Άρα 5*6=30 τρόπους. Αφού έχουμε 12 υπουργούς μπορούμε να φτιάξουμε 12*30 =360 τριάδες. Εδώ πρέπει να προσέξουμε αφού η κάθε τριάδα έχει διπλομετρηθεί. Άρα έχουμε 180 καθαρές τριάδες. Συνολικά μπορούν να φτιαχτούν C(12,3)=220 τριάδες. Συνεπώς, οι ζητούμενες τριάδες είναι 220-180=40
**Γιατί η κάθε τριάδα έχει διπλομετρηθεί ; Ας δώσουμε ένα παράδειγμα. Έστω ο υπουργός Α αυτός έχει έναν φίλο υπουργό τον Β και έναν εχθρό υπουργό τον Γ.
Εμείς δε γνωρίζουμε τη σχέση Β και Γ. Έστω Β-Γ είναι φίλοι. Όταν υπολογίσουμε την τριάδα με επικεφαλής αυτή τη φορά τον Β το τρίγωνο Β-Α-Γ δεν μπορεί να προσμετρηθεί γιατί όλοι είναι φίλοι. Αντίθετα, το τρίγωνο Γ-Α-Β προσμετράται κανονικά αφού για τον Γ οι Α και Β είναι εχθρός και φίλος αντίστοιχα. Συνεπώς, το τρίγωνο Α-Β-Γ έχει μετρηθεί δύο φορές στα 360. Με αντίστοιχο τρόπο καταλαβαίνουμε το διπλομέτρημα στην περίπτωση που Β-Γ είναι εχθροί.
1. Στη γενική περίπτωση, υπάρχουν D(ν,κ,δ) = [ν-(κ-1)*δ]! / {κ!*[ν-(κ-1)*δ-κ]!} τρόποι για να κατανεμηθούν κ ομοειδή στοιχεία μέσα σε ένα σύνολο ν στοιχείων, έτσι ώστε να έχουν τουλάχιστον απόσταση δ μεταξύ τους.
Εδώ, θα κατανείμουμε από 0 έως 6 φορές το στοιχείο “1” (κ=[0,6]) μέσα σε 11 θέσεις (ν=11) ώστε να μην υπάρχουν δύο διαδοχικά στοιχεία “1” (δ=1) και οι υπόλοιπες θέσεις θα καλυφθούν από το στοιχείο “2”. Στο τέλος θα αθροίσουμε όλους αυτούς τους τρόπους κατανομών. Έχουμε λοιπόν:
D(11,0,1)= 1
D(11,1,1)= 11
D(11,2,1)= 45
D(11,3,1)= 84
D(11,4,1)= 70
D(11,5,1)= 21
D(11,6,1)= 1
Το άθροισμα αυτών των κατανομών είναι 233, οπότε αυτό είναι και το ζητούμενο του προβλήματος.
2. Η πιθανότητα να βρεθεί ο βάτραχος στον νούφαρο κ είναι Ρ(κ)= (1/2)*Ρ(κ-1) + (1/2)*Ρ(κ-2). Οπότε, έχουμε με τη σειρά:
Η πιθανότητα να βρεθεί στο νούφαρο 1 είναι Ρ1= 1
Η πιθανότητα να βρεθεί στο νούφαρο 2 είναι Ρ2= (1/2)*Ρ1 + (1/2)*0 = 1/2
Η πιθανότητα να βρεθεί στο νούφαρο 3 είναι Ρ3= (1/2)*Ρ2 + (1/2)*Ρ1 = 3/4
…
Συνεχίζοντας αυτό το μοτίβο, καταλήγουμε ότι η πιθανότητα να βρεθεί στο νούφαρο 11 είναι Ρ11= 683/1024.
Πολύ σωστές οι λύσεις των φίλων, μπράβο!
Δίνω μία ακόμα για το πρόβλημα 1:
Έστω π(ν) το πλήθος των ν-ψήφιων αριθμών με τη δεδομένη ιδιότητα.
Σε έναν (ν+1)-ψήφιο με την ίδια ιδιότητα:
-αν το τελευταίο του ψηφίο είναι 2, τότε πριν από αυτό μπορεί να βρίσκεται οποιοσδήποτε ν-ψήφιος με την ίδια ιδιότητα.
-αν το τελευταίο του ψηφίο είναι 1, τότε το προτελευταίο του ψηφίο είναι 2 και πριν από αυτό μπορεί να βρίσκεται οποιοσδήποτε (ν-1)-ψήφιος με την ίδια ιδιότητα.
Επομένως:
π(ν+1)=π(ν)+π(ν-1) και
π(1)=2, π(2)=3, π(3)=5,….,π(11)=233