Putnam 2016/A4

#1

Δίνεται μια $(2m-1)\times(2n-1)$ σκακιέρα όπου οι

και

είναι ακέραιοι με $m,n\geqslant 4.$ Θέλουμε να καλύψουμε την σκακιέρα χρησιμοποιώντας σχήματα της πιο κάτω μορφής:

$\displaystyle{ \begin{picture}(140,40) \put(0,0){\line(0,1){40}} \put(0,0){\line(1,0){20}} \put(0,40){\line(1,0){40}} \put(20,0){\line(0,1){20}} \put(20,20){\line(1,0){20}} \put(40,20){\line(0,1){20}} \multiput(0,20)(5,0){4}{\line(1,0){3}} \multiput(20,20)(0,5){4}{\line(0,1){3}} \put(80,0){\line(1,0){40}} \put(120,0){\line(0,1){20}} \put(120,20){\line(1,0){20}} \put(140,20){\line(0,1){20}} \put(80,0){\line(0,1){20}} \put(80,20){\line(1,0){20}} \put(100,20){\line(0,1){20}} \put(100,40){\line(1,0){40}} \multiput(100,0)(0,5){4}{\line(0,1){3}} \multiput(100,20)(5,0){4}{\line(1,0){3}} \multiput(120,20)(0,5){4}{\line(0,1){3}} \end{picture} }$

(Οι διακεκομμένες γραμμές χωρίζουν τα σχήματα σε $1\times 1$ κελιά.) Τα σχήματα μπορούν να περιστραφούν και να ανακλαστούν αρκεί να τοποθετηθούν ώστε να καλύπτουν κελιά της σκακιέρας.

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

nikkru · #2

Demetres έγραψε:Δίνεται μια $(2m-1)\times(2n-1)$ σκακιέρα όπου οι και είναι ακέραιοι με $m,n\geqslant 4.$ Θέλουμε να καλύψουμε την σκακιέρα χρησιμοποιώντας σχήματα της πιο κάτω μορφής:

$\displaystyle{ \begin{picture}(140,40) \put(0,0){\line(0,1){40}} \put(0,0){\line(1,0){20}} \put(0,40){\line(1,0){40}} \put(20,0){\line(0,1){20}} \put(20,20){\line(1,0){20}} \put(40,20){\line(0,1){20}} \multiput(0,20)(5,0){4}{\line(1,0){3}} \multiput(20,20)(0,5){4}{\line(0,1){3}} \put(80,0){\line(1,0){40}} \put(120,0){\line(0,1){20}} \put(120,20){\line(1,0){20}} \put(140,20){\line(0,1){20}} \put(80,0){\line(0,1){20}} \put(80,20){\line(1,0){20}} \put(100,20){\line(0,1){20}} \put(100,40){\line(1,0){40}} \multiput(100,0)(0,5){4}{\line(0,1){3}} \multiput(100,20)(5,0){4}{\line(1,0){3}} \multiput(120,20)(0,5){4}{\line(0,1){3}} \end{picture} }$

(Οι διακεκομμένες γραμμές χωρίζουν τα σχήματα σε $1\times 1$ κελιά.) Τα σχήματα μπορούν να περιστραφούν και να ανακλαστούν αρκεί να τοποθετηθούν ώστε να καλύπτουν κελιά της σκακιέρας.

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

Μια λύση για m=n=4

είναι η επόμενη.

: Α4.png (3.59 KiB) Προβλήθηκε 1135 φορές

Κάθε σχήμα καταλαμβάνει το πολύ δύο διαδοχικά τετράγωνα είτε οριζόντια είτε κάθετα.

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

Έτσι χρειαζόμαστε τουλάχιστον $4\cdot4=16$ σχήματα, δηλαδή ο ελάχιστος αριθμός σχημάτων είναι

.

Για $(2m-1)\times(2n-1)$ σκακιέρα, μετρώντας πάλι ένα παρά 'ένα τα κελιά, έχουμε κάθετα

κελιά και οριζόντια

κελιά.

Επομένως ο ελάχιστος αριθμός των σχημάτων που χρειαζόμαστε σε $(2m-1)\times(2n-1)$ σκακιέρα είναι $m\times n$ .

Putnam 2016/A4

Putnam 2016/A4

Re: Putnam 2016/A4

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