Προβλήματα και Γρίφοι Μαθηματικών

Ενα blog για τα Μαθηματικά

Άσκηση 8

2 Σχόλια

Υποθέτουμε ότι βρισκόμαστε στο σημειακό χώρο {\mathbb{N} \times \mathbb{N}} και συγκεκριμένα στο σημείο {(0,0)}. Αν θέλουμε να πάμε στο σημείο {(n,k)} με πόσους τρόπους μπορούμε να πάμε:

  1. αν μπορούμε κάθε φορά να κάνουμε ένα βήμα μηκους 1 προς τα δεξιά ή προς τα πάνω.
  2. αν μπορούμε κάθε φορά να κάνουμε ένα βήμα μηκους 1 προς τα δεξιά ή προς τα πάνω και δεν θέλουμε να περάσουμε από το σημείο {(n-1,k-1)}.Υποθέτουμε ότι {n >1 } και {k > 1}
Advertisements

Written by Κιουβρέκης Γιάννης / Kiouvrekis Yiannis

Μαρτίου 2, 2010 στις 2:31 μμ

2 Σχόλια

Subscribe to comments with RSS.

  1. Απαντώ στο 1ο. Θα ακολουθήσει απάντηση στο 2ο σκέλος κάποια στιγμή που θα νιώθω λιγότερο τεμπέλης.
    – Συμβολικά για κάθε κίνηση προς τα δεξιά γράφουμε 0 και για κάθε κίνηση προς τα πάνω 1. Έτσι για παράδειγμα η γραμμή {(\underbrace{0, 0, ...., 0}_{\textrm{n times}}, \underbrace{1, 1, ...., 1}_{\textrm{k times}})} στην ουσία υποδηλώνει τη διαδρομή ορίζεται κάνοντας αρχικά {n} μοναδιακά βήματα δεξιά και έπειτα {k} μοναδιακά βήματα πάνω. Είναι φανερό ότι ο συνολικός αριθμός των πιθανών διαδρομών από το σημείο {(0, 0)} εώς το {(n, k)} αντιστοιχεί στον αριθμό των διαφορετικών διατάξεων {n} μηδενικών και {k} μονάδων. Μπορούμε να χρησιμοποιήσουμε έτοιμο τον τύπο της συνδυαστικής {\left(\begin{array}{c}n+k\\ n\end{array}\right)} ή μπορούμε να ακολουθήσουμε μια πιο «διαφανή» συλλογιστική αποδεικνύοντας παράλληλα την παραπάνω σχέση. Η λογική έχει ως εξής:
    Ο αριθμός βημάτων για να φτάσουμε στο σημείο {(n, k)} είναι {n+k}, συνεπώς έχουμε να κάνουμε με μεταθέσεις {n+k} στοιχείων. Έστω τώρα ότι τα στοιχεία είναι διακριτά, δηλαδή όλα διαφορετικά μεταξύ τους. Ο αριθμός των διαφορετικών διατάξεων είναι {(n+k)!}. Θέτουμε τώρα κάποια από αυτά, πλήθους {n} να είναι ίδια (απαίτηση να κινούμαστε οριζόντια μόνο προς τα δεξιά) και τα ονομάζουμε 0. Εφόσον οι διατάξεις που περιλαμβάνουν μεταθέσεις μεταξύ των είναι ταυτόσημες ({n!} τω αριθμώ), πρέπει να αφαιρέσουμε αυτό το πλήθος από το πλήθος των συνολικών αρχικών μεταθέσεων όπου όλα τα στοιχεία είναι διαφορετικά μεταξύ τους. Αυτό το κάνουμε διαιρώντας, δηλαδή καταλήγουμε στο {\frac{(n+k)!}{n!}}. Στο επόμενο και τελευταίο βήμα θέτουμε τα {k} εναπομείναντα στοιχεία ίσα μεταξύ τους και τα συμβολίζουμε με 1. Με την ίδια συλλογιστική αφαιρούμε από το μέχρι τώρα πλήθος των μεταθέσεων τις μεταθέσεις που λαμβάνουν χώρα μεταξύ των 1. Καταλήγουμε στην τελική σχέση, η οποία είναι:
    {\boxed{N=\frac{(n+k)!}{k!\cdot{}n!}=\left(\begin{array}{c}n+k\\ n\end{array}\right)=\left(\begin{array}{c}n+k\\ k\end{array}\right)}}
    όπου Ν το πλήθος των ζητούμενων διαφορετικών διαδρομών.

    Begotten

    Μαρτίου 3, 2010 at 12:22 μμ

  2. Για το 2ο σκέλος τώρα:
    – Συμβολίζουμε με {N_{\widehat{(n-1,k-1)}}} το πλήθος των διαδρομών από το {(0,0)} στο {(n,k)} με τον περιορισμό πως δεν διέρχονται από το σημείο {(n-1,k-1)} και με {\tilde{N}_{(n-1,k-1)}} το πλήθος εκείνων που διέρχονται από το εν λόγω σημείο. Προφανώς ισχύει {N=\tilde{N}_{(n-1,k-1)}+N_{\widehat{(n-1,k-1)}}}. Επομένως για να λύσουμε το πρόβλημα πρέπει να βρούμε το {\tilde{N}_{(n-1,k-1)}}. Όμως {\tilde{N}_{(n-1,k-1)}=N_{(n-1,k-1)}\times{}N_{(n-1,k-1)\rightarrow{}(n,k)}}, όπου {N_{(n-1,k-1)}} είναι το πλήθος των διαδρομών για το πρόβλημα {(0,0)\rightarrow{}(n,k)} και {N_{(n-1,k-1)\rightarrow{}(n,k)}} το πλήθος των διαδρομών για το πρόβλημα {(n-1,k-1)\rightarrow{}(n,k)}. Για να δικαιολογήσουμε την παραπάνω σκέψη ακολουθούμε την εξής συλλογιστική:
    Θέλουμε να απορρίψουμε τις διαδρομές που περνάνε από το σημείο {(n-1,k-1)}, επομένως αρχικά πρέπει να βρούμε πόσες είναι. Ξεκινάμε λύνοντας το πρόβλημα {(0,0)\rightarrow{}(n-1,k-1)}. Η λύση είναι εκείνη του 1ου σκέλους με την αντικατάσταση {n\rightarrow{}n-1} και {k\rightarrow{}k-1}. Επιστρέφοντας στο πρόβλημά μας οι διαδρομές που περνάνε από το {(n-1,k-1)} είναι ακριβώς τόσες, πολλαπλασιασμένες με το πλήθος των τρόπων που μπορούμε να μεταβούμε από το {(n-1,k-1)} στο {(n,k)}. Στην περίπτωσή μας το πλήθος αυτό είναι 2 (ένας τρόπος κάνοντας το βήμα 0,1 και ένας με το βήμα 1,0). Δηλαδή {N_{(n-1,k-1)\rightarrow{}(n,k)}=2} και {N_{(n-1,k-1)}=\binom{n+k-2}{n-1}=\binom{n+k-2}{k-1}=\frac{(n+k-2)!}{(k-1)!(n-1)!}}.
    Δηλαδή {\tilde{N}_{(n-1,k-1)}=2\frac{(n+k-2)!}{(k-1)!(n-1)!}=2\frac{(n+k)!k\cdot{}n}{(n+k-1)(n+k)k!n!}} και τελικά
    {\boxed{N_{\widehat{(n-1,k-1)}}=\frac{(n+k)!}{k!n!}\left(1-2\frac{k\cdot{}n}{(n+k-1)(n+k)}\right)}}

    Begotten

    Μαρτίου 4, 2010 at 10:46 μμ


Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Αρέσει σε %d bloggers: