next up previous contents
Next: 4 Πρόβλημα 3 (10/7/2001) Up: Προβλήματα για το Μαθηματικό Previous: 2 Πρόβλημα 1: Από   Contents

3 Πρόβλημα 2 (2/7/2001) - Δόθηκε υπόδειξη (5/7/2001) - Λύθηκε (5/8/2001)

(α) Το Δημόσιο έχει αναθέσει σ'ένα εργολάβο να περάσει 15 καλώδια κάτω από ένα πολύ φαρδύ ποτάμι στη Βόρεια Ελλάδα. Στην πρώτη επιθεώρηση του έργου ο επιθεωρητής του Δημοσίου ανακαλύπτει ότι ο εργολάβος κάνει απίστευτες προχειροδουλειές: πέρασε τα καλώδια κάτω από το ποτάμι χωρίς να τα έχει μαρκάρει πριν με αποτέλεσμα στις δύο όχθες του ποταμιού να βρίσκονται τώρα από 15 όμοιες άκρες άσπρων καλωδίων, χωρίς κανείς να ξέρει ποιό καλώδιο από την αριστερή όχθη αντιστοιχεί σε ποιο καλώδιο στη δεξιά.

Ως συνήθως γίνεται σε τέτοιες περιπτώσεις, ο εργολάβος απολύεται αμέσως ...

Το Δημόσιο σας αναθέτει να ξεκαθαρίσετε τα πράγματα: τα καλώδια αριστερά ονομάζονται αυθαίρετα $A_1, \ldots , A_{15}$ κι αυτά δεξιά $B_1, \ldots, B_{15}$. Σκοπός σας είναι να τα ταυτίσετε, π.χ. το $A_1$ είναι το $B_3$, το $A_2$ είναι το $B_{11}$, κλπ.

Οι κανόνες του παιχνιδιού είναι οι εξής:

  1. Δουλεύετε μόνος/η σας.
  2. Το μόνο όργανο που μπορείτε να χρησιμοποιήσετε είναι ένα πολύμετρο, που σας επιτρέπει να ελέγξετε αν ένα κύκλωμα είναι κλειστό ή όχι.
  3. Ξεκινάτε από την αριστερή πλευρά και σας επιτρέπεται να ταξιδέψετε στη δεξιά μεριά μόνο μια φορά (μετ' επιστροφής) προτού καταλήξετε στο συμπέρασμά σας (είναι φαρδύ το ποτάμι και το ταξίδι κοστίζει - το Δημόσιο προσέχει τα χρήματά του, ως γνωστόν).
Με βάση αυτούς τους κανόνες, το μόνο πράγμα που μπορείτε να κάνετε είναι να βραχυκυκλώσετε κάποιες ομάδες καλωδίων αριστερά, να πάτε δεξιά, να κάνετε τις μετρήσεις σας, να βραχυκυκλώσετε κι εκεί κάποιες ομάδες καλωδίων, να επιστρέψετε αριστερά, να κάνετε κι εκεί κάποιες, ενδεχομένως άλλες, συνδέσεις καλωδίων μεταξύ τους, μετρήσεις, και μετά να καταλήξετε σε συμπέρασμα. (Όταν λέμε ότι βραχυκυκλώνουμε μια ομάδα καλωδίων μεταξύ τους, εννούμε ότι πιάνουμε τις άκρες τους και τις δένουμε όλες μαζί. Αν τώρα ελέγξουμε στην άλλη όχθη οποιοδήποτε ζεύγος από αυτά που βραχυκυκλώσαμε το πολύμετρο θα μας δείξει ότι είναι ενωμένα στην άλλη μεριά.)

Δείξτε ότι αυτό που ζητά το Δημόσιο είναι εφικτό.

(β) Αν το πλήθος των καλωδίων είναι οποιοδήποτε $n\neq 2$ δείξτε ότι και πάλι το πρόβλημα λύνεται, με ένα σταθερό αριθμό από πήγαινε-έλα, που δεν εξαρτάται από το $n$. Δε νομίζω πως αξίζει τον κόπο να βρείτε ποιος είναι ο ελάχιστος αυτός αριθμός, απλώς δείξτε ότι μπορείτε με 10, π.χ., πήγαινε-έλα, να λύσετε το πρόβλημα για οποιοδήποτε $n$ (εκτός από $n=2$ για το οποίο είναι φυσικά αδύνατο να λυθεί!).

Υπόδειξη για το (α) (5/7/2001): 

*
**
***
****
*****

Μια λύση για το πρόβλημα από Τιμόθεο Ζαντορόζνι (5/8/2001)


Mihalis Kolountzakis