From aasteroid@hotmail.com Mon Aug 6 14:24:07 2001 Date: Sun, 05 Aug 2001 13:20:25 +0300 From: Tim Zadorozhny <AASTEROID@HOTMAIL.COM> To: solutions@fourier.math.uoc.gr Subject: solution, to, Problem, 0.3 Προβλήμα 0.3. (Τιμόθεος Ζαντορόζνι, aasteroid@hotmail.com) Θα αποδείξουμε ότι το πρόβλημα λύνεται για ν=κ*(κ+1)/2 με ένα πήγαινε-έλα, ενώ για όλες τις άλλες τιμές του ν μπορούμε να το λύσουμε με ενάμισι πήγαινε-έλα. Για ευκολία ας υποθέσουμε ότι και στις δυο όχθες του ποταμού υπάρχει ένας ξύλινος πίνακας με τρύπες τοποθετημένες ως εξής: + + + + + + + + + + + + + + + ... ... ... (οι πίνακες είναι απείρως μεγάλοι) σε κάθε μια τρυπά μπορούμε να βάλουμε ένα άκρο καλωδίου. Στην περίπτωση που το ν=κ*(κ+1)/2, τοποθετούμε τις άκρες τον καλωδίων στην αριστερή όχθη στον πίνακα με τον παρακάτω τρόπο: (αριστερή όχθη) * * * * * * * * * * * * * * * τώρα συνδέουμε μετάξι τους τις άκρες καλωδίων που βρίσκονται στην ίδια σειρά, και περνούμε κάτι σαν: (αριστερή όχθη) * *-* *-*-* *-*-*-* *-*-*-*-* Διασχίζουμε το ποτάμι και μοιράζουμε τις άκρες καλωδίων στην δεξιά όχθη σε κλάσεις. Δυο άκρες ανήκουν στην ίδια κλάση αν και μόνο αν το πολύμετρο δείχνει ότι οι άκρες αυτές είναι βραχυκυκλωμένες στην αριστερή μεριά. Όλες οι κλάσης θα έχουν διαφορετικό αριθμό καλωδίων, και συγκεκριμένα θα υπάρχει μια κλάση με 1, 2, 3, ..., κ άκρες καλωδίων. Τώρα μπορούμε να τοποθετήσουμε τις άκρες τις δεξιάς όχθης στον πίνακα έτσι ώστε κάθε δυο άκρες που ανήκουν στην ίδια κλάση να βρίσκονται στην ίδια σειρά και στης ίδιες γραμμές τwv δυο πινάκων να βρίσκετε ίσο πλήθος ακρων. Προφανώς, δυο άκρες του ίδιου καλωδίου και στις δυο όχθες θα βρίσκονται στην ίδιες σειρές των πινάκων. Τώρα βραχυκυκλώνουμε τις άκρες που βρίσκονται στην ίδια στήλη και επιστρέφουμε στην αριστερή όχθη. ( δεξιά όχθη ) * | * * | | * * * | | | * * * * | | | | * * * * * Εκεί ελευθερώνουμε όλες τις άκρες, και μοιράζουμε τις άκρες τις αριστερής μεριάς σε κλάσεις, ακριβός με τον ίδιο τρόπο που κάναμε και πριν. Παρατηρούμε ότι κάθε δυο άκρες της αριστερής όχθης που βρίσκονται στην ίδια κλάση βρίσκονται σε διαφορετικές γραμμές. Επίσης κάθε δυο κλάσης έχουν διαφορετικό πλήθος άκρwν, το όπιο δεν υπερβαίνει το κ. Τώρα μπορούμε να βγάλουμε τα συμπεράσματα μας. Κάθε άκρο καλωδίου Α στην αριστερή όχθη, αντιστοιχεί στην άκρη Β της δεξιάς όχθης αν και μόνο αν και οι δυο άκρες βρίσκονται στην ίδια σειρά των πινάκων και το πλήθος της κλάσης στην όπια ανήκει το Α ισούται με τον αριθμό τον ακρών της δεξιάς όχθης που βρίσκονται στην ίδια στήλη με το Β. Όταν ν != κ*(κ+1)/2 , για παράδειγμα ν=13, τότε βάζουμε τις άκρες τον καλωδίων της αριστερής όχθης στον πίνακα με τον παρακάτω τρόπο, και βραχυκυκλώνουμε αυτές που βρίσκονται στην ίδια γραμμή. (αριστερή όχθη) * *-* *-*-* *-*-*-* *-*-* . . πάμε από την άλλη και μοιράζουμε σε κλάσεις όπως και πριν. Βάζουμε τις άκρες καλωδίων στον πίνακα έτσι ώστε κάθε δυο άκρες από την ίδια κλάση να βρίσκονται στην ίδια γραμμή και στης ίδιες γραμμές τον δυο πινάκων να βρίσκετε ίσο πλήθος ακρων. Τώρα δεν μπορούμε να είμαστε σίγουροι ότι και οι δυο άκρες του ίδιου καλωδίου βρίσκονται στεις ίδιες σειρές, και για αυτό συνδέουμε τις άκρες στην δεξιά όχθη ως εξής (βραχυκυκλώνουμε τις άκρες όλων των σειρών εκτός της τελευταίας). (δεξιά όχθη) * | *-* | *-*-* | *-*-*-* * * * . . Διασχίζουμε το ποτάμι και ελέγχουμε σε πια από τις δυο γραμμές με ίσο πλήθος ακρών τα άκρα δεν βραχυκυκλώνονται με κανένα άλλο άκρο. Αν χρειαστεί, εναλλάσσουμε τις δυο αυτές γραμμές, έτσι ώστε κάθε καλώδιο έχει και το αριστερό και το δεξί του άκρα στις ίδιες γραμμές. Μετά κάνουμε ότι κάναμε και προηγούμενος, παρατηρώντας βέβαια ότι όλες οι στήλες έχουν διαφορετικό πλήθος άκρωv. _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp </HTML>