Tuesday 12 June 2018

Το κρασί νερό δεν γίνεται

Υπάρχει ένας ωραίος γρίφος που λέει το εξής: Έχουμε δύο βαρέλια, Ν και Κ. Το Ν περιέχει νερό και το Κ κρασί ίσου όγκου. Γεμίζουμε ένα δοχείο με νερό από το βαρέλι Ν, το χύνουμε στο βαρέλι Κ και αναδεύουμε μέχρι να γίνει το μείγμα ομογενές. Έπειτα, γεμίζουμε το ίδιο δοχείο με «νοθευμένο» κρασί από το βαρέλι Κ και το επιστρέφουμε στο βαρέλι Ν αναμειγνύοντάς το με το νερό. Ποιανού η καθαρότητα παραμένει μεγαλύτερη, του νερού στο βαρέλι Ν ή του κρασιού στο βαρέλι Κ; Για να το θέσουμε λιγάκι διαφορετικά, ποιο από τα δύο είναι μικρότερο, η περιεκτικότητα του βαρελιού Ν σε κρασί ή η περιεκτικότητα του βαρελιού Κ σε νερό;

Η διαίσθηση μάς παρακινεί να ισχυριστούμε ότι η καθαρότητα του νερού είναι μεγαλύτερη από εκείνη του κρασιού, αφού ενώ αρχικά μεταφέρουμε καθαρό νερό στο βαρέλι με το κρασί, σε δεύτερο χρόνο επιστρέφουμε ένα μείγμα νερού με κρασί στο βαρέλι με το νερό. Η σωστή απάντηση ωστόσο μπορεί να αφήσει τους περισσότερους άφωνους, αφού τόσο το νερό στο βαρέλι Ν όσο και το κρασί στο βαρέλι Κ έχουν την ίδια ακριβώς καθαρότητα! Αυτό μπορούμε να το καταλάβουμε αμέσως θέτοντας συγκεκριμένες τιμές στις διάφορες ποσότητες που εμπλέκονται στο γρίφο. Για παράδειγμα, ας υποθέσουμε ότι το βαρέλι Ν περιέχει 100 λίτρα νερού και το βαρέλι Κ 100 λίτρα κρασιού (βλ. Εικόνα 1). 

Εικόνα 1. Αρχική κατάσταση.

Έστω τώρα ότι παίρνουμε με ένα δοχείο 25 λίτρα νερού από το Ν και τα μεταφέρουμε στο Κ. Τότε, το βαρέλι Ν περιέχει 75 λίτρα νερού και το βαρέλι Κ περιέχει 125 λίτρα εκ των οποίων τα 100 είναι κρασί και τα 25 νερό (βλ. Εικόνα 2). Με άλλα λόγια η νέα σύσταση του βαρελιού Κ αποτελείται από \( \frac{100}{125} = 80 \% \) κρασί και \( \frac{25}{125} = 20 \% \) νερό. 

Εικόνα 2. Αποτέλεσμα μετά τη μεταφορά 25 λίτρων νερού από το βαρέλι Ν στο βαρέλι Κ.

Χρησιμοποιώντας το ίδιο δοχείο, παίρνουμε 25 λίτρα από το βαρέλι Κ και τα μεταφέρουμε στο βαρέλι Ν. Λόγω της ομογένειας του μείγματος στο βαρέλι Κ, η αναλογία κρασιού/νερού διατηρείται και στα 25 λίτρα που βρίσκονται μέσα στο δοχείο. Πιο συγκεκριμένα, τα 20 από τα 25 λίτρα (\( 80 \% \)) είναι κρασί και τα 5 από τα 25 λίτρα (\( 20 \% \)) είναι νερό. Κατά συνέπεια, μετά την ανάμειξη αυτών των 25 νοθευμένων λίτρων με το νερό, το βαρέλι Ν θα περιέχει 80 λίτρα νερό και 20 λίτρα κρασί. Όμοια, το βαρέλι Κ θα περιέχει 80 λίτρα κρασί και 20 λίτρα νερό (βλ. Εικόνα 3), που συνεπάγεται ότι και τα δύο βαρέλια έχουν την ίδια ακριβώς καθαρότητα.

Εικόνα 3. Αποτέλεσμα μετά την επιστροφή 25 λίτρων από το βαρέλι Κ στο βαρέλι Ν.

Όταν καταπιάστηκα με αυτόν το γρίφο, πέρα από τη βασική του λύση με ενδιέφερε να μάθω αν είναι δυνατόν το κάθε βαρέλι να περιέχει ίση ποσότητα νερού και κρασιού μετά από πεπερασμένου πλήθους επαναλήψεις της παραπάνω διαδικασίας ανάμειξης. Προς αυτήν την κατεύθυνση, ας δούμε πρώτα από όλα αν κάτι τέτοιο είναι εφικτό σε ένα μόνο βήμα, όπου ως βήμα ορίζουμε τη διπλή ενέργεια της μεταφοράς μιας ποσότητας από το βαρέλι N στο K και της επιστροφής ίσης ποσότητας από το βαρέλι K στο N. Για ευκολία, ορίζουμε ως μονάδα όγκου, τον όγκο του νερού που περιέχεται αρχικά στο βαρέλι Ν. Στη συνέχεια θα χρησιμοποιήσουμε τις επόμενες μεταβλητές:

\( x^N \): ο όγκος του νερού στο βαρέλι Ν
\( x^K \): ο όγκος του νερού στο βαρέλι Κ 
\( y^N \): ο όγκος του κρασιού στο βαρέλι Ν
\( y^K \): ο όγκος του κρασιού στο βαρέλι Κ
\( c \): ο όγκος που μεταφέρεται από το ένα βαρέλι στο άλλο. Φυσικά ισχύει ο περιορισμός \( 0 \le c \le 1 \).

Με βάση αυτούς τους συμβολισμούς, αρχικά έχουμε:

\( x^N = 1 \),          \( x^K = 0 \),          \( y^N = 0 \),          \( y^K = 1 \)

Μετά τη μεταφορά \( c \) μονάδων όγκου νερού από το βαρέλι Ν στο βαρέλι Κ οι μεταβλητές θα αποκτήσουν τις παρακάτω νέες τιμές:

\( x^N = 1-c \),          \( x^K = 0 \),          \( y^N = c \),          \( y^K = 1 \)

Επιστρέφοντας \( c \) μονάδες όγκου μείγματος κρασιού/νερού από το βαρέλι Κ στο βαρέλι Ν, το \( \frac{c}{1+c} \times c \) θα είναι νερό και το \( \frac{1}{1+c} \times c \) κρασί. Έτσι οι νέοι όγκοι του νερού και του κρασιού στα βαρέλια θα γίνουν:

\( x^N = 1-c+\frac{c^2}{1+c} = \frac{1}{c+1} \),          \( x^K = \frac{c}{1+c} \),          \( y^N = c - \frac{c^2}{1+c} = \frac{c}{1+c} \),          \( y^K = 1 - \frac{c}{1+c} = \frac{1}{1+c} \)

Παρατηρούμε ότι

\( x^N = y^K \)     και     \( x^K = y^N \)     (1)

πράγμα που ουσιαστικά αποδεικνύει με πιο αυστηρό τρόπο ότι τα δύο βαρέλια έχουν ακριβώς την ίδια καθαρότητα. Για να πετύχουμε ίση ποσότητα νερού και κρασιού σε κάθε βαρέλι θα πρέπει να απαιτήσουμε \( x^N = y^N \) και \( x^K = y^K$ \) καταληγοντας στην εξίσωση:
\[ \frac{1}{1+c} = \frac{c}{1+c} \Leftrightarrow c = 1 \]
Αυτό ποιοτικά σημαίνει ότι θα πρέπει να αδειάσουμε όλο το νερό του βαρελιού Ν στο βαρέλι Κ και έπειτα να επιστρέψουμε το μισό περιεχόμενο του βαρελιού Κ στο βαρέλι Ν. Απόλυτα λογικό θα έλεγα!

Μπορεί όμως να συμβεί το ίδιο σε πεπερασμένο αριθμό βημάτων εάν \( 0 \le c < 1 \), εάν δηλαδή δεν επιτρέψουμε το \( c \) να πάρει την τιμή 1; Για να διερευνήσουμε αυτήν την περίπτωση είναι σκόπιμο να προσθέσουμε στους προηγούμενους συμβολισμούς κι ένα δείκτη που θα δηλώνει το εκάστοτε βήμα της διαδικασίας. Έτσι για παράδειγμα, το \( x_5^N \) εκφράζει τον όγκο του νερού στο βαρέλι Ν μετά από \( 5 \) βήματα της διαδικασίας. Επιπλέον, για λόγους πληρότητας, με τον δείκτη 0 συμβολίζουμε τους αρχικούς όγκους του προβλήματος. Έτσι έχουμε:

\( x_0^N = 1 \),          \( x_0^K = 0 \),          \( y_0^N = 0 \),          \( y_0^K = 1 \)

Λόγω των σχέσεων (1) μπορούμε να περιοριστούμε μόνο στη μελέτη των \( x \). Χρησιμοποιώντας παρόμοια συλλογιστική με την περίπτωση του πρώτου βήματος που είδαμε παραπάνω, αλλά με κάπως πιο κοπιώδεις υπολογισμούς προκύπτουν οι επόμενοι γενικοί τύποι, στους οποίους για πρακτικούς λόγους έχει γίνει η διάκριση μεταξύ περιττών και άρτιων δεικτών:

\( x_{2k}^N = \frac{\sum_{p=0}^k {{2k}\choose{2p}} c^{2p}}{(c+1)^{2k}} \),     \( x_{2k}^K = \frac{\sum_{p=0}^k {{2k}\choose{2p+1}} c^{2p+1}}{(c+1)^{2k}} \),     \( x_{2k+1}^N = \frac{\sum_{p=0}^k {{2k+1}\choose{2p}} c^{2p}}{(c+1)^{2k+1}} \),     \( x_{2k+1}^K = \frac{\sum_{p=0}^k {{2k+1}\choose{2p+1}} c^{2p+1}}{(c+1)^{2k+1}} \)     (2)

όπου \( {{j} \choose {i}} = \frac{j!}{i! (j-i)!} \) είναι το πλήθος των συνδυασμών \( j \) αντικειμένων ανά \( i \) και ως γνωστόν \( j! = 1 \cdot 2 \cdots j \). Είναι σημαντικό να παρατηρήσουμε ότι ο αριθμητής σε καθεμία από τις τέσσερις παραπάνω ποσότητες αποτελείται από τους μισούς όρους του διωνυμικού αναπτύγματος (γνωστού και ως αναπτύγματος του Newton)

\( (1+c)^n = 1 + {{n} \choose {1}} c + {{n} \choose {2}} c^2 + \dots + {{n} \choose {n-1}} c^{n-1} + c^n = \sum_{p=0}^n {{n} \choose {p}} c^p \)

Πιο συγκεκριμένα, το \( x_{2k}^N \) χρησιμοποιεί τους συντελεστές που εμφανίζονται στις θέσεις με περιττό δείκτη (1ο, 3ο, 5ο, κ.ο.κ.), ενώ το \( x_{2k}^K \) χρησιμοποιεί τους υπόλοιπους συντελεστές, δηλαδή εκείνους που εμφανίζονται στις θέσεις με άρτιο δείκτη (2ο, 4ο, 6ο, κ.ο.κ.). Όμοια συμπεράσματα προκύπτουν και για τα \( x_{2k+1}^N \) και \( x_{2k+1}^K \). Αυτό, πέρα από την κομψότητα που προσδίδει στη λύση του προβλήματος, βοηθάει πολύ και στους υπολογισμούς όπως θα δούμε παρακάτω. 

Προτού προχωρήσουμε, θα ήταν παράλειψη να μην αναφερθούμε στη σχέση των συντελεστών του διωνυμικού αναπτύγματος, και κατ' επέκτασιν των τύπων (2), με το γνωστό τρίγωνο του Pascal (βλ. Εικόνα 4).


Εικόνα 4. Το τρίγωνο του Pascal.

