mathematica.gr

Ψαχνοντας κατι παλιά αρχεία στο pc βρήκα αυτό το γρίφο που τον είχα βρεί τυχαία στο internet

"Υπάρχουν ν κυρίες και κάθε μία γνωρίζει ενα μικρό κομμάτι ενός κουτσομπολιού που δεν γνωρίζουν οι άλλες. Οι κυρίες επικοινωνουν μόνο με το τηλέφωνο και κάθε φορά που η μία καλεί την άλλη ανταλλάσουν όλες τις πληροφορίες που έχουν μεχρι εκείνη τη στιγμή.
Ποιός είναι ο ελάχιστος αριθμός τηλεφωνημάτων που απαιτούνται ετσι ώστε όλες οι κυρίες να γνωρίζουν πληρως το κουτσομπολιό;"

Καλή σας μέρα
Με το παρακάτω σχήμα επικοινωνίας:

εξασφαλίζεται ότι όλες έχουν όλη την ιστορία με τηλεφωνήματα. Ο αριθμός αυτός είναι για μικρότερος του που προτείνει ο Αντώνης. Δεν ξέρω όμως αν είναι βέλτιστος. Δηλαδή δεν έχω απόδειξη ότι είναι όντως ο μικρότερος δυνατός αριθμός τηλεφωνημάτων.
Μαυρογιάννης

Nίκο είναι όντως βέλτιστος ως προς τον αριθμό τηλεφωνημάτων. όπως άλλωστε ζητάει και το πρόβλημα.
ν-1 τηλεφωνήματα να το μάθει ένας. (του λείπουν ν-1 κομμάτια, και κάθε κομμάτι του μυστικού που του λείπει, θα πρέπει να έχει μετακινηθεί τουλάχιστον μια φορά για να έχει φτάσει εως αυτόν.)
οι υπόλοιποι ν-1 χρειάζονται τουλάχιστον άλλο ένα τηλεφώνημα. άρα άλλα ν-1 τηλεφωνήματα.

Πιο σύνθετο θα γίνει αν ρωτήσουμε να είναι και βέλτιστος ως προς τον χρόνο που θα μαθευτεί.
Με την επιπλέον υπόθεση οτι το ν είναι δύναμη του 2. (και οτι κάθε τηλεφώνημα έχει συκεκριμένη διάρκεια κατα μέσο όρο)
Κουτσομπόλες είναι.. πες οτι βιάζονται...

nsmavrogiannis έγραψε:Καλή σας μέρα
Με το παρακάτω σχήμα επικοινωνίας:

εξασφαλίζεται ότι όλες έχουν όλη την ιστορία με τηλεφωνήματα. Ο αριθμός αυτός είναι για μικρότερος του που προτείνει ο Αντώνης. Δεν ξέρω όμως αν είναι βέλτιστος. Δηλαδή δεν έχω απόδειξη ότι είναι όντως ο μικρότερος δυνατός αριθμός τηλεφωνημάτων.
Μαυρογιάννης

Το βέλτιστο είναι 2n-3. To σχήμα επικοινωνίας του Νίκου είναι η απάντηση με εξαίρεση ότι το τελευταίο τηλεφώνημα δεν χρειάζεται: Ο έμαθε όλα τα κουτσομπολιά ήδη από το πρώτο του τηλεφώνημα με τον .

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

Βασιζόμενος στα παραπάνω αλλά τροποποιώντας ελάχιστα ως προς την λεπτομέρεια που ανέφερα, να μία απόδειξη του βέλτιστου:

Εφόσον ο καθένας ξέρει ένα κουτσομπολιό, απαιτούνται n-1 τηλέφωνα ώστε ο καθένας να πεi κάπου την πληροφορία που ξέρει. Πριν από το (n-1)-οστό τηλεφώνημα κανείς δεν ξέρει όλες τις πληροφορίες, άρα ο καθένας πρέπει να ξαναμιλήσει τηλεφωνικά με κάποιον για να πληροφορηθεί και αυτά που δεν ξέρει. Μόλις κάποιος (άρα και ο συνομιλητής του) μάθει όλα τα κουτσομπολιά, χρειάζονται τουλάχιστον άλλα n-2 τηλεφωνήματα για να ακούσουν και οι υπόλοιποι όλα τα κουτσομπολιά. Άρα σύνολο τουλάχιστον (n-1)+(n-2)=2n-3 τηλεφωνήματα. Και επειδή η διαδικασία του Νίκου έβγαλε λύση με 2n-3, έχουμε βέλτιστη επικοινωνία.



Φιλικά,

Μιχάλης

Πολύ ωραία η παρατήρηση του Μιχάλη..
προσθέτω λοιπόν στην απόδειξη την παρατήρησή του.
ν-1 τηλεφωνήματα να το μάθει ένας. (του λείπουν ν-1 κομμάτια, και κάθε κομμάτι του μυστικού που του λείπει, θα πρέπει να έχει μετακινηθεί τουλάχιστον μια φορά για να έχει φτάσει εως αυτόν.)
παρατήρηση του Μιχάλη: Το μυστικό το μαθάινουν δύο ταυτόχρονα! (πράγματι, αυτός που το μαθαίνει όταν το μαθαίνει, μιλάει με κάποιον οπότε το μαθαίνει κι αυτός ο κάποιος)
άρα
οι υπόλοιποι ν-2 χρειάζονται τουλάχιστον άλλο ένα τηλεφώνημα. άρα άλλα ν-2 τηλεφωνήματα.
νομίζω τώρα διορθώθηκε.

Η βέλτιστη λύση του Νίκου επιτυγχάνεται και με άλλους τρόπους, πχ ορίζεται ένα απο τα άτομα σαν κεντρικός κόμβος στον οποίον μεταβιβάζονται όλες οι πληροφορίες με ν-1 τηλεφωνήματα και απο τον οποίον μετα παίρνουν ολοκληρωμένη την πληροφορία οι υπόλοιποι ν-2 σύμφωνα με την παρατήρηση του Μιχάλη

Έστω f(n) ο μικρότερος αριθμός τηλεφωνημάτων που απαιτείται για n άτομα
Είναι εύκολο να δούμε ότι f(1)=0, f(2)=1, f(3)=3 για n=4 έστω Α,Β,Γ,Δ τέσσερις κυρίες σύμφωνα με την εξης διαδικασία (Α—Β) (Γ—Δ) (Α—Γ) (Β—Δ) απαιτούνται 4 τηλεφωνήματα αρα f(4)=4. Με δεδομένο ότι f(4)=4 Για n>4 2n-4 είναι ο μικρότερος αριθμός τηλεφωνημάτων που απαιτούνται σύμφωνα με την παρακάτω διαδικασία: Μία από τις Α,Β,Γ,Δ τηλεφωνεί στις υπόλοιπες n-4 κυρίες, μετά οι 4 επικοινωνούν μεταξύ τους, στο σημείο αυτό οι 4 ξέρουν τα πάντα απαιτούνται ακόμη n-4 τηλεφωνήματα έτσι ώστε όλες να γνωρίζουν τα πάντα. (n-4)+4+(n-4)=2n-4 ο μικρότερος αριθμός τηλεφωνημάτων.

Σχόλιο: Όπως είπα τον γρίφο τον βρήκα στο internet. Στην αρχή εδωσα την λυση
2n-3 μετά όμως από μια μικρή ερευνά ανακάλυψα την παραπάνω απάντηση και μια αυστηρά μαθηματική θεμελίωση της. Στο συνημμένο υπάρχουν δύο αποδείξεις στα αγγλικά. Οι γνώσεις μου στα αγγλικά είναι από ελάχιστες εως ανύπαρκτες έτσι δεν μπορώ να μεταφράσω τις αποδείξεις. Αν σε κάποιο συνάδελφο είναι ευκολο και έχει τον χρόνο ας τις μεταφράσει. Μια αυτόματη μετάφραση που δοκίμασα έκανε το κείμενο πιο ακαταλαβίστικο από ότι είναι στα αγγλικά.