mathematica.gr

Κάποια κελιά ενός πίνακα έχουν μολυνθεί από μια ασθένεια. Η ασθένεια επεκτείνεται και στα υπόλοιπα κελιά με βάση τον ακόλουθο κανόνα:

Για κάθε τέσσερα γειτονικά κελιά που σχηματίζουν ένα υποπίνακα, αν τα τρία είναι μολυσμένα, τότε μολύνεται και το τέταρτο.

Να υπολογιστεί ο ελάχιστος αριθμός μολυσμένων κελιών ώστε να μπορούν να μολύνουν με βάση τον πιο πάνω κανόνα όλα τα υπόλοιπα κελιά.

Κάθε τετραγωνάκι μπορεί να χρησιμοποιηθεί το πολύ μία φορά για να μολύνει κάποιο κελί. Άρα αφού ο πίνακας έχει τετραγωνάκια θα χρειαστούμε τουλάχιστον μολυσμένα κελιά αρχικά, αφού στη συνέχεια μπορεί να μολυνθούν το πολύ κελιά. Εύκολα βλέπουμε ότι αν αρχικά η μία διαγώνιος του πίνακα και τα σημεία που βρίσκονται ακριβώς από κάτω της είναι αρχικά μολυσμένα, ο πίνακας τελικά θα μολυνθεί ολόκληρος.

Πότε πρόλαβες; Παρά την απλότητα της απάντησης δεν το θεωρώ εύκολο πρόβλημα.