Περίπατος σε πλέγμα

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

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7864
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Περίπατος σε πλέγμα

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μάιος 16, 2018 3:16 pm

Κάνουμε ένα περίπατο στο πιο κάτω πλέγμα, ξεκινώντας από το κουτάκι 1

\begin{tabular}{|c|c|} \hline  1 & 2 \\ \hline 4 & 3 \\ \hline \end{tabular}

Σε κάθε βήμα μετακινούμαστε από το τετράγωνο στο οποίο βρισκόμαστε, σε ένα άλλο γειτονικό τετράγωνο, δηλαδή ένα άλλο τετράγωνο με κοινή πλευρά με αυτό που βρισκόμαστε. Στο τέλος του περιπάτου προσθέτουμε τους αριθμούς από όλα τα τετραγωνάκια από τα οποία περάσαμε από το πρώτο βήμα και μετά, με την κατάλληλη πολλαπλότητα. Δεν λαμβάνουμε υπόψη σε αυτό το άθροισμα το τετραγωνάκι από το οποίο ξεκινήσαμε.

Με πόσους διαφορετικούς τρόπους μπορούμε να κάνουμε τον περίπατο ώστε το τελικό μας άθροισμα να ισούται με 20;

Επεξεργασία: Έγινε διόρθωση τυπογραφικού.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1310
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Περίπατος σε πλέγμα

#2

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Τετ Μάιος 16, 2018 4:28 pm

Demetres έγραψε:
Τετ Μάιος 16, 2018 3:16 pm
Κάνουμε ένα περίπατο στο πιο κάτω πλέγμα, ξεκινώντας από το κουτάκι 1

\begin{tabular}{|c|c|} 
\hline  
1 & 2 \\ \hline 
3 & 4 \\ \hline 
\end{tabular}

Σε κάθε βήμα μετακινούμαστε από το τετράγωνο στο οποίο βρισκόμαστε, σε ένα άλλο γειτονικό τετράγωνο, δηλαδή ένα άλλο τετράγωνο με κοινή πλευρά με αυτό που βρισκόμαστε. Στο τέλος του περιπάτου προσθέτουμε τους αριθμούς από όλα τα τετραγωνάκια από τα οποία περάσαμε από το πρώτο βήμα και μετά, με την κατάλληλη πολλαπλότητα. Δεν λαμβάνουμε υπόψη σε αυτό το άθροισμα το τετραγωνάκι από το οποίο ξεκινήσαμε.

Με πόσους διαφορετικούς τρόπους μπορούμε να κάνουμε τον περίπατο ώστε το τελικό μας άθροισμα να ισούται με 20;
Ωραίο!

Υποθέτω ότι ο πίνακας είναι \begin{tabular}{|c|c|} 
\hline  
1 & 2 \\ \hline 
4 & 3 \\ \hline 
\end{tabular} (γιατί αλλιώς δεν μου βγαίνει :lol: ).

Καταρχήν παρατηρούμε, ότι στο πρώτο βήμα, καταλήγουμε στο κουτάκι 2 ή 4, και στο δεύτερο βήμα στο 1 ή 3.

Έστω N ο αριθμός των βημάτων που θα χρειαστούμε.

Για να επιτύχουμε άθροισμα 20, θα χρειαστούμε τουλάχιστον 6 βήματα, καθώς αν έχουμε 5 βήματα, το άθροισμα είναι \leqslant 4+3+4+3+4=18<20, άτοπο.

Επίσης, θα χρειαστούμε το πολύ 13 βήματα, καθώς αν είχαμε 14, το άθροισμα θα ήταν \geqslant 2+1+2+1+2+1+2+1+2+1+2+1+2+1=21>20, άτοπο.

Άρα, 6 \leqslant N \leqslant 13.

Έστω N=6.

Αν είμαστε στο κουτάκι 1, θα μετακινηθούμε στο 2 ή στο 4. Επομένως, η διαφορά των δύο επιλογών είναι 4-2=2, και όμοια αν είμαστε π.χ. στο 2, θα πάμε ή στο 1, ή στο 3, με διαφορά πάλι 2.

Αν s λοιπόν ο αριθμός των φορών που επιλέγουμε να πάμε στο μεγαλύτερο κουτάκι (αυτό με τη μεγαλύτερη ένδειξη), το άθροισμα είναι 2+1+2+1+2+1+2s, και πρέπει να ισούται με 20, οπότε 2s+9=20, άτοπο.

Όμοια, N \neq 7,10,11, άρα N \in \{8,9,12,13 \}.

Αν N=8, με την ίδια διαδικασία με πριν, 2+1+2+1+2+1+2+1+2s=20 \Rightarrow s=4, οπότε, αφού κάνουμε 8 βήματα, έχουμε \displaystyle \binom{8}{4}=70, τρόπους.

