Putnam 2016/A4

Συντονιστής: Demetres

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

Putnam 2016/A4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιαν 02, 2017 12:15 am

Δίνεται μια (2m-1)\times(2n-1) σκακιέρα όπου οι m και n είναι ακέραιοι με 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
Δημοσιεύσεις: 336
Εγγραφή: Σάβ Δεκ 26, 2009 6:42 pm

Re: Putnam 2016/A4

#2

Μη αναγνωσμένη δημοσίευση από nikkru » Τρί Ιαν 03, 2017 12:43 am

Demetres έγραψε:Δίνεται μια (2m-1)\times(2n-1) σκακιέρα όπου οι m και n είναι ακέραιοι με 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
Α4.png (3.59 KiB) Προβλήθηκε 429 φορές
Κάθε σχήμα καταλαμβάνει το πολύ δύο διαδοχικά τετράγωνα είτε οριζόντια είτε κάθετα.

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

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

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

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


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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