Το τρίγωνο αυτό συγκεντρώνει σε κάθε σειρά τους συντελεστές του διωνυμικού αναπτύγματος
\[ (\alpha + \beta)^n = \sum_{p=0}^n \alpha^{n-p} \beta^p \]
όπου το \( n \) αντιστοιχεί στον αύξοντα αριθμό της σειράς ξεκινώντας τη μέτρηση με \( n=0 \). Δια του λόγου το αληθές παρέχουμε τα αναπτύγματα για τις πρώτες τιμές του φυσικού αριθμού \( n \): 

\( n=0 \):     \( (\alpha + \beta)^0 = 1 \)

\( n=1 \):     \( (\alpha + \beta)^1 = 1 \alpha + 1 \beta \)

\( n=2 \):     \( (\alpha + \beta)^2 = 1 \alpha^2 + 2 \alpha \beta + 1 \beta^2 \)

\( n=3 \):     \( (\alpha + \beta)^3 = 1 \alpha^3 + 3 \alpha^2 \beta + 3 \alpha \beta^2 + 1 \beta^3 \)

κ.ο.κ.

Το τρίγωνο του Pascal συγκεντρώνει τόσες πολλές «μυστικιστικές» ιδιότητες που αποτελεί αντικείμενο λατρείας για πολλούς μαθηματικούς. Μάλιστα θα χρειαζόταν ένα ξεχωριστό άρθρο για να αναφερθούμε σε καθεμία από αυτές. Εδώ θα αναφέρουμε την πιο χαρακτηριστική ιδιότητα, σύμφωνα με την οποία το κάθε στοιχείο του τριγώνου είναι το άθροισμα των δύο αριθμών που βρίσκονται ακριβώς από πάνω του (βλ. Εικόνα 5). Η ιδιότητα αυτή είναι τόσο θεμελιώδης που χρησιμοποιείται ως ορισμός του τριγώνου του Pascal. 

Εικόνα 5. Η θεμελιώδης ιδιότητα του τριγώνου του Pascal. Κάθε στοιχείο ισούται με το άθροισμα των δύο αριθμών που βρίσκονται ακριβώς από πάνω του.

Ας επιστρέψουμε όμως στη διερεύνησή μας. Αρχικά θα αποδείξουμε ότι 

\( x_{n}^N > x_{n}^K,     \forall n \in \mathbb{N} \)     (3). 

Πράγματι, για \( n = 2k \)

\( x_{2k}^N > x_{2k}^K \Leftrightarrow \frac{\sum_{p=0}^k {{2k}\choose{2p}} c^{2p}}{(c+1)^{2k}} > \frac{\sum_{p=0}^k {{2k}\choose{2p+1}} c^{2p+1}}{(c+1)^{2k}} \Leftrightarrow \frac{\sum_{p=0}^k \left[ {{2k}\choose{2p}} c^{2p} - {{2k}\choose{2p+1}} c^{2p+1} \right]}{(c+1)^{2k}} > 0 \Leftrightarrow \frac{(1-c)^{2k}}{(c+1)^{2k}} > 0 \)

που ισχύει αφού \( 0 \le c < 1 \). Στο τελευταίο βήμα της απόδειξης κάναμε χρήση του διωνυμικού αναπτύγματος του \( (1-c)^{2k} \). Με ακριβώς ίδιο τρόπο μπορούμε φυσικά να αποδείξουμε επίσης ότι 
\[ x_{2k+1}^N > x_{2k+1}^K, \forall k \in \mathbb{N} \] 
και άρα γενικά 
\[ x_n^N > x_n^K,     \forall n \in \mathbb{N}. \] 

Λαμβάνοντας υπόψιν τη σχέση \( x_n^K = y_n^N \) που ισχύει για κάθε βήμα \( n \), έχουμε τελικά ότι 
\[ x_n^N > y_n^N,     \forall n \in \mathbb{N}. \] 
Αυτό βέβαια αποδεικνύει ότι σε πεπερασμένο πλήθος επαναλήψεων της διαδικασίας ανάμειξης των δύο βαρελιών, δεν είναι δυνατόν να πετύχουμε ίση κατανομή νερού και κρασιού σε κάθε βαρέλι, αφού όσες επαναλήψεις κι αν κάνουμε, το νερό στο βαρέλι Ν θα είναι πάντα περισσότερο από το κρασί. Τι γίνεται όμως αν επαναλάβουμε άπειρες φορές τη διαδικασία; Στην περίπτωση αυτή θα αποδείξουμε ότι
\[ \lim_{k \rightarrow \infty} x_{2k}^N = \lim_{k \rightarrow \infty} x_{2k+1}^N = \lim_{k \rightarrow \infty} y_{2k}^N = \lim_{k \rightarrow \infty} y_{2k+1}^N = \frac{1}{2}     (4) \]

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

Καθώς \( 0 \le c < 1 \), έχουμε: 
\[ \lim_{k \rightarrow +\infty} (1 - c)^{2k} = 0 \Leftrightarrow \lim_{k \rightarrow +\infty} \left[ \sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p} - \sum_{p=0}^{2k} {{2k} \choose {2p+1}} c^{2p} \right] = 0 \]
\[ \Leftrightarrow \lim_{k \rightarrow +\infty} \sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p} = \lim_{k \rightarrow +\infty} \sum_{p=0}^{2k} {{2k} \choose {2p+1}} c^{2p} \Leftrightarrow \lim_{k \rightarrow +\infty} \frac{\sum_{p=0}^{2k} {{2k} \choose {2p+1}} c^{2p}}{\sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p}} =1 \]
Συνεπώς,
\[ \lim_{k \rightarrow +\infty} \frac{(c+1)^{2k}}{\sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p}} = \lim_{k \rightarrow +\infty} \frac{\sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p} + \sum_{p=0}^{2k} {{2k} \choose {2p+1}} c^{2p}}{\sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p}} = 2 \]
και άρα
\[ \lim_{k \rightarrow +\infty} x_{2k}^N = \lim_{k \rightarrow +\infty} \frac{\sum_{p=0}^{2k} {{2k} \choose {2p}} c^{2p}}{(c+1)^{2k}} = \frac{1}{2} \]
Όμοια αποδεικνύονται και οι υπόλοιπες ισότητες της (4).

Κλείνοντας να επισημάνουμε ότι:

\( x_1^N = y_1^N \Leftrightarrow x_1^N = x_1^K \Leftrightarrow 1-c = 0 \Leftrightarrow c = 1 \)

\( x_2^N = y_2^N \Leftrightarrow x_2^N = x_2^K \Leftrightarrow 1-2c+c^2 = 0 \Leftrightarrow (1-c)^2 = 0 \Leftrightarrow c = 1 \) με πολλαπλότητα 2.

\( x_3^N = y_3^N \Leftrightarrow x_3^N = x_3^K \Leftrightarrow (1-c)^3 = 0 \Leftrightarrow c = 1 \) με πολλαπλότητα 3.

Γενικά \( x_n^N = y_n^N \Leftrightarrow x_n^N = x_n^K \Leftrightarrow (1-c)^n = 0 \Leftrightarrow c = 1 \) με πολλαπλότητα \( n \).

Ας αποδείξουμε τη γενική περίπτωση για \( n \) βήματα.

Αν \( n \) άρτιος:
\[ x_n^N = x_n^K \Leftrightarrow \sum_{p=0}^k {{2k}\choose{2p}} c^{2p} = \sum_{p=0}^k {{2k}\choose{2p+1}} c^{2p+1} \Leftrightarrow \sum_{p=0}^k \left[ {{2k}\choose{2p}} c^{2p} - {{2k}\choose{2p+1}} c^{2p+1} \right] = 0 \] 
όπου το τελευταίο αποτελεί όπως είδαμε και πιο πάνω το διωνυμικό ανάπτυγμα του \( (1-c)^{2k} \). Συνεπώς, 

\( (1-c)^{2k} = 0 \Leftrightarrow c = 1 \) με πολλαπλότητα \( n \). 

Όμοια αν \( n \) περιττός.

Αυτό βέβαια με απλά λόγια σημαίνει ότι αν \( c=1 \), τότε όσες φορές κι αν επαναλάβουμε τη διαδικασία ανάμειξης, τα δύο βαρέλια θα περιέχουν κάθε φορά ίση ποσότητα νερού και κρασιού.