Φωταγώγηση πλατείας

#1

Η πλατεία μιας πόλης έχει σχήμα ορθογώνιο σχήμα $n \times m$ αποτελούμενη από $1 \times 1$ τετράγωνα. Για να φωταγωγηθεί η πλατεία θα τοποθετηθούν φανάρια στις γωνίες των τετραγώνων. (Επιτρέπεται η τοποθέτηση και σε γωνίες των τετραγώνων που βρίσκονται περιμετρικά της πλατείας.) Κάθε φανάρι φωτίζει όλα τα τετράγωνα στα οποία βρίσκεται στην γωνία τους. Θέλουμε να τοποθετήσουμε τα φανάρια με τέτοιο τρόπο ώστε να φωτίζονται όλα τα τετράγωνα ακόμη και αν καεί ένα από τα φανάρια.

Να βρεθεί ο ελάχιστος αριθμός φαναριών που πρέπει να τοποθετήσουμε.

#2

Υπάρχει καλύτερη λύση και σε άλλες περιπτώσεις.

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

Ίσως λίγο δύσκολη για Αρχιμήδη. Θα την μεταφέρω στο Προχωρημένο Επίπεδο.

Διονύσιος Αδαμόπουλος · #3

nikkru έγραψε: $\left \lceil \frac{(n+1)(m+1)}{2} \right \rceil$ .

Νομίζω ότι έχω βρει τον καλύτερο τύπο:

$\displaystyle(x+1)\left \lfloor \frac{(y+1)}{2} \right \rfloor$

όπου x, y

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

Π.χ. στην πλατεία $4 \times 6$ νομίζω πως αρκούν

φανάρια αντί για

που προκύπτουν από την παραπάνω λύση. Θα επανέρθω... όταν βρω λίγο χρόνο...

#4

Διονύσιος Αδαμόπουλος έγραψε:
Π.χ. στην πλατεία $4 \times 6$ νομίζω πως αρκούν φανάρια αντί για που προκύπτουν από την παραπάνω λύση. Θα επανέρθω... όταν βρω λίγο χρόνο...

Ναι για την $4 \times 6$ αυτό είναι το βέλτιστο.

Είσαι αρκετά κοντά και στον γενικό τύπο αλλά υπάρχουν ακόμη κάποιες περιπτώσεις όπου ο τύπος δεν δουλεύει. Π.χ. στην πλατεία $5 \times 6$ χρειάζονται μόνο

φώτα και όχι

. Χώρισέ το όπως είπες σε περιπτώσεις. Δεν είναι ανάγκη να δώσεις έναν τύπο για όλες τις περιπτώσεις.

Διονύσιος Αδαμόπουλος · #5

Demetres έγραψε:
Διονύσιος Αδαμόπουλος έγραψε:
Π.χ. στην πλατεία $4 \times 6$ νομίζω πως αρκούν φανάρια αντί για που προκύπτουν από την παραπάνω λύση. Θα επανέρθω... όταν βρω λίγο χρόνο...
Ναι για την $4 \times 6$ αυτό είναι το βέλτιστο.

Είσαι αρκετά κοντά και στον γενικό τύπο αλλά υπάρχουν ακόμη κάποιες περιπτώσεις όπου ο τύπος δεν δουλεύει. Π.χ. στην πλατεία $5 \times 6$ χρειάζονται μόνο φώτα και όχι . Χώρισέ το όπως είπες σε περιπτώσεις. Δεν είναι ανάγκη να δώσεις έναν τύπο για όλες τις περιπτώσεις.

Βασικά νομίζω ότι έχει να κάνει με την αρτιότητα του

(της μικρότερης πλευράς). Αν το

είναι άρτιο, τότε είναι ο τύπος που ανέφερα, δηλαδή $\displaystyle(x+1)\left \lfloor \frac{(y+1)}{2} \right \rfloor$ . Αν όμως το

είναι περιττό, τότε ο τύπος είναι $\displaystyle(y+1)\left \lfloor \frac{(x+1)}{2} \right \rfloor$ .

Πιο συγκεκριμένα, τοποθετώ τα φανάρια με τον εξής τρόπο:

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

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

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

περιπτώσεις της αρτιότητας ή "περιττότητας" των x, y

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

#6

Ναι, αυτή είναι η κατασκευή.

Μένει λοιπόν η απόδειξη ότι είναι όντως βέλτιστη.

#7

Περίπτωση 1:

Αν n = 2k+1

και $m = 2\ell + 1$ τότε χρωματίζουμε τα τετράγωνα της πλατείας όπως την σκακιέρα. Κάθε τετράγωνο θέλει τουλάχιστον δύο φανάρια. Επίσης δεν μπορεί ένα φανάρι να φωτίζει τετράγωνα διαφορετικού χρώματος. Επειδή έχουμε $(k+1)(\ell+1)$ τετράγωνα του ιδίου χρώματος χρειαζόμαστε τουλάχιστον $2(k+1)(\ell+1)$ φανάρια. Η κατασκευή του Διονύση δείχνει ότι μπορούμε να έχουμε τόσα φανάρια.

Περίπτωση 2:

Αν n = 2k+1

και $m = 2\ell$ τότε πάλι χρωματίζουμε όπως στην σκακιέρα. Τώρα έχουμε $\ell(k+1)$ τετράγωνα του ιδίου χρώματος που θέλουν $2\ell(k+1)$ φανάρια. Πάλι αυτό επιτυγχάνεται από την κατασκευή του Διονύση.

Περίπτωση 3: Αν

άρτιος,

περιττός αντιμετωπίζεται όπως στην περίπτωση 2.

Περίπτωση 4: Αν $n = 2k, m = 2\ell$ τότε χρωματίζουμε την πλατεία όπως στην πιο κάτω εικόνα (για m=4,n=6

.)

$\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(-0.52,-0.46) rectangle (6.44,4.44); \fill[fill=black,fill opacity=1.0] (0.,4.) -- (0.,3.) -- (1.,3.) -- (1.,4.) -- cycle; \fill[fill=black,fill opacity=1.0] (2.,4.) -- (2.,3.) -- (3.,3.) -- (3.,4.) -- cycle; \fill[fill=black,fill opacity=1.0] (4.,4.) -- (4.,3.) -- (5.,3.) -- (5.,4.) -- cycle; \fill[fill=black,fill opacity=1.0] (5.,3.) -- (5.,2.) -- (6.,2.) -- (6.,3.) -- cycle; \fill[fill=black,fill opacity=1.0] (0.,2.) -- (0.,1.) -- (1.,1.) -- (1.,2.) -- cycle; \fill[fill=black,fill opacity=1.0] (2.,2.) -- (2.,1.) -- (3.,1.) -- (3.,2.) -- cycle; \fill[fill=black,fill opacity=1.0] (3.,1.) -- (3.,0.) -- (4.,0.) -- (4.,1.) -- cycle; \fill[fill=black,fill opacity=1.0] (5.,1.) -- (5.,0.) -- (6.,0.) -- (6.,1.) -- cycle; \draw (0.,0.)-- (0.,4.); \draw (0.,4.)-- (6.,4.); \draw (6.,4.)-- (6.,0.); \draw (6.,0.)-- (0.,0.); \draw (0.,3.)-- (6.,3.); \draw (0.,2.)-- (6.,2.); \draw (0.,1.)-- (6.,1.); \draw (1.,4.)-- (1.,0.); \draw (2.,0.)-- (2.,4.); \draw (3.,4.)-- (3.,0.); \draw (4.,0.)-- (4.,4.); \draw (5.,4.)-- (5.,0.); \draw (0.,4.)-- (0.,3.); \draw (0.,3.)-- (1.,3.); \draw (1.,3.)-- (1.,4.); \draw (1.,4.)-- (0.,4.); \draw (2.,4.)-- (2.,3.); \draw (2.,3.)-- (3.,3.); \draw (3.,3.)-- (3.,4.); \draw (3.,4.)-- (2.,4.); \draw (4.,4.)-- (4.,3.); \draw (4.,3.)-- (5.,3.); \draw (5.,3.)-- (5.,4.); \draw (5.,4.)-- (4.,4.); \draw (5.,3.)-- (5.,2.); \draw (5.,2.)-- (6.,2.); \draw (6.,2.)-- (6.,3.); \draw (6.,3.)-- (5.,3.); \draw (0.,2.)-- (0.,1.); \draw (0.,1.)-- (1.,1.); \draw (1.,1.)-- (1.,2.); \draw (1.,2.)-- (0.,2.); \draw (2.,2.)-- (2.,1.); \draw (2.,1.)-- (3.,1.); \draw (3.,1.)-- (3.,2.); \draw (3.,2.)-- (2.,2.); \draw (3.,1.)-- (3.,0.); \draw (3.,0.)-- (4.,0.); \draw (4.,0.)-- (4.,1.); \draw (4.,1.)-- (3.,1.); \draw (5.,1.)-- (5.,0.); \draw (5.,0.)-- (6.,0.); \draw (6.,0.)-- (6.,1.); \draw (6.,1.)-- (5.,1.); \end{tikzpicture}$

Πιο συγκεκριμένα για την πλατεία $2k \times 2\ell$ με $k \leqslant \ell$ .

Στην πρώτη σειρά χρωματίζουμε $\ell$ τετράγωνα μαύρα εναλλάξ ξεκινώντας από αριστερά.
Στην τρίτη σειρά χρωματίζουμε $\ell-1$ τετράγωνα μαύρα εναλλάξ ξεκινώντας από αριστερά.
...
Στην 2k-1

σειρά χρωματίζουμε $\ell-k+1$ τετράγωνα μαύρα εναλλάξ ξεκινώντας από αριστερά.

Στην δεύτερη σειρά χρωματίζουμε

τετράγωνο μαύρο ξεκινώντας από δεξιά.
Στην τέταρτη σειρά χρωματίζουμε

τετράγωνα μαύρα ξεκινώντας από δεξιά.
...
Στην

σειρά χρωματίζουμε

τετράγωνα μαύρα ξεκινώντας από δεξιά.

Συνολικά χρωματίσαμε $k(\ell+1)$ μαύρα τετράγωνα. Κάθε ένα θέλει από

φανάρια. Μόνο που υπάρχουν

ζεύγη μαύρων τετραγώνων που μαζί αντί

φανάρια θέλουν μόνο

. Συνολικά λοιπόν χρειάζονται $2k(\ell+1)-k = k(2\ell+1)$ φανάρια. Πάλι η τοποθέτηση του Διονύση χρησιμοποιεί μόνο τόσο φανάρια.

Επεξεργασία: Προσθέτω και την πηγή.

Φωταγώγηση πλατείας

Φωταγώγηση πλατείας

Re: Φωταγώγηση πλατείας

Re: Φωταγώγηση πλατείας

Re: Φωταγώγηση πλατείας

Re: Φωταγώγηση πλατείας

Re: Φωταγώγηση πλατείας

Re: Φωταγώγηση πλατείας

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