Άνθρωποι σε κύκλο

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

socrates
Επιμελητής
Δημοσιεύσεις: 6603
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Άνθρωποι σε κύκλο

#1

Μη αναγνωσμένη δημοσίευση από socrates »

Τα 96 μέλη ενός σωματείου αρίθμησης κάθονται σε ένα μεγάλο κύκλο. Αρχίζουν να λένε 1, 2, 3 κ.ο.κ. με σειρά γύρω από τον κύκλο. Το κάθε μέλος που λέει ένα άρτιο (ζυγό) αριθμό βγαίνει από τον κύκλο και οι υπόλοιποι συνεχίζουν, αρχίζοντας το δεύτερο κύκλο με το 97. Συνεχίζουν με αυτό τον τρόπο μέχρι να μείνει ένα μέλος. Ποιον αριθμό είπε στον πρώτο κύκλο το μέλος που έμεινε τελευταίο;
Θανάσης Κοντογεώργης

Ετικέτες:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 806
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Άνθρωποι σε κύκλο

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος »

Ονομάζουμε το κάθε μέλος με τον αριθμό που θα πει στον 1ο γύρο και ξεκινάμε:

1ος γύρος:
Έχουμε 96 αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το 1 (περιττός αριθμός).
Θα μείνουν οι 48 αριθμοί της μορφής 2n+1, δηλαδή οι: 1, 3, 5, \ldots, 95.

2ος γύρος:
Έχουμε 48 αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το 96+1=97 (περιττός αριθμός).
Θα μείνουν οι 24 αριθμοί της μορφής 4n+1, δηλαδή οι: 1, 5, 9, \ldots, 93.

3ος γύρος:
Έχουμε 24 αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το 96+48+1=145 (περιττός αριθμός).
Θα μείνουν οι 12 αριθμοί της μορφής 8n+1, δηλαδή οι: 1, 9, 17, \ldots, 89.

4ος γύρος:
Έχουμε 12 αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το 96+48+24+1=169 (περιττός αριθμός).
Θα μείνουν οι 6 αριθμοί της μορφής 16n+1, δηλαδή οι: 1, 17, 33, \ldots, 81.

5ος γύρος:
Έχουμε 6 αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το 96+48+24+12+1=181 (περιττός αριθμός).
Θα μείνουν οι 3 αριθμοί της μορφής 32n+1, δηλαδή οι: 1, 33, 65.

6ος γύρος:
Έχουμε 3 αριθμούς (περιττός αριθμός).
Ξεκινάμε με την αρίθμηση με το 96+48+24+12+6+1=187 (περιττός αριθμός).
Θα μείνουν οι 2 αριθμοί της μορφής 64n+1, δηλαδή οι: 1, 65.

7ος γύρος:
Έχουμε 2 αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το 96+48+24+12+6+3+1=190 (άρτιος αριθμός).
Ο αριθμός 1 φεύγει και ο αριθμός \boxed{65} μένει τελευταίος.
Houston, we have a problem!
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 9010
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Άνθρωποι σε κύκλο

#3

Μη αναγνωσμένη δημοσίευση από Demetres »

Πιο γενικά, έστω ότι έχουμε n άτομα σε κύκλο και έστω ότι f(n) είναι η θέση του ατόμου που μένει τελευταίο. Τότε:

Παρατήρηση 1: f(2n) = 2f(n) - 1

Απόδειξη: Μετά το τέλος του πρώτου γύρου θα μείνουν n άτομα, τα 1,3,\ldots,2n-1. Ο δεύτερος γύρος θα αρχίζει από περιττό αριθμό. Άρα θα την γλιτώσει αυτός που βρίσκεται στην θέση f(n) από τους 1,3,\ldots,2n-1. Αυτός είναι ο 2f(n)-1.

Παρατήρηση 2: f(2n+1) = 2f(n) +1 1

