Διάδοση ασθένειας 2

Συντονιστές: cretanman, Demetres, polysot, achilleas, socrates, silouan

GVlachos
Δημοσιεύσεις: 126
Εγγραφή: Κυρ Μαρ 13, 2011 8:04 pm

Διάδοση ασθένειας 2

#1

Μη αναγνωσμένη δημοσίευση από GVlachos » Τετ Ιουν 08, 2011 6:23 pm

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

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

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


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


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11881
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Διάδοση ασθένειας 2

#2

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Ιουν 08, 2011 7:51 pm

Απάντηση: 2011.

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

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

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

Φιλικά,

Μιχάλης Λάμπρου
Συνημμένα
molinsi.JPG
molinsi.JPG (7.31 KiB) Προβλήθηκε 699 φορές


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8346
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Διάδοση ασθένειας 2

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Ιουν 08, 2011 8:00 pm

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

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

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


Απάντηση

Επιστροφή σε “Άλγεβρα - Θεωρία Αριθμών - Συνδυαστική (Seniors) - Παλαιότερες Συζητήσεις”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης