Ο γρίφος της εβδομάδας – 11 εναντίον 11

1. Πόσοι 11-ψήφιοι θετικοί ακέραιοι σχηματίζονται από τα ψηφία 1 ή 2 σε κάθε θέση χωρίς να εμφανίζεται το ψηφίο 1 σε δύο διαδοχικές θέσεις;

 

2. Σε μια λίμνη βρίσκονται μια σειρά από νούφαρα, αριθμημένα 1,2,3,…

Ένας βάτραχος που θα βρεθεί κάποια στιγμή στο νούφαρο κ, αμέσως μετά πηδάει με ίσες πιθανότητες στο νούφαρο κ+1 ή το νούφαρο κ+2.

Αν ο βάτραχος ξεκινήσει από το νούφαρο 1, ποια είναι η πιθανότητα να βρεθεί κάποια στιγμή στο νούφαρο 11;

 

4 σχόλια

  1. Θανάσης Παπαδημητρίου

    Δοκιμότερος θα ήταν ο τίτλος 11 εναντίον 12, αφού τα 11 νούφαρα είναι επανάληψη.

    Η κυβέρνηση μιας χώρας έχει 12 υπουργούς. Κάθε υπουργός έχει 5 από τους άλλους υπουργούς φίλους και τους υπόλοιπους 6 εχθρούς. Πόσες τριάδες υπουργών είναι όλοι τους φίλοι ή όλοι τους εχθροί μεταξύ τους;

  2. ΚΣ

    Πρόβλημα 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. Με αντίστοιχο τρόπο καταλαβαίνουμε το διπλομέτρημα στην περίπτωση που Β-Γ είναι εχθροί.

  3. pantsik

    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.

  4. Θανάσης Παπαδημητρίου

    Πολύ σωστές οι λύσεις των φίλων, μπράβο!
    Δίνω μία ακόμα για το πρόβλημα 1:
    Έστω π(ν) το πλήθος των ν-ψήφιων αριθμών με τη δεδομένη ιδιότητα.
    Σε έναν (ν+1)-ψήφιο με την ίδια ιδιότητα:
    -αν το τελευταίο του ψηφίο είναι 2, τότε πριν από αυτό μπορεί να βρίσκεται οποιοσδήποτε ν-ψήφιος με την ίδια ιδιότητα.
    -αν το τελευταίο του ψηφίο είναι 1, τότε το προτελευταίο του ψηφίο είναι 2 και πριν από αυτό μπορεί να βρίσκεται οποιοσδήποτε (ν-1)-ψήφιος με την ίδια ιδιότητα.
    Επομένως:
    π(ν+1)=π(ν)+π(ν-1) και
    π(1)=2, π(2)=3, π(3)=5,….,π(11)=233

Αφήστε μια απάντηση

Η ηλ. διεύθυνση σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *