THMMY.gr

Εδώ μπορείτε να σχολιάζετε τα θέματα και
να συζητάτε τις όποιες απορίες σας πάνω σε παλιά θέματα των
Διακριτών Μαθηματικών.
(Τα παλιά θέματα υπάρχουν εδώ (http://www.thmmy.gr/smf/index.php?action=tpmod;dl=cat713)).

Μην αναζητείτε και μην ανεβάζετε παλιά θέματα και σημειώσεις εδώ.
Χρησιμοποιείστε τον τομέα Downloads που φτιάχτηκε για αυτόν το σκοπό.
Έτσι βοηθάτε στην καλύτερη κατηγοριοποίησή τους
και στην διευκόλυνση της εύρεσής τους.

Για τα Διακριτά Μαθηματικά μπορείτε να βρείτε παλιά θέματα ή να ανεβάσετε νέα εδώ (http://www.thmmy.gr/smf/index.php?action=tpmod;dl=cat713).

Σχόλια ή απορίες πάνω στα παλιά θέματα των Διακριτών Μαθηματικών, μπορούν να διατυπωθούν εδώ (http://www.thmmy.gr/smf/index.php?topic=1880.msg11472#msg11472).

Αν κάποιος έδωσε το μάθημα τον Ιανουάριο, είναι εύκολο να αναρτήσει τα θέματα?
Έστω κι αν αυτό δεν είναι δυνατό, αν κάποιος θυμάται, ας μας πει περίπου τι έπεσε.
Ευχαριστώ

Το μαθημα το δωσαμε Ιουνιο.Εβαλε 2 ασκησεις με γραφηματα(βασικα πραματα απο τη θεωρια τους).Μια ασκηση με δεντρο.Απο τις σημειωσεις αν διαβασεις τις ελυνες αυτες ανετα.Η 4 και τελευταια ασκηση υποψιαζομαι οτι ητανε με γεννητριες συναρτησεις.Σου ζητουσε κατι συνδυασμους κτλ.Πολυ γενικα αυτα που θυμαμαι βεβαια αλλα το μαθημα περνιεται ευκολα και με κανα 7ρακι ας ειναι καλα ο "θεος" πιτσουλης.Btw οταν εδινα εγω μονο σε γυναικες απαντουσε σε ερωτησεις...

Λιγο αργά βέβαια αλλα οποιος μπορει με σώζει :)

Ποια ειναι η λύση στο τεταρτο θέμα εξετάσεων του 2005?

Θεμα 4 :

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

Να βρεθούν πόσες είναι οι διαφορετικές διατάξεις που μπορούν να δώσουν και οι τρεις κριτές μαζι.

Σε πόσες απο αυτές ο κος Πιτσουλης προσλαμβανεται??

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

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

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

Στα λέω αυτά για να μην αγχώνεσαι... Αν δεν ξέρεις κάτι στίψε λίγο το μυαλό σου και θα βρεις λύση  ;)

Απλώς βλέπω ότι αρκετές ασκήσεις είναι από λίγο εως πολύ περίεργες χωρίς να μπορεί να βγει κάποια μεθοδολογία κτλ!!! Αυτές που μπαίνουν βγαίνουν ή πρέπει να έχεις φοβερή εκοικίωση με ατού του τύπου τις ασκήσεις?
Το 3ο θέμα στο πολύ περίπου?

Τα θέματα της Α' Περιόδου βρίσκονται στο υλικό του μαθήματος εδώ (http://www.thmmy.gr/smf/index.php?action=tpmod;dl=cat713).

Μια ερώτηση στο 3ο θέμα εννοεί δένδρο ελάχιστου βάρους ή κάτι άλλο? Πώς λύνεται αυτό το πράγμα?

Δεν ξέρω κατά πόσο αυτό που λέω είναι σωστό, αλλά έστω w(T) το άθροισμα των βαρών του ελάχιστου δένδρου. Τότε είναι w(T)<a,b,c... όλων των άλλων πιθανών δένδρων. Αν τώρα διπλασιάσουμε κάθε βάρος, τότε θα έχουμε τελικά για το "πρώην" ελάχιστο w(T')=2xw(T), ενώ για τα υπόλοιπα πιθανά δένδρα θα έχουμε ομοίως διπλασιασμό των αθροισμάτων! οπότε w(T')<2a,2b,2c κοκ! Άρα το ελάχιστο δένδρο παραμένει ελάχιστο και μετά τον διπλασιασμό των βαρών του. Όσο για το 2ο σκέλος δεν είμαι 100%σίγουρος αλλά μάλλον προκύπτει ομοίως το ίδιο! Αυτά με κάθε επιφύλαξη, αν κάποιος ξέρει στα σίγουρα ας μας πει να μας βοηθήσει!

Για το 2ο θέμα τώρα, έχουμε E<=3xV-6 από τον τύπο για να είναι ένας γράφος επίπεδος! Επίσης, Σd(i)=2xE, ενώ αφού μας ζητάει έναν 4-κανονικό γράφο έχω 4xV=2xE=> E=2xV αντικαθιστώ στον πρώτο τύπο και θα έχω 2xV<=3xV-6 => V>=6, άρα ο ελάχιστος αριθμός κορυφών για να έχω επίπεδο, απλό 4-κανονικό γράφο είναι 6! Μάλλον σωστό ειναι αυτό, πάλι με κάθε επιφύλαξη όμως! Ελπίζω να βοήθησα, αν κάποιος είναι σίγουρος για κάτι, περιμένω διορθώσεις!

Άρα σαν ελάχιστο δένδρο εννοεί αυτό με το ελάχιστο βάρος? Άμα ισχύει αυτό τότε και εμένα αυτό μου φαίνεται σωστό και στις δύο περιπτώσεις να είναι το ίδιο

Όσο για το 2ο θέμα έτσι ακριβώς λύνεται. Άμα θέλεις σχεδίασε το κιόλας με λιγότερο από 6 κορυφές δεν γίνεται.

Για το 3ο θέμα:

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

Για το 2ο θέμα:

Η παραπάνω λύση είναι πολύ απλή και μάλλον είναι σωστή, αλλά δυστυχώς την σκέφτηκα μετά το πέρας της εξέτασης.. :(. Συνδυάζεις δυο τύπους και έχεις την απάντηση μέσα σε 2 γραμμές!! :o

Εγώ εδωσα μια άλλη λύση. Πρώτα εξήγησα ότι χρειάζονται τουλάχιστον 5 κορυφές (αφου κάθε κορυφή έχει βαθμό 4).
Μετά σχεδίασα γράφο με 5 κορυφές τον μεγιστοτικό στην ιδιότητα "απλός και επίπεδος". Αυτός ο γράφος δεν μπορεί να έχει όλες τις κορυφές με βαθμό 4, δυο κορυφές θα έχουν βαθμό 3. Και επειδή είναι μεγιστοτικός(maximal) σ'αυτήν την ιδιότητα, δεν υπάρχει ούτε άλλος γράφος 5ης τάξης με όλες τις κορυφές του με βαθμό 4.
Στη συνέχεια κατασκεύασα έναν ζητούμενο γράφο(ζητούσε και να σχεδιαστεί!) με 6 κορυφές. Αποδείξαμε ότι μπορούμε να τον κατασκευάσουμε, άρα αποδείξαμε ότι υπάρχει! ;)
(Είναι τρόπος απόδειξης και αυτός. Τον χρησιμοποιεί στην απόδειξη κάποιου θεωρήματος στις σημειώσεις.)

στο θεμα ιουνιου 2005 το 4ο θεμα ποια ειναι η λυση?? μηπως C(9,3)*C(8,2)*C(7,1)???
και στο 2ο 8εμα τι θελει?



το 2006 ολοκληρο οποιος το ξερει...φως επειγοντως

καμια ιδεα ρε παιδια???!!!

Ιούνιος 2005 θέμα4

Κάθε κριτής έχει 9! διαφορετικές δυνατές διατάξεις. Άρα συνολικά (9!^)3 αν έχει σημασία ποιος κριτής κάνει την κάθε διάταξη, αλλιώς (9!)^3/6, αν δεν ξεχωρίζουν οι κριτές μεταξύ τους

Ο Πιτσούλης προσλαμβάνεται σε (3!)^3 (ή (3!)^3/6 αντίστοιχα) από αυτές
Δεν είναι ξεκάθαρο αν έχει σημασία ποιος κριτής δίνει την κάθε διάταξη ή όχι.

γιατο θεμα με τους βουλευτες το 2007 η λυση ειναι C(16,4)??τα υπολοιπα με τους γραφους καμια ιδεα?

Τώρα που βρήκα περισσότερο χρόνο...

Για το 2ο του Ιουνίου 2005:
Επαγώμενος υπογράφος αν δεν κάνω λάθος σημαίνει ότι περιέχει ορισμένες κορυφές του αρχικού γράφου, αλλά όλες τις ακμές μεταξύ αυτών των κορυφών. 4-κανονικός σημαίνει ότι όλες οι κορυφές του έχουν 4 ακμές.
Δηλαδή πρέπει απλά να προσθέσεις κάποιες κορυφές στο γράφο G και μερικές ακμές ώστε να πάρεις τον H 4-κανονικό γράφο. Δεν επιτρέπεται όμως να προσθέσεις ακμές μεταξύ δύο κορυφών που υπάρχουν και οι δύο στον G γράφο.

Στο θέμα με τους βουλευτές, τοποθετούμε καταρχήν ένα βουλευτή σε κάθε επιτροπή. Έχουμε 20 επιλογές για την πρώτη, 19 για τη δεύτερη, 18 για την τρίτη, 17 για την τέταρτη. Τώρα οι υπόλοιποι 16 μπορούν να τοποθετηθούν οπουδήποτε. Ο καθένας έχει 4 επιλογές, άρα 4^16 δυνατές επιλογές. Άρα 20*19*28*17*4^16 συνολικοί τρόποι να τοποθετηθούν.

Για το 2006: Πρώτο θέμα: Το Α εμφανίζεται τουλάχιστον 2 φορές, τα υπόλοιπα τουλάχιστον μία. Άρα με 3 γράμματα δε γίνεται καμιά συμβολοσειρά.
Για μήκος 4, επιέγουμε μία από τις 4 θέσεις για το Β, μία από τις υπόλοιπες 3 θέσεις για το Γ και τα Α μπαίνουν αναγκαστικά στις δύο θέσεις που μένουν, άρα συνολικά 3*4=12 τρόποι.
Για μήκος 5, καταρχήν παρατηρούμε ότι δεν μπορούμε να έχουμε 2 Γ, αλλά ούτε και 3 Α. Επομένως θα έχουμε 2 Α, 2 Β και 1 Γ. Καταρχήν θεωρούμε ότι τα 2 Α διαφέρουν και τα 2 Β επίσης. Τα συμβολίζουμε με κεφαλαία Α,Β και μικρά α,β. Με αυτά τα 5 διαφορετικά γράμματα παίρνουμε 5! διαφορετικές συμβολοσειρές. Όμως στην πραγματικότητα τα α και Α μπορούν να αντιμετατεθούν, όπως και τα β και Β. Άρα ανά 4 συμβολοσειρές είναι στην πραγματικότητα ίδιες. (πχ αΓΑβΒ = ΑΓαβΒ = αΓΑΒβ = ΑΓαΒβ). Άρα οι διαφορετικές συμβολοσειρές είναι 5!/4 = 30.

Θέμα 2: Προφανώς θα είναι n>=5. Αλλά με 5 κορυφές δε γίνεται. γιατί θα περιέχει σαν υπογράφο έναν από τους γράφους Kuratowski (ή κάπως έτσι) που δεν είναι επίπεδοι. Άρα n>=6. Δοκιμάζουμε να σχεδιάσουμε και βλέπουμε ότι όντως γίνεται με 6.

Θέμα 3: Με εις άτοπον απαγωγή. Αυτό το δέντρο είχε αρχικά βάρος Β και μετά το διπλασιασμό των βαρών είχε βάρος 2Β. Έστω ότι υπάρχει άλλο δέντρο με βάρος μικρότερο από 2Β, έστω 2Β'. Άρα πριν το διπλασιασμό θα είχε Β' < Β. Άτοπο, αντίκειται στην υπόθεση ότι το δέντρο ήταν ελάχιστο αρχικά.
Το ίδιο θα ισχύει και αν προσθέσουμε ένα σταθερό αριθμό c στο βάρος κάθε ακμής. Το στοιχείο κλειδί είναι ότι όλα τα δέντρα έχουν ίδιο αριθμό ακμών, άρα το ίδιο βάρος θα προστεθεί σε οποιοδήποτε δέντρο.
Από Β θα γίνει Β+n*c όπου n ο αριθμός των ακμών. Αν υπάρχει άλλο με μικρότερο βάρος, έστω B'+n*c, θα πρέπει το αρχικό του βάρος να ήταν B', αλλά από Β+n*c > B'+n*c προκύπτει πάλι ότι Β > Β', άτοπο.

Αυτά...

αφου πηρεσ φορα μν σταματας...δες και τα υπολοιπα...!!!

επιβεβαιώνει κανείς τα παρακάτω αποτελέσματα για τα πρώτα θέματα Ιουνίου-Σεπτεμ. 2007??

1ο Θ Ιούνιος 2007:     20! / n1!*n2!*n3!*n4!   όπου n1...οι βουλευτές σε κάθε επιτροπή

1ο Θ Σεπ 2007:    2520 διαφορετικές μεταθέσεις

Σόρρυ Άκη, έχω να διαβάσω και Οπτική! Δίνω την ίδια μέρα

ok!!πλακα εκανα...θενξ ε λοτ

To 1o Θ Ιουνίου 2007 με τους βουλευτές έχει λυθεί πιο πάνω απ'τον Junior.
Όσο για το Θ Σεπτεμβρίου ναι και γω αυτό το αποτέλεσμα βρήκα

πειτε κ πως το βγαλατε ρε παιδες

Η λέξη ΠΑΡΑΠΟΝΑ αποτελείται από 8 γράμματα και συγκεκριμένα από 2Π, 3Α, 1Ρ, 1Ο και 1Ν. Ο αριθμός των διαφορετικών μεταθέσεων των γραμμάτων της λέξης χωρίς κανέναν περιορισμό είναι 8!/(2!*3!*1!*1!*1!)=3360.
Τώρα βρίσκουμε τον αριθμό των διαφορετικών μεταθέσεων στις οποίες τα δύο Π ΕΙΝΑΙ σε  διαδοχικές θέσει θεωρώντας το ΠΠ σαν ένα αντικείμενο. Έχουμε 7!/(3!*1!*1!*1!) =840
Άρα η τελική απάντηση είναι 3360-840=2520

thnx.εκανα λαθος στον αριθμο των γραμματων ο καραγκιοζης...κανα αλλο θεμα λυεσατε εκτος απο αυτα π ελυσε ο junior?

νομιζω πως οι δυνατες επιλογες για τους υπολοιπους 16 ειναι C(16+4-1,4)καθως ειναι αντιστοιχο με την τοποθετηση 16 μπαλων του ιδιου χρωματος(16 βουλευτες) σε 4 κουτια(=επιτροπες)......



τον παρονομαστη γιατι 6??




                                                                                                                                                         
ιουνιος 2007 2.b)θεωρημα γραφων:k1*n=2*e1 & k2*n=2*e2 (ιδιο n γιατι ειναι συμπληρωματικοι).ετσι
         _
ειναι:dG(V)=|V(G)|-1-dG(V)=>k2=n-1-k1=>n^2-n=2(e2-e1) μετα τι??....επειδη λεει δενδρα μηπως e2=e1 οποτε n=0 ή n=1 και δεχομαστε μονο την n=1???αλλα τι δεντρο ειναι αυτο??!!!ουτε κλωναρι δεν ειναι!!!


ιουνιος 2007 αυτο για χρωματισμους.....????

Παίδες για τα θέματα 2007 Σεπτεμβρίου για τους χρωματικούς αριθμούς έχει κανείς καμιά ιδέα? ^beg^
 δεν μπορώ να το βγάλω με τίποτα............. :(

τα υπολοιπα δηλ θεματα τα ελυσες??αν ναι δωσε τα φωτα σου....

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

Στο άλλο πρόβλημα που διαιρώ με 6: Αν δεν έχει σημασία ποιος κριτής κάνει ποια διάταξη, τότε, μετρώντας όλες τις δυνατές τριάδες διατάξεων, κάθε τριάδα προσμετράται 6 φορές. Είναι σαν να ανταλλάζουμε τις διατάξεις μεταξύ των κριτών. Γενικά 3 αντικείμενα μπορούν να μοιραστούν σε 3 ανθρώπους με 3!=6 τρόπους (1 στον καθένα εννοείται).

το 2ο το καταλαβα.θενξ.τωρα οσο για το πρωτο αφου μας ενδιαφερει η διαταξη τοτε εχουμε μεταθεση και οχι συνδυασμο....αλλα τοτε οντως 4^16 πρεπει να ειναι σωστο....

Ναι, το λάθος βρίσκεται αλλού: Μπορεί ένας βουλευτής να τοποθετηθεί σε μια ομάδα κατά την αρχική τοποθέτηση 4 βουλευτών ή μπορεί να τοποθετηθεί στην ίδια ομάδα κατά την τοποθέτηση των 16. Έτσι μετράμε την ίδια λύση πάνω από μία φορά :S
Νομίζω ότι πρέπει να αλλάξουμε αρκετά την προσέγγιση.
πχ: Οι δυνατές τοποθετήσεις των 20 βουλευτών είναι 4^20. Από αυτές εξαιρούμε όσες αφήνουν έστω και μια ομάδα άδεια. Αν μετρήσουμε τους τρόπους να μείνει άδεια η κάθε ομάδα, τότε μερικές περιπτώσεις θα τις έχουμε μετρήσει 2 φορές, αφού μπορεί ταυτόχρονα να μένουν άδειες 2 ή περισσότερες ομάδες. Πρέπει να αντρέξουμε λίγο στη θεωρία...
Αν Α είναι το ενδεχόμενο να μένει η πρώτη ομάδα άδεια και Β, Γ, Δ αντίστοιχα για τις άλλες, τότε ψάχνουμε το |ΑUBUΓUΔ|
Σύμφωνα με αρχή του εγκλεισμού και αποκλεισμού (βιβλίο παράγραφος 1.6, δε θυμάμαι αν το έχουν οι σημειώσεις) που στην ουσία λέει ότι όταν ενώνουμε δύο σύνολα πρέπει να αφαιρούμε τα στοιχεία που βάλαμε δύο φορές κλπ, έχουμε (με U σημειώνω την ένωση συνόλων και με Π την τομή):
|ΑUBUΓUΔ| = |Α| + |Β| + |Γ| + |Δ| - |ΑΠB| - |ΑΠΓ| - |ΑΠΔ| - |ΒΠΓ| - |ΒΠΔ| - |ΓΠΔ| + |ΑΠΒΠΓ| + |ΑΠΒΠΔ|+ |ΑΠΓΠΔ| + |ΒΠΓΠΔ| - |ΑΠΒΠΓΠΔ|
Λόγω συμμετρίας, γίνεται |ΑUBUΓUΔ| = 4|Α| - 6|ΑΠB| + 4 |ΑΠΒΠΓ| - |ΑΠΒΠΓΠΔ|
Το |Α| είναι οι τρόποι να μείνει άδεια η μία ομάδα. Αυτοί είναι 3^20, αφού πρέπει να τοποθετήσουμε 20 βουλευτές σε 3 ομάδες. Το |ΑΠB| είναι να μείνουν άδειες ταυτόχρονα δύο ομάδες και είναι 2^20, αντίστοιχα |ΑΠΒΠΓ| = 1^20 =1 και |ΑΠΒΠΓΠΔ| = 0.
Όλο το αποτέλεσμα του |ΑUBUΓUΔ| το αφαιρούμε από το 4^20 και τελειώσαμε.

Καταλαβαίνει κάποιος τι ζητάει (ο ποιητής->Πιτσούλης) στο 3ο θέμα Ιουνίου 2005??
 :???:

Ναι :P

...Για δώσε μου τα φώτα σου λοιπόν :P

Φαντάζομαι ότι είναι κάτι όπως στη σελ.9 των σημειώσεων Γράφοι-Ριζωμένα Δέντρα
Δημιουργείς όλα τα διατεταγμένα ζεύγη και αντιστοιχείς καθένα σ' ένα μονοπάτι ρίζας-φύλλου

Χμμ...οπότε η λύση θα είναι κάτι τέτοιο??
         r
        /\
      a   b
     / | \
    1 2 3
   /\  /\   /\
  + - + - + -

(όπου υποδένδρο του b ίδιο με αυτό του a)

Ναι!

Α, εύκολο τότε :P

Ευχαριστώωωωω! (κ εσύ του ξενυχτιού είσαι βλέπω τελικά...)

Τίποτα :)
Ναι άσε και να πεις ότι διαβάζω...
μ@#$%ζομαι

ρε μπιορκ γιατι δεν ηρθες?το 3αρι ηταν ευκολο αλλα εκανα πατατα και στο τελος εκανα μια αχρειαστη αφαιρεση...ειδωμεν αι βουλαι του κυριου...

Το 3άρι ήταν εύκολο, το 5άρι όμως?
Αν και είχα διαβάσει λίγο θα ερχόμουν, αλλά μου βγήκε κούραση και δεν την πάλευα...
Και σας είχα γνωρίσει τους περισσότερους, θα ήμασταν μια ωραία παρέα  :D






εδιτ: αν πήρε κάποιος τα θέματα ας τ' ανεβάσει

Τα έχω εγώ, αλλά δεν έχω σκάννερ για να τα ανεβάσω...αν θες μπορώ να στα δώσω όμως κάποια στιγμή  :)

