Ένας κύκλος έχει χωριστεί σε $n$ τομείς. Μερικοί τομείς περιέχουν πέτρες ενώ το συνολικό πλήθος των πετρών είναι $n + 1$.Στην συνέχεια, αναδιατάσ-
σουμε τις πέτρες σύμφωνα με τον εξής κανόνα:
Επιλέγουμε δύο τυχαίες πέτρες που βρίσκονται στον ίδιο τομέα και τις μετακινούμε στους δύο διπλανούς τομείς - μία αριστερά και μία δεξιά.
Αποδείξτε ότι έπειτα από συγκεκριμένο πλήθος τέτοιων μετακινήσεων οι μισοί τουλάχιστον τομείς θα περιέχουν πέτρες.
Αποδείξτε ότι έπειτα από συγκεκριμένο πλήθος τέτοιων μετακινήσεων οι μισοί τουλάχιστον τομείς θα περιέχουν πέτρες.
N. Konstantinov - N. Vasilyev
Περιοδικό Quantum
Ας υποθέσουμε ότι υπάρχει αρχική κατανομή των ν+1 πετρών στους ν τομείς και διαδοχή κινήσεων από την οποία προκύπτουν πάντα λιγότεροι από τους μισούς τομείς που περιέχουν πέτρες. Η υπόθεση αυτή συνεπάγεται ότι σε οποιοδήποτε στάδιο μιας τέτοιας διαδικασίας θα υπάρχει πάντα μπλοκ δύο τουλάχιστον διαδοχικών τομέων που είναι άδειοι από πέτρες.
ΑπάντησηΔιαγραφήΠαρατηρούμε όμως ότι ένα τέτοιο μπλοκ, αν δεν υπάρχει εξαρχής, δεν μπορεί να προκύψει από οποιαδήποτε διαδοχή κινήσεων, αφού σε κάθε κίνηση, ακόμα κι αν αδειάζει ένας τομέας που περιείχε αρχικά 2 μόνο πέτρες, οι δύο γειτονικοί του τομείς θα περιέχουν τελικά πέτρες ακόμα κι αν ήταν αρχικά άδειοι. Επομένως, μετά από κάθε κίνηση, το πλήθος των ζευγαριών άδειων διαδοχικών τομέων παραμένει σταθερό ή μειώνεται.
Για να είναι δυνατόν όμως ένα ζευγάρι διαδοχικών τομέων να παραμείνουν επ’ άπειρον άδειοι, θα πρέπει καθένας από αυτούς να έχει δεύτερο γειτονικό τομέα που περιέχει πάντα 1 το πολύ πέτρα και για να είναι αυτό δυνατό θα πρέπει με τη σειρά τους και οι γειτονικοί των γειτονικών τομείς να περιέχουν πάντα 1 το πολύ πέτρα κ.ο.κ. Καταλήγουμε δηλαδή τελικά, ότι για να υπάρχει πάντα ζευγάρι διαδοχικών άδειων τομέων, θα πρέπει σε καθέναν από τους υπόλοιπους ν-2 τομείς να υπάρχει πάντα 1 το πολύ πέτρα, άρα ν-2 το πολύ πέτρες συνολικά, δηλαδή λιγότερες από ν+1, άτοπο.
Καταλήγουμε λοιπόν ότι η αρχική υπόθεση δεν ισχύει, επομένως με οποιαδήποτε αρχική κατανομή των πετρών, σε κάποιο στάδιο της διαδικασίας οι μισοί τουλάχιστον τομείς θα περιέχουν πέτρες.