Απόδειξη: Μετά το τέλος του πρώτου γύρου θα μείνουν n+1 άτομα, τα 1,3,\ldots,2n-1,2n+1. Ο δεύτερος γύρος θα αρχίζει από άρτιο αριθμό. Θα φύγει λοιπόν ο 1 και μένουν n άτομα, τα 3,5,\ldots,2n+1 με τον επόμενο, δηλαδή τον 3 να λέει περιττό αριθμό. Άρα θα την γλιτώσει αυτός που βρίσκεται στην θέση f(n) από τους 3,\ldots,2n-1. Αυτός είναι ο 2f(n)+1.

Θέλουμε το f(96). Αρκεί να υπολογίσουμε τα f(48),f(24),f(12),f(6),f(3),f(1).

Έχουμε

f(1) = 1

f(3) = 2f(1)+1 = 3

f(6) = 2f(3) - 1 = 5

f(12) = 2f(6) - 1 = 9

f(24) = 2f(12) - 1 = 17

f(48) = 2f(24) - 1 = 33

και τέλος

f(96) = 2f(48)-1 = 65.

Άσκηση: Βρείτε τύπο για το f(n).
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 806
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Άνθρωποι σε κύκλο

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος »

Demetres έγραψε:Πιο γενικά, έστω ότι έχουμε n άτομα σε κύκλο και έστω ότι f(n) είναι η θέση του ατόμου που μένει τελευταίο. ...

Άσκηση: Βρείτε τύπο για το f(n).
Νομίζω πως η συνάρτηση f(n) είναι η εξής:

\displaystyle{f(n)=2(n-2^{\lfloor \log_2 n \rfloor})+1}

Έχω κάποιες ιδέες σχετικά με το πώς αποδεικνύεται, π.χ με δεντροδιάγραμμα, αλλά δεν είμαι σίγουρος αν κάτι τέτοιο θα αρκούσε. Επίσης προβληματίζομαι πώς θα μπορούσα να ανεβάσω τη λύση από τεχνικής απόψεως (LaTeX, εικόνα, ...).

Υ.Γ. Για δοκιμή στο Excel, βάζουμε τον τύπο σε κάποιο κελί εκτός του Α1, και στο Α1 δίνουμε τιμές για το n
=2*(A1-2^ROUNDDOWN(LOG(A1;2);0))+1
Houston, we have a problem!
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 9010
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Άνθρωποι σε κύκλο

#5

Μη αναγνωσμένη δημοσίευση από Demetres »

Διονύσιος Αδαμόπουλος έγραψε:
Demetres έγραψε:Πιο γενικά, έστω ότι έχουμε n άτομα σε κύκλο και έστω ότι f(n) είναι η θέση του ατόμου που μένει τελευταίο. ...

Άσκηση: Βρείτε τύπο για το f(n).
Νομίζω πως η συνάρτηση f(n) είναι η εξής:

\displaystyle{f(n)=2(n-2^{\lfloor \log_2 n \rfloor})+1}

Έχω κάποιες ιδέες σχετικά με το πώς αποδεικνύεται, π.χ με δεντροδιάγραμμα, αλλά δεν είμαι σίγουρος αν κάτι τέτοιο θα αρκούσε. Επίσης προβληματίζομαι πώς θα μπορούσα να ανεβάσω τη λύση από τεχνικής απόψεως (LaTeX, εικόνα, ...).
Διονύση, είναι σωστή η απάντηση. :coolspeak:

Για δεντροδιάγραμμα ίσως ο πιο εύκολος τρόπος είναι να δοκιμάσεις να το κάνεις στο geogebra. (Δεν χρειάζεται για την απόδειξη όμως. Μπορείς να χρησιμοποιήσεις επαγωγή.)
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 806
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Άνθρωποι σε κύκλο

#6

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος »

Λίγο Μπελάς αλλά τέλος πάντων... :roll:

Αρχικά, είναι προφανές ότι κάθε θετικός ακέραιος μπορεί να γραφτεί στην μορφή:

2^{k}+m, όπου k και m μη αρνητικοί ακέραιοι και m<2^{k}. Ακόμη ισχύουν τα εξής: f(2a)=2f(a)-1 και f(2a+1)=2f(a)+1, όπου a μη αρνητικός ακέραιος.

