Θέμα από την ολυμπιάδα της Ουκρανίας 2015

petros r · #1

Έστω μια σκακιέρα $8\times 8$ που αποτελείται από λευκά κελιά.Σε μια κίνηση ο Δημήτρης μπορεί να επιλέξει ένα $2\times 2$ τετράγωνο της σκακιέρας αυτής που αποτελείται μόνο από λευκά κελιά και να χρωματίσει δυο κελιά από αυτό, τα οποία θα βρίσκονται στην διαγώνιο του. Ποιος είναι ο μέγιστος αριθμός μαύρων κελιών που μπορούν να χρωματιστούν από τον Δημήτρη;

#2

Επαναφορά!

#3

Ο μέγιστος αριθμός είναι

.

Θεώρημα 1: Σε μια $2^n \times 2^n$ σκακιέρα μπορούμε να μαυρίσουμε $\displaystyle{ a_n = \frac{2}{3}(4^n-1)}$ κελιά. Επιπλέον μπορούμε να έχουμε όλα τα γωνιακά κελιά λευκά εκτός από την περίπτωση n=1

όπου έχουμε δύο αντιδιαμετρικά γωνιακά κελιά λευκά.

Απόδειξη: Για n=1

είναι προφανές. Έστω ότι ισχύει για n=k

και έστω ότι έχουμε μια $2^{k+1} \times 2^{k+1}$ σκακιέρα. Την μοιράζουμε σε τέσσερις $2^k \times 2^k$ σκακιέρες στις οποίες μπορούμε να μαυρίσουμε από a_k

κελιά. Επίσης μπορούμε να το κάνουμε με τέτοιο τρόπο ώστε τα τέσσερα κεντρικά κελιά καθώς και όλα τα γωνιακά να είναι λευκά. Εφόσον τα τέσσερα κεντρικά κελιά είναι λευκά μπορούμε να μαυρίσουμε δύο από αυτά. Συνολικά λοιπόν τώρα τα λευκά κελιά είναι $4a_k + 2 = a_{k+1}$ .

Μένει τώρα να δείξουμε ότι δεν μπορούμε να μαυρίσουμε περισσότερα κελιά. Αυτό είναι και το «δύσκολο» κομμάτι του θέματος .

Η σκακιέρα έχει

τετράγωνα της μορφής $2\times 2$ . Τα σκεφτόμαστε σαν κελιά μιας $7\times 7$ σκακιέρας. Θα δείξουμε ότι μπορούμε να επιλέξουμε το πολύ

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

Παρατήρηση 1: Δεν μπορούμε να επιλέξουμε δύο γειτονικά κελιά.

Απόδειξη: Προφανές διότι όποιο και να επιλέξει πρώτο, και όποια κελιά του αντίστοιχου $2\times 2$ τετραγώνου και να χρωματίσουμε, θα χρωματιστεί τουλάχιστον και ένα κελί από το $2 \times 2$ τετράγωνο που αντιστοιχεί στο δεύτερο.

Παρατήρηση 2: Δεν μπορούμε να επιλέξουμε τέσσερα κελιά τα οποία να είναι γειτονικά σε ένα κελί.

Απόδειξη: Χωρίς βλάβη της γενικότητας το πρώτο κελί που επιλέγουμε είναι το αριστερά. Επίσης χωρίς βλάβη της γενικότητας χρωματίζουμε το άνω αριστερά και κάτω δεξιά κελί του αντίστοιχου $2 \times 2$ τετραγώνου. Τότε το $2 \times 2$ τετράγωνο που αντιστοιχεί στο κάτω κελί δεν μπορεί να χρωματιστεί.

Παρατήρηση 3: Σε κάθε $3 \times 3$ τετράγωνο της $7 \times 7$ σκακιέρας μπορούμε να επιλέξουμε το πολύ

κελιά. Σε αυτήν την περίπτωση πρέπει να τα επιλέξουμε όπως στο πιο κάτω σχήμα.

$\begin{tikzpicture} \fill[fill=black,fill opacity=1.0] (0.,1.) -- (0.,0.) -- (1.,0.) -- (1.,1.) -- cycle; \fill[fill=black,fill opacity=1.0] (0.,3.) -- (0.,2.) -- (1.,2.) -- (1.,3.) -- cycle; \fill[fill=black,fill opacity=1.0] (2.,3.) -- (2.,2.) -- (3.,2.) -- (3.,3.) -- cycle; \fill[fill=black,fill opacity=1.0] (2.,1.) -- (2.,0.) -- (3.,0.) -- (3.,1.) -- cycle; \fill[fill=black,fill opacity=1.0] (1.,2.) -- (1.,1.) -- (2.,1.) -- (2.,2.) -- cycle; \draw (0.,0.)-- (0.,3.); \draw (0.,3.)-- (3.,3.); \draw (3.,3.)-- (3.,0.); \draw (3.,0.)-- (0.,0.); \draw (0.,1.)-- (3.,1.); \draw (0.,2.)-- (3.,2.); \draw (1.,3.)-- (1.,0.); \draw (2.,3.)-- (2.,0.); \draw (0.,1.)-- (0.,0.); \draw (0.,0.)-- (1.,0.); \draw (1.,0.)-- (1.,1.); \draw (1.,1.)-- (0.,1.); \draw (0.,3.)-- (0.,2.); \draw (0.,2.)-- (1.,2.); \draw (1.,2.)-- (1.,3.); \draw (1.,3.)-- (0.,3.); \draw (2.,3.)-- (2.,2.); \draw (2.,2.)-- (3.,2.); \draw (3.,2.)-- (3.,3.); \draw (3.,3.)-- (2.,3.); \draw (2.,1.)-- (2.,0.); \draw (2.,0.)-- (3.,0.); \draw (3.,0.)-- (3.,1.); \draw (3.,1.)-- (2.,1.); \draw (1.,2.)-- (1.,1.); \draw (1.,1.)-- (2.,1.); \draw (2.,1.)-- (2.,2.); \draw (2.,2.)-- (1.,2.); \end{tikzpicture}$

