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

JimNt. · #1

Με πόσους τρόπους μπορούμε να επιλέξουμε

αριθμούς από το σύνολο $A=\{1,2,3,\ldots,18\}$ ώστε κάθε αριθμός να απέχει τουλάχιστον

από έναν άλλο;

dement · #2

Η επιλογή αντιστοιχεί 1-1 σε τυχαία επιλογή

αριθμών από ένα σύνολο

αριθμών και στη συνέχεια "εισαγωγή"

ακόμα αριθμών (ενός αμέσως μετά από κάθε έναν από τους πρώτους

επιλεγέντες) έτσι ώστε να εξασφαλίζεται η απόσταση.

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

harrisp · #3

[quote="dement"]Η επιλογή αντιστοιχεί 1-1 σε τυχαία επιλογή

αριθμών από ένα σύνολο

αριθμών και στη συνέχεια "εισαγωγή"

ακόμα αριθμών (ενός αμέσως μετά από κάθε έναν από τους πρώτους

επιλεγέντες) έτσι ώστε να εξασφαλίζεται η απόσταση.

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

Το εχω συναντήσεις αρκετές φορές μα δεν το καταλαβαϊνω. Και επειδή το

ειναι για να μαθαίνουμε θα μπορούσατε να μου εξήγησε τι εννοείται στην σημειωμένη φράση;

dement · #4

Έστω ότι θέλω (για απλούστευση) να επιλέξω

από

αριθμούς (με τον περιορισμό). Αντί αυτού επιλέγω χωρίς περιορισμό

από

αριθμούς.
Στη συνέχεια επιτυγχάνω 1-1 αντιστοίχιση εισάγοντας ακόμα έναν αριθμό ανάμεσα στούς επιλεγέντες. Έστω

επιλεγμένος και

μη επιλεγμένος αριθμός. Τότε:

ccnnn

αντιστοιχεί στο cncnnn

στο

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

#5

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

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

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

και

για $2 \leqslant i \leqslant 5$ .

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

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

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

Διονύσιος Αδαμόπουλος · #6

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

Αντιστοιχούμε τους αριθμούς που θα επιλέξουμε με

και αυτούς που απομένουν με

δημιουργώντας έναν

-ψήφιο δυαδικό αριθμό με

άσσους και

μηδενικά, έτσι ώστε να μην έχουμε καθόλου συνεχόμενους άσσους.

Π.χ. ο αριθμός 001000101001000001

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

Για να βρούμε τον αριθμό των τρόπων δημιουργίας ενός τέτοιου

-ψήφιου αριθμού, έτσι ώστε να μην έχουμε καθόλου συνεχόμενους άσσους, εφαρμόζουμε την εξής τεχνική:

Βάζουμε στη σειρά τα

μηδενικά. Αυτά οριοθετούν

σημεία όπου μπορούμε να τοποθετήσουμε άσσο (

σημεία ανάμεσα στα μηδενικά,

σημείο αριστερά από το πρώτο μηδενικό και

σημείο δεξιά από το τελευταίο μηδενικό):

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

Στη συνέχεια απλώς επιλέγουμε

από αυτά τα

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

Με το ίδιο σκεπτικό για να δημιουργήσουμε έναν δυαδικό αριθμό με

μη συνεχόμενους άσσους και

μηδενικά υπάρχουν $\displaystyle{\binom{n+1}{k}}$ τρόποι.

JimNt. · #7

Πολύ ωραία λύση!

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

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

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

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

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

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

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

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

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