Όμοια, για N=9, έχουμε 84, για N=12 έχουμε 12 τρόπους , και για N=13 έχουμε 1 τρόπο.

Σύνολο, 70+84+12+1=\boxed{167} τρόποι.


Ο καθένας λέει ότι να΄ναι και είναι πάντα σύμφωνος με τον εαυτό του ! 'Ολοι μιλάνε και κανείς δεν ακούει! Ο κόσμος είναι σε νοητική αδράνεια ! Ελένη Γλυκατζή Αρβελέρ
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7864
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Περίπατος σε πλέγμα

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μάιος 16, 2018 4:36 pm

Ορέστης Λιγνός έγραψε:
Τετ Μάιος 16, 2018 4:28 pm
Υποθέτω ότι ο πίνακας είναι \begin{tabular}{|c|c|} 
\hline  
1 & 2 \\ \hline 
4 & 3 \\ \hline 
\end{tabular} (γιατί αλλιώς δεν μου βγαίνει :lol: ).

:oops: Θα διορθωθεί.

Ορέστης Λιγνός έγραψε:
Τετ Μάιος 16, 2018 4:28 pm
Σύνολο, 70+84+12+1=\boxed{167} τρόποι.

Σωστά.

Το μόνο που ήθελε ήταν χωρισμός σε απλούστερες περιπτώσεις, προσοχή στις πράξεις, και κυρίως να μην το φοβηθούμε.


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 729
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Περίπατος σε πλέγμα

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Παρ Μάιος 18, 2018 12:05 am

Demetres έγραψε:
Τετ Μάιος 16, 2018 3:16 pm
Κάνουμε ένα περίπατο στο πιο κάτω πλέγμα, ξεκινώντας από το κουτάκι 1

\begin{tabular}{|c|c|} 
\hline  
1 & 2 \\ \hline 
4 & 3 \\ \hline 
\end{tabular}

Σε κάθε βήμα μετακινούμαστε από το τετράγωνο στο οποίο βρισκόμαστε, σε ένα άλλο γειτονικό τετράγωνο, δηλαδή ένα άλλο τετράγωνο με κοινή πλευρά με αυτό που βρισκόμαστε. Στο τέλος του περιπάτου προσθέτουμε τους αριθμούς από όλα τα τετραγωνάκια από τα οποία περάσαμε από το πρώτο βήμα και μετά, με την κατάλληλη πολλαπλότητα. Δεν λαμβάνουμε υπόψη σε αυτό το άθροισμα το τετραγωνάκι από το οποίο ξεκινήσαμε.

Με πόσους διαφορετικούς τρόπους μπορούμε να κάνουμε τον περίπατο ώστε το τελικό μας άθροισμα να ισούται με 20;
Ας δούμε με αναδρομή:

Έστω a_n το πλήθος των τρόπων να κάνουμε περίπατο ξεκινώντας από το κουτάκι 1 ώστε τελικό μας άθροισμα να ισούται με n. Ομοίως, b_n ξεκινώντας από το κουτάκι 2, c_n από το κουτάκι 3 και d_n από το 4.

\begin{tabular}{|c|c|} 
\hline  
a_n & b_n \\ \hline 
d_n & c_n \\ \hline 
\end{tabular}

Ισχύουν οι σχέσεις:

a_n=b_{n-2} + d_{n-4}
b_n=a_{n-1} + c_{n-3}
c_n=b_{n-2} + d_{n-4}
d_n=a_{n-1} + c_{n-3}

Από τις παραπάνω προκύπτει ότι a_n=c_n και b_n=d_n. Επομένως έχουμε:

a_n=b_{n-2} + b_{n-4}
b_n=a_{n-1} + a_{n-3}

και τελικά: a_n=a_{n-3} + 2a_{n-5}+a_{n-7}.

Εμείς ουσιαστικά χρειαζόμαστε το a_{20}. Εύκολα βρίσκουμε τις αρχικές τιμές:

a_1=0
a_2=1
a_3=1
a_4=1
a_5=3 (1 \to 2 \to 3, 1 \to 2 \to 1 \to 2, 1 \to 4 \to 1)
a_6=1
a_7=4 (1 \to 2 \to 1 \to 4, 1 \to 4 \to 1 \to 2, 1 \to 2 \to 3 \to 2, 1 \to 4 \to 3)

και εφαρμόζοντας τον παραπάνω αναδρομικό τύπο, βρίσκουμε διαδοχικά τις επόμενες τιμές: 5, 4, 11, 8, 15, 22, 20, 42, 42, 61, 94, 97 και τέλος a_{20}=167.


Houston, we have a problem!
Απάντηση

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

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

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