Δευτέρα 4 Φεβρουαρίου 2013

▪ Τέσσερα meeting

Εννέα άτομα πρέπει να παραστούν σε τέσσερις διαφορετικές συνεδριάσεις και να καθίσουν γύρω από ένα τραπέζι.
Γίνεται να καθίσουν με τέτοιο τρόπο, ώστε κανείς να μην καθίσει δίπλα στο ίδιο πρόσωπο σε περισσότερες από μία συνεδριάσεις;
Αναρτήθηκε από στις 4.2.13
Ετικέτες

2 σχόλια:

  1. RIZOPOULOS GEORGIOS5 Φεβρουαρίου 2013 στις 4:56 π.μ.

    Oι κυκλικοί συνδυασμοί 9 προσώπων(ή αντικειμένων) γενικά είναι 9! /9
    Αυτό προκύπτει από την απλή σκέψη ότι σε ευθεία γραμμή έχουμε 9! συνδυασμούς, αλλά ο κάθε διακριτός γραμμικός συνδυασμός ,αν σχηματίσει κύκλο, δημιουργεί άλλους 8 ισοδύναμους.
    Π.χ ο συνδυασμός 1 2 3 4 5 6 7 8 9 είναι ο ίδιος κύκλος (ως προς τους γείτονες του κάθε κόμβου/κορυφής) με τον 2 3 4 5 6 7 8 9 1 ,και με τον 3 4 5 6 7 8 9 1 2 κλπ.
    Οπότε το πρόβλημά μας ισοδυναμεί με το να βρούμε σε ένα πλήρες κυκλικό γράφημα τάξεως 9 ,ουσιαστικά δηλαδή ένα 9γωνο έστω Α Β Γ Δ Ε Ζ Η Θ Ι , τους αμοιβαία αποκλειόμενους -ως προς τις κορυφές- κύκλους Χάμιλτον. Δηλαδή την αναδιάταξη των κόμβων του γραφήματος ή ισοδυνάμως την αλληλουχία διαδρομών που δεν ‘’γράφουν’’ δυο διαδοχικούς ίδιους κόμβους.
    Ο γενικός τύπος για ένα γράφημα Κ(2ν+1) που δίνει των αριθμό αυτό είναι : v κύκλοι για 2ν+1 κορυφές. Άρα στην περίπτωσή μας υπάρχουν 4 τέτοιοι κύκλοι ,που σημαίνει ότι σε 4 συνεδριάσεις γίνεται ,την 5η ,όχι!
    Για 5 συνέδρους π.χ ,ο μέγιστος αριθμός συνεδριάσεων θα ήταν 2 .Μετά κάποιος υποχρεωτικά θα είχε έναν ίδιο με προηγουμένως γείτονα.
    Αναλυτικά για το Κ9 γράφημα που εξετάζουμε, είναι εύκολο να σχεδιάσει κάποιος τους 4 κύκλους Χάμιλτον, αρχίζοντας από τον 1ο, δηλαδή ένα 9- γωνο Α Β Γ Δ Ε Ζ Η Θ Ι , στον δεύτερο: Δ Α Η Ε Β Θ Ζ Γ Ι ,και στους άλλους δύο.

    ΑπάντησηΔιαγραφή
  2. RIZOPOULOS GEORGIOS5 Φεβρουαρίου 2013 στις 2:36 μ.μ.

    Διόρθωση ορολογίας: Όπου ''πλήρες'' γράφημα, εννοούσα "συνεκτικό γράφημα"

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

Εγγραφή σε: Σχόλια ανάρτησης (Atom)