Εκατό άτομα βαρών 1,2,3,..,100 μονάδων αντιστοίχως βρίσκονται στην αριστερή όχθη ενός ποταμιού και θέλουν να περάσουν στη δεξιά όχθη.
Δεν μπορούν να κολυμπήσουν και έχουν στη διάθεσή τους μόνο μία βάρκα με δυνατότητα μεταφοράς μέχρι 100 μονάδων βάρους.
Λόγω ισχυρού ρεύματος του ποταμιού, η βάρκα πηγαίνει χωρίς δυσκολία στη δεξιά όχθη, αλλά για να επιστρέψει στην αριστερή πρέπει να την οδηγήσει πίσω, μόνο του, ένα διαφορετικό κάθε φορά άτομο ως κωπηλάτης.
Ο Σταύρος αναρωτιέται αν υπάρχει τρόπος για να περάσουν όλα τα άτομα στη δεξιά όχθη.
Εσείς τι λέτε, υπάρχει;
Αν ναι πώς, αν όχι γιατί;
Αρχικά κάποιες παρατηρήσεις:
Α. Ο βαρύτερος τύπος δεν μπορεί να ξεκινήσει πρώτος ούτε και τελευταίος. Αν είναι πρώτος, αφού θα ταξιδέψει μόνος είναι υποχρεωμένος να επιστρέψει και στην ουσία να έχουμε ξοδέψει ένα ταξίδι επιστροφής. Δεν μπορεί να ταξιδέψει τελευταίος, γιατί αναγκαστικά πρέπει να υπάρχει κάποιος που θα φέρει τη βάρκα στην όχθη που είναι αρχικά ο βαρύτερος και συνεπώς να γίνει ένα επιπλέον ταξίδι για να πάρει αυτόν που θα έχει μείνει πίσω.
Β. Ο βαρύτερος δεν πρέπει να κάνει κανένα ταξίδι επιστροφής. Αν κάνει, αυτό σημαίνει ότι θα υπάρχει κάποιος από τους υπόλοιπους που θα αναγκαστεί να κάνει επιπλέον ταξίδι επιστροφής αφού όπως είδαμε ο βαρύτερος δεν ταξιδεύει ούτε πρώτος ούτε και τελευταίος. Στην ουσία το πήγαινε έλα του βαρύτερου μας επιβαρύνει. Θέλουμε μόνο το πήγαινε.
Γ. Συμφέρει η βάρκα πάντα στο πήγαινε να ταξιδεύει με το μέγιστο της χωρητικότητας.
Μπορούμε να πετύχουμε το ζητούμενο σε όλες τις περιπτώσεις που έχουμε μονό αριθμό ατόμων. Δηλαδή για ν=1,3,5,7,…99,101,…..2κ+1
Πώς μπορούμε να το πετύχουμε ; Αυτό γίνεται αν χωρίσουμε την ομάδα των ατόμων σε ζευγάρια συνολικού βάρους ίσου με το βαρύτερο άτομο. Αν για παράδειγμα έχουμε ν=7 θα έχουμε1-6, 2-5, 3-4, 7
Περνάνε δεξιά 1-6
Επιστρέφει ο 1
Περνάει δεξιά ο 7
Επιστρέφει ο 6
Και πλέον έχουμε 2 ταξίδια και τους 123456 από τη μια όχθη με τη βάρκα και τον 7 από την άλλη.
Στη συνέχεια παίρνουμε με τη σειρά όλα τα ζευγάρια εκτός του 1-6 που ήδη έχουμε χρησιμοποιήσει, να περάσουν απέναντι ανά δύο με την επιστροφή να την αναλαμβάνει ο βαρύτερος. Για παράδειγμα περνάνε δεξιά οι 2-5 και επιστρέφει ο 5. Στο τέλος αυτής της διαδικασίας θα έχουμε τον βαρύτερο κάθε ζευγαριού στην αριστερή όχθη μαζί με το ζευγάρι 1-6 και τη βάρκα και από τη δεξιά όχθη τον βαρύτερο (στην προκειμένη περίπτωση τον 7) και τον ελαφρύτερο κάθε ζευγαριού.
Στη συνέχεια περνάει απέναντι το ζευγάρι 1-6 και μετά αναλαμβάνουν οι ελαφρύτεροι να μεταφέρουν τον έτερο του ζεύγους τους.
Με αυτή τη διαδικασία περνάνε όλοι και όλοι εκτός του βαρύτερου έχουν κωπηλατήσει ακριβώς μια φορά. Θα πρέπει να σημειωθεί ότι υπάρχει και η παραλλαγή όπου ο βαρύτερος περνάει αφού έχουν περάσει πρώτα όλα τα ελαφρύτερα μέλη των ζευγαριών.
Σε κάθε περίπτωση καταφέρνουμε το ζητούμενο με ακριβώς ν=2κ+1 ταξίδια. Για 3 άτομα 3 ταξίδια, 5 άτομα 5 ταξίδια …για 99 άτομα 99 ταξίδια κοκ
Δυστυχώς αυτή τη διαδικασία δεν μπορούμε να την εφαρμόσουμε σε περίπτωση που το πλήθος των ατόμων είναι ζυγός αριθμός γιατί αν αφαιρέσουμε τον βαρύτερο, οι υπόλοιποι που είναι μονός αριθμός δεν μπορούν να σχηματίσουν ζευγάρια συνολικού βάρους ίσου με τον βαρύτερο αφού μας περισσεύει ένας. Στην προκειμένη περίπτωση μας περισσεύει ο 50, με την υποχρέωση κάποιος από τους υπόλοιπους που ήδη έχουν κωπηλατήσει μια φορά προς τα αριστερά να το κάνει και δεύτερη.
Θα δείξουμε ότι δεν υπάρχει τρόπος, όχι μόνον για τα 100 άτομα, αλλά για οποιοδήποτε άρτιο αριθμό ατόμων ν βάρους 1,2,3…ν μονάδων και μιας βάρκας δυνατότητας μέχρι ν μονάδων με διαφορετικό κάθε φορά κωπηλάτη επιστροφής.
Είναι προφανές ότι δεν μπορούν να γίνουν περισσότερες από (ν-1) επιστροφές (η μονάδα βάρους ν, δεν έχει νόημα να επιστρέψει στην αριστερή όχθη). Επομένως ο μέγιστος αριθμός διαδρομών από την αριστερή όχθη στην δεξιά, είναι ν.
Ας παρακολουθήσουμε τι γίνεται σε κάθε διαδρομή.
Αρχικά είναι όλα τα άτομα στην αριστερή όχθη, δηλαδή βρίσκονται αριστερά 1+2+3+…+ν=ν*(ν+1)/2 μονάδες βάρους.
Στη πρώτη διαδρομή θα περάσουν στη δεξιά όχθη το πολύ ν μονάδες βάρους και θα επιστρέψει τουλάχιστον μία μονάδα βάρους. Αρα μετά τη πρώτη διαδρομή και επιστροφή, στην αριστερή όχθη θα βρίσκονται ακόμα τουλάχιστον ν*(ν+1)/2-(ν-1) μονάδες βάρους.
Μετά και τη δεύτερη διαδρομή και επιστροφή, στην αριστερή όχθη θα βρίσκονται ακόμα τουλάχιστον ν*(ν+1)/2-[(ν-1)+(ν-2)] μονάδες βάρους. Επομένως, ακόμα και ύστερα από (ν-1) διαδρομές και επιστροφές, στην αριστερή όχθη θα βρίσκονται ακόμα τουλάχιστον:
ν*(ν+1)/2-[(ν-1)+(ν-2)+…+2+1]=ν*(ν+1)/2-ν*(ν-1)/2=ν μονάδες βάρους
Συμπέρασμα: Εάν υπάρχει τρόπος να συμβεί το ζητούμενο, τότε:
1. Απαιτούνται ακριβώς ν διαδρομές και (ν-1) επιστροφές
2. Σε κάθε διαδρομή, η βάρκα πρέπει να είναι φορτωμένη με ακριβώς ν μονάδες βάρους
Κατά τις (ν-1) επιστροφές, θα επιστρέψουν σταδιακά στην αριστερή όχθη όλες οι μονάδες βάρους από 1…(ν-1). Επομένως, κατά τις ν διαδρομές από την αριστερή όχθη στη δεξιά θα μεταφερθούν συνολικά από δύο φορές οι μονάδες βάρους 1…(ν-1) και μία φορά η μονάδα βάρους ν. Επειδή όμως σε κάθε διαδρομή, η βάρκα πρέπει να είναι φορτωμένη με ακριβώς ν μονάδες βάρους είναι προφανές ότι:
Η μονάδα βάρους (ν-1) θα μεταφέρεται πάντα μαζί με τη μονάδα βάρους 1
Η μονάδα βάρους (ν-2) θα μεταφέρεται πάντα μαζί με τη μονάδα βάρους 2
Η μονάδα βάρους (ν-3) θα μεταφέρεται πάντα μαζί με τη μονάδα βάρους 3
………………………………………………………………………………………………………………
Εάν ο ν είναι περιττός, τότε είναι δυνατόν η μονάδα βάρους (ν+1)/2 να μεταφερθεί μαζί με την μονάδα βάρους (ν-1)/2, και το εγχείρημα να στεφθεί από επιτυχία. Εάν όμως ο ν είναι άρτιος, τότε η μονάδα βάρους ν/2 δεν μπορεί να συνδυαστεί με καμία άλλη ώστε να δώσει άθροισμα ν. (Ακόμα και αν συνδυαστεί με δύο άλλες μικρότερες μονάδες βάρους που αθροίζουν ν/2, αυτές θα λείψουν από τα ζευγαρώματα των μεγαλύτερων μονάδων βάρους).
Συμπέρασμα: Για ν=100 άτομα, δεν υπάρχει τρόπος
Το ζητούμενο είναι αδύνατο και ένας τρόπος για να το δείξουμε είναι ο εξής:
Συνολικό φορτίο για να μεταφερθεί δεξιά 5050
Μέγιστο φορτίο που μεταφέρεται κάθε φορά 100
Ελάχιστος αριθμός μεταφορών 51
Ελάχιστος αριθμός ατόμων που θα επιστρέψουν 51
Μέσο βάρος όσων επέστρεψαν (π.χ. οι 25-75) 50
Συνολικό βάρος όσων επέστρεψαν 2550
Ελάχιστος αριθμός μεταφορών 26
Ελάχιστος αριθμός ατόμων που θα επιστρέψουν 26
Μέσο βάρος όσων επέστρεψαν (π.χ. οι 12-24 και 76-88) 50
Συνολικό βάρος όσων επέστρεψαν 1300
Ελάχιστος αριθμός μεταφορών 13
Ελάχιστος αριθμός ατόμων που θα επιστρέψουν 13
Μέσο βάρος όσων επέστρεψαν (π.χ. οι 5-11 και 89-94) 46,53846154
Συνολικό βάρος όσων επέστρεψαν 605
Ελάχιστος αριθμός μεταφορών 7
Ελάχιστος αριθμός ατόμων που θα επιστρέψουν 7
Μέσο βάρος όσων επέστρεψαν (π.χ. οι 2-4 και 95-98) 56,42857143
Συνολικό βάρος όσων επέστρεψαν 395
Ελάχιστος αριθμός μεταφορών 4
Ελάχιστος αριθμός ατόμων που θα επιστρέψουν 4
Δεν υπάρχουν 4, γιατί μπορούν να επιστρέψουν μόνο ο 1 και ο 99
Ολόσωστες οι απαντήσεις, μπράβο σε όλους!
Υποδειγματικές οι γενικεύσεις από Κωστή, Στράτο, υποκλίνομαι!