Απόδειξη: Άμεσο από την Παρατήρηση 1 (και την αρχή του περιστερώνα).

Παρατήρηση 4: Σε κάθε $4 \times 4$ τετράγωνο της $7 \times 7$ σκακιέρας μπορούμε να επιλέξουμε το πολύ

κελιά.

Απόδειξη: Αν μπορούσαμε να επιλέξουμε περισσότερα, θα ήταν

και χωρίς βλάβη της γενικότητας θα ήταν όπως πιο κάτω

$\begin{tikzpicture} \fill[fill=black,fill opacity=1.0] (0.,1.) -- (0.,0.) -- (1.,0.) -- (1.,1.) -- cycle; \fill[fill=black,fill opacity=1.0] (0.,3.) -- (0.,2.) -- (1.,2.) -- (1.,3.) -- cycle; \fill[fill=black,fill opacity=1.0] (2.,3.) -- (2.,2.) -- (3.,2.) -- (3.,3.) -- cycle; \fill[fill=black,fill opacity=1.0] (2.,1.) -- (2.,0.) -- (3.,0.) -- (3.,1.) -- cycle; \fill[fill=black,fill opacity=1.0] (1.,2.) -- (1.,1.) -- (2.,1.) -- (2.,2.) -- cycle; \fill[fill=black,fill opacity=1.0] (3.,2.) -- (4.,2.) -- (4.,1.) -- (3.,1.) -- cycle; \draw (0.,0.)-- (0.,3.); \draw (0.,3.)-- (3.,3.); \draw (3.,3.)-- (3.,0.); \draw (3.,0.)-- (0.,0.); \draw (0.,1.)-- (3.,1.); \draw (0.,2.)-- (3.,2.); \draw (1.,3.)-- (1.,0.); \draw (2.,3.)-- (2.,0.); \draw (0.,1.)-- (0.,0.); \draw (0.,0.)-- (1.,0.); \draw (1.,0.)-- (1.,1.); \draw (1.,1.)-- (0.,1.); \draw (0.,3.)-- (0.,2.); \draw (0.,2.)-- (1.,2.); \draw (1.,2.)-- (1.,3.); \draw (1.,3.)-- (0.,3.); \draw (2.,3.)-- (2.,2.); \draw (2.,2.)-- (3.,2.); \draw (3.,2.)-- (3.,3.); \draw (3.,3.)-- (2.,3.); \draw (2.,1.)-- (2.,0.); \draw (2.,0.)-- (3.,0.); \draw (3.,0.)-- (3.,1.); \draw (3.,1.)-- (2.,1.); \draw (1.,2.)-- (1.,1.); \draw (1.,1.)-- (2.,1.); \draw (2.,1.)-- (2.,2.); \draw (2.,2.)-- (1.,2.); \draw (3.,2.)-- (4.,2.); \draw (4.,2.)-- (4.,1.); \draw (4.,1.)-- (3.,1.); \draw (3.,1.)-- (3.,2.); \draw (3.,3.)-- (4.,3.); \draw (4.,3.)-- (4.,0.); \draw (4.,0.)-- (3.,0.); \end{tikzpicture}$

Αυτό όμως είναι αδύνατον από την Παρατήρηση 2.

Χωρίζουμε τώρα την $7 \times 7$ σκακιέρα όπως πιο κάτω.

$\begin{tikzpicture} \draw (7.,0.)-- (0.,0.); \draw (0.,7.)-- (0.,0.); \draw (0.,7.)-- (7.,7.); \draw (7.,7.)-- (7.,0.); \draw (0.,4.)-- (4.,4.); \draw (4.,4.)-- (4.,7.); \draw (3.,4.)-- (3.,0.); \draw (3.,3.)-- (7.,3.); \draw (4.,4.)-- (4.,3.); \end{tikzpicture}$

Κάθε ένα από τα ορθογώνια είναι της μορφής $3 \times 4$ ή $4 \times 3$ . Από την Παρατήρηση

σε αυτά μπορούμε να επιλέξουμε συνολικά το πολύ

κελιά. Οπότε στην $7 \times 7$ σκακιέρα μπορούμε να επιλέξουμε το πολύ

κελιά και η απόδειξη ολοκληρώθηκε.

Θέμα από την ολυμπιάδα της Ουκρανίας 2015

Θέμα από την ολυμπιάδα της Ουκρανίας 2015

Re: Θέμα από την ολυμπιάδα της Ουκρανίας 2015

Re: Θέμα από την ολυμπιάδα της Ουκρανίας 2015

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