'Ενα ωραίο πρόβλημα "φαντασίας" του μαθηματικού Béla Bollobás. Σε έναν κάναβο διαστάσεων n X n εξαπλώνεται μια "επιδημία". Κάποια τετράγωνα είναι "Μολυσμένα" και κάποια είναι "Υγιή".
Για παράδειγμα, στον 12 Χ 12 κάναβο του σχήματος, τα μαύρα τετράγωνα είναι μολυσμένα, τα άσπρα είναι τα υγιή και τα γκρίζα με το Χ είναι ας πούμε τα "προγραμμένα". Στον επόμενο γύρο ,όλα τα γκρίζα θα μολυνθούν και θα γίνουν μαύρα.
Ποιος είναι ο μικρότερος αριθμός από αρχικώς μολυσμένα (μαύρα) τετράγωνα που μπορούν να εξαπλώσουν τη μόλυνση σε ολόκληρο το πλέγμα nXn;
Χωρίς να το πολυ-βασανίσω, (με την βοήθεια του MASTER για τον σχεδιασμό ενός πλέγματος 8χ8), εύκολα φαίνεται ότι σε πλέγμα nXn, n μολυσμένα τετράγωνα στη μία διαγώνιο αρκούν για να μολύνουν όλα τα τετράγωνα του πλέγματος.
ΑπάντησηΔιαγραφήΜετά την τοποθέτηση των n μολυσμένων τετραγώνων διαγωνίως,
στον 1ο "γύρο" θα μολυνθούν τα (n-1) + (n-1) ένθεν και ένθεν των n, στον 2ο "γύρο" (τα n-2) + (n-2) , ένθεν και ένθεν των (n-1) kai (n-1),.., κ.ο.κ μέχρι τα τελευταία γωνιακά n-(n-1)=1 και n-(n-1)=1 στον (n-1)-οστό "γύρο".
Βασανίζοντας αρκετά το θέμα τείνω να "πιστεύω" ότι στο πλέγμα
ΑπάντησηΔιαγραφήnXn, τα n αρχικώς μολυσμένα τετράγωνα
Όχι απλώς " αρκούν για να μολύνουν όλα τα τετράγωνα του πλέγματος" αλλά είναι και ο μικρότερος απαιτούμενος αριθμός.
Μπορούν δε να τοποθετηθούν με πάμπολλους τρόπους, τμηματικά λοξά/διαγώνια με την προϋπόθεση σε κάθε γραμμή και κάθε στήλη τετραγώνων να υπάρχει μόνο ένα μολυσμένο τετράγωνο.
(Και αυθόρμητα γεννιέται το ερώτημα: Υπολογίζονται όλοι οι δυνατοί τρόποι τοποθέτησης των n αρχικώς μολυσμένων τετραγώνων?)
Ευχαριστώ για τα εμπνευσμένα σχόλια κύριε Αλεξίου!
ΑπάντησηΔιαγραφήΤο πρόσθετο ερώτημα/προβληματισμός που έβαλες είναι πολύ ενδιαφέρον ,όπως ενδιαφέρουσα είναι και η "χρονική παράμετρος" του προβλήματος, δηλαδή σε πόσους γύρους/βήματα επιτυγχάνεται η ολική μόλυνση της σκακιέρας, από κάποιον συγκεκριμένο αρχικό σχηματισμό;
Καταρχάς , μιας και το πρόβλημα προέρχεται από γνωστές μαθηματικές ιδέες και μέθοδες ,τα "Κυταρικά αυτόματα"(Cellular automaton) του Νόϋμαν ,και τη Θεωρία των percolations (Διηθήσεις) φαντάζομαι ότι θα υπάρχει κάποια αυστηρά φορμαλιστική μαθηματική απόδειξη πως ο ελάχιστος αριθμός είναι όντως 12 ,ή n γενικά. Δεν έχω προσωπικά υπόψι τέτοια απόδειξη,αλλά τα επιχειρήματα που έδειξε ο Ε.Αλεξίου νομίζω είναι υπεραρκετά για μία "διαισθητική"μεν , αλλά πανίσχυρη λογικά απόδειξη.
Καταρχάς, το "αναγκαίο" είναι φανερό ότι ισχύει.
Με τη διαγώνιο μήκους n είναι προφανές ότι πετυχαίνουμε ολική μόλυνση.Στο πρώτο βήμα 2n-2 τετρ. ένθεν κι ένθεν της διαγωνίου, στο επόμενο 2n-4, κ.λ.π.
Ολικός αριθμός βημάτων :n-1.
Στην περίπτωση 12 Χ 12 δηλαδή, σε 11 βήματα μολύνεται όλη η σκακιέρα.
Το "ικανό" τώρα ,είναι κάπως πιο λεπτό, αλλά νομίζω πως η απλή παρατήρηση πως η ΣΥΝΟΛΙΚΗ ΠΕΡΙΜΕΤΡΟΣ μιας οποιαδήποτε μολυσμένης περιοχής ΔΕΝ μεταβάλλεται από μια χρονική στιγμή t στο επόμενο βήμα t+1,λύνει το κυρίως θέμα, που είναι αν ο αριθμός n είναι το κατώτατο όριο ή όχι.
Αν δηλαδή για παράδειγμα πάρουμε οποιοδήποτε τετράγωνο ή ορθογώνιο ή τυχαίο υποσύνολο γειτνιαζόντων τετραγώνων ,η περίμετρος που ορίζουν τα "ακραία/περιμετρικά" τετράγωνα ορίζει και το συνολικό εμβαδόν μόλυνσης. Εφόσον η περιοχή που θέλουμε να μολυνθεί λοιπόν αντιστοιχεί σε περίμετρο=48 ή 4n στη γενική περίπτωση, τόση πρέπει να είναι κατ'ελάχιστον και η περίμετρος της αρχικά μολυσμένης περιοχής. Προφανώς,αρκούν 48/4 ή 4n/4=n αρχικά τετράγωνα, και για να έχουμε μόνο disjoint(μη αλληλοτεμνόμενες) περιοχές η "ελάχιστη" οικονομική 'Ενωση" αυτών των συνόλων είναι όλο το τετράγωνο. Kαι η διαγώνιός του ορίζει με τον "οικονομικότερο" τρόπο την επιθυμητή περίμετρο, άρα είναι η βέλτιστη λύση (αυτή με τα λιγότερα αρχικά "μαύρα", που κάνουν τη δουλειά)
Έτσι,και για τον πρόσθετο προβληματισμό, όπως το βλέπω δεν υπάρχουν άλλοι "ελάχιστοι" συνδυασμοί τετραγώνων(n) ,εκτός από τις δύο κύριες διαγώνιες.
Εννοούσα στο από πάνω σχόλιο, "η περίμετρος του ΟΡΘΟΓΩΝΙΟΥ που ορίζει μια ακολουθία "ακραίων/περιμετρικών" μαύρων δεν μεταβάλλεται"
ΔιαγραφήΑν ζητούμενο είναι “ο μικρότερος αριθμός από αρχικώς μολυσμένα (μαύρα) τετράγωνα που μπορούν να εξαπλώσουν τη μόλυνση σε ολόκληρο το πλέγμα nXn” με τα λιγότερα
ΑπάντησηΔιαγραφήβήματα (n-1), τότε μόνον οι ελάχιστοι συνδυασμοί είναι στις δύο κύριες διαγώνιες.
Αν ζητούμενο είναι μόνο ο μικρότερος αριθμός μολυσμένων ανεξαρτήτως των βημάτων που θα χρειασθούν για να μολυνθεί όλο το πλέγμα τετραγώνων, όπως εδώ, και σε αυτό αναφερόμουν τότε επέτρεψε μου να επιμείνω, οι συνδυασμοί είναι πολλοί, πάρα πολλοί και ο χρόνος-βήματα διαφέρει ανάλογα με τις περιπτώσεις αλλά μπορεί να προσδιορισθεί.
Τέτοιους συνδυασμούς μπορούμε να σχηματίσουμε με:
2 διαγώνιες d1 kai d2, di+d2=n, παράλληλες ή κάθετες μεταξύ τους,
3 διαγώνιες d1, d2, d3, d1+d2+d3=n, παράλληλες ή κάθετες ανά δύο,
κ.ο.κ 4,5,...,κ ή κ+1(για πλέγμα n=2κ ή n=2κ+1) διαγώνιες, παράλληλες ή κάθετες ανά δύο.
Στην ουσία χωρίζουμε το πλέγμα σε 2,3,4,... τετράγωνα με μία κοινή κορυφή και συμπληρωματικά ορθογώνια.
Αρχικά εξαπλώνεται η επιδημία στα τετράγωνα μέχρι να μολυνθεί και το μεγαλύτερο από αυτά, maxdi, απαιτούμενος χρόνος-βήματα γιαυτό maxdi-1
και στην συνέχεια η επιδημία εξαπλώνεται στα ορθογώνια, σε βήματα (n-di)+(di-1)=n-1
Άρα συνολικός χρόνος (maxdi-1)+(n-1)= maxdi+n-2
O μεγαλύτερος χρόνος απαιτείται αν χωρίσουμε το πλέγμα σε 2 τετράγωνα, 1Χ1 και (n-1)*(n-1) kai τα αντίστοιχα 2 ορθογώνια 1*(n-1) kai (n-1)*1 και είναι n-1+n-2=2n-3 βήματα
Ανεξάρτητα από τα παραπάνω, η “οικονομικότερη” λύση συνολικά σε τετράγωνα και βήματα είναι, φυσικά, n τετράγωνα στις κύριες διαγώνιες σε (n-1) βήματα
Πράγματι ωραίο πρόβλημα φαντασίας, χωρίς ιδιαίτερους τύπους και κανόνες!
Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΣτέλνω γραφική απεικόνιση πλέγματος 5χ5(Μ=μαύρο Α=άσπρο) με τον ελάχιστο αρχικό αριθμό μολυσμένων τετραγώνων (5) αλλά όχι στον ελάχιστο αριθμό βημάτων (4)
ΑπάντησηΔιαγραφήΑ
M A A A A....M A A A A.....M A A A A....M A A A A
A A A A M...A A A Μ M.....A A Μ Μ M...A Μ Μ Μ M
A A A M A...A A Μ M Μ... A Μ Μ M Μ...A Μ Μ M Μ
A A M A A...A Μ M Μ A... A Μ M Μ Μ...A Μ M Μ Μ
A Μ A A Α...A Μ Μ A A... A Μ Μ Μ A...A Μ Μ Μ Μ
M Μ A A A....M Μ Μ Α A...M Μ Μ Μ A...M Μ Μ Μ Μ
Μ Μ Μ Μ M...Μ Μ Μ Μ M...Μ Μ Μ Μ M...Μ Μ Μ Μ M
A Μ Μ M Μ...Μ Μ Μ M Μ...Μ Μ Μ M Μ...Μ Μ Μ M Μ
A Μ M Μ Μ...A Μ M Μ Μ...Μ Μ M Μ Μ...Μ Μ Μ M Μ
A Μ Μ Μ Μ...A Μ Μ Μ Μ...Α Μ Μ M Μ...Μ Μ Μ M Μ
Βήματα 7(2*5-3, 2ν-3)
Β
M A A A A..M A A A A...M Μ A A A...M Μ Μ A A...
A A Μ A Α..A Μ Μ A Α..Μ Μ Μ A Α..Μ Μ Μ Μ Α..
A Μ A Α A..A Μ Μ Α A..A Μ Μ Μ A..Μ Μ Μ Μ Μ..
A A Α A Μ..A A Α Μ Μ..A A Μ Μ Μ..A Μ Μ Μ Μ..
A Α A Μ Α..A Α A Μ Μ..A Α A Μ Μ..A Α Μ Μ Μ..
M Μ Μ Μ A..M Μ Μ Μ Μ
Μ Μ Μ Μ Μ..Μ Μ Μ Μ Μ
Μ Μ Μ Μ Μ..Μ Μ Μ Μ Μ
Μ Μ Μ Μ Μ..Μ Μ Μ Μ Μ
A Μ Μ Μ Μ..Μ Μ Μ Μ Μ
Βήματα 5((2-1)+(5-1)), (max(κ-1),(n-1))
κ.ο.κ για τους παρακάτω συνδυασμούς
και όχι μόνο αυτούς
Γ...................Δ.................Ε
Α Μ A A A... Α Μ A A A... Α Μ A A A
Μ A A A Α... Μ A A A Α... Μ A A A Α
A A A A Μ... A A Μ Α Α... A A Μ Α Α
A A A Μ A... A A Α Α Μ... A A Α Μ Α
A Α Μ A Α... A Α Α Μ Α... A Α Α Α Μ