Επιλογή Αριθμών.

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

JimNt.
Δημοσιεύσεις: 500
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Επιλογή Αριθμών.

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Τετ Μαρ 15, 2017 6:37 pm

Με πόσους τρόπους μπορούμε να επιλέξουμε 5 αριθμούς από το σύνολο A=\{1,2,3,\ldots,18\} ώστε κάθε αριθμός να απέχει τουλάχιστον 2 από έναν άλλο;
τελευταία επεξεργασία από Demetres σε Τετ Μαρ 15, 2017 7:24 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: Βελτίωση latex


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.

Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1304
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Επιλογή Αριθμών.

#2

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Μαρ 16, 2017 10:11 am

Η επιλογή αντιστοιχεί 1-1 σε τυχαία επιλογή 5 αριθμών από ένα σύνολο 14 αριθμών και στη συνέχεια "εισαγωγή" 4 ακόμα αριθμών (ενός αμέσως μετά από κάθε έναν από τους πρώτους 4 επιλεγέντες) έτσι ώστε να εξασφαλίζεται η απόσταση.

Έτσι, ο αριθμός είναι \displaystyle \binom{14}{5} = 2002.


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

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ
Δημοσιεύσεις: 494
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Επιλογή Αριθμών.

#3

Μη αναγνωσμένη δημοσίευση από ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ » Πέμ Μαρ 16, 2017 1:04 pm

[quote="dement"]Η επιλογή αντιστοιχεί 1-1 σε τυχαία επιλογή 5 αριθμών από ένα σύνολο 14 αριθμών και στη συνέχεια "εισαγωγή" 4 ακόμα αριθμών (ενός αμέσως μετά από κάθε έναν από τους πρώτους 4 επιλεγέντες) έτσι ώστε να εξασφαλίζεται η απόσταση.

Έτσι, ο αριθμός είναι \displaystyle \binom{14}{5} = 2002. [/quote]


Το εχω συναντήσεις αρκετές φορές μα δεν το καταλαβαϊνω. Και επειδή το :logo: ειναι για να μαθαίνουμε θα μπορούσατε να μου εξήγησε τι εννοείται στην σημειωμένη φράση;


dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1304
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Επιλογή Αριθμών.

#4

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Μαρ 16, 2017 1:14 pm

Έστω ότι θέλω (για απλούστευση) να επιλέξω 2 από 6 αριθμούς (με τον περιορισμό). Αντί αυτού επιλέγω χωρίς περιορισμό 2 από 5 αριθμούς.
Στη συνέχεια επιτυγχάνω 1-1 αντιστοίχιση εισάγοντας ακόμα έναν αριθμό ανάμεσα στούς επιλεγέντες. Έστω c επιλεγμένος και n μη επιλεγμένος αριθμός. Τότε:

ccnnn αντιστοιχεί στο cncnnn
cncnn στο cnncnn
cnncn στο cnnncn
cnnnc στο cnnnnc
nccnn στο ncncnn

και ούτω καθεξής...


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

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

Re: Επιλογή Αριθμών.

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Μαρ 16, 2017 2:05 pm

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

Αν και το έχει καλύψει ο Δημήτρης, ας το δούμε και ελάχιστα διαφορετικά:

Θα αποφασίσουμε πόσους αριθμούς θα αφήσουμε πριν τον πρώτο αριθμό, πόσους μεταξύ του πρώτου και του δεύτερου, κ.τ.λ. μέχρι το πόσους αριθμούς θα αφήσουμε από τον πέμπτο και μετά. Ας γράψουμε x_1,\ldots,x_6 για αυτούς τους αριθμούς. Τότε έχουμε

x_1 + \cdots + x_6 = 18-5 = 13

Επιπλέον τα x_1,x_6 είναι μη αρνητικοί ακέραιοι ενώ τα x_2,\ldots,x_4 είναι θετικοί ακέραιοι. Γράφω τώρα y_1=x_1,y_6=x_6 και y_i = x_i-1 για 2 \leqslant i \leqslant 5.

Οπότε μένει να λύσω την εξίσωση

y_1+\cdots+y_6 = 13-4=9

στους μη αρνητικούς ακεραίους. Ο τύπος για αυτό είναι \binom{9+6-1}{6-1} = \binom{14}{5}. Αντί όμως να θυμόμαστε τον τύπο, είναι καλύτερα να θυμόμαστε πως προκύπτει αυτός ο τύπος. Τον εξηγώ, αρκετά αναλυτικά πιστεύω, στο λύση του Προβλήματος 4 εδώ.


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

Re: Επιλογή Αριθμών.

#6

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Μαρ 18, 2017 2:52 pm

Μια άλλη προσέγγιση:

Αντιστοιχούμε τους αριθμούς που θα επιλέξουμε με 1 και αυτούς που απομένουν με 0 δημιουργώντας έναν 18-ψήφιο δυαδικό αριθμό με 5 άσσους και 13 μηδενικά, έτσι ώστε να μην έχουμε καθόλου συνεχόμενους άσσους.

Π.χ. ο αριθμός 001000101001000001 αντιστοιχεί στην επιλογή των \{ 3, 7, 9, 12, 18 \} από το αρχικό σύνολο.

Για να βρούμε τον αριθμό των τρόπων δημιουργίας ενός τέτοιου 18-ψήφιου αριθμού, έτσι ώστε να μην έχουμε καθόλου συνεχόμενους άσσους, εφαρμόζουμε την εξής τεχνική:

Βάζουμε στη σειρά τα 13 μηδενικά. Αυτά οριοθετούν 14 σημεία όπου μπορούμε να τοποθετήσουμε άσσο (12 σημεία ανάμεσα στα μηδενικά, 1 σημείο αριστερά από το πρώτο μηδενικό και 1 σημείο δεξιά από το τελευταίο μηδενικό):

- 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 -

Στη συνέχεια απλώς επιλέγουμε 5 από αυτά τα 14 σημεία για να τοποθετήσουμε άσσο. Άρα έχουμε \displaystyle{\binom{14}{5}} τρόπους.

Με το ίδιο σκεπτικό για να δημιουργήσουμε έναν δυαδικό αριθμό με k μη συνεχόμενους άσσους και n μηδενικά υπάρχουν \displaystyle{\binom{n+1}{k}} τρόποι.
τελευταία επεξεργασία από Διονύσιος Αδαμόπουλος σε Σάβ Μαρ 18, 2017 3:16 pm, έχει επεξεργασθεί 1 φορά συνολικά.


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

Re: Επιλογή Αριθμών.

#7

Μη αναγνωσμένη δημοσίευση από JimNt. » Σάβ Μαρ 18, 2017 3:00 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.
Απάντηση

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

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

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