Ξέρει κάποιος τι είναι ο χρωματικός αριθμός? Υπάρχει στις σημειώσεις?

 :)

|
|
v

Thanks!

ρε παιδιά τα θέματα δε δοκίμασα να τα λύσω αλλά οι σημειώσεις με κάνουν να έχω.. πονοκέφαλο :( Ή λύνονται ως δια μαγείας όλες οι απορίες στα δέντρα ( που δεν έφτασα ακόμα) ή κάτι δεν πάει καλά...!

Αποριες

Θεμα 1 Ιουνιος 2005

πως βρισκουμε ολα τα γεννητορικα δενδρα του G??

Στις σημειωσεις εχει δυο αλγορι8μους την διασχιση κατα πλατος και κατα βα8ος
αρα θα ειναι δυο τα γεννητορικα δενδρα(παντα)???


Θέμα 2 Ιουνιος 2007 :
α) Θεωρούμε απλό επίπεδο γράφημα του οποίου όλες οι κορυφές έχουν βαθμό 4. Ποιος είναι ο ελάχιστος αριθμός κορυφών ενός τέτοιου γραφήματος;(η απαντηση οκ ειναι 6) Να σχεδιάσετε ένα τέτοιο γράφημα.

ολα τα γραφηματα που σχεδιαζω με αυτο το κριτηριο μου θυμιζουν τα γραφηματα Kuratowski οποτε κατι κανω λα8ος μπορει καποιος να κανει ενα σχημα που απαντα στο ερωτημα??

β)Πόσες κορυφές μπορεί να έχει ένα γράφημα που έιναι ίσο με το συμπληρωματικό του αν είναι δένδρο; Να σχεδιάσετε όλα τα γραφήματα που είναι ίσα με το συμπληρωματικό τους και είναι δένδρα

Αυτο δεν το πιασα κα8ολου.... οποτε ειναι ολο μια απορια

Θεμα 2 Σεπτεμβριου 2007
τι ειναι τουτο?? που ειναι στις σημειωσεις ο χρωματικος βα8μος??

επισης ολο μια απορια αυτο το θεμα...

Οπως και τα θεματα 2 και 3 του Ιουνιου 2008


καθε βοηθεια δεκτη....

οι αλγοριθμοι δεν σου δινουν διαφορετικα δεντρα. σου δινουν απλα καποια δεντρα.
και οχι δεν ειναι παντα δυο.

το γραφημα θα πρεπει να εχει e=[n*(n-1)]/4 ακμες για να ειναι ισο με το συμπληρωματικο του.
και επειδη ειναι δεντρο πρεπει e=n-1(?)
(η ισως να πρεπει να ισχυει e>=3n-6)


για το δυο, αν υποθεσεις οτι δυο κορυφες δεν συνδεονται μεταξυ τους,
ουτε συνδεονται με καποια κοινη κορυφη τοτε συνολικα θα πρεπει να υπαρχουν
[ν-1]/2 + [ν-1]/2 +2 κορυφες=ν+1 κορυφες, που ακουγεται μαλακια.
οποτε ειτε ειναι συνδεδεμενες μεταξυ τους, ειτε ειναι συνδεδεμενες με κοινη κορυφη.
win.

ούτε κι εγώ την είχα παλέψει με αυτές τις σημειώσεις τότε.. :(

κάτι πρωτοβάθμιες γλώσσες κλπ που λέει στο τέλος των σημειώσεων είναι κι αυτά μέσα? γιατί αν κατάλαβα καλά τα θέματα είναι πιθανότητες & γράφοι / δέντρα μέχρι στιγμής...

αυτο νομιζω ειναι το σχημα του 2ου θεματος του Ιουνιου 2005

Θέμα 2 Ιουνιος 2007

α)..για επίπεδο γραφημα ισχύει α<=3κ-6 <=>  κ>=(α+6)/3

Επίσης ισχύει άθροισμα βαθμών όλων κορυφών=2*α,άρα κ*4=2α,λύνουξμε τη πρώτη εξ΄'ισωση ως προς κ και βρίσκουμε κmin=6

παρατίθεται και το σχήμα

b)Ισχύει ότι το δένδρο θα έχει v κορyφές και v-1 ακμές,άρα και το συμπληρωματικό του θα έχει ν κορυφές και ν-1 ακμές

Ισ΄χυει για το αρχικό μας δένδρο Σδ=2*(ν-1)   όπου  δ ο βαθμός ΄καθε μιας κορυφής

επίσης για το συμπληρωματικό έιναι  Σδ'=2*(ν-1) όπου δ' ο βαθμός μιας κορυφής στο συμπληρωματικό δένδρο...Ισχύει όμως

δ'=ν-1-δ...Αρα Σδ'=2*(ν-1) <=> Σ(ν-1-δ)=2*(ν-1)<=Σν -Σ1-Σδ=2(ν-1) <=> ν^2 - ν -2(ν-1)=2(ν-1)  <=>  ν^2-5ν+4=0

και βγάζουμε ν=4 και ν=1

^^DaRk_HunTeR κι εγώ κάπως έτσι το σκέφτηκα το σχήμα, αλλά ακολούθησες κάποιο τρόπο για να το βρείς? ή προσπαθώντας και ό,τι βγει?

Επίσης τελικά ο χρωματικός αριθμός ΤΙ ΣΤΗΝ ΕΥΧΗ ΕΙΝΑΙ?

αμα βαλει πρωτοβαθμιες γλωσσες
θα του προκαλεσω εκαυματα τριτου βαθμου.

@Θανος  προσπα8ησα και οτι βγει....  εβαλα φαντασια :P

μαλακα Πασχαλη ξερω εγω γλωσσες βαλε εσυ τα αλλα και ειμαστε τζι τζι :D

Ανεβασα τα θεματα 2009...στα νταουνλοαντς

Ενα θα πω μεσος ορος του μα8ηματος φετος ηταν 7,7 
δωσαν 37 ατομα και κοπηκαν 6
οποιος δεν το παρει ως επιλογης απλα ειναι τρομπας...

Να ναι καλα ο σοφος δασκαλος :P

Ναι όντως σε σχέση με την απάλευτη μετάδοση θερμότητας που κάποιοι ενεργειακοί προμοτάρουν σαν εύκολο.. αυτό είναι πολύ πιο εύκολο μάθημα..!
(και πιο ενδιαφέρον... ακους εκεί εναλλάκτες θερμότητας μπρρρρ)

Στα θέματα Ιουνίου 2009:
(2)
(α) Δείξτε ότι έαν ένα απλό γράφημα έχει κύκλο Hamilton, τότε δεν μπορεί να περιέχει γέφυρα.
Ισχύει αυτό εάν έχει κύκλο Euler?
(β) Δείξτε ότι το συμπληρωματικό κάθε απλού μη συνδεόμενου γραφήματος είναι συνδεόμενο.

Καμία ιδέα;

(α) Είναι τόσο απλό όσο το σκέφτομαι; Εφόσον έχει γέφυρα, δεν μπορώ να επιστρέψω στην αρχική κορυφή χωρίς να διασχίσω και πάλι τη γέφυρα;
(β)"συνδεόμενο" means?

Ναι ειναι τοσο απλο... βγαινει απο τον ορισμο του κυκλου euler και του κυκλου Hamilton.
 
Συνδεομενο η Συνεκτικο ονομαζεται ενα μη κατευ8υνομενο γραφημα αν υπαρχει μονοπατι μεταξυ καθε δυο κορυφων(σελ 180 βιβλιο)

γενικα τα θεματα ηταν τρομακτικα εκ 1ης οψεως, αλλα βγαιναν ολα απο τους ορισμους των εννοιων,με λιγα λογια γραψαμε εκ8εσεις :P

Για Euler ισχύει ή όχι;

ναι προφανως an Eulerian path is a path in a graph which visits each edge exactly once
δεν μπορει να περιεχει γεφυρα γιατι θα περασει δυο φορες απο τις κορυφες που αποτελουν τη "γεφυρα".

ευχαριστώ πολύ Dark ;)

μπορεί κάποιος να πει πως λυνόταν το 2β και 3β των θεμάτων ιουνίου??

Έχω 2 λύσεις στο μυαλό μου για το 1)β του Ιουνη 2009 αλλά δε μπορώ να φανταστώ ποιά είναι η σωστή!

Α λύση.
Από το α έχουμε βρεί ότι οι πιθανές μεταθέσεις με 16 φορές επανάλληψη του Ο είναι 20!/16!=116280
Εάν θεωρήσουμε 2 Ο σταθερά στην αρχή και στο τέλος θα έχουμε ενδιάμεσα το ίδιο πρόβλημα με πρίν μόνο που έχουμε 18 θέσεις με 14 επαναλήψεις του Ο δηλαδή 18!/14!=73440 μεταθέσεις. Εάν αφαιρέσουμε αυτές από όλες τις δυνατές μεταθέσεις έχουμε 116280-73440=42840 πιθανές μεταθέσεις.

Β λύση.
Αν θεωρήσουμε ότι έχουμε ένα από τα Α,Β,Γ,Δ στην αρχή και ένα στο τέλος, οι πιθανές μεταθέσεις τους (Αρχή-Τελος) είναι 12 (Α-Β,Α-Γ,Α-Δ,Β-Α,Β-Γ,Β-Δ,Γ-Α,Γ-Β,Γ-Δ,Δ-Α,Δ-Β,Δ-Γ)
Για κάθε μία από αυτές θεωρούμε ότι ενδιάμεσα έχουμε τα υπόλοιπα δύο γράμματα από τα Α,Β,Γ,Δ που απομένουν και 16 Ο δηλαδή συνολικα 18 θέσεις. Οι πιθανές μεταθέσεις είναι 18!/16!=306. Δηλαδή έχουμε 306 μεταθέσεις στο εσωτερικό για κάθε μία από τις 12 μεταθέσεις των 2 γραμμάτων που βρίσκονται στα άκρα. Άρα 12*306=3672 μεταθέσεις.

Τελευταία φορά που έλεγξα, 42840≠3672. Που την κάνω τη μαλακία;

EDIT:
Εντάξει το βρήκα. Στην Α λύση είναι το λάθος καθώς δεν πρέπει να αφαιρέσω μόνο τις περιπτώσεις με Ο στην αρχή και στο τέλος. Πρέπει να αφαιρεθούν και οι περιπτώσει με Ο μόνο στην αρχή ή μόνο στο τέλος (2x) και όλες οι παραπάνω για κάθε ένα απο τα Α,Β,Γ,Δ (4x). Με λίγα λόγια, εκτός από τις 42840 μεταθέσεις για στάνταρ Ο στα άκρα πρέπει να αφαιρεθούν και οι (18!/15!)*2*4=39168 που αφορούν μόνο ένα Ο στην αρχή ή στο τέλος. Έτσι παίρνουμε και πάλι 3672 μεταθέσεις.

Για το 2β δες το συνημμένο στην 6η σελίδα (κόκκινα γράμματα). :)

Για το 3β δεν ξέρω. :(
Επίσης αν μπορεί κάποιος να δώσει λύση στο θέμα 2 και 3 του Ιούνη 2008, και Σεπτέμβρη 2007 (χρωματικός αριθμός) plz!!!!

ναι γενικα οποιος μπορει να πει εστω και δυο λογια για το πως βγαινουν τα θεματα 2008 και 2009..

οσο για τον χρωματικο αριθμο ειδα ενα βιβλιο στην βιβλιοθηκη των ηλεκτρολογων που κατι λεει αλλα δεν το'χω διαβασει ακομα :P

Ρε παιδια δεν ειπε ο Πιτσουλης οτι θα βαλει απο τις λυμενες ασηκσεις του ethmmy? Λαθος καταλαβα?

Ναι ετσι είπε

E τοτε γτ ¨κωλοτρωγονται¨ με τα παλια θεματα αφου ξερουν τα "θεματα¨"?

ela mou nte

πιστευω οτι κανεις λαθος εδω.. δεν μας πειραζει δεν πα να περασει και 100 φορες απο μια κορυφη.. αφτο που μας ενοχλει ειναι να περασει πανω απο μια ακμη πανω απο 1 φορες.. οποτε μπορει να περιεχει eulerian path.. hamilton ομως δεν μπορει. δοκιμασε το με ενα απλο γραφο με γεφυρα

και επισης το θεμα 1 ιουνιου 2008, αν και λυνεται με περιεργο τροπο στις σημειωσεις δεν μπορουμε να το λυσουμε και περνωντας τα 000 σαν ενα γραμμα?

και κατι τελευταιο μπορει καποιος να μου πει πως βρισκω επαγωμενους υπογραφους?? ειλικρινα δεν εχω καταλαβει.. :'(

δεν κανω λαθος...
το θεμα σωστα το χα λυσει οταν το ειχα περασει,

Ξανασκεψου τι ειναι γεφυρα... και μετα θα καταλαβεις οτι εχω δικιο

Διαδρομή= ακολουθία κορυφών και ακμών ενός γράφου
μονοπάτι= διαδρομή με διακριτές κορυφές
μονοπάτι Euler= μονοπάτι με διακριτές ακμές

.--.--.--.

αν αυτό που σχεδίασα από πάνω είναι γράφος με 4 κορυφές και 3 ακμές,  τότε ο ίδιος ο γράφος είναι και το μονοπάτι Euler. Και κάθε του ακμή επίσης, είναι γέφυρα.

ΥΓ. Το μονοπάτι που έχει την ίδια κορυφή για αρχή και τέλος είναι  "κύκλος"

κατσε δεν μπορω να καταλαβω ισως τοτε τι σημαινει γεφυρα.. γραφος με γεφυρα δεν ειναι ενας γραφος για παραδειγμα που ειναι σαν 2 τετραγωνα που ενωνονται σε 2 κορυφες τους με μια ακμη? λεω παραδειγμα τωρα..

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

τι να πω εγω ετσι πως το βρισκω βλεπω οτι εχει κυκλο euler..εκτος κ αν τ παιδι ειναι σιγουρο απολυτως.. αλλα χωρις σχηματα εδω τι να πουμε :D
καλη επιτυχια αυριο σε οσους δινουν διακριτα.. μακαρι να μην βαλει περιεργα θεματα.. :-\

κύκλο ή μονοπάτι ψάχνεις;

κυκλο..

Δεν υπάρχουν γέφυρες σε κύκλο. Οποιαδήποτε ακμή του κύκλου και να διαγράψεις, το υπόλοιπο παραμένει συνεκτικό.

Δίνουμε με ανοιχτά βιβλία ή όλα κλειστα;

κλειστα απ'οτι θυμαμαι

Οκτώβριος 2013-Θέμα 1

α) P(400,250) / 80!*100!*70!
250 φοιτητές,400 ΔΙΑΚΡΙΤΕΣ Θέσεις

β) P(100,100)/100!(=1) * [ 3*P(100,80)*P(200,70) / (80!70!)  + 3*P(100,70)*P(200,80) / (80!70!) ]

P(100,100)/100! (=1)για τους Β στο Ω
Οι υπόλοιποι σε 3->Λογω διαχωρισμού θα πάνε σε 1 η 2 αμφιθέατρα κάθε έτος.(3+3=6 συνδυασμοί)
Αρα 3*P(100,80)*P(200,70) + 3*P(100,70)*P(200,80)
 Όλο /80!70!

Κάνουμε / 80!70! επειδή θεωρούμε πως μεταθέσεις θέσεων από φοιτητές του ίδιου έτους δεν παίζουν ρόλο..
Αν το έχει κάνει κανείς ας πει αν συμφωνεί ή διαφωνεί να το διορθώσω αν είναι...

**Τα απότελέσματα βγαίνουν πολύ μεγάλοι αριθμοί...

Εγινε εδιτ μετά από βοήθεια συμφοιτήτριας...

Οκτώβριος 2013-Θέμα 2
Με μεγάλη επιφύλαξη..
To γράφημα του σχήματος έχει 10 κορυφές.
Ο πλήρης γράφος Κ10, μόνο και μόνο επειδή είναι πλήρης θα εμπεριέχει όλους του πιθανούς συνδυασμούς
των ισόμορφων υπογράφων.Θα υπάρχει λοιπόν κάθε πιθανή αντιστοιχία 10 από 10 (Διακριτές κορυφές αρα nPr) ..
αρα

α) P(10,10)=3628800

β)Για τον K20 παρόμοια θα ισχύει P(20,10)

Εγινε εδιτ μετά από βοήθεια συμφοιτήτριας...

Περιμένω feedback από τους συναδέλφους των διακριτών να ξεκαθαρίζει σιγά σιγά η κατάσταση...

Θα εδινα εγω φιντμπακ αλλα δεν ξερω το χριστο μου

Ναι, συμφωνω, στην ουσια ειναι προβλημα συνδυαστικης με περιτυλιγμα γραφων.

Επισης συμφωνω και με την προσεγγιση σου στο πρωτο θεμα, μια παρατηρηση που (νομιζω) δειχνει πιο κατανοητα τι ακριβως κανουμε και γιατι προστιθεται εκεινο το δια, σε καθε περιπτωση ειναι ακριβως ιδιο αποτελεσμα οποτε ο,τι βολευει τον καθενα.

Δινουμε "υπαρξη" και στα κενα, σα να ηταν μια κατηγορια μαθητων, η "Δ". Αρα εχουμε καποιους ιδιους της ομαδας Α, καποιους της Β, της Γ και της Δ, και θελουμε να φτιαξουμε ολα τα permutations. Αυτο ειναι ο τυπος
n! / (n1! n2! n3! n4! ) = 400! / ( 70! * 100! * 80! * 150! ) που ειναι ισο με αυτο που εγραψες εσυ.

Για το θεμα 3ο θεμα, με τους γραφους, οκτωβριος 13,
α) Καθε δεντρο εχει τουλαχιστον 2 φυλλα (κομβους δηλαδη με βαθμο 1, εναν γειτονα). Αυτα τα δυο ειναι και τα σημεια κοπης.

Για να αποδειξουμε οτι υπαρχουν πραγματι δυο φυλλα, μπορουμε να δουλεψουμε ως εξης :
Υπαρχει σιγουρα 1 φυλλο, γιατι αν δεν υπηρχε τοτε ολοι οι κομβοι θα ειχαν βαθμο >= 2.
Αρα οι ακμες θα ηταν τουλαχιστον 2*V / 2 (το /2 επειδη διπλομετραμε τις ακμες, μια φορα απο καθε κομβο στον οποιο εφαπτεται). Αρα οι ακμες τουλαχιστον V, δε στεκει γιατι ξερουμε οτι το δεντρο εχει V-1 ακμες.

Γνωριζοντας οτι υπαρχει ενα φυλλο, μπορουμε να δειξουμε την υπαρξη του 2ου επαγωγικα. Ισχυει για ν=2, κι αν ισχυει για καποιο Ν, τοτε για το Ν+1 το δειχνουμε ετσι :
Πηγαινουμε στο 1 φυλλο που εχουμε σιγουρακι (το αποδειξαμε πιο πανω ), και το αφαιρουμε. Προκυπτει συνδεδεμενος γραφος (αφου το φυλλο ειναι σημειο κοπης, αρα οταν βγαινει δεν χαλαει η συνεκτικοτητα), και παιρνουμε ενα Ν-δεντρο, που ξερουμε οτι εχει τουλαχιστον 2 φυλλα, αρα αποδειχτηκε.

β) Παιρνουμε ενα ελαχιστο γεννητορικο δεντρο του γραφου και συμφωνα με το 1 εχει 2 σημεια κοπης (το δεντρο). Αυτα ειναι και σημεια κοπης για τον γενικο γραφο. Αποδεικνυεται ευκολα, αφου ολος ο υπολοιπος γραφος ειναι ακομα συνδεδεμενος, μεσω των ακμων του ελαχιστου γεννητορικου δεντρου του, που ειναι υπογραφος του.

γ) Αρκει να αποδειξουμε οτι οι γεφυρες ανηκουν παντα στα συνδετικα δεντρα.
Αποδειξη, εστω οτι δεν τις συμπεριλαμβανουν, αρα απ την ιδιοτητα της γεφυρας οτι οταν λειπει ο γραφος ειναι ασυνδετος, καταληγουμε οτι δε μπορει να ηταν συνδεδεμενα δεντρα, ατοπο, αρα ανηκουν οι γεφυρες παντα στα συνδετικα δεντρα.

καμια ιδεα για Θεμα 2β απο σεπτεμβρη του 14 ?

Γνωρίζεις πως κάθε γράφημα που έχει κύκλους ΑΡΤΙΟΥ μήκους μπορεί να χρωματιστεί μόνο με 2 χρώματα.
Από την στιγμή που αφαιρείς μια ακμή που ανήκει σε όλους τους περιττούς κύκλους πλεόν έχεις μόνο ΑΡΤΙΟΥΣ ΚΥΚΛΟΥΣ-->2 χρώματα.
Χάρη στην υπόδειξη που έχεις καταλαβαίνεις πως πλεόν 3 χρώματα σου είναι αρκετά...

ναι οκ ξερουμε οτι το G δεν ειναι διμερες αλλα πως ξερουμε οτι δεν ειναι πληρες ωστε να μπορει να χρωματιστει μονο με 1 χρωμα?

βασικα δεν παιζει και το ενδεχομενο να πανε οι του Α ετους σε μια αιθουσα οι του Γ σε μια αλλη και να μεινει μια αιθουσα κενη?

