Επιδημία

'Ενα ωραίο πρόβλημα "φαντασίας" του μαθηματικού Béla Bollobás. Σε έναν κάναβο διαστάσεων n X n εξαπλώνεται μια "επιδημία". Κάποια τετράγωνα είναι "Μολυσμένα" και κάποια είναι "Υγιή".

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

Για παράδειγμα, στον 12 Χ 12 κάναβο του σχήματος, τα μαύρα τετράγωνα είναι μολυσμένα, τα άσπρα είναι τα υγιή και τα γκρίζα με το Χ είναι ας πούμε τα "προγραμμένα". Στον επόμενο γύρο ,όλα τα γκρίζα θα μολυνθούν και θα γίνουν μαύρα.

Ποιος είναι ο μικρότερος αριθμός από αρχικώς μολυσμένα (μαύρα) τετράγωνα που μπορούν να εξαπλώσουν τη μόλυνση σε ολόκληρο το πλέγμα nXn;