Τα θρανία

Συντονιστές: Demetres, socrates, silouan

Λάμπρος Κατσάπας
Δημοσιεύσεις: 435
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

Τα θρανία

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Παρ Οκτ 26, 2018 9:23 am

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

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

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

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

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

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

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



Λέξεις Κλειδιά:
Λάμπρος Κατσάπας
Δημοσιεύσεις: 435
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

Re: Τα θρανία

#2

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Σάβ Οκτ 27, 2018 8:32 pm

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


Λάμπρος Κατσάπας
Δημοσιεύσεις: 435
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

Re: Τα θρανία

#3

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Κυρ Οκτ 28, 2018 9:48 pm

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

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

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

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

στο θρανίο του το χαρτάκι με τον αριθμό 1. Αν i=1 τότε το ζητούμενο έχει αποδειχθεί. Αν i\neq 1,

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

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

\mu _j,j\neq i\neq1\neq j ο οποίος έχει στο θρανίο του το χαρτάκι με τον αριθμό i. Αφού ο \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) μας δίνει το ζητούμενο.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8175
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Τα θρανία

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Οκτ 29, 2018 12:11 pm

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

Ξεκινάμε με οποιοδήποτε και έστω ότι αρχικά κάθεται στην θέση 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}. Δηλαδή όντως σε κάποια φάση θα επανέλθει στο αρχικό θρανίο.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Juniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης