♟️ Η «Μόλυνση» της Σκακιέρας – Ένα Έξυπνο Πρόβλημα από το KVANT

♟️ Πόσα Τετράγωνα Χρειάζονται για να «Μολυνθεί» Όλη η Σκακιέρα;

Ένα όμορφο πρόβλημα από το σοβιετικό μαθηματικό περιοδικό KVANT (1986).

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

Για παράδειγμα, αν αρχικά μολυνθούν τα \(n\) τετράγωνα της κύριας διαγωνίου, η μόλυνση μπορεί σταδιακά να εξαπλωθεί στις γειτονικές διαγωνίους και τελικά σε ολόκληρη τη σκακιέρα.

Αποδείξτε ότι ολόκληρη η σκακιέρα δεν μπορεί να μολυνθεί αν αρχικά υπάρχουν λιγότερα από \(n\) μολυσμένα τετράγωνα.

🔍 Δείτε την ιδέα της απόδειξης

Το κλειδί είναι να παρακολουθήσουμε όχι το πλήθος των μολυσμένων τετραγώνων, αλλά την περίμετρο της μολυσμένης περιοχής.

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

Άρα η συνολική περίμετρος της μολυσμένης περιοχής δεν μπορεί ποτέ να αυξηθεί.

Αν αρχικά υπάρχουν \(k\) μολυσμένα τετράγωνα, η συνολική περίμετρός τους είναι το πολύ

\[ 4k. \]

Αν τελικά μολυνθεί ολόκληρη η \(n\times n\) σκακιέρα, η περίμετρος θα είναι

\[ 4n. \]

Εφόσον η περίμετρος δεν μπορεί να αυξηθεί, πρέπει

\[ 4k\ge 4n, \]

και συνεπώς

\[ \boxed{k\ge n}. \]

Άρα απαιτούνται τουλάχιστον \(n\) αρχικά μολυσμένα τετράγωνα.

Πηγή: KVANT, 1986

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →