Διαδρομές

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

socrates
Επιμελητής
Δημοσιεύσεις: 5799
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Διαδρομές

#1

Μη αναγνωσμένη δημοσίευση από socrates » Σάβ Φεβ 27, 2016 12:25 pm

Έστω τα σημεία P = (a, b) και Q = (c, d) του επιπέδου x-y, όπου a, b, c, d ακέραιοι με a<b, a<c, b<d , c<d. Θέλουμε να μεταβούμε από το σημείο P στο σημείο Q κινούμενοι σε κάθε βήμα κατά 1 είτε δεξιά είτε πάνω. Με πόσους τρόπους μπορεί να γίνει αυτό αν δεν επιτρέπεται να αγγίξουμε την ευθεία x = y;


Θανάσης Κοντογεώργης
socrates
Επιμελητής
Δημοσιεύσεις: 5799
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Re: Διαδρομές

#2

Μη αναγνωσμένη δημοσίευση από socrates » Δευ Νοέμ 21, 2016 10:20 pm

Επαναφορά! :)


Θανάσης Κοντογεώργης
Άβαταρ μέλους
ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ
Δημοσιεύσεις: 349
Εγγραφή: Πέμ Νοέμ 22, 2018 9:43 pm

Re: Διαδρομές

#3

Μη αναγνωσμένη δημοσίευση από ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ » Κυρ Μαρ 24, 2019 1:48 pm

socrates έγραψε:
Σάβ Φεβ 27, 2016 12:25 pm
Έστω τα σημεία P = (a, b) και Q = (c, d) του επιπέδου x-y, όπου a, b, c, d ακέραιοι με a<b, a<c, b<d , c<d. Θέλουμε να μεταβούμε από το σημείο P στο σημείο Q κινούμενοι σε κάθε βήμα κατά 1 είτε δεξιά είτε πάνω. Με πόσους τρόπους μπορεί να γίνει αυτό αν δεν επιτρέπεται να αγγίξουμε την ευθεία x = y;
Ενδεχομένως να έχω λάθος αλλά κάνω μία προσπάθεια :
Έστω N οι τρόποι.
Από την εκφώνηση παίρνουμε το αυτό το σχήμα(1).
Μεταφέρουμε το ορθόγωνιο που σχηματίζεται μεταξύ των σημείων σε άλλο σχήμα(2)

Έστω ότι το ορθογώνιο αποτελέιται από τα τετραγωνάκια του σχήματος μήκους ίδιου με την μονάδα μέτρησης των a,b,c,d
Για να προσδιορίσουμε ένα σημείο το n δηλώνει το ύψος ενώ το i το πόσο δεξιά είναι και γράφουμε i_n π.χ το σημείο A είναι το 2_5 και ας πούμε 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 )!}
(Δεν ξέρω εαν η λύση μου είναι μόνο για μία ειδική περίπτωση ή είναι γενική....χάθηκα λίγο με τις πράξεις :wacko: )
Συνημμένα
Capture1.PNG
Σχήμα(2)
Capture1.PNG (35.91 KiB) Προβλήθηκε 247 φορές
Capture2.PNG
Σχήμα(1)
Capture2.PNG (8.11 KiB) Προβλήθηκε 247 φορές


Λάμπρος Κατσάπας
Δημοσιεύσεις: 435
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

Re: Διαδρομές

#4

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Κυρ Μαρ 24, 2019 1:59 pm

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


Άβαταρ μέλους
ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ
Δημοσιεύσεις: 349
Εγγραφή: Πέμ Νοέμ 22, 2018 9:43 pm

Re: Διαδρομές

#5

Μη αναγνωσμένη δημοσίευση από ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ » Κυρ Μαρ 24, 2019 4:28 pm

Λάμπρος Κατσάπας έγραψε:
Κυρ Μαρ 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!}


Απάντηση

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

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

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