JotD / QotD Ελληνική Λίστα Κουίζ (QotD)


Θέμα: Re: Η κατάλληλη διαδρομή



(nil): Vassilios Papadopoulos (md02808(@)cc.uoi.gr)
Ημερομηνία: Tue 15 Apr 2003 - 16:56:46 EEST

Απάντηση:
 Δεν μπορεί να στρωθεί τέτοιος δρόμος.

 Απόδειξη:
 Προκειμένου να ασφαλτοστρώσει τους δρόμους, η μπουλντόζα θα πρέπει να
 περάσει περισσότερες από μία φορά από κάθε πόλη. Δεν φεύγει από τον ίδιο
 δρόμο από τον οποίο ήρθε γιατί είναι ήδη στρωμένος, θα φύγει από κάποιον
 χωματόδρομο για να τον στρώσει κι εκείνον.

 Άρα μπορεί να περάσει από κάθε πόλη τόσες φορές, όσοι είναι οι δρόμοι που
 οδηγούν προς (και από) κάποια πόλη. Αν σχεδιάσουμε το τετράπλευρο ή και
μόνο
 από τα δεδομένα του προβλήματος, υπολογίζουμε ότι:
 Στην πόλη Α καταλήγουν 5 δρόμοι.
 Στην πόλη Β καταλήγουν 3 δρόμοι.
 Στην πόλη Γ καταλήγουν 3 δρόμοι.
 Στην πόλη Δ καταλήγουν 3 δρόμοι.

 Έστω ότι "απλώνουμε" τη διαδρομή της μπουλντόζας που θα στρώσει τους
 δρόμους, πάνω σε μια γραμμή
 που στο ένα άκρο της έχει την πόλη από όπου ξεκινάει η μπουλντόζα, στο άλλο
 άκρο την πόλη όπου τελειώνει και σε ενδιάμεσα σημεία βρίσκονται οι πόλεις
 από τις οποίες περνάει. Προφανώς κάθε πόλη σημειώνεται πάνω από 1 φορά στη
 γραμμή. Πρέπει δηλαδή να βρούμε με ποια σειρά θα διασχίσει η μπουλντόζα τις
 πόλεις ή με ποια σειρά θα μπουν οι πόλεις πάνω στη γραμμή.

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

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

 Άρα πρέπει ή δύο πόλεις να έχουν μονό αριθμό δρόμων ή καμμία. Κάτι που δεν
ισχύει εδώ (και οι 4 έχουν μονό αριθμό), άρα το πρόβλημα δεν λύνεται.

--
_______________________________________________________________
      Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
             https://anekdota.duckdns.org
        ___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________

Γραφτείτε και εσείς στην Ελληνική Λίστα με σπαζοκεφαλιές (QotD) και στείλτε τα κουίζ σας!!!

Επιστροφή στον κεντρικό κατάλογο αυτού του αρχείου