Διαδρομές

#1

Έστω τα σημεία P = (a, b)

και

του επιπέδου x-y,

όπου

ακέραιοι με a<b, a<c, b<d , c<d.

Θέλουμε να μεταβούμε από το σημείο

στο σημείο

κινούμενοι σε κάθε βήμα κατά

είτε δεξιά είτε πάνω. Με πόσους τρόπους μπορεί να γίνει αυτό αν δεν επιτρέπεται να αγγίξουμε την ευθεία x = y;

#2

Επαναφορά!

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #3

socrates έγραψε: Σάβ Φεβ 27, 2016 12:25 pm Έστω τα σημεία και του επιπέδου όπου ακέραιοι με Θέλουμε να μεταβούμε από το σημείο στο σημείο κινούμενοι σε κάθε βήμα κατά είτε δεξιά είτε πάνω. Με πόσους τρόπους μπορεί να γίνει αυτό αν δεν επιτρέπεται να αγγίξουμε την ευθεία

Ενδεχομένως να έχω λάθος αλλά κάνω μία προσπάθεια :
Έστω

οι τρόποι.
Από την εκφώνηση παίρνουμε το αυτό το σχήμα(1).
Μεταφέρουμε το ορθόγωνιο που σχηματίζεται μεταξύ των σημείων σε άλλο σχήμα(2)

Έστω ότι το ορθογώνιο αποτελέιται από τα τετραγωνάκια του σχήματος μήκους ίδιου με την μονάδα μέτρησης των a,b,c,d

Για να προσδιορίσουμε ένα σημείο το

δηλώνει το ύψος ενώ το

το πόσο δεξιά είναι και γράφουμε i_n

π.χ το σημείο

είναι το

και ας πούμε $N_{i_{n}}$ τον αριθμό των τρόπων με τους οποίους μπορούμε να φτάσουμε στο i_n

.Σε κάθε σημείο είναι $N_{i_{n}}=N_{{\left (i-1 \right )}_n}+N_{i_{\left (n-1 \right )}}$ (βλέπε Αρχιμήδης Juniors 2009 θέμα 4).
Είναι

$N_{1_n}=1,\forall\, n$

$N_{2_n}=n$

$\displaystyle { N_{3_n}=N_{2_n}+N_{3_{\left (n-1 \right )}}=n+N_{3_{\left (n-1 \right )}} \Leftrightarrow \sum_{k=1}^{n}N_{3_k}=\sum_{k=1}^{n-1}N_{3_k}+\sum_{k=1}^{n}k\Leftrightarrow N_{3_{n}}=\dfrac{n\left ( n+1 \right )}{2}}$

$\displaystyle{N_{4_n}=N_{3_n}+N_{4_{n-1}}\Leftrightarrow \sum_{k=1}^{n}N_{4_k}=\sum_{k=1}^{n-1}N_{4_{k}}+\sum_{k=1}^{n}N_{3_k}\Leftrightarrow ..\Leftrightarrow N_{4_n}=\dfrac{n\left ( n+1 \right )\left ( n+2 \right )}{6}}$

$\displaystyle{N_{5_n}=N_{4_n}+N_{5_{n-1}}\Leftrightarrow \sum_{k=1}^{n}N_{5_k}=\sum_{k=1}^{n-1}N_{5_k}+\sum_{k=1}^{n}N_{4_k}\Leftrightarrow ..\Leftrightarrow N_{5_n}=\dfrac{n\left ( n+1 \right )\left ( n+2 \right )\left ( n+3 \right )}{24}}$

.
.

$\displaystyle {N_{i_{n}}=\dfrac{\displaystyle{\prod_{k=0}^{i-2}\left ( n+k \right )}}{\left ( i-1 \right )!}}$

Με τα νούμερα του προβλήματος έχουμε

$N=\dfrac{\displaystyle\prod_{k=0}^{c-a-1}\left ( d-b+k+1 \right )}{\left ( c-a \right )!}$
(Δεν ξέρω εαν η λύση μου είναι μόνο για μία ειδική περίπτωση ή είναι γενική....χάθηκα λίγο με τις πράξεις

)

Λάμπρος Κατσάπας · #4

Γεια σου Πρόδρομε. Για ρίξε μια ματιά Bertrand's ballot theorem, πρόβλημα ψηφοφορίας στη θεωρία πιθανοτήτων, αρχή ανακλάσης - τυχαίος περίπατος. Θα βρεις βρεις ενδιαφέροντα και ωραία πράγματα. Το παραπάνω πρόβλημα είναι αρκετά γνωστό.

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #5

Λάμπρος Κατσάπας έγραψε: Κυρ Μαρ 24, 2019 1:59 pm Γεια σου Πρόδρομε. Για ρίξε μια ματιά Bertrand's ballot theorem, πρόβλημα ψηφοφορίας στη θεωρία πιθανοτήτων, αρχή ανακλάσης - τυχαίος περίπατος. Θα βρεις βρεις ενδιαφέροντα και ωραία πράγματα. Το παραπάνω πρόβλημα είναι αρκετά γνωστό.

Σας ευχαριστώ πολύ! Δεν ήξερα πως είναι τόσο γνωστό, βρήκα στο Wikipedia και αυτόν τον τύπο $N=\dbinom{c+d}{c}$
όταν a=b=0

ο οποίος είναι ισοδύναμος αυτού που βρήκα στην λύση μου αφού:
$\dbinom{c+d}{c}=\dfrac{\left ( c+d \right )!}{c!\cdot d!}=\dfrac{\displaystyle\prod_{k=0}^{c-1}\left ( d+1+k \right )}{c!}$

Διαδρομές

Διαδρομές

Re: Διαδρομές

Re: Διαδρομές

Re: Διαδρομές

Re: Διαδρομές

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