▪ H μεγάλη ουρά

"Όλοι οι θετικοί ακέραιοι αριθμοί ήταν προσωπικοί φίλοι του Ραμάνουτζαν."

John E. Littlewood

$N$ άνθρωποι στέκονται σε μια σειρά/ουρά, κοιτώντας όλοι μπροστά (προς την αρχή της ουράς).

Πόσοι απ'αυτούς, κατά μέσο όρο, είναι σε θέση να πουν : "Είμαι ψηλότερος/η απ'όλους όσοι είναι μπροστά μου!";
AΠΑΝΤΗΣΗ:

Έστω Ψ(N) ο αναμενόμενος αριθμός/μέσος όρος  των ανθρώπων που μπορούν να κάνουν τη δήλωση. Ψ για «ψηλός». :-)

Αν τους εξετάσουμε όλους ,εκτός από τον τελευταίο στη σειρά, τότε αυτή η ομάδα των  N - 1 ανθρώπων περιέχει εξ ορισμού Ψ(Ν-1) ανθρώπους που είναι σε θέση να κάνουν τη δήλωση. Ας προσθέσουμε τώρα και τον τελευταίο στη σειρά! Υπάρχει πιθανότητα  1/N  να είναι ο ψηλότερος, οπότε σ’αυτήν την περίπτωση μπορεί να κάνει τη δήλωση. Αλλιώς δεν μπορεί.

Έτσι βρήκαμε την θεμελιώδη επαγωγική/αναδρομική σχέση:

Ψ(Ν) =Ψ(Ν-1) + 1/Ν  (1)

Ξεκινώντας λοιπόν με το Ψ(1)=1 επαγωγικά βρίσκουμε:

Ψ(Ν)= 1 +1/2 +1/3+...+1/Ν  (2)

Αυτή η ακολουθία για μεγάλα Ν , έχει όριο το ln(N)  (το οποίο, σημειωτέον  ότι μεγαλώνει «πολύ λίγο» όσο μεγαλώνει το Ν).

2^η(εναλλακτική /πιο «αυστηρή» απόδειξη):

Έστω Ψ(Ν) ο ζητούμενος μέσος όρος.

Ας θεωρήσουμε τη θέση του ψηλότερου ατόμου στη σειρά!

Αν είναι ο τελευταίος στη σειρά (πράγμα που έχει πιθανότητα 1/Ν να συμβαίνει), τότε το πρόβλημα περιορίζεται στα Ν-1 άτομα που βρίσκονται μπροστά του.  Έτσι, σ’αυτήν την περίπτωση, μπορούμε να περιμένουμε  1+Ψ(Ν-1)  ανθρώπους να είναι σε θέση να κάνουν την δήλωση.

Αν ο ψηλότερος είναι ο δεύτερος από το τέλος (πράγμα που και πάλι έχει πιθανότητα 1/Ν να συμβαίνει), τότε το πρόβλημα μετατοπίζεται στα Ν-2 άτομα που βρίσκονται μπροστά του.(γιατί ο  τελευταίος στη σειρά πίσω του ,δεν μπορεί να κάνει τη δήλωση αφού είναι κοντύτερος). Έτσι, σ’αυτην την περίπτωση, μπορούμε να αναμένουμε  1+Ψ(Ν-2) ανθρώπους να είναι σε θέση να κάνουν τη δήλωση.

Συνεχίζοντας στο ίδιο λογικό-επαγωγικό μοτίβο και προσθέτωντας κάθε φορά όλες τις  Ν πιθανότητες σε σχέση με την θέση του ψηλότερου ατόμου, καταλήγουμε στην :

Ψ(Ν)=  (1/Ν) * ((1+Ψ(Ν-1)) + (1+Ψ(Ν-2)) +...+(1+Ψ(1)) + (1+Ψ(0))  η οποία γίνεται:

N*Ψ(Ν)= Ν+ Ψ(Ν-1) +Ψ(Ν-2) +...+Ψ(1)  (α)

Η αντίστοιχη εξίσωση για  Ν-1  ,είναι:

(N-1)*Ψ(Ν-1)= (Ν-1) + Ψ(Ν-2) +Ψ(Ν-2)+...+Ψ(1)  (β)

Αφαιρώντας την (β) από την (α) προκύπτει:

Ψ(Ν)=Ψ(Ν-1) +1/Ν  (που είναι η θεμελιώδης σχέση  (1) που βρήκαμε και στην 1^η λύση).

📘

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →