Άπειρες πολλές θέσεις παρατάσσονται κατά μήκος ενός ιπποδρόμου και αριθμούνται $1,2, 3, 4, ....$ Ένας ζαλισμένος ταμίας πούλησε εισιτήρια για τις πρώτες $m$ θέσεις, αλλά πούλησε περισσότερα από ένα εισιτήρια για ορισμένες θέσεις και κανένα εισιτήριο για άλλες.
Συνολικά, πούλησε $n$ εισιτήρια, όπου $n> m$. Οι θεατές μπαίνουν ένας ένας.
Ο καθένας προσπαθεί να καθίσει στο κάθισμα για το οποίο έχει εισιτήριο. Αν δεν είναι κανείς στο κάθισμα, κάθονται. Εάν αυτή η θέση είναι ήδη κατειλημμένη, ο θεατής λέει "Ω!" και μετακινείται στο κάθισμα με τον επόμενο μεγαλύτερο αριθμό. Αν αυτό το κάθισμα δεν είναι κατειλημμένο, το παίρνει ο θεατής. Διαφορετικά, το άτομο λέει ξανά "Ω!" και μετακινείται στη θέση με τον επόμενο μεγαλύτερο αριθμό. Αυτό συνεχίζεται έως ότου ο θεατής βρει μια κενή θέση.
Αποδείξτε ότι ο αριθμός των "Ω!" που εκφωνούνται είναι ανεξάρτητος από τη σειρά με την οποία εισέρχονται οι θεατές.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου