Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
![\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-2.42,-6.1) rectangle (9.18,3.36);
\draw [line width=1.2pt] (-2.,3.)-- (-2.,1.);
\draw [line width=1.2pt] (-2.,1.)-- (2.,1.);
\draw [line width=1.2pt] (2.,1.)-- (2.,3.);
\draw [line width=1.2pt] (2.,3.)-- (-2.,3.);
\draw [line width=1.2pt] (-2.,2.)-- (2.,2.);
\draw [line width=1.2pt] (0.,3.)-- (0.,2.);
\draw [line width=1.2pt] (-1.,2.)-- (-1.,1.);
\draw [line width=1.2pt] (1.,2.)-- (1.,1.);
\begin{scriptsize}
\draw [fill=black] (-2.,2.) circle (1.5pt);
\draw [fill=black] (-1.,2.) circle (1.5pt);
\draw [fill=black] (0.,2.) circle (1.5pt);
\draw [fill=black] (1.,2.) circle (1.5pt);
\draw [fill=black] (2.,2.) circle (1.5pt);
\draw [fill=black] (-2.,3.) circle (1.5pt);
\draw [fill=black] (2.,3.) circle (1.5pt);
\draw [fill=black] (0.,3.) circle (1.5pt);
\draw [fill=black] (-2.,1.) circle (1.5pt);
\draw [fill=black] (-1.,1.) circle (1.5pt);
\draw [fill=black] (1.,1.) circle (1.5pt);
\draw [fill=black] (2.,1.) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}](/forum/ext/geomar/texintegr/latexrender/pictures/e4664e41afb5ef73d0001a1a7ee74976.png "\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-2.42,-6.1) rectangle (9.18,3.36);
\draw [line width=1.2pt] (-2.,3.)-- (-2.,1.);
\draw [line width=1.2pt] (-2.,1.)-- (2.,1.);
\draw [line width=1.2pt] (2.,1.)-- (2.,3.);
\draw [line width=1.2pt] (2.,3.)-- (-2.,3.);
\draw [line width=1.2pt] (-2.,2.)-- (2.,2.);
\draw [line width=1.2pt] (0.,3.)-- (0.,2.);
\draw [line width=1.2pt] (-1.,2.)-- (-1.,1.);
\draw [line width=1.2pt] (1.,2.)-- (1.,1.);
\begin{scriptsize}
\draw [fill=black] (-2.,2.) circle (1.5pt);
\draw [fill=black] (-1.,2.) circle (1.5pt);
\draw [fill=black] (0.,2.) circle (1.5pt);
\draw [fill=black] (1.,2.) circle (1.5pt);
\draw [fill=black] (2.,2.) circle (1.5pt);
\draw [fill=black] (-2.,3.) circle (1.5pt);
\draw [fill=black] (2.,3.) circle (1.5pt);
\draw [fill=black] (0.,3.) circle (1.5pt);
\draw [fill=black] (-2.,1.) circle (1.5pt);
\draw [fill=black] (-1.,1.) circle (1.5pt);
\draw [fill=black] (1.,1.) circle (1.5pt);
\draw [fill=black] (2.,1.) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}")
Πηγή: Σοβιετική Ένωση 1961
Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Συντονιστές: Demetres, silouan
-
Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 9010
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Το πιο κάτω σχήμα αποτελείται από 16 ευθύγραμμα τμήματα. Να αποδειχθεί ότι δεν υπάρχει καμπύλη η οποία να τέμνει κάθε τμήμα από ακριβώς μία φορά.
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
Πηγή: Σοβιετική Ένωση 1961
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
Πηγή: Σοβιετική Ένωση 1961
Λέξεις Κλειδιά:
-
Mihalis_Lambrou
- Επιμελητής
- Δημοσιεύσεις: 18246
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Πρόκειται για πάρα πολύ ωραία άσκηση. Δεν γράφω λύση γιατί την γνωρίζω ήδη αλλά θέλω μόνο να προσθέσω ότι
η άσκηση απευθυνόταν σε μαθητές Γυμνασίου. Ο Διαγωνισμός από όπου προέρχεται, είναι καταπληκτικός.
Παρακαλώ να μην γράψουν λύση όσοι την έχουν ξαναδεί (κυκλοφορεί και στην ελληνική - μεταφρασμένη - βιβλιογραφία).
η άσκηση απευθυνόταν σε μαθητές Γυμνασίου. Ο Διαγωνισμός από όπου προέρχεται, είναι καταπληκτικός.
Παρακαλώ να μην γράψουν λύση όσοι την έχουν ξαναδεί (κυκλοφορεί και στην ελληνική - μεταφρασμένη - βιβλιογραφία).
-
Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 9010
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Πράγματι έτσι είναι. Μου ζητήθηκε πρόσφατα να βάλω περισσότερες ασκήσεις συνδυαστικής. Θα αντλήσω σίγουρα πολλές από αυτόν τον διαγωνισμό. (Από εκεί άλλωστε αντλεί και ο Engel αρκετές από τις ασκήσεις του.)Mihalis_Lambrou έγραψε:Ο Διαγωνισμός από όπου προέρχεται, είναι καταπληκτικός.
Ένας άλλος διαγωνισμός με πολύ καλές ασκήσεις είναι ο tournament of the towns. Έβαλα ήδη εδώ και εδώ τις ασκήσεις από τον πρώτο διαγωνισμό αλλά ακόμη δεν υπήρξε μεγάλη ανταπόκριση.
-
Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 9010
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Βοήθεια: Ας υποθέσουμε πως υπάρχει τέτοια καμπύλη η οποία ξεκινάει από το πάνω αριστερά κουτάκι. Πρέπει να καταλήξει μέσα ή έξω από αυτό το κουτάκι;Demetres έγραψε:Το πιο κάτω σχήμα αποτελείται από 16 ευθύγραμμα τμήματα. Να αποδειχθεί ότι δεν υπάρχει καμπύλη η οποία να τέμνει κάθε τμήμα από ακριβώς μία φορά.
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
Πηγή: Σοβιετική Ένωση 1961
-
Mihalis_Lambrou
- Επιμελητής
- Δημοσιεύσεις: 18246
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Για να κλείνει η ωραία αυτή άσκηση:Demetres έγραψε:Το πιο κάτω σχήμα αποτελείται από 16 ευθύγραμμα τμήματα. Να αποδειχθεί ότι δεν υπάρχει καμπύλη η οποία να τέμνει κάθε τμήμα από ακριβώς μία φορά.
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
Μπορούμε να θεωρήσουμε ότι τα "κουτάκια" είναι δωμάτια και ότι έχουν σημειωθεί οι πόρτες που συνδέουν τα δωμάτια μεταξύ τους ή με τον εξωτερικό χώρο. Παρατηρούμε ότι μερικά από τα δωμάτια έχουν από
πόρτες (τα γαλάζια) ενώ τα υπόλοιπα (τα πράσινα) έχουν από 
. Θέλουμε μία διαδρομή που να περνά από όλες τις πόρτες, μία φορά την καθεμία.
Τα δωμάτια που έχουν
πόρτες πρέπει να είναι στην αρχή ή στο τέλος της διαδρομής διότι σε αυτά πρέπει να "μπεις και να βγεις" δύο φορές και άλλη μία για να μπεις (χωρίς να ξαναβγεις) ή το ανάποδο, δηλαδή να βγεις (χωρίς να ξαναμπείς).Όμως τα δωμάτια με τις
πόρτες είναι τρία τον αριθμό, ενώ τα άκρα της διαδρομής είναι μόνον δύο. Οπότε δεν υπάρχει διαδρομή που να περνά όλες τις πόρτες από μία φορά..
- Συνημμένα
-
- portes.png (3.93 KiB) Προβλήθηκε 4486 φορές
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Εάν θεωρήσουμε οτι το κάθε δωμάτιο είναι μία κορυφή γράφου (συμπεριλαμβάνουμε ως δωμάτιο το εξωτερικό χωρίο) και κάθε κοινή πλευρά ανάμεσα σε δωμάτια είναι μία ακμή, τότε δημιουργείται γράφος με 6 κορυφές. Η κορυφή που συμβολίζει το εξωτερικό χωρίο είναι σε επαφή με 9 ακμές, 3 κορυφές είναι σε επαφή με 5 ακμές και 2 κορυφές ειναι σε επαφή με 4 ακμές.
Το πρόβλημα είναι εάν μπορούμε ξεκινώντας απο οποιαδήποτε κορυφή να διανύσουμε όλες τις ακμές ακριβώς μία φορά. Κάθε κορυφή με περιττό πλήθος ακμών πρέπει είτε να είναι η αρχική είτε η τελική κορυφή. Εφόσον υπάρχουν 4 τέτοιες κορυφές συμπεραίνουμε οτι δεν υπάρχει λύση.
Ουσιαστικά αυτή είναι η λύση του κύριου Λάμπρου, δεν πρόσθεσα κάτι καινούριο. Απλώς παρέθεσα μία διαφορετική οπτική του προβλήματος ως γράφου.
Απο ποιόν διαγωνισμό είναι το πρόβλημα?
Το πρόβλημα είναι εάν μπορούμε ξεκινώντας απο οποιαδήποτε κορυφή να διανύσουμε όλες τις ακμές ακριβώς μία φορά. Κάθε κορυφή με περιττό πλήθος ακμών πρέπει είτε να είναι η αρχική είτε η τελική κορυφή. Εφόσον υπάρχουν 4 τέτοιες κορυφές συμπεραίνουμε οτι δεν υπάρχει λύση.
Ουσιαστικά αυτή είναι η λύση του κύριου Λάμπρου, δεν πρόσθεσα κάτι καινούριο. Απλώς παρέθεσα μία διαφορετική οπτική του προβλήματος ως γράφου.
Απο ποιόν διαγωνισμό είναι το πρόβλημα?
-
gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3523
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Ειδική περίπτωση του Θεωρήματος Euler, πρώτου ιστορικά της Θεωρίας Γράφων, που εμπνεύστηκε στην προσπάθεια του να επιλύσει το πρόβλημα των επτά γεφυρών της Καινιξβέργης (Seven Bridges of Königsberg): οι ντόπιοι προσπαθούσαν να αρχίσουν και να τελειώσουν τον περίπατο τους στην πόλη διασχίζοντας κάθε μία από τις επτά γέφυρες της ακριβώς μία φορά 
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
-
Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 9010
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Είναι από την πρώτη πανρωσική ολυμπιάδα του 1961. Μπορείτε να δείτε τα προβλήματα από το 1961 ως το 1986 στα αγγλικά εδώ.taratoris έγραψε: Απο ποιόν διαγωνισμό είναι το πρόβλημα?
Ας πούμε και τι λέει: Ένα γράφημαgbaloglou έγραψε:Ειδική περίπτωση του Θεωρήματος Euler, πρώτου ιστορικά της Θεωρίας Γράφων, που εμπνεύστηκε στην προσπάθεια του να επιλύσει το πρόβλημα των επτά γεφυρών της Καινιξβέργης (Seven Bridges of Königsberg): οι ντόπιοι προσπαθούσαν να αρχίσουν και να τελειώσουν τον περίπατο τους στην πόλη διασχίζοντας κάθε μία από τις επτά γέφυρες της ακριβώς μία φορά
έχει μονοπάτι Euler αν και μόνο το είναι συνεκτικό και έχει το πολύ δύο κορυφές περιττού βαθμού.Ορολογία:
Ουσιαστικά το «μόνο αν» έχει αποδειχθεί.
-
gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3523
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Ακριβέστερα, υπάρχει κύκλωμα Euler (που αρχίζει και τελειώνει στην ίδια κορυφή, Euler circuit) αν και μόνον αν όλες οι κορυφές είναι αρτίου βαθμού, και μονοπάτι Euler (που αρχίζει σε μία κορυφή και τελειώνει σε μιαν άλλη, Euler path) αν και μόνον αν υπάρχουν δύο ακριβώς κορυφές περιττού βαθμού (η αρχή και το τέλος του μονοπατιού).Demetres έγραψε:Είναι από την πρώτη πανρωσική ολυμπιάδα του 1961. Μπορείτε να δείτε τα προβλήματα από το 1961 ως το 1986 στα αγγλικά εδώ.taratoris έγραψε: Απο ποιόν διαγωνισμό είναι το πρόβλημα?
Ας πούμε και τι λέει: Ένα γράφημαgbaloglou έγραψε:Ειδική περίπτωση του Θεωρήματος Euler, πρώτου ιστορικά της Θεωρίας Γράφων, που εμπνεύστηκε στην προσπάθεια του να επιλύσει το πρόβλημα των επτά γεφυρών της Καινιξβέργης (Seven Bridges of Königsberg): οι ντόπιοι προσπαθούσαν να αρχίσουν και να τελειώσουν τον περίπατο τους στην πόλη διασχίζοντας κάθε μία από τις επτά γέφυρες της ακριβώς μία φορά
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης