mathematica.gr

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

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

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


Το πρόβλημα αυτό το εμπνεύστηκα από το πρόβλημα εδώ(viewtopic.php?f=111&t=16299), για αυτό μοιάζουν και τόσο πολύ οι εκφωνήσεις.

Απάντηση: 2011.

Αν τα 2011 κελιά της διαγωνίου είναι μολυσμένα, τότε εύκολα βλέπουμε ότι μολύνονται όλα.

Θα δείξουμε ότι αν τα μολυσμένα είναι 2010 ή λιγότερα, τότε αποκλείεται να μολυνθούν όλα.

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

Φιλικά,

Μιχάλης Λάμπρου

Η λύση του Μιχάλη λύνει και αυτό το πρόβλημα.

Σκόπευα να το βάλω και εδώ αλλά πλέον δεν υπάρχει λόγος.

Για το πρόβλημα του Γιώργου υπάρχει και η εξής πιο απλή λύση: Αν μια σειρά δεν έχει μολυσμένο τετραγωνάκι, τότε δεν θα αποκτήσει ποτέ μολυσμένο τετραγωνάκι. Επομένως απαιτούνται τουλάχιστον 2011 μολυσμένα τετραγωνάκια.