Η Αποστολή

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

Πηγή:http://diadiktyomathphys.wordpress.com/

Λύση

Λύση του Γ. Ριζόπουλου. Για να μην παρουσιάζω δουλειά και σκέψεις άλλων για δικές μου,ιδού ένα ενδιαφέρον σχετικό λινκ σε άλλο μπλογκ, όπου συζητείται το ίδιο πρόβλημα: 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