Τα θρανία

Λάμπρος Κατσάπας · #1

Για μαθητές...

Τα θρανία μιας τάξης είναι αριθμημένα από το

μέχρι το

. Κάθε μαθητής έχει το δικό του θρανίο.

Μια μέρα ο δάσκαλος αποφάσισε να αλλάξει θέσεις τους μαθητές βάζοντας από κάτω από το θρανίο τους ένα χαρτί με τον

αριθμό του θρανίου που έπρεπε να κάτσουν. Κάθε μέρα οι μαθητές θα πρέπει να κάθονται στις θέσεις που αναγράφονται στο

χαρτί που είναι από κάτω από το θρανίο που κάθονταν την προηγούμενη ημέρα. Να αποδειχθεί ότι μετά από κάποιο αριθμό

ημερών οι μαθητές θα επιστρέψουν στις αρχικές τους θέσεις (ταυτόχρονα). ΣΗΜΕΙΩΣΗ: Ο δάσκαλος μια φορά στην αρχή

τοποθέτησε τα χαρτάκια και από εκεί και πέρα τα άφησε στη θέση τους.

Λάμπρος Κατσάπας · #2

Ανοικτό για όλους.

Λάμπρος Κατσάπας · #3

Ας πούμε ότι ο μαθητής που κάθεται στο θρανίο υπ'αριθμόν

είναι ο $\mu _1$ , αυτός που κάθεται στο

ο $\mu _2$ και ούτω καθεξής. Αν πάρουμε οποιονδήποτε μαθητή τότε αυτός μετά από κάποιες μέρες

θα επιστρέψει αναγκαστικά στη θέση του. Πράγματι, ας πάρουμε τον $\mu _1$ (το ίδιο θα ισχύει και για τους

υπόλοιπους όπως θα φανεί παρακάτω). Για τον $\mu _1$ υπάρχει κάποιος $\mu _i,i=1,2,...,n$ ο οποίος έχει

στο θρανίο του το χαρτάκι με τον αριθμό

. Αν

τότε το ζητούμενο έχει αποδειχθεί. Αν $i\neq 1$ ,

υποθέτωντας (προς άτοπο) ότι ο $\mu _1$ δεν θα φτάσει στη θέση του τότε δεν θα πρέπει να φτάσει ποτέ στη

θέση του $\mu _i$ (διαφορετικά την επόμενη μέρα θα κάθονταν στη θέση του). Για τον $\mu _i$ υπάρχει

$\mu _j,j\neq i\neq1\neq j$ ο οποίος έχει στο θρανίο του το χαρτάκι με τον αριθμό

. Αφού ο $\mu _1$

δεν θα κάτσει στη θέση του $\mu _i$ , δεν θα πρέπει να κάτσει αναγκαστικά και στη θέση του $\mu _j$

(διαφορετικά μετά από δύο μέρες θα κάθονταν στη θέση του). Επειδή το πλήθος των μαθητών είναι πεπερασμένο, είναι

φανερό ότι συνεχίζοντας αυτό το σκεπτικό ο $\mu _1$ δεν θα κάτσει σε καμία από τις θέσεις 2,3,...,n

το

οποίο είναι προφανώς άτοπο. Αν d_i,i=1,2,...,n

ο ελάχιστος αριθμός ημερών ώστε o $\mu _i$ να κάτσει

στη θέση του τότε το LCM(d_1,d_2,...,d_n)

μας δίνει το ζητούμενο.

#4

Ας δούμε και ένα άλλο σκεπτικό γιατί ο κάθε ένας επιστρέφει κάποτε στην θέση του.

Ξεκινάμε με οποιοδήποτε και έστω ότι αρχικά κάθεται στην θέση a_1

, την επόμενη μέρα στην a_2

, την μεθεπόμενη στην a_3

κ.ο.κ. Σε κάποια φάση θα πρέπει να κάτσει ξανά σε μια καρέκλα που έχει ήδη καθίσει. Δηλαδή $a_k = a_{\ell}$ για κάποιο $k < \ell$ . Τότε πρέπει $a_{k-1} = a_{\ell-1}$ αφού φτάνει στο θρανίο $a_k = a_{\ell}$ από ένα και μοναδικό θρανίο. Ομοίως πρέπει $a_{k-2} = a_{\ell-2}$ κ.ο.κ. Καταλήγουμε στο $a_1 = a_{1+\ell-k}$ . Δηλαδή όντως σε κάποια φάση θα επανέλθει στο αρχικό θρανίο.

Τα θρανία

Τα θρανία

Re: Τα θρανία

Re: Τα θρανία

Re: Τα θρανία

Μέλη σε σύνδεση