Πέμπτη 12 Ιουνίου 2014

Η Αποστολή

Ένας καθηγητής Μαθηματικών έδωσε την εξής αποστολή στους 20 μαθητές του. Είπε στον καθένα από μία λέξη και στόχος των μαθητών είναι να βάλουν και τις 20 λέξεις στη σωστή σειρά ώστε να αποκαλυφθεί μια πρόταση. Ο καθηγητής όμως έβαλε και έναν όρο, οι μαθητές θα πρέπει τηλεφωνικά να γνωστοποιούν τις λέξεις στους συμμαθητές τους, δηλαδή, εάν ένας μαθητής γνωρίζει 3 λέξεις μπορεί να τις μεταφέρει και στον επόμενο με τον ελάχιστο αριθμό τηλεφώνων. Μπορείτε να βρείτε πόσα τηλεφωνήματα θα γίνουν; (Κατ.34/Νο. 703)

Λύση

Λύση του Γ. Ριζόπουλου. Για να μην παρουσιάζω δουλειά και σκέψεις άλλων για δικές μου,ιδού ένα ενδιαφέρον σχετικό λινκ σε άλλο μπλογκ, όπου συζητείται το ίδιο πρόβλημα: http://kolount.wordpress.com/2008/11/26/peer-to-peer/#comments Εκεί υπάρχει σε εκρεμότητα το "αναγκαίο" της υπόθεσης. Το θέμα είναι διττό,καθότι δεν αρκεί μόνο το "ικανό" δηλαδή πως υπάρχει λύση ας πουμε με 2ν-4 (2*20-4=40-4=36 τηλεφωνήματα στην εκδοχή μας εδώ) αλλά και πως δεν υπάρχει λύση ή γενικά αλγόριθμος με λιγότερα. Αυτή η απόδειξη λοιπόν (του "αναγκαίου και ικανού") για το 2ν-4 παρουσιάζεται στο ωραίο αυτό πέηπερ, με χρήση Θεωρίας Γράφων: http://web.pdx.edu/~caughman/Gossip.pdf

3 σχόλια:

RIZOPOULOS GEORGIOS είπε...

Mια ερώτηση Κάρλο (αν έχεις την απάντηση):
Kάθε τηλεφώνημα δημιουργεί "αμφίδρομη" πληροφόρηση;
Δηλαδή π.χ, κάποιος που μεταφέρει 3 λέξεις σε άλλον μαθαίνει και τις όποιες λέξεις ξέρει ο άλλος;
Υποθέτω πως ναι. (;)

RIZOPOULOS GEORGIOS είπε...

Για να μην παρουσιάζω δουλειά και σκέψεις άλλων για δικές μου,ιδού ένα ενδιαφέρον σχετικό λινκ σε άλλο μπλογκ, όπου συζητείται το ίδιο πρόβλημα:
http://kolount.wordpress.com/2008/11/26/peer-to-peer/#comments
Εκεί υπάρχει σε εκρεμότητα το "αναγκαίο" της υπόθεσης. Το θέμα είναι διττό,καθότι δεν αρκεί μόνο το "ικανό" δηλαδή πως υπάρχει λύση ας πουμε με 2ν-4 (36 τηλεφωνήματα στην εκδοχή μας εδώ) αλλά και πως δεν υπάρχει λύση ή γενικά αλγόριθμος με λιγότερα.
Αυτή η απόδειξη λοιπόν (του "αναγκαίου και ικανού") για το 2ν-4 παρουσιάζεται στο ωραίο αυτό πέηπερ, με χρήση Θεωρίας Γράφων:
http://web.pdx.edu/~caughman/Gossip.pdf

Papaveri είπε...

@RIZOPOULOS GEORGIOS
Γιώργο δεν έχω την λύση του προβλήματος, γι' αυτό το ανάρτησα επειδή μου άρεσε, για να μου δώση κάποιος τη λύση εάν την γνωρίζει. Τη διεύθυνση που μου γραφεις για ένα παρόμοιο πρόβλημα την έχω δει κι' εγώ. Λογικά πιστεύω κι' εγώ ότι αυτό συμβαίνει, ανταλλάσουν πληροφορίες.
Ένα παρόμοιο ανάρτησα κι' έγώ το 2011 δες εδώ:
http://papaveri48.blogspot.gr/2011/10/blog-post_11.html

 

Papaveri48 © 2010

PSD to Blogger Templates by OOruc & PSDTheme by PSDThemes