Η κερκίδα μιας πίστας αγώνων περιλαμβάνει μια άπειρη σειρά καθισμάτων, αριθμημένα ως $1, 2, 3, ...$
Ένας απρόσεκτος ταμίας πούλησε μεν εισιτήρια για τις $m$ πρώτες θέσεις έκοψε όμως περισσότερα από ένα εισιτήρια για ορισμένες θέσεις ενώ για κάποιες άλλες δεν έκοψε κανένα.
Συνολικά πούλησε $n$ εισιτήρια, όπου $n > m$. Οι θεατές πηγαίνουν στις θέσεις τους ένας - ένας.
Κάθε θεατής προσπαθεί να καθίσει στη θέση για την oποία έχει εισιτήριο. Αν δεν βρει κάποιον να έχει καταλάβει τη θέση, κάθεται σ' αυτή. Αν όμως τη βρει κατειλημμένη, μετακινείται στη θέση με την αμέσως μεγαλύτερη αρίθμηση μουρμουρίζοντας κάτι που ακούγεται σαν «αμάν» και εφόσον τη βρει ελεύθερη, κάθεται σ' αυτή.
Διαφορετικά, ξαναμουρμουρίζει «αμάν» και μετακινείται στην αμέσως επόμενη θέση.
Αυτό συνεχίζεται έως ότου βρει ελεύθερη θέση για να καθίσει.
Συνολικά πούλησε $n$ εισιτήρια, όπου $n > m$. Οι θεατές πηγαίνουν στις θέσεις τους ένας - ένας.
Κάθε θεατής προσπαθεί να καθίσει στη θέση για την oποία έχει εισιτήριο. Αν δεν βρει κάποιον να έχει καταλάβει τη θέση, κάθεται σ' αυτή. Αν όμως τη βρει κατειλημμένη, μετακινείται στη θέση με την αμέσως μεγαλύτερη αρίθμηση μουρμουρίζοντας κάτι που ακούγεται σαν «αμάν» και εφόσον τη βρει ελεύθερη, κάθεται σ' αυτή.
Διαφορετικά, ξαναμουρμουρίζει «αμάν» και μετακινείται στην αμέσως επόμενη θέση.
Αυτό συνεχίζεται έως ότου βρει ελεύθερη θέση για να καθίσει.
Αποδείξτε ότι το πλήθος των «αμάν» που θα ξεστομιστούν είναι ανεξάρτητο από τη σειρά προσέλευσης των Θεατών.
(Α. Shen και Ν. Vasilyev)
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου