Πόσες διαφορετικές παραστάσεις;

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

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

Πόσες διαφορετικές παραστάσεις;

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Νοέμ 04, 2016 11:46 pm

Δίνεται η παράσταση

\displaystyle{ x_1 \div x_2 \div \cdots \div x_n}

Μπορούμε να τοποθετήσουμε παρενθέσεις με όποιο τρόπο θέλουμε. Πόσες διαφορετικές παραστάσεις προκύπτουν αν τοποθετήσουμε παρενθέσεις με όλους τους δυνατούς τρόπους;



Λέξεις Κλειδιά:
Άβαταρ μέλους
taratoris
Δημοσιεύσεις: 49
Εγγραφή: Παρ Ιουν 12, 2009 7:11 pm

Re: Πόσες διαφορετικές παραστάσεις;

#2

Μη αναγνωσμένη δημοσίευση από taratoris » Σάβ Νοέμ 05, 2016 8:26 pm

Έστω K_n ο αριθμός των παραστάσεων όταν έχουμε n στοιχεία.

Τότε προφανώς K_1=K_2=1 διότι μπορούμε να ομαδοποιήσουμε 1 και 2 στοιχεία με μοναδικό τρόπο.

Για n στοιχεία ισχύει K_n=\sum_{i=1}^{n-1}K_iK_{n-i}. Ο λόγος είναι οτι μπορούμε να διαλέξουμε με n-1 τρόπους το σημείο στο οποίο θα γίνει ο πρώτος "εξωτερικός διαχωρισμός" των n στοιχείων σε δύο ομαδοποιήσεις και κατόπιν οι εσωτερικοί διαχωρισμοί γίνονται αποκλειστικά εντός της καθε μίας ομάδοποίησης. Ουσιαστικά διαλέγουμε ποια στοιχεία θα είναι στον "εξωτερικό" αριθμητή και ποιά στον "εξωτερικό" παρονομαστή και κατόπιν δουλεύουμε αναγωγικά.

Επαγωγικά μπορούμε να δείξουμε οτι K_n=\frac{1}{n}{2n-2 \choose n-1}.


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

Re: Πόσες διαφορετικές παραστάσεις;

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Νοέμ 05, 2016 9:20 pm

Βαγγέλη, πάτησες μπανανόφλουδα.


Άβαταρ μέλους
taratoris
Δημοσιεύσεις: 49
Εγγραφή: Παρ Ιουν 12, 2009 7:11 pm

Re: Πόσες διαφορετικές παραστάσεις;

#4

Μη αναγνωσμένη δημοσίευση από taratoris » Σάβ Νοέμ 05, 2016 9:31 pm

Γειά σου Δημήτρη, το σκέφτηκα αυτό που λες και έχεις δίκαιο. Η λογική μου είναι πως αν και δημιουργούν το ίδιο κλάσμα ΚΑΤΟΠΙΝ αλγεβρικών χειρισμών, θα θεωρούσα αυτές τις δύο ως διαφορετικές παραστάσεις. Για παράδειγμα x και \frac{1}{\frac{1}{x}} είναι ισοδύναμες παραστασεις αλλά δεν είναι ίδιες παραστάσεις.

Θα προσπαθήσω να παραθεσω λύση για το πρόβλημα όπου λαμβάνονται ως ίδιες δυο ισοδύναμες παραστάσεις.


nikkru
Δημοσιεύσεις: 338
Εγγραφή: Σάβ Δεκ 26, 2009 6:42 pm

Re: Πόσες διαφορετικές παραστάσεις;

#5

Μη αναγνωσμένη δημοσίευση από nikkru » Κυρ Νοέμ 06, 2016 9:36 am

Demetres έγραψε:Δίνεται η παράσταση

\displaystyle{ x_1 \div x_2 \div \cdots \div x_n}

Μπορούμε να τοποθετήσουμε παρενθέσεις με όποιο τρόπο θέλουμε. Πόσες διαφορετικές παραστάσεις προκύπτουν αν τοποθετήσουμε παρενθέσεις με όλους τους δυνατούς τρόπους;


Άβαταρ μέλους
taratoris
Δημοσιεύσεις: 49
Εγγραφή: Παρ Ιουν 12, 2009 7:11 pm

Re: Πόσες διαφορετικές παραστάσεις;

#6

Μη αναγνωσμένη δημοσίευση από taratoris » Κυρ Νοέμ 06, 2016 10:31 am

Η σωστή απάντηση (όπως υπέδειξε και ο nikkru) είναι 2^{n-2}.

Η απόδειξη έχει ως εξής:

Θα δείξουμε οτι χρησιμοποιώντας τις παρενθέσεις με όλους τους δυνατούς τρόπους μπορούμε να δημιουργήσουμε όλα τα κλάσματα που έχουν το a_1 στον αριθμητή και το a_2 στον παρονομαστή. Εφόσον υπάρχουν n-2 στοιχεία πλην των a_1 και a_2, και εφόσνον έχουμε την επιλογή να τοποθετήσουμε κάθε στοιχείο είτε στον αριθμητή είτε στον παρονομαστή βλέπουμε οτι έχουμε 2^{n-2} παραστάσεις. (Μπορούμε εύκολα να δείξουμε επαγωγικά οτι τα a_1 και a_2 πρέπει υποχρεωτικά να είναι στον αριθμητή και παρονομαστή αντίστοιχα.)

Θα αποδείξουμε την προτασή μας με επαγωγή στο n. Βλέπουμε οτι η υπόθεσή μας ισχύει για n=2. Έστω οτι ισχύει για κάθε n \leq k-1. Θα δείξουμε οτι ισχύει για n=k

Έστω οτι θέλουμε να δημιουργήσουμε ένα κλάσμα της μορφής \frac{a_1 x}{a_2 y a_k} όπου κάθε a_i με 3\leq i \leq k-1 ανήκει είτε στο x είτε στο y.

