Διάδοση ασθένειας (Δ. 7)

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

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

Διάδοση ασθένειας (Δ. 7)

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιουν 06, 2011 4:37 pm

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

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

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


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

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

#2

Μη αναγνωσμένη δημοσίευση από GVlachos » Δευ Ιουν 06, 2011 4:56 pm

Κάθε τετραγωνάκι 2x2 μπορεί να χρησιμοποιηθεί το πολύ μία φορά για να μολύνει κάποιο κελί. Άρα αφού ο πίνακας έχει 2010^2 τετραγωνάκια 2x2 θα χρειαστούμε τουλάχιστον 2011^2-2010^2=2010+2011=4021 μολυσμένα κελιά αρχικά, αφού στη συνέχεια μπορεί να μολυνθούν το πολύ 2010^2 κελιά. Εύκολα βλέπουμε ότι αν αρχικά η μία διαγώνιος του πίνακα και τα 2010 σημεία που βρίσκονται ακριβώς από κάτω της είναι αρχικά μολυσμένα, ο πίνακας τελικά θα μολυνθεί ολόκληρος.


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

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

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιουν 06, 2011 5:31 pm

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


Απάντηση

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

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

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