Δύσκολη;

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

Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 593
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Δύσκολη;

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Δευ Μαρ 20, 2017 4:21 pm

Δίνεται το σύνολο A=\{1,2,...,n\}, όπου n θετικός ακέραιος. Αν \displaystyle{m \in \mathbb{Z^+}} και m \le n, να βρείτε το μέγιστο αριθμό σοιχείων f ενός υποσυνόλου B του A , ώστε να μην υπάρχουν δύο στοιχεία που να απέχουν ακριβώς κατά m. Για μαθητές.
τελευταία επεξεργασία από JimNt. σε Δευ Μαρ 20, 2017 6:55 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Bye :')

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

Re: Δύσκολη;

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Μαρ 20, 2017 5:41 pm

Μάλλον κάτι δεν πάει καλά με την εκφώνηση.


Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 593
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Δύσκολη;

#3

Μη αναγνωσμένη δημοσίευση από JimNt. » Δευ Μαρ 20, 2017 6:53 pm

Για να γίνει πιο κατανοητό το ζητούμενο. Βρείτε το μέγιστο πλήθος στοιχείων του B για A=\{1,2,...,2017\} και m=4. (Η αλήθεια είναι πως όντως υπήρχε νοηματικό λάθος :oops: )


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

Re: Δύσκολη;

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Δευ Μαρ 20, 2017 7:42 pm

JimNt. έγραψε:Για να γίνει πιο κατανοητό το ζητούμενο. Βρείτε το μέγιστο πλήθος στοιχείων του B για A=\{1,2,...,2017\} και m=4. (Η αλήθεια είναι πως όντως υπήρχε νοηματικό λάθος :oops: )
Χωρίζουμε τους αριθμούς σε 4 κατηγορίες, ανάλογα με το υπόλοιπο που θα αφήνει η διαίρεσή τους με το 4.

Με άλλα λόγια οι κατηγορίες πάνε κάπως έτσι:

4, 8, 12, ... , 2016

1, 5, 9, ... , 2017

2, 6, 10, ... , 2014

3, 7, 11, ... , 2015

Χωρίζουμε τους αριθμούς σε ζεύγη ανά 4. Ειδικότερα:

(4, 8), (12, 16), ... , (2012, 2016) (252 ζευγάρια)

(1, 5), (9, 13), ... , (2009, 2013), 2017 (253 ζευγάρια)

(2, 6), (10, 14), ... , (2010, 2014) (252 ζευγάρια)

(3, 7), (11, 15), ... , (2011, 2015) (252 ζευγάρια)

Προφανώς αν επιλέξουμε πάνω από 252 αριθμούς από την πρώτη κατηγορία, τότε θα σύμφωνα με την αρχή της περιστεροφωλιάς θα υπάρχουν 2 αριθμοί στο ίδιο ζευγάρι, άρα η διαφορά τους θα ήταν 4 άρα έχουμε πρόβλημα. Όμως μπορούμε να διαλέξουμε 252 αριθμούς, παίρνοντας τους πρώτους των ζευγαριών.

Άρα μπορούμε να επιλέξουμε το πολύ 252 αριθμούς από την πρώτη κατηγορία, 253 από τη δεύτερη, 252 από την τρίτη και 252 από την τέταρτη.

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

Συνεπώς μπορούμε να επιλέξουμε το πολύ 252+253+252+252= 1009 αριθμούς από το A χωρίς να υπάρχει πρόβλημα.


Houston, we have a problem!
Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 593
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Δύσκολη;

#5

Μη αναγνωσμένη δημοσίευση από JimNt. » Δευ Μαρ 20, 2017 7:46 pm

Αυτή ακριβώς είναι η ιδέα πίσω από το πρόβλημα. :coolspeak:


Bye :')
harrisp
Δημοσιεύσεις: 547
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Δύσκολη;

#6

Μη αναγνωσμένη δημοσίευση από harrisp » Δευ Μαρ 20, 2017 8:01 pm

Με μια βιαστική σκέψη , για την γενίκευση οι αριθμοι του συνόλου B θα είναι οι:

1,2,3,4,...,m,2m+1,2m+2,...,3m,4m+1,4m+2,...,


Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 593
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Δύσκολη;

#7

Μη αναγνωσμένη δημοσίευση από JimNt. » Δευ Μαρ 20, 2017 8:06 pm

Πόσοι είναι αυτοί όμως ;) ;


Bye :')
Απάντηση

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

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

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