Κουμπαράδες στην σειρά

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

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

Κουμπαράδες στην σειρά

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μάιος 16, 2018 4:46 pm

Σε ένα τραπέζι έχουμε στην σειρά 2018 κουμπαράδες. Κάθε μέρα, ο Δημήτρης επιλέγει 15 διαδοχικούς κουμπαράδες και βάζει σε κάθε ένα από αυτούς από ένα νόμισμα.

Μετά από κάποιες μέρες παρατηρήθηκε ότι υπάρχουν N κουμπαράδες, όχι απαραίτητα διαδοχικοί, που περιέχουν τον ίδιο (θετικό) αριθμό νομισμάτων.

Ποια είναι η μέγιστη δυνατή τιμή του N;



Λέξεις Κλειδιά:
Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1317
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Κουμπαράδες στην σειρά

#2

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Τετ Μάιος 16, 2018 11:48 pm

Θα αποδείξουμε πρώτα ότι ισχύει N \geqslant 2011.

Προς άτοπο, έστω ότι γίνεται N=2012, και έστω x το κοινό πλήθος νομισμάτων των κουμπαράδων αυτών.

Έστω c_1,c_2, \ldots, c_{2018} τα νομίσματα που περιέχουν οι 2018 κουμπαράδες.

Για k \in \{1,2, \ldots, 15\}, ορίζουμε s_k=c_k+c_{k+15}+c_{k+30}+ \ldots (π.χ. s_1=c_1+c_{16}+c_{31}+ \ldots +c_{2011}).

Εύκολα παρατηρούμε ότι όλα τα c_k είναι ίσα μεταξύ τους. Π.χ. s_1=s_2 \Rightarrow c_1+c_{16}+ \ldots+c_{2011}=c_2+c_{17}+ \ldots+c_{2012} γιατί αν προσθέσουμε ένα νόμισμα στον κουμπαρά με πλήθος νομισμάτων π.χ. c_{16}, στην 15-άδα που διαλέξαμε ανήκει ή ο c_{17} ή ο c_2, οπότε κάθε φορά που προστίθεται νόμισμα στο s_1, προστίθεται και στο s_2, ό.έ.δ.

Ορίζουμε έναν κουμπαρά ως καλό, αν έχει πλήθος νομισμάτων x.

Καταρχήν παρατηρούμε ότι τα αθροίσματα s_i, με i \in \{1,2, \ldots, 8 \} έχουν 135 προσθετέους, ενώ τα αθροίσματα s_j, με j \in \{9,10, \ldots, 15 \} έχουν 134 προσθετέους.

Θα αποδείξουμε το εξής Λήμμα:

Λήμμα

Υπάρχουν δείκτες i,j ώστε στα αθροίσματα s_i,s_j όλοι οι προσθετέοι είναι καλοί κουμπαράδες.

Θα δειχτεί πρώτα το εξής Λήμμα 1 (ως μέρος της απόδειξης του Λήμματος πιο πάνω):

Λήμμα 1
Σε ένα τουλάχιστον εκ των s_k, με k \in \{1,2, \ldots,15 \} όλοι οι προσθετέοι είναι καλοί κουμπαράδες.

Απόδειξη

Αν σε κανένα εκ των s_k όλοι οι προσθετέοι δεν είναι καλοί, τότε το μέγιστο πλήθος των καλών κουμπαράδων είναι το πολύ s_1+s_2+ \ldots+ s_8 +s_9+ \ldots+s_{15} \leqslant 8 \cdot 134+7 \cdot 133=2003<2011, άτοπο, οπότε το Λήμμα 1 αποδείχτηκε.

Έστω λοιπόν ότι ο κουμπαράς s_1 έχει όλα τα στοιχεία του καλά. Με την διαδικασία του Λήμματος 1, δείχνουμε ότι τουλάχιστον 9 ακόμη εκ των s_k πρέπει να έχουν όλα τα στοιχεία τους καλά. Αν τώρα κάποιος εκ των s_j έχει τα στοιχεία του καλά, το αρχικό Λήμμα αποδείχτηκε. Αν όχι, τότε όλοι οι s_i, \, i \in \{1,2, \ldots, 8 \} πρέπει να έχουν όλα τα στοιχεία τους καλά. Πάλι, όμως, μένει ένα ακόμη s_k που πρέπει να έχει όλα τα στοιχεία του καλά, και προφανώς αυτό ανήκει στα s_j

Έστω λοιπόν s_1,s_9 τα δύο αυτά αθροίσματα, με όλους τους προσθετέους να είναι καλοί κουμπαράδες.

Το s_1 είναι άθροισμα 135 καλών κουμπαράδων, με καθένα τιμή x.

