Οι Διαδρομές

Στην μακρινή χώρα της Λοξολάνδης, οι πόλεις «Α», «Β», και «Γ» συνδέονται μεταξύ τους με το οδικό δίκτυο της χώρας. Γνωρίζουμε ότι υπάρχει τουλάχιστον ένας δρόμος (μπορεί να είναι και περισσότεροι) που να συνδέει άμεσα κάθε ζεύγος των τριών πόλεων. Για παράδειγμα, εάν κάποιος ταξιδιώτης θέλει να μεταβεί από την πόλη «Α» στην πόλη «Β» μπορεί να πάρει κάποιο δρόμο που συνδέει άμεσα τις δυο πόλεις ή να  χρησιμοποιήσει σαν ενδιάμεσο σταθμό την πόλη «Γ». Ανάλογη διαδικασία προβλέπεται για την μετάβαση από οποιαδήποτε από τις τρεις πόλεις με προορισμό τις άλλες δυο πόλεις. Το υπουργείο μεταφορών της Λοξολανδης υπολόγισε ότι ο αριθμός των συνολικών διαδρομών από την πόλη «Α» στην πόλη «Β» είναι 33. Συμπεριλαμβανομενων και των διαδρομών με ενδιάμεσο σταθμό την πόλη «Γ». Ανάλογα, ο αριθμός των συνολικών διαδρομών από την πόλη «Β» στην πόλη «Γ» είναι 23, επισης συμπεριλαμβανόμενων των διαδρομών με ενδιάμεσο σταθμό την πόλη «Α». Να υπολογίσετε το συνολικό αριθμό των διαδρομών από την πόλη «Α» στην πόλη «Γ». ( συμπεριλαμβανόμενων και των διαδρομών με ενδιάμεσο σταθμό την πόλη «Β»).  (Κατ.34/Νο.750)

Πηγη: http://mathhmagic.blogspot.gr/2013/08/blog-post_25.html

Λύση

-Έστω «x» το πλήθος των διαδρομών που συνδέουν άμεσα (δεν διέρχονται από την πόλη «Γ») τις πόλεις «Α» και «Β». -Έστω «y» το πλήθος των διαδρομών που συνδέουν άμεσα (δεν διέρχονται από την πόλη «A») τις πόλεις «Β» και «Γ». -Έστω «z» το πλήθος των διαδρομών που συνδέουν άμεσα (δεν διέρχονται από την πόλη «B») τις πόλεις «A» και «Γ». Αν «y» δρόμοι συνδέουν την πόλη «Β» με την πόλη «Γ» και «z» δρόμοι την πόλη «Γ» με την πόλη «Α» τότε μεταβαίνουμε έμμεσα (διερχόμενοι από την πόλη «Γ» ) από την πόλη «Β» στην πόλη «Α» από yz διαφορετικές διαδρομές. Έχουμε λοιπόν τις παρακάτω αλγεβρικές σχέσεις: x+yz=33 (1), y+xz=23 (2). Αν προσθέσουμε κατά μέλη τις (1) και (2) και παραγοντοποιήσουμε λαμβάνουμε: x+y+yz+xz=56 ---> (x+xz)+(y+yz)=56 ---> x(z+1)+y(z+1) ---> (x+y)(z+1)=56 (3) Αν αφαιρέσουμε κατά μέλη τις (1) και (2) και παραγοντοποιήσουμε λαμβάνουμε: (x+yz)-(y+xz)=33-23 ---> x+yz-y-xz=10 ---> (yz-y)-(xz-x)=10 ---> y(z-1)-x(z-1)=10 ---> (y-x)(z-1)=10 (4) O z είναι θετικός ακέραιος διαφορετικός του μηδέν. Από την σχέση (3) προκύπτει ότι ο (z+1) είναι διαιρέτης του 56. Από την σχέση (4) προκύπτει ότι ο (z-1) είναι διαιρέτης του 10. Οι μοναδικοί αριθμοί που ικανοποιούν τις παραπάνω είναι z=3 ή z=6. Για z=3 οι τιμές x, και y προκύπτουν δεκαδικοί αριθμοί, άρα η τιμή απορρίπτεται. Για z=6 τότε έχουμε x=3, και y=5. Οπότε οι συνολικές διαδρομές από την πόλη «Α» στην πόλη «Γ» είναι:6+3*5=6+15=21.