Σελίδα 1 από 1

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

Δημοσιεύτηκε: Τετ Μαρ 15, 2017 6:37 pm
από JimNt.
Με πόσους τρόπους μπορούμε να επιλέξουμε 5 αριθμούς από το σύνολο A=\{1,2,3,\ldots,18\} ώστε κάθε αριθμός να απέχει τουλάχιστον 2 από έναν άλλο;

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

Δημοσιεύτηκε: Πέμ Μαρ 16, 2017 10:11 am
από dement
Η επιλογή αντιστοιχεί 1-1 σε τυχαία επιλογή 5 αριθμών από ένα σύνολο 14 αριθμών και στη συνέχεια "εισαγωγή" 4 ακόμα αριθμών (ενός αμέσως μετά από κάθε έναν από τους πρώτους 4 επιλεγέντες) έτσι ώστε να εξασφαλίζεται η απόσταση.

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

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

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

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


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

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

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

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

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

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

Δημοσιεύτηκε: Πέμ Μαρ 16, 2017 2:05 pm
από Demetres
Είναι αρκετά σημαντική άσκηση μιας και τέτοιες απαριθμήσεις με διάφορες παραλλαγές εμφανίζονται πολύ συχνά ως κομμάτια ασκήσεων.

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

Θα αποφασίσουμε πόσους αριθμούς θα αφήσουμε πριν τον πρώτο αριθμό, πόσους μεταξύ του πρώτου και του δεύτερου, κ.τ.λ. μέχρι το πόσους αριθμούς θα αφήσουμε από τον πέμπτο και μετά. Ας γράψουμε 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 εδώ.

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

Δημοσιεύτηκε: Σάβ Μαρ 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}} τρόποι.

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

Δημοσιεύτηκε: Σάβ Μαρ 18, 2017 3:00 pm
από JimNt.
Πολύ ωραία λύση!