Θα αποδείξουμε ότι f(2^{k}+m)=2m+1 (1)

Απόδειξη:

Θα αποδείξουμε πως για m=0 ισχύει f(2^{k})=1. Για k=0, έχουμε πως f(1)=1. Έστω πως για κάποιο k ισχύει f(2^{k})=1. Για k+1 έχουμε f(2^{k+1})=f(2\cdot 2^{k})=2f(2^{k})-1=1. Επομένως ισχύει.

Έστω πως για m=l, ισχύει για κάθε k ότι f(2^{k}+l)=2l+1.

Για m=2l ισχύει πως f(2^{k}+2l)=f(2(2^{k-1}+l))=2f(2^{k-1}+l)-1=4l+1=2(2l)+1, επομένως ισχύει ο ισχυρισμός (1)

Για m=2l+1 έχουμε ότι f(2^{n}+2l+1)=f(2(2^{n-1}+l)+1)=2f(2^{n-1}+l)+1=4l+3=2(2l+1)+1, επομένως ισχύει ο ισχυρισμός (1)

Παρατηρούμε λοιπόν πως αν δεν ίσχυε για κάποιο m ο ισχυρισμός (1), τότε δεν θα ίσχυε και για \lfloor \frac{m}{2} \rfloor άρα ούτε και για \lfloor \frac{m}{4} \rfloor, ... μέχρι που θα φτάναμε να μην ισχύει και για m=0, άτοπο.

Τώρα έστω n=2^{k}+m. Τότε m=n-2^{k}. Όμως επειδή m<2^{k}, θέλουμε το μέγιστο 2^k που είναι μικρότερο ή ίσο του n. Αυτό είναι το 2^{\lfloor \log_2n \rfloor}. Άρα f(n)=2(n-2^{\lfloor \log_2n \rfloor})+1
Houston, we have a problem!
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 9010
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Άνθρωποι σε κύκλο

#7

Μη αναγνωσμένη δημοσίευση από Demetres »

Διονύσιος Αδαμόπουλος έγραψε: Θα αποδείξουμε ότι f(2^{k}+m)=2m+1 (1)
Ουσιαστικά αυτό λέει το εξής:

Θεώρημα: Αν n = \overline{a_1 \cdots a_k} στην δυαδική του αναπαράσταση, με a_1 = 1, τότε f(n) = \overline{a_2 \cdots a_k a_1}.

Μπορούμε λοιπόν να γράψουμε την απόδειξη του Διονύση πιο απλά ως εξής:

Προχωράμε με επαγωγή στο n. Στην απόδειξη όλοι οι αριθμοί θα είναι σε δυαδική αναπαράσταση: Έστω n = \overline{a_1a_2 \cdots a_k} με a_1 = 1.

Αν a_k = 0 τότε n = 2\overline{a_1 a_2 \cdots a_{k-1}} άρα

\displaystyle{ \begin{aligned} 
f(n) &=  2f(\overline{a_1 a_2 \cdots a_{k-1}})-1 \\ 
&= 2\overline{a_2 \cdots a_{k-1} a_1} - 1 \\ 
&= \overline{a_2 \cdots a_{k-1}10} - 1 \\ 
&= \overline{a_2 \cdots a_{k-1}01}  \\ 
&= \overline{a_2 \cdots a_{k-1}a_ka_1} 
\end{aligned}}

Αν a_k = 1 τότε n = 2\overline{a_1 a_2 \cdots a_{k-1} + 1} άρα

\displaystyle{ \begin{aligned} 
f(n) &=  2f(\overline{a_1 a_2 \cdots a_{k-1}})+1 \\ 
&= 2\overline{a_2 \cdots a_{k-1} a_1} + 1 \\ 
&= \overline{a_2 \cdots a_{k-1}10} + 1 \\ 
&= \overline{a_2 \cdots a_{k-1}11}  \\ 
&= \overline{a_2 \cdots a_{k-1}a_ka_1} 
\end{aligned}}
Απάντηση

Επιστροφή στο “Γενικά - Επίπεδο Θαλή/Ευκλείδη (Seniors)”

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

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