Σελίδα 1 από 1
Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Πέμ Νοέμ 10, 2016 12:46 am
από socrates
Τα 96 μέλη ενός σωματείου αρίθμησης κάθονται σε ένα μεγάλο κύκλο. Αρχίζουν να λένε 1, 2, 3 κ.ο.κ. με σειρά γύρω από τον κύκλο. Το κάθε μέλος που λέει ένα άρτιο (ζυγό) αριθμό βγαίνει από τον κύκλο και οι υπόλοιποι συνεχίζουν, αρχίζοντας το δεύτερο κύκλο με το 97. Συνεχίζουν με αυτό τον τρόπο μέχρι να μείνει ένα μέλος. Ποιον αριθμό είπε στον πρώτο κύκλο το μέλος που έμεινε τελευταίο;
Re: Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Πέμ Νοέμ 10, 2016 3:53 pm
από Διονύσιος Αδαμόπουλος
Ονομάζουμε το κάθε μέλος με τον αριθμό που θα πει στον 1ο γύρο και ξεκινάμε:
1ος γύρος:
Έχουμε

αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το

(περιττός αριθμός).
Θα μείνουν οι

αριθμοί της μορφής

, δηλαδή οι:

.
2ος γύρος:
Έχουμε

αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το

(περιττός αριθμός).
Θα μείνουν οι

αριθμοί της μορφής

, δηλαδή οι:

.
3ος γύρος:
Έχουμε

αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το

(περιττός αριθμός).
Θα μείνουν οι

αριθμοί της μορφής

, δηλαδή οι:

.
4ος γύρος:
Έχουμε

αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το

(περιττός αριθμός).
Θα μείνουν οι

αριθμοί της μορφής

, δηλαδή οι:

.
5ος γύρος:
Έχουμε

αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το

(περιττός αριθμός).
Θα μείνουν οι

αριθμοί της μορφής

, δηλαδή οι:

.
6ος γύρος:
Έχουμε

αριθμούς (περιττός αριθμός).
Ξεκινάμε με την αρίθμηση με το

(περιττός αριθμός).
Θα μείνουν οι

αριθμοί της μορφής

, δηλαδή οι:

.
7ος γύρος:
Έχουμε

αριθμούς (άρτιος αριθμός).
Ξεκινάμε με την αρίθμηση με το

(άρτιος αριθμός).
Ο αριθμός

φεύγει και ο αριθμός

μένει τελευταίος.
Re: Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Πέμ Νοέμ 10, 2016 4:35 pm
από Demetres
Πιο γενικά, έστω ότι έχουμε

άτομα σε κύκλο και έστω ότι

είναι η θέση του ατόμου που μένει τελευταίο. Τότε:
Παρατήρηση 1:
Απόδειξη: Μετά το τέλος του πρώτου γύρου θα μείνουν

άτομα, τα

. Ο δεύτερος γύρος θα αρχίζει από περιττό αριθμό. Άρα θα την γλιτώσει αυτός που βρίσκεται στην θέση

από τους

. Αυτός είναι ο

.
Παρατήρηση 2:
Απόδειξη: Μετά το τέλος του πρώτου γύρου θα μείνουν

άτομα, τα

. Ο δεύτερος γύρος θα αρχίζει από άρτιο αριθμό. Θα φύγει λοιπόν ο

και μένουν

άτομα, τα

με τον επόμενο, δηλαδή τον

να λέει περιττό αριθμό. Άρα θα την γλιτώσει αυτός που βρίσκεται στην θέση

από τους

. Αυτός είναι ο

.
Θέλουμε το

. Αρκεί να υπολογίσουμε τα

.
Έχουμε
και τέλος

.
Άσκηση: Βρείτε τύπο για το

.
Re: Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Πέμ Νοέμ 10, 2016 9:15 pm
από Διονύσιος Αδαμόπουλος
Demetres έγραψε:Πιο γενικά, έστω ότι έχουμε

άτομα σε κύκλο και έστω ότι

είναι η θέση του ατόμου που μένει τελευταίο. ...
Άσκηση: Βρείτε τύπο για το

.
Νομίζω πως η συνάρτηση

είναι η εξής:
Έχω κάποιες ιδέες σχετικά με το πώς αποδεικνύεται, π.χ με δεντροδιάγραμμα, αλλά δεν είμαι σίγουρος αν κάτι τέτοιο θα αρκούσε. Επίσης προβληματίζομαι πώς θα μπορούσα να ανεβάσω τη λύση από τεχνικής απόψεως (LaTeX, εικόνα, ...).
Υ.Γ. Για δοκιμή στο Excel, βάζουμε τον τύπο σε κάποιο κελί εκτός του Α1, και στο Α1 δίνουμε τιμές για το
=2*(A1-2^ROUNDDOWN(LOG(A1;2);0))+1
Re: Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Κυρ Νοέμ 13, 2016 11:53 am
από Demetres
Διονύσιος Αδαμόπουλος έγραψε:Demetres έγραψε:Πιο γενικά, έστω ότι έχουμε

άτομα σε κύκλο και έστω ότι

είναι η θέση του ατόμου που μένει τελευταίο. ...
Άσκηση: Βρείτε τύπο για το

.
Νομίζω πως η συνάρτηση

είναι η εξής:
Έχω κάποιες ιδέες σχετικά με το πώς αποδεικνύεται, π.χ με δεντροδιάγραμμα, αλλά δεν είμαι σίγουρος αν κάτι τέτοιο θα αρκούσε. Επίσης προβληματίζομαι πώς θα μπορούσα να ανεβάσω τη λύση από τεχνικής απόψεως (LaTeX, εικόνα, ...).
Διονύση, είναι σωστή η απάντηση.
Για δεντροδιάγραμμα ίσως ο πιο εύκολος τρόπος είναι να δοκιμάσεις να το κάνεις στο geogebra. (Δεν χρειάζεται για την απόδειξη όμως. Μπορείς να χρησιμοποιήσεις επαγωγή.)
Re: Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Κυρ Νοέμ 13, 2016 3:37 pm
από Διονύσιος Αδαμόπουλος
Λίγο Μπελάς αλλά τέλος πάντων...
Αρχικά, είναι προφανές ότι κάθε θετικός ακέραιος μπορεί να γραφτεί στην μορφή:

, όπου

και

μη αρνητικοί ακέραιοι και

. Ακόμη ισχύουν τα εξής:

και

, όπου

μη αρνητικός ακέραιος.
Θα αποδείξουμε ότι

(1)
Απόδειξη:
Θα αποδείξουμε πως για

ισχύει

. Για

, έχουμε πως

. Έστω πως για κάποιο

ισχύει

. Για

έχουμε

. Επομένως ισχύει.
Έστω πως για

, ισχύει για κάθε

ότι

.
Για

ισχύει πως

, επομένως ισχύει ο ισχυρισμός (1)
Για

έχουμε ότι

, επομένως ισχύει ο ισχυρισμός (1)
Παρατηρούμε λοιπόν πως αν δεν ίσχυε για κάποιο

ο ισχυρισμός (1), τότε δεν θα ίσχυε και για

άρα ούτε και για

, ... μέχρι που θα φτάναμε να μην ισχύει και για

, άτοπο.
Τώρα έστω

. Τότε

. Όμως επειδή

, θέλουμε το μέγιστο

που είναι μικρότερο ή ίσο του

. Αυτό είναι το

. Άρα

Re: Άνθρωποι σε κύκλο
Δημοσιεύτηκε: Κυρ Νοέμ 13, 2016 6:45 pm
από Demetres
Διονύσιος Αδαμόπουλος έγραψε:
Θα αποδείξουμε ότι

(1)
Ουσιαστικά αυτό λέει το εξής:
Θεώρημα: Αν

στην δυαδική του αναπαράσταση, με

, τότε

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

. Στην απόδειξη όλοι οι αριθμοί θα είναι σε δυαδική αναπαράσταση: Έστω

με

.
Αν

τότε

άρα
Αν

τότε

άρα