Αν ήταν πλήρες θα είχες σίγουρα και κύκλους περιττού μήκους και πολλά χρώματα θα ήταν απαραίτητα...
Σε κάθε περίποτωση δεν θα μπορούσες να αποφύγεις περιτού μήκους κύκλους..


Το ενδεχόμενο αυτό περιλαμβάνεται στους υπολογισμους...

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.
Το 1γ) σε ενδιαφέρει και πόσοι και ποιοι επιβάτες πάνε στα ταμεία. Άρα είναι διακεκριμένοι για το πρόβλημα. Άρα θα πάρουμε εκθετική γεννήτρια συνάρτηση που θα αρχίζει από τον τον όρο x²⁰/20! και θα τελειώνει στο όρο x¹⁰⁰/100! και για τα 10 ταμεία. Άρα θα έχεις (x²⁰/20! +x²¹/21!+....+x¹⁰⁰/100!)¹⁰ και θα σε ενδιαφέρει ο συντελεστής του x⁵⁰⁰/500!

Για το 1β νομιζω παει διαφορετικα. Γιατι αν σκεφτουμε το πολυ απλουστερο προβλημα των 2 ανθρωπων σε 2 ταμεια, η λυση σου βγαζει 8 ενω η σωστη ειναι 6. Αυτο βγαινει γιατι δυο διαφορετικα permutations μπορει να καταληγουν στο ιδιο πραγμα (πχ η διαταξη 1-2, αν μετα μοιρασεις τον πρωτο της διαταξης στο πρωτο ταμειο και τον δευτερο της διαταξης στο δευτερο ταμειο, ειναι ιδια με την διαταξη 2-1, που στελνεις τον πρωτο της διαταξης στο δευτερο ταμειο και τον πρωτο της διαταξης στο πρωτο ταμειο).

Προτεινω, χωρις να ειμαι σιγουρος, μεσα στους 500 επιβατες να μπλεξουμε 11 φορες τον αριθμο 0. Ο αριθμος 0 ειναι διαχωριστικο, δηλαδη οτι βρισκεται αναμεσα σε δυο μηδενικα, πηγαινει στο αντιστοιχο ταμειο (επειδη παντα η πρωτη κι η τελευταια θεση θα ειναι μηδενικα με αυτη την θεωρηση, ειναι χαζο να βαλουμε 11 μηδενικα, βαζουμε 9 λοιπον! ).
Πλεον ειναι ενα προβλημα αντιμεταθεσεων, οπου ενα αντικειμενο εμφανιζεται 9 φορες, δηλαδη 509! / 9!
Στην προηγουμενη περιπτωση θα εβγαζε 3! / 1! = 6, που ειναι κι η σωστη απαντηση.

+1
Oυσιαστικα έχουμε το πρόβλημα τοποθέτησης n διακεκριμένων σφαιριδίων σε m διακεκεριμένα κουτιά όπου ΕΧΕΙ σημασία η σειρά      =(m+n-1)! / (m-1)!   άρα τελική λύση 500!*[ 509! / 9! ]


Για το 1β δες αυτό που έγραψα παραπάνω.Η λύση σου θα ήταν σωστή αν ΔΕΝ μας ενδιέφερε η σειρά στα ταμεία.Για το 1γ  +1 συμφωνώ μαζί σου.

A εντάξει. Είχα δει άλλο τύπο από τις ασκήσεις που έλεγε για τοποθέτηση διακεκριμένων σφαιρών σε διακεκριμένα κουτιά αλλά δεν είχα δει ότι έλεγε οτι δεν μας ενδιαφέρει η σειρά τοποθέτησης! Thanks!

Ρε αδέρφια τι παίζει με το 2ο 2ο Θέμα του Ιουνίου του 2017;

Μόλις βρήκα ένα 4 κανονικό γράφημα, διμερές.

Το Κ_4,4

γνωμη για λύσεις θεμαΑ Σεπτ2014;

ολα σωστα εκτος απο το γ) θεωρω οτι πρεπει  να παρεις γενητρια της μορφης  χ^20/20! +...+χ^100/100!

οντως.. το λεγαν και πιο πανω τα παιδια δεν το προσεξα

Καμια ιδεα πως συνεχίζω το β);;;
θεμα3 σεπτ14

Ζορικο θελει παρομοια τακτικη με το α ..δες στις χειργραφες

σε ποια σελιδα; εχει κατι παρόμοιο;

Θεματα Σεπτ2017
οποιος βρηκε τα ιδια ας πει

Τα ιδια για το πρωτο θεμα εγω απλα δεν ξερω αν ειναι σωστο στο πρωτο ερωτημα να συμπεριλαβουμε και τα 8 βασικα χρωματα

σωστό είναι απλά στο 1β θέλει και μια διαίρεση με το 2. Δείτε άσκηση 13 στο combinatronics.pdf

Ιουνιος 15 θεμα β ακουω

κι εγω ετσι με δυο ατοπα

Εχει κανεις τα θέματα του Ιουνίου?

παιδες η σχεση που ισχυει ειναι  m>3n-6  η  m<3n-6 ?

m <= 3n -6 , για n>=3

Ιούνιο 2015 , που ήταν ακρίβως ίδια θέματα με φέτος το σεπτέμβρη , στο θέμα 1ο τις γεννητριες πως τις βαλατε ?

Αυτό είναι για n=8, η άσκηση ζητάει να το αποδείξεις για κάθε n :)

ουσιαστικα πως θα το λυναμε το 3ο θεμα ιουνιου 2017?

Ναι, αλλα εφοσον βρηκαμε ενα αντιπαραδειγμα που υπαρχει, τοτε πως θα αποδειξουμε οτι ΔΕΝ υπαρχουν τετοια γραφηματα για καθε n? :P

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

Το θεμα ειναι σωστο αν πεσει διευκρινηση οτι το γραφημα πρεπει να ειναι επιπεδο και υπαρχει εγκυρη λυση για αυτο.

Σεπτ 13 - Θεμα 2 εχουμε καμια ιδέα; Η λύση που δίνεται πιο πίσω στο τοπικ δεν ειναι λαθος;

Ιουνιος 20 - Θεμα 1 Γιατι για καθε 3 κορυφες του v1 και 3 κορυφες του v2 μπορουμε να σχηματισουμε 6 διαφορετικους κυκλους;