Τότε ξέρουμε οτι υπάρχει παράσταση A=((((...))) που δημιουργεί το κλάσμα \frac{a_1 x}{a_2 y} λόγω της επαγωγικής υπόθεσης.

Σε αυτή την περίπτωση η παράσταση B=A\textdiv / a_k δημιουργεί το ζητούμενο κλάσμα.

Έστω οτι θέλουμε να δημιουργήσουμε ένα κλάσμα της μορφής \frac{a_1 x a_k a_{k-1}...a_{k-i+1}}{a_2 y a_{k-i}} όπου i \geq 1 και κάθε a_j με 3\leq j \leq k-i ανήκει είτε στο x είτε στο y.

Τότε ξέρουμε οτι υπάρχει παράσταση A=((((...))) που δημιουργεί το κλάσμα \frac{a_1 x}{a_2 y a_{k-i}} λόγω της επαγωγικής υπόθεσης. Τότε θέτοντας όπου a_{k-i} την τιμή (((...(a_{k-i}/a_{k-i+1})/a_{k-i+2})...)a_{k})=\frac{a_{k-i}}{a_{k-i+1}a_{k-i+2}...a_{k}} στην A δημιουργούμε το ζητούμενο κλάσμα.

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

Δημήτρη δεν βρήκα πως να γράψω το σύμβολο της διαίρεσης που χρησιμοποιείς οπότε χρησιμοποίησα απλώς /


nikkru
Δημοσιεύσεις: 338
Εγγραφή: Σάβ Δεκ 26, 2009 6:42 pm

Re: Πόσες διαφορετικές παραστάσεις;

#7

Μη αναγνωσμένη δημοσίευση από nikkru » Κυρ Νοέμ 06, 2016 11:33 am

Demetres έγραψε:Δίνεται η παράσταση

\displaystyle{ x_1 \div x_2 \div \cdots \div x_n}

Μπορούμε να τοποθετήσουμε παρενθέσεις με όποιο τρόπο θέλουμε. Πόσες διαφορετικές παραστάσεις προκύπτουν αν τοποθετήσουμε παρενθέσεις με όλους τους δυνατούς τρόπους;
Καλημέρα,
ας παραθέσω άλλη μια λύση.

Προφανώς οι \displaystyle{ x_1 ,  x_2 όπου και να τοποθετήσουμε παρενθέσεις δεν αλλάζουν θέσεις, ο x_1 είναι πάντα στον αριθμητή και ο x_2 στον παρονομαστή του τελικού απλού κλάσματος.
Τους υπόλοιπους n-2 όρους μπορούμε να τους έχουμε στον αριθμητή ή στον παρονομαστή του τελικού απλού κλάσματος άρα υπάρχουν 2^{n-2} διαφορετικές παραστάσεις( θεωρούμε όλα τα x_i διαφορετικά μεταξύ τους και παραβλέπουμε τις τυχόν απλοποιήσεις ).

Η διαδικασία είναι η εξής:

Ξεκινάμε από το δεξιό μέρος της παράστασης και κινούμενοι προς τα αριστερά:
βάζουμε δεξιά παρένθεση μετά από κάθε \displaystyle{ x_i } που συναντάμε και θέλουμε να είναι στον αριθμητή
ενώ πριν από κάθε x_i που συναντάμε και θέλουμε να είναι στον παρονομαστή βάζουμε όσες αριστερές παρενθέσεις χρειάζονται για να συμπληρώσουν τις δεξιές παρενθέσεις που έχουμε ήδη βάλει.
Η διαδικασία τελειώνει όταν φτάσουμε σε όρο που θέλουμε να είναι στον παρονομαστή και έχει μόνο δεξιά του όρους που θέλουμε να είναι στον αριθμητή.

Π.χ. στην παράσταση \displaystyle{ 1 \div 2 \div 3 \div 4 \div 5\div 6 \div 7\div 8} αν θέλουμε να έχουμε στον αριθμητή τους 4,5,7 γράφουμε: \displaystyle{ 1 \div 2 \div ((3 \div 4) \div 5)\div (6 \div 7)\div 8}


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

Re: Πόσες διαφορετικές παραστάσεις;

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Νοέμ 06, 2016 2:04 pm

taratoris έγραψε: Δημήτρη δεν βρήκα πως να γράψω το σύμβολο της διαίρεσης που χρησιμοποιείς οπότε χρησιμοποίησα απλώς /
Με το \div. Αν πάρεις το βελάκι πάνω από τον τύπο, τότε φαίνεται ο κώδικας του latex που χρησιμοποιήθηκε.

Δίνω και την δική μου απόδειξη:

Αναγκαστικά το x_1 είναι στον αριθμητή και το x_2 στον παρονομαστή. Θα δείξω επαγωγικά ότι μπορώ να έχω οποιοδήποτε κλάσμα που να έχει το x_1 στον αριθμητή και το x_2 στον παρονομαστή.

Για n=2 προφανώς ισχύει. Έστω λοιπόν ότι ισχύει για n=k. Έστω n=k+1 και ότι θέλω να φτιάξω ένα συγκεκριμένο κλάσμα A το οποίο να έχει το x_1 στον αριθμητή και το x_2 στον παρονομαστή.

Αν για αυτό το κλάσμα υπάρχει δείκτης i ώστε το x_i να βρίσκεται στον παρονομαστή και το x_{i+1} στον αριθμητή τότε ξεκινάω με τις παρενθέσεις
\displaystyle{ (x_1 \div \cdots \div x_{i-1}) \div (x_i \div \cdots \div x_{k+1})}
Από την επαγωγική υπόθεση μπορώ να βάλω παρενθέσεις στο πρώτο κομμάτι ώστε τα x_j με j < i να βρίσκονται στην ίδια θέση όπως στο κλάσμα A. Επίσης μπορώ να βάλω παρενθέσεις στο δεύτερο κομμάτι ώστε τα x_j με j \geqslant i να βρίσκονται σε αντίθετη θέση από ότι στο A. Το τελικό αποτέλεσμα θα είναι το επιθυμητό.

Αν τώρα δεν υπάρχει τέτοιος δείκτης i αυτό σημαίνει ότι θέλω να φτιάξω το κλάσμα \displaystyle{ \frac{x_1}{x_2 \cdots x_{k+1}}.} Αυτό όμως μπορεί να φτιαχτεί ως εξής:

\displaystyle{ (\cdots((x_1 \div x_2) \div x_3) \div \cdots \div x_{k+1})}


Απάντηση

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

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

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