From: Vassilios Papadopoulos (md02808(@)cc.uoi.gr)
Date: Τρι 15 Απρ 2003 - 16:56:46 EEST
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
- Mail actions: [ respond to this message ] [ mail a new topic ]
Απάντηση:
Δεν μπορεί να στρωθεί τέτοιος δρόμος.
Απόδειξη:
Προκειμένου να ασφαλτοστρώσει τους δρόμους, η μπουλντόζα θα πρέπει να
εράσει περισσότερες από μία φορά από κάθε πόλη. Δεν φεύγει από τον ίδιο
δρόμο από τον οποίο ήρθε γιατί είναι ήδη στρωμένος, θα φύγει από κάποιον
χωματόδρομο για να τον στρώσει κι εκείνον.
Άρα μπορεί να περάσει από κάθε πόλη όσες φορές, όσοι είναι οι δρόμοι που
οδηγούν προς (και από) κάποια πόλη. Αν σχεδιάσουμε ο τετράπλευρο ή και
μόνο
από τα δεδομένα του προβλήματος, υπολογίζουμε ότι:
Στην πόλη Α καταλήγουν 5 δρόμοι. Στην πόλη Β καταλήγουν 3 δρόμοι. Στην πόλη Γ καταλήγουν 3 δρόμοι. Στην πόλη Δ καταλήγουν 3 δρόμοι.
Έστω ότι "απλώνουμε" τη διαδρομή της μπουντόζας που θα στρώσει τους δρόμους, πάνω σε μια γραμμή που στο ένα άκρο της έχει την πόλη από όπου ξεκινάει η μπουλντόζα, στο άλλο άκρο την πόλη όπου τελειώνει και σε ενδιάμεσα σημεία βρίσκονται οι πόλεις από τις οποίες περνάει. Προφανώς κάθε πόλη σημειώνεται πάνω από 1 φορά στη γραμμή. Πρέπει δηλαδή να βρούμε μ ποια σειρά θα διασχίσει η μπουλντόζα τις πόλεις ή με ποια σειρά θα μπουν οι πόλεις πάνω στη γραμμή.
Για να μπει μια πόλη στο εσωτερικό, πρέπει να έχει 2μη ασφαλτοστρωμένους ακόμη δρόμους, έναν για να έρθει η μπουλντόζα κι έναν για να φύγει. Οι πόλεις που βρίσκονται στα άκρα μπορούν να έχουν έναν μη ασφαλτοστρωμένο δρόμο (ή και δύο, αν η μπουλντόζα ξεκινάει και τελειώνει στην ίδια πόλη).
Άρα οι πόλεις που θα μπουν στο ενδιάμεσο της διαδρομής πρέπει να έχουν
άρτιο
(ζυγό) αριθμό δρόμων που οδηγούν σε/φεύγουν από αυτές. Οι πόλεις που
βρίσκονται στα άκρα αν είαι διαφορετικές, θα είναι δύο πόλεις με μονό
αριθμό δρόμων, ή αν είναι η ίδια πόλη, θα έχει και αυτή ζυγό αριθμό δρόμων.
Άρα πρέπει ή δύο πόλεις να έχουν μονό αριθμό δρόμων ή καμμία. Κάτι που δεν ισχύει εδώ (και οι 4 έχουν μονό αριθμό), άρα το πρόβλημα δεν λύνεται.
--
_______________________________________________________________
Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
https://anekdota.duckdns.org
___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________
- Next message: George Papargiris: "Re: Η κατάλληλη διαδρομή (Λύση)"
- Previous message: Dionisios Belekoukias: "Πλάτος δρόμου και ένα ορθογώνιο τρίγωνο (2 quiz σε 1)"
- Maybe in reply to: George Papargiris: "Η κατάλληλη διαδρομή"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
- Mail actions: [ respond to this message ] [ mail a new topic ]