Προβλήματα Μαθηματικών

Νοέμβριος 26, 2008

Peer to peer

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Michalis Loulakis @ 1:52 μμ

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

Advertisements

28 Σχόλια »

  1. Η λυση που θα παρουσιασω παρακατω δεν γνωριζω αν ειναι η βελτιστη η οχι, πιστευω πως δεν θα ειναι , γιατι αν μπορουσε να την λυση τοσο ευκολα ενας μαθητης δεν βρισκοταν εδω το προβλημα αυτη τη στιγμη. Εστω οτι P1 -> m1 δηλαδη Ατομο 1 που γνωριζει το μηνυμα 1, θα εχουμε

    P1 – > m1
    P2 -> m2
    P3 -> m3
    …..
    P10-> m10

    Η λυση λειτουργει ως εξης, οι P2 εως και P10 αναφερουν το μηνυμα (κουτσομπολιο) που γνωριζουν στον P1 και μετα ο P1 γνωριζοντας ολα τα μηνυματα πλεον τα αναφερουν στους P2 εως και P10. Αρα εχουμε 9 αναφορες κουτσομπολιων και αλλες 9 ολοκληρωμενες αναφορες κουτσομπολιων που μας κανει 18αναφορες δηλαδη 18 τηλεφωνηματα.

    Η λυση αυτη θυμιζει και λιγο το δυκτιο bittorrent οπου υπαρχει ο tracker με τις ip:ports του καθε χρηστη και καθε χρηστης κανει ενα get για να μαθει τις υπολοιπες ip’s . Ξεφυγα λιγο. Ελπιζω η λυση να μην ειναι εντελως χαλια.

    Μου αρέσει!

    Σχόλιο από alexakasilo — Νοέμβριος 26, 2008 @ 8:22 μμ

  2. Ο αλγόριθμος που προτείνεις είναι εύκολα υλοποιήσιμος, δεν είναι όμως ο βέλτιστος. Μπορούμε να κατεβούμε και κάτω από τα 18 τηλεφωνήματα.

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

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 26, 2008 @ 9:07 μμ

  3. Οταν ο P10 θα λεει το κουτσομπολιο στον P1, ο P1 θα γνωριζει ολα οσα χρειαζεται για να ξερει ο P10 ολα τα κουτσομπολια , αρα δεν πρεπει να τον παρει μετα τηλ, αρα εχουμε 17 τηλεφωνηματα. Τωρα αν κατεβενει περισσοτερο ο αριθμος αυτος θελει και αλλη σκεψη.

    Μου αρέσει!

    Σχόλιο από alexakasilo — Νοέμβριος 26, 2008 @ 9:35 μμ

  4. Μπορούμε να κατεβούμε και κάτω από τα 17.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 26, 2008 @ 9:38 μμ

  5. γινεται και με 10 ? Αν ο P1 παρα τηλ τον P2 τοτε θα γνωριζουν και οι 2 τα μ1,μ2, αν ο P3 τηλεφωνησει στον p2 τοτε γνωριζουν και οι 2 τα μ1,μ2,μ3 χρειαζεται και αλλο ενα τηλεφωνημα για να μαθει και ο P1 to μ3 αρα γεια την διαδοση 3 κουτσομπολιων μεταξυ 3 ατομων χρειαστηκαν 3 τηλεφωνηματα, στουσ 10 θα χρειαζονται 10 τηλεφωνηματα, αλλα μαλλον εχει καποιο λαθος αυτη η λυση κατι δεν συμπεριλαμβανω στην λυση, γιατι με περισσοτερους ανθρωπους ισως αλλαζει ο αριθμος των τηλεφωνηματων που χρειαζονται.

    Μου αρέσει!

    Σχόλιο από alexakasilo — Νοέμβριος 26, 2008 @ 9:53 μμ

  6. Αν για 3 άτομα αρκούν 3 τηλεφωνήματα αυτό δε σημαίνει ότι για ν άτομα αρκούν ν τηλεφωνήματα!

    Παρόλα αυτά για 4 άτομα, 4 τηλεφωνήματα είναι αρκετά. Βρες πώς και ίσως αυτό σε βοηθήσει να βρεις τη λύση για 10 (ή ν εν γένει) άτομα.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 26, 2008 @ 10:07 μμ

  7. Σκέφτηκα μια λύση με 16, και γενικότερα έναν αλγόριθμο που θα χρειάζονται 2ν-4 τηλεφωνήματα για ν άρτιο.Όμως δεν γνωρίζω αν είναι η βέλτιστη αν και δεν βρίσκω κάτι καλύτερο για την ώρα.

    Πάει 1–>2–>3–>4–>5 και 6–>7–>8–>9–>10 και τότε 4–>9 και 5–>10.Τότε οι 4,5,9,10 τα ξέρουν όλα και έχουν γίνει 10 τηλεφωνήματα.Οπότε με 6 ακόμα τα ξέρουν όλοι.Γενικά γίνονται 2(ν/2-1) + 2 + ν – 4 τηλεφωνήματα με αυτή την ιδέα για ν άρτιο.

    Μου αρέσει!

    Σχόλιο από olack — Νοέμβριος 27, 2008 @ 4:24 μμ

  8. Το 16 είναι ο μικρότερος αριθμός τηλεφωνημάτων που χρειάζονται -και 2ν-4 εν γένει (για ν\ge 4) ακόμη κι αν το ν είναι περιττός. Ο ίδιος αλγόριθμος δουλεύει και όταν το ν είναι περιττός, απλά οι δύο ομάδες στις οποίες θα χωρίσετε αρχικά τα άτομα δεν θα είναι ισοπληθείς. Μένει τώρα να βρείτε γιατί δεν γίνεται να μαθευτούν όλα τα κουτσομπολιά από όλους με λιγότερα από 16 (ή 2ν-4 γενικότερα) τηλεφωνήματα. Πόσο σύντομα μπορεί ένας από τους κατοίκους να μάθει όλα τα κουτσομπολιά;

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 28, 2008 @ 11:17 πμ

  9. Για το 1ο ερώτημα που αφορα στο γιατί δεν μπορεί να γίνουν λιγότερα απο 16 (2ν-4) τα τηλεφωνήματα. Κατ’αρχάς, το «καλύτερο» ( αποδοτικότερο ) τηλεφώνημα αποφέρει διπλασιασμό των μηνυμάτων ( κουτσομπολιών ) ( για παράδειγμα σε επικοινωνία μεταξύ δυο ατόμων που γνωρίζουν διαφορετικά μηνύματα ). Βάσει αυτού, στην περίπτωση των 10 ατόμων, επιλέγουμε πρώτα να χωρίσουμε 2 ομάδες των 5 ατόμων ( Α,Β,Γ,Δ,Ε τα άτομα της πρώτης έστω, Ζ,Η,Θ,Ι,Κ της δεύτερης ).
    Και για να έχουμε όσο γίνεται περισσότερα «βέλτιστα» τηλεφωνήματα: Α->Β,Β->Γ..Δ->Ε (4+4=8 τηλεφωνήματα). Όμοια για τη δεύτερη ομάδα. Μετά, για να διατηρήσουμε τον καλύτερο διπλασιασμό επιλέγουμε Δ->Ι,Ε->Κ,οπότε Δ,Ε,Ι,Κ ξέρουν όλα τα κουτσομπολιά ( 8+2=10 ). Μετά γίνονται και τηλεφωνήματα στα άτομα Α,Β,Γ,Ζ,Η,Θ (10+6=16 –2ν-4). Τα τελευταία τηλεφωνήματα δεν είναι «βέλτιστα», αλλά δεν υπάρχει άλλος τρόπος λύσης, προφανώς.
    Βέβαια, αυτή η λύση δεν είναι καθαρά μαθηματική, αλλά δεν μπόρεσα να βρω άλλη απόδειξη.
    Τέλος, ένα άτομο μαθαίνει όλα τα κουτσομπολιά μετά από 9 τηλεφωνήματα,γιατί μόνο έτσι μπορούν να «καταχωρηθούν» τα υπόλοιπα 9 κουτσομπολιά (σε ισάριθμα τηλεφωνήματα).Π.χ. Α->Β,Β->Γ…Ι->Κ και το Κ έχει τελικά μάθει όλα τα κουτσομπολιά.

    Μου αρέσει!

    Σχόλιο από talsfan — Δεκέμβριος 4, 2008 @ 1:05 πμ

  10. talsfan:

    Αυτά που γράφεις περιγράφουν τον αλγόριθμο της λύσης. Δεν αποδεικνύεις όμως ότι δεν γίνεται να μάθουν όλοι όλα τα κουτσομπολιά με λιγότερα από 2ν-4 τηλεφωνήματα, ούτε ότι ο μικρότερος αριθμός τηλεφωνημάτων ώστε κάποιος να ξέρει όλα τα μυστικά είναι ν-1. Την ερώτηση αυτή την έκανα για να σας βοηθήσω. Τα δύο αυτά ερωτήματα σχετίζονται…

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Δεκέμβριος 4, 2008 @ 4:21 μμ

  11. Ο μικρότερος αριθμός τηλεφωνημάτων για να μάθει κάποιος όλα τα κουτσομπολιά είναι ν-1, διότι:
    στα 4 άτομα χρειάζονται 4-1=3 τηλεφωνήματα. Προφανώς δεν υπάρχει δυνατότητα για συντομότερη λύση (τηλεφωνήματα Α->Β,Β->Γ και λοιπά, όπου Α,Β,Γ…τα άτομα)
    στα 5 άτομα: 5-1=4 τηλεφωνήματα

    στα ν άτομα: ν-1 τηλεφωνήματα
    Όμως, στο τέλος του τελευταίου τηλεφωνήματος (ν-1),2 άτομα θα ξέρουν όλα τα μηνύματα.

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

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

    Από τα ν άτομα, για να τα μάθουν όλα τα μυστικά 2 άτομα, χρειάζονται,επομένως, ν-1 τηλεφωνήματα.

    Από τα ν άτομα, για να τα μάθουν όλα τα μυστικά 4 άτομα ( μια επιπλέον δυάδα ), αρκούν ν τηλεφωνήματα.

    Αυτό αποδεικνύεται αλγοριθμικά. Χωρίζουμε τα άτομα σε 2 ομάδες ( αν ν άρτιος – αν ο ν περιττός,χωρίς να βλάπτεται η γενικότητα, η μία ομάδα θα έχει απλώς ένα παραπάνω άτομο,αν θεωρήσουμε ότι οι ομάδες χωρίζονται ώστε να έχουν ακριβώς ή έστω σχεδόν τον ίδιο αριθμό μελών ).
    Γιά άρτιο ν:η 1η ομάδα περιλαμβάνει τα άτομα Κ1,Κ2,…Κν/2 και η 2η τα Κ(ν/2 +1)…Κν. Τα τηλεφωνήματα σε κάθε ομάδα είναι πάλι της μορφής Κ1->Κ2,Κ2->Κ3 και λοιπά. Έτσι, μετά από (ν/2 – 1) + (ν/2 – 1) [ για κάθε ομάδα δηλαδή χωριστά ] = ν-2 τηλεφωνήματα, προκύπτουν 2 άτομα σε κάθε ομάδα που ξερουν τα μυστικά της ομάδας στην οποία ανήκουν. Αυτά επικοινωνούν μεταξύ τους (ομάδα-ομάδα) και με 2 ακόμα τηλεφωνήματα (ν-2+2=ν) προκύπτουν 4 πλήρως ενημερωμένα άτομα.

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

    Αυτό σημαίνει ότι ο βέλτιστος τρόπος για διάδοση των μυστικών είναι:
    ν (στην αρχή τηλεφωνήματα για να προκύψουν 4 πλήρως ενημερωμένα άτομα) + ν-4 (τηλεφωνήματα για ενημέρωση και των υπολοίπων) = 2ν-4 τηλεφωνήματα με ν>4, ν φυσικός.

    Μου αρέσει!

    Σχόλιο από talsfan — Δεκέμβριος 5, 2008 @ 2:18 πμ

  12. talsfan:

    Λες: «Αυτό αποδεικνύεται αλγοριθμικά».
    Αυτό που αποδεικνύεις είναι ότι μπορούν όλοι να μάθουν τα κουτσομπολιά με 2ν-4 τηλεφωνήματα,
    και όχι ότι δεν γίνεται με λιγότερα.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Δεκέμβριος 5, 2008 @ 7:50 μμ

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

    Μου αρέσει!

    Σχόλιο από vigavril — Ιουνίου 15, 2009 @ 3:33 μμ

  14. Η απάντηση 2ν-4 είναι σωστή- η αιτιολόγηση δεν είναι επαρκής. Το logν (για την ακρίβεια 2logν) θα ήταν ο χρόνος που χρειάζεται να ολοκληρωθεί η διαδικασία γιατί κάποια τηλέφωνα μπορούν να γίνουν παράλληλα.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιουνίου 15, 2009 @ 4:39 μμ

  15. Πιστεύω η απάντηση είναι 9 και γενικά ν-1.

    Απόδειξη: Με επαγωγή: ξεκινάμε απο την αρχή: ο 1 επικοινωνεί με τον 2 και μοιράζονται τις πληροφορίες τους. Στο επόμενο βήμα, η καλύτερη δυνατή επικοινωνία είναι μεταξύ ενός εκ των 1 ή 2 με έναν άλλο πχ τον 3 (έτσι ώστε ο 3 να πάρει δύο πληροφοριες αντί για μια). Στο επόμενο βήμα, πάλι συμφέρει να επικοινωνήσουν ο 3 με τον 4 (και όχι πχ ο 5 με τον 6). …. σε κάθε βήμα άριστη επικοινωνία = ένας που ήδη γνωρίζει τις πληροφορίες άλλων να επικοινωνήσει με έναν που δεν ξέρει τίποτα για τους άλλους. Έτσι, πχ, μια άριστη ακολουθία επικοινωνιών είναι 1->2, 2->3, …., ν-1->ν, το οποίο σημαίνει ν-1 συνολικά τηλεφωνήματα.-

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 5:51 μμ

  16. Sorry για το λάθος στην προηγούμενη διαδικασία.

    Το σκέφτηκα λίγο, και η απάντηση νομίζω είναι 2v-3 (εκτός αν πάλι κάνω το λάθος …)

    Απόδειξη: Συνέχεια απο προηγούμενη. … Μετά λοιπόν απο ν-1 βήματα, ο ν έχει μάθει όλα τα κουτσομπολιά. Όχι όμως μόνο αυτός, αλλά και ο ν-1. Το θέμα είναι να τα μάθουν και οι υπόλοιποι. Απο ποιούς; Απο αυτούς τους δύο (πχ). Άρα απαιτούνται ακόμη ν-2 τηλεφωνήματα επιπλέον. Σύνολο ν-1 + ν-2 = 2ν-3.

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 6:14 μμ

  17. Μία άλλη άριστη διαδοχή επικοινωνιών είναι

    1->2, 2->3, 3->4, …, ν-1->ν (1η φάση) ν-1 βήματα
    ν-1->ν-2,…3->2,2->1 (2η φάση) ν-2 βήματα

    back to work

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 6:34 μμ

  18. harris1976

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

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Σεπτεμβρίου 25, 2009 @ 6:59 μμ

  19. Δηλαδή για ν=2 χρειάζονται 0 τηλεφωνήματα?

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 7:46 μμ

  20. Νομίζω οτι η κατασκευή που περιέγραψα αποδεικνύει την διαδικασία μιας άριστης διαδοχής τηλεφωνημάτων. Δηλαδή, στην 1η φάση ζητούμενο είναι σε κάθε βήμα να μεταφέρονται το δυνατό περισσότερα κουτσομπολιά απο κάποιον σε κάποιον άλλο (ν-1 τηλεφωνήματα). Στη 2η φάση απλά πρέπει οι υπόλοιποι ν-2 να πληροφορηθούν απο κάποιον ‘παντογνώστη’ όλα τα κουτσομπολιά που δεν ξέρουν (ήτοι ν-2 τηλεφωνήματα επιπλέον).

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 7:49 μμ

  21. Ονομάζουμε τα n άτομα του χωριού A_1,A_2,\ldots,A_n.

    Θα δείξουμε επαγωγικά ότι τα n άτομα μπορούν να μάθουν όλα τα κουτσομπολιά όχι σε λιγότερο από 2n-4 τηλεφωνήματα.
    Για n=4 ισχύει. Έστω (προς άτοπο) ότι σε ένα χωριό με n=k+1 άτομα μπορούν να διαδοθούν όλα τα κουτσομπολιά σε 2k-3=(2n-4)-1 τηλεφωνήματα και έστω ότι το τελευταίο τηλεφώνημα γίνεται στον A_{k+1}. Διακρίνουμε δύο περιπτώσεις:

    1)Το πρώτο τηλεφώνημα γίνεται από τον A_{k+1} . Σε αυτή τη περίπτωση αγνοώντας το πρώτο και τελευταίο τηλεφώνημα (και πιθανον καποια άλλα ενδιάμεσα τηλεφωνήματα (*) ) μπορούμε να δούμε ότι στο «υποχωριό» με άτομα \{A_1,\ldots,A_k\} διαδίδονται όλα τα κουτσομπολιά του, με το πολύ 2k-5 τηλεφωνήματα.

    2)Το πρώτο τηλεφώνημα δεν γίνεται από τον A_{k+1} . Σε αυτή τη περίπτωση σίγουρα κάποιο ενδιάμεσο τηλεφώνημα, ας πούμε το r οστό (1\leq r<2k-3 ), γίνεται στον A_{k+1} . (*) Τώρα αν το r+1 τηλεφώνημα δεν έγινε από τον A_{k+1} μπορούμε να αγνοήσουμε το rοστό τηλεφώνημα. Διαφορετικά ¨συγχωνεύουμε¨ τα τηλεφωνήματα r,r+1 σε ένα τηλεφώνημα. Σε κάθε υποπερίπτωση αγνοώντας και το τελευταίο τηλεφώνημα (και πιθανον καποια άλλα ενδιάμεσα τηλεφωνήματα (*) ) μπορούμε να δούμε ότι στο "υποχωριό" με άτομα \{A_1,\ldots,A_k\} διαδίδονται όλα τα κουτσομπολιά του, με το πολύ 2k-5 τηλεφωνήματα.

    Επαγωγικά λόγο του αρχικού βήματος καταλήγουμε σε άτοπο.

    Μου αρέσει!

    Σχόλιο από Pambos — Μαΐου 18, 2012 @ 10:03 μμ

  22. ?

    Μου αρέσει!

    Σχόλιο από Pambos — Ιουνίου 29, 2012 @ 6:37 μμ

  23. Pambos

    Στη βέλτιστη στρατηγική ο A_{k+1} μπορεί να κάνει και ενδιάμεσα τηλεφωνήματα (ανάμεσα σε αυτά που διαγράφεις) που γνωστοποιούν κουτσομπολιά σε άλλους. Σίγουρα όμως είσαι πολύ κοντά και μπορεί κανείς να φτιάξει μια απόδειξη παραλλάσοντας το επιχείρημά σου. Μπορείς να διαγράψεις το τελευταίο τηλεφώνημα, το πρώτο τηλεφώνημα που συμμετείχε ο A_{k+1}, και να αλλάξεις κατάλληλα τα ενδιάμεσα, δείχνοντας έτσι ότι αν για ένα χωριό ν ατόμων γνωρίζουμε μια στρατηγική διάδοσης με Ν τηλεφωνήματα, τότε για ένα χωριό ν-1 ατόμων μπορούμε να φτιάξουμε μια στρατηγική διάδοσης με Ν-2 τηλεφωνήματα.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιουνίου 30, 2012 @ 4:50 πμ

  24. Στις περιπτώσεις (1) και (2) εκεί που λέω σε παρένθεση «και πιθανον καποια άλλα ενδιάμεσα τηλεφωνήματα» ήθελα να πω αυτό που εξηγήσατε. Ότι ο A_{k+1} μπορεί να κάνει και ενδιάμεσα τηλεφωνήματα. Αυτά μπορούμε να τα αγνοήσουμε με τον τρόπο που περιγράφω στην 2\textsuperscript{nd},3\textsuperscript{rd},4\textsuperscript{th} πρόταση της περίπτωσης (2).

    Όπως είπατε έδειξα ότι αν σε ένα χωριό με n=k+1 άτομα μπορούν να διαδοθούν όλα τα κουτσομπολιά με N=(2n-4)-1=2k-3 τηλεφωνήματα τότε σε ένα χωριό με n-1=k άτομα μπορούν να διαδοθούν όλα τα κουτσομπολιά του με το πολύ N-2=2k-5 τηλεφωνήματα.

    Μου αρέσει!

    Σχόλιο από Pambos — Ιουνίου 30, 2012 @ 10:54 πμ

  25. Pambos

    Τα ενδιάμεσα τηλεφωνήματα που κάνει ο A_{k+1} δεν μπορούμε να τα αγνοήσουμε και να είμαστε βέβαιοι ότι τα κουτσομπολιά μεταδίδονται σ’ όλο το υποχωριό. Επίσης, ο συνομιλήτής του A_{k+1} στο τελευταίο τηλεφώνημα (έστω Ζ) μαθαίνει ενδεχομένως κατά τη διάρκειά του κάποια κουτσομπολιά που δεν ήξερε και δεν θα μάθει ποτέ αν απλά διαγράψουμε αυτό το τηλεφώνημα. Θα πρέπει να αλλάξεις τη στρατηγική των k+1 ατόμων έτσι ώστε να εξασφαλίσεις δύο πράγματα: 1) η πληροφορία που μεταφέρει ο A_{k+1} στα ενδιάμεσα τηλεφωνήματα μεταφέρεται από κάποιον άλλο, 2) ο Ζ θα έχει μάθει ήδη ότι μπορεί να ήξερε ο A_{k+1} πριν το τελευταίο τηλεφώνημα.

    Είσαι κοντά αλλά χρειάζονται ακόμη 2-3 επιχειρήματα.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιουνίου 30, 2012 @ 1:25 μμ

  26. Τώρα το βλέπω, είναι λάθος το σχόλιο 21. Επειδή δεν μπορώ να το διορθώσω θα το αλλάξω λίγο.

    Θα δείξουμε πως μπορούμε να πετύχουμε αυτό που εξηγείτε τέλος του σχόλιου 23: αν για ένα χωριό n ατόμων γνωρίζουμε μια στρατηγική διάδοσης με N τηλεφωνήματα, να φτιάξουμε για ένα χωριό n-1 ατόμων μια στρατηγική διάδοσης με N-2 τηλεφωνήματα.

    Ονομάζουμε τα n άτομα του χωριού A_1,A_2,\ldots,A_n. Έστω ότι έχουμε μια στρατηγική διάδοσης όλων των κουτσομπολιών. Υποθέτουμε ότι στο πρώτο τηλεφώνημα εμπλέκεται ο A_1.
    Έστω ότι όλα τα τηλεφωνήματα που εμπλέκεται ο A_1 είναι:B_1\leftrightarrow A_1,B_2\leftrightarrow A_1,B_3\leftrightarrow A_1,\ldots, B_i\leftrightarrow A_1 για κάποια άτομα B_1,B_2,\ldots,B_i του χωριού. Ας πούμε ότι τα τηλεφωνήματα αυτά είναι το 1,a_2,\ldots,a_i-οστό τηλεφώνημα που γίνεται αντίστοιχα(a_2,\ldots,a_i \in \mathbb{N}).

    Στο χωριό με άτομα A_2,\ldots,A_{n-1} η στρατηγική διάδοσης των κουτσομπολιών του είναι η εξής:
    Όλα τα τηλεφωνήματα είναι τα ίδια με την περίπτωση των n ατόμων εκτός το πρώτο και a_2 τηλεφώνημα δεν γίνονται και τα τηλεφωνήματα a_3,\ldots,a_i αλλάζουν σε B_3\leftrightarrow B_2,B_4\leftrightarrow B_3,\ldots, B_i\leftrightarrow B_{i-1}.

    Μου αρέσει!

    Σχόλιο από Pambos — Ιουλίου 3, 2012 @ 7:39 μμ

  27. Διόρθωση στη τελευταία παράγραφο: Στο χωριό με άτομα A_2,A_3,\ldots,A_n

    Μου αρέσει!

    Σχόλιο από Pambos — Ιουλίου 3, 2012 @ 7:41 μμ

  28. Αν κατάλαβα σωστά, το μόνο που μένει να αποδειχθεί είναι ότι για ν ≥ 4 άτομα / κουτσομπολιά δεν είναι δυνατό να μάθουν όλοι τους όλα τα κουτσομπολιά με λιγότερα από 2ν-4 τηλεφωνήματα, ενώ αρκούν πάντα 2ν-4 τηλεφωνήματα.

    Αν είχαμε 4 άτομα, προφανώς θα χρειαζόμασταν όχι λιγότερα από 4=2*4-4 τηλεφωνήματα, αφού χρειάζονται 3 τηλεφωνήματα για να κοινοποιηθούν ισάριθμα κουτσομπολιά σε κάποιον/ους που δεν τα γνώριζε/αν εξαρχής ο ίδιος / οι ίδιοι, αλλά με 3 μόνο τηλεφωνήματα μπορεί να υπάρξουν 2 το πολύ άτομα που γνωρίζουν όλα τα κουτσομπολιά. Τα 4 τηλεφωνήματα αρκούν ως εξής: οι Α και Β ανταλλάσσουν τα κουτσομπολιά τους, οι Γ και Δ επίσης, οι Α και Γ ανταλλάσσουν τα κουτσομπολιά που γνωρίζουν, οι Β και Δ επίσης. Έτσι τώρα και τα 4 άτομα γνωρίζουν και τα 4 κουτσομπολιά.

    Η πρόταση επομένως ισχύει για ν=4.

    Έστω ότι ισχύει για κάποιο ν ≥ 4. Θα δείξουμε ότι ισχύει και για ν+1.

    Προσθέτοντας στα ν άτομα / κουτσομπολιά Α, Β, Γ, … ακόμα 1 άτομο / κουτσομπολιό Ω, έχουμε ν+1 άτομα / κουτσομπολιά. Αν το πρώτο τηλεφώνημα γίνεται μεταξύ των ατόμων Α και Ω, τότε μετά από αυτό οι Α και Ω είναι το μόνο ζευγάρι ατόμων που γνωρίζουν από 2 κουτσομπολιά ο καθένας, συγκεκριμένα τα κουτσομπολιά Α και Ω, ενώ όλοι οι υπόλοιποι εξακολουθούν να γνωρίζουν από 1 κουτσομπολιό ο καθένας. Εξαιρώντας προσωρινά τον Ω, έχουμε ουσιαστικά αναχθεί στην περίπτωση ν ατόμων Α, Β, Γ, … που ο καθένας τους γνωρίζει ένα διαφορετικό κουτσομπολιό, θεωρώντας τα κουτσομπολιά Α+Ω που γνωρίζει ο Α ως ενιαίο κουτσομπολιό. Σύμφωνα με την επαγωγική υπόθεση, χρειάζονται τώρα 2ν-4 τηλεφωνήματα για να μάθουν τα ν άτομα Α, Β, Γ, … και τα ν+1 κουτσομπολιά Α+Ω, Β, Γ,.. Τώρα όλοι εκτός του Ω γνωρίζουν και τα ν+1 κουτσομπολιά. Χρειάζεται λοιπόν 1 ακόμα τηλεφώνημα από τον Α (ή οποιονδήποτε άλλον από τους ν) προς τον Ω για να μάθει και ο Ω όλα τα κουτσομπολιά που δεν ξέρει.

    Συνεπώς για ν+1 άτομα χρειάζονται απαραιτήτως 1+(2ν-4)+1 = 2ν-2 = 2(ν+1)-4 τηλεφωνήματα, άρα η πρόταση ισχύει και για ν+1, γεγονός που ολοκληρώνει την επαγωγική απόδειξη.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — Σεπτεμβρίου 3, 2016 @ 5:54 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: