Δύσκολη;

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

Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 562
Εγγραφή: Παρ Μάιος 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 φορά συνολικά.


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.

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

Re: Δύσκολη;

#2

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

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


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

Re: Δύσκολη;

#3

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

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


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 794
Εγγραφή: Σάβ Μαρ 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.
Δημοσιεύσεις: 562
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Δύσκολη;

#5

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

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


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.
harrisp
Δημοσιεύσεις: 536
Εγγραφή: Σάβ Μαρ 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.
Δημοσιεύσεις: 562
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Δύσκολη;

#7

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

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


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.
Απάντηση

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

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

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