Το s_9 είναι άθροισμα 134 καλών κουμπαράδων, με καθένα τιμή x.

Τότε, αφού s_1=s_9 , όπως δείχτηκε στην αρχή, είναι 135x=134x \Rightarrow x=0, άτοπο.

Επομένως, N \leqslant 2011.

Για N=2011 πραγματοποιούμε την εξής κατασκευή :

Για 0 \leqslant t \leqslant 133, επιλέγουμε τους 15t+1, 15t+2, \ldots, 15t+15.

Επίσης, επιλέγουμε τους Νο -2004-2018 κουμπαράδες.

Έτσι , κάθε ένας εκ των κουμπαράδων 1,2, \ldots, 2003,2011,2012, \ldots, 2018 έχει ένα νόμισμα, άρα επιτυγχάνεται η τιμή N=2011.

Τελικά, \rm maxN=2011.
τελευταία επεξεργασία από Ορέστης Λιγνός σε Πέμ Μάιος 17, 2018 4:18 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Ο καθένας λέει ότι να΄ναι και είναι πάντα σύμφωνος με τον εαυτό του ! 'Ολοι μιλάνε και κανείς δεν ακούει! Ο κόσμος είναι σε νοητική αδράνεια ! Ελένη Γλυκατζή Αρβελέρ
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1389
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Κουμπαράδες στην σειρά

#3

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Μάιος 17, 2018 8:05 am

Ορέστης Λιγνός έγραψε:
Τετ Μάιος 16, 2018 11:48 pm
Θα δείξουμε ότι στο σύνολο  \{s_1, s_2 , \ldots, s_8 \}, ένα εκ των s_i έχει όλους τους προσθετέους καλούς, και στο σύνολο \{s_9, s_{10}, \ldots, s_{15} \} ένα εκ των s_j έχει όλους τους προσθετέους καλούς.

Αν σε κανένα εκ των s_k όλοι οι προσθετέοι είναι καλοί, ..., άτοπο.
Προσοχή Ορέστη, η υπόθεσή σου προς άτοπο δεν είναι το αντίθετο αυτού που θέλεις να δείξεις (έβαλα σε bold δύο λέξεις).


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Altrian
Δημοσιεύσεις: 58
Εγγραφή: Τρί Μάιος 01, 2018 4:51 pm
Τοποθεσία: Βούλα, Αττική

Re: Κουμπαράδες στην σειρά

#4

Μη αναγνωσμένη δημοσίευση από Altrian » Πέμ Μάιος 17, 2018 11:40 am

Καλημέρα,
Με μια απλή προσέγγιση μπορούμε εύκολα να επιτύχουμε N= 2011. Ξεκινώντας από την πρώτη 15άδα την πρώτη μέρα (Νο 1 - Νο15) την δεύτερη 15άδα την δεύτερη μέρα κοκ, μετά από 134 μέρες θα έχουμε 134\times 15= 2010 κουμπαράδες στην σιερά με ένα νόμισμα έκαστος. Την επόμενη ημέρα τοποθετούμε από ένα νόμισμα στους 15 τελευταίους κουμπαράδες (Νο2004 ως Νο2018). Τότε 7 κουμπαράδες (Νο 2004 ως και Νο2010) θα έχουν 2 νομίσματα και οι υπόλοιποι 2011 από 1. Αρα υπάρχει N= 2011. Διασθητικά φαίνεται να είναι και το μέγιστο ζητούμενο.


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

Re: Κουμπαράδες στην σειρά

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Μάιος 17, 2018 2:01 pm

Η σωστή απάντηση είναι 2011 με κατασκευή όπως στην ανάρτηση του Altrian.

Η ιδέα του Ορέστη, όταν διορθωθεί θα δείξει ότι δεν μπορούμε να έχουμε περισσότερα.


Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1317
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Κουμπαράδες στην σειρά

#6

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Πέμ Μάιος 17, 2018 4:20 pm

Έγινε η επεξεργασία. Ευχαριστώ για την διόρθωση (νομίζω ήταν λίγο ασαφής η διατύπωση).

Επίσης, το τελευταίο κομμάτι της λύσης (απόδειξη ότι το N=2011 μας κάνει), το αντέγραψα από τον Altrian, ώστε να υπάρχει πλήρης η λύση.


Ο καθένας λέει ότι να΄ναι και είναι πάντα σύμφωνος με τον εαυτό του ! 'Ολοι μιλάνε και κανείς δεν ακούει! Ο κόσμος είναι σε νοητική αδράνεια ! Ελένη Γλυκατζή Αρβελέρ
Απάντηση

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

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

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