7 Ιαν 2011

Τα 5 τούβλα

Το σημερινό πρόβλημα είναι ένα από τα παλιότερα προβλήματα τοπολογίας.

Σχήμα 1.
Μπορείτε να ζωγραφίσετε το διάγραμμα του Σχ. 1(α) με το πολύ τρεις μολυβιές χωρίς να περάσετε πάνω από μία γραμμή περισσότερες από μία φορές;

Είναι εύκολο να ζωγραφίσουμε το διάγραμμα με τρεις μολυβιές εκτός από μία γραμμή. Μερικές προσπάθειες φαίνονται στο Σχ. 1(γ). Μπορούμε όμως να ζωγραφίσουμε ολόκληρο το διάγραμμα του Σχ. 1(α) με τρεις μολυβιές;

Το πρόβλημα είναι τοπολογικό επειδή το ακριβές μέγεθος και σχήμα δεν παίζουν ρόλο. Για παράδειγμα αντί του διαγράμματος του Σχ. 1(α) το πρόβλημα θα μπορούσε να διατυπωθεί ισοδύναμα για το διάγραμμα του Σχ. 1(β).

6 σχόλια:

  1. Λοιπόν το κλειδί εδώ νομίζω πως είναι ότι κάθε κόμβος (τελεία) συνδέεται με άλλους 2 και μόνο. Αν υποθέσουμε ότι ξεκινάμε από οποιοδήποτε κόμβο, τότε για να κλείσουμε ένα βρόχο απαιτείται να περάσουμε από την αρχίκη τελεία, και μπορούμε να συνεχίσουμε, αλλά μόνο μέχρι να κλείσουμε και δεύτερο βρόχο, αφού θα σημαίνει ότι έχουμε φτάσει από κόμβο από τον οποίο έχουμε ήδη περάσει. Γενικά δηλαδή, οι πρώτοι 2 βρόχοι μπορούν να γίνουν με μία μολυβία, και χρειάζεσαι 1 μολυβιά για κάθε επόμενο (αφού ένας κόμβος αρχίζει και τελειώνει με τελεία), άρα για Ν τούβλα, θέλουμε τουλάχιστον Ν-1 μολυβιές.

    Φαντάζομαι η εξήγηση δεν είναι απολύτως σωστή, αφού για 6 τούβλα μπορείς να κάνεις 2 φορές από 2 βρόχους με μια μολυβιά, και μετά να συνδέσεις τους υπόλοιπους, αλλά και πάλι το Ν-1 ισχύει.

    ΑπάντησηΔιαγραφή
  2. Χμ... πολύ ενδιαφέρον αυτό που λες, Messie. Σκέψου όμως το εξής:

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

    Τότε στο σχήμα υπάρχουν πάλι 5 βρόχοι αλλά μπορούμε να το ζωγραφίσουμε με μόνον 3 μολυβιές.

    ΑπάντησηΔιαγραφή
  3. Ναι αλλα τότε θα έχεις ένα κόμβο με 4 κλάδους, και επομένως μπορείς να περάσεις 2 φορές με το μολύβι σου και δεν χρειάζεται να σηκώσεις το μολύβι, άρα περνώντας από ένα κόμβο με 4 κλάδους μπορείς να σχεδιάσεις πλέον 3 βρόχους. Στο σχήμα κάθε κόμβος έχει 3 και μόνο 3 κλάδους, άρα περνώντας από οποιοδήποτε κόμβο μπορείς να σχεδιάσεις μόνο 2 το πολύ βρόχους.

    ΑπάντησηΔιαγραφή
  4. Ακριβώς εκεί ήθελα να εστιάσω, στον αριθμό των κλάδων που φτάνουν σε έναν κόμβο.

    Αλλά ας επανέλθουμε στη λύση σου. Λες ότι με μία μολυβιά μπορούμε να φτιάξουμε 2 βρόχους και πράγματι είναι πολλοί οι τρόποι που μπορούμε να το κάνουμε αυτό.

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

    Το ερώτημα είναι: υπάρχει περίπτωση να φτιάξουμε τους δύο πρώτους βρόχους με μία συγκεκριμένη μολυβιά τέτοια, ώστε να μπορούμε να φτιάξουμε άλλους δύο βρόχους με μία μόνον μολυβιά (και τελικά ακόμα ένα βρόχο με μία τρίτη μολυβιά);

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

    ΑπάντησηΔιαγραφή
  5. Ναι, αλλά σκέψου και αυτο:

    Αν είχες ένα αντίστοιχο πρόβλημα με 6 τουβλα, τοτε θα μπορούσες να κάνεις το εξής:

    [IMG]http://i56.tinypic.com/2vc6zrk.png[/IMG]

    το ανέβασα για να δεις το παράδειγμά μου.
    Εδώ μπορείς να κάνεις 2 βρόχους με 1 μολυβιά, για τους 2 πρώτους βρόχους ενώ για τους άλλους χρειάζεσαι τρεις μολυβιές. Σύνολο Ν-1 =5 μολυβιές για Ν=6 βρόχους

    ΑπάντησηΔιαγραφή
  6. Λοιπόν μου ήρθε και το εξής:

    ->1 σχήμα που είναι απομονωμένο και έχει ν βρόχους χρειάζεται 2(ν-1) κόμβους (εάν ένας κόμβος έχει 3 κλάδους)

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

    ->Για να ενώσεις 2 απομονωμένα σχήματα μεταξύ τους χρειάζεσαι 2 μολυβιές, και δημιουργείς +1 βρόχο (τον μεταξύ τους).

    Τα παραπάνω σημαίνουν ότι κάθε απομονωμένο σχήμα με ν βρόχους έχει 2(ν-1) κόμβους καιχρειάζεται ν-1 μολυβιές, αφού κάθε μολυβιά δημιουργεί 2 κόμβους.

    Επομένως, μπορούμε να δούμε ότι η πρώτη μολυβία κάθε απομονωμένου σχήματος δημιουργεί 2 βρόχους και 2(2-1) κόμβους. Κάθε επόμενη μολυβιά που ξεκινά από το σχήμα και τελειώνει στο ίδιο σχήμα δημιουργεί 1 και μόνο κλάδο, και 2 κόμβους. Μπορείς για πολλούς κλάδους να δημιουργήσεις απομονωμένους βρόχους, με 2(2-1) μολυβιές, αλλά για να τα ενώσεις και να τα κάνεις 1 ενωμένο σχήμα πρέπει να δημιουργήσεις +2 κλάδους και να ξοδέψεις +1 μολυβιά, χωρίς να δημιουργήσεις επιπλέον βρόχο.

    ΑπάντησηΔιαγραφή