Προβλήματα Μαθηματικών

Ιουνίου 29, 2009

L-πλακόστρωση

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 3:55 μμ

Δείξτε ότι με ένα πλακάκι σχήματος L

l-shape

μπορείτε να πλακοστρώσετε ένα δωμάτιο 2^n \times 2^n το οποίο έχει μέσα μια 1×1 κολώνα (το πλάτος του κάθε τετραγώνου στο πλακάκι είναι 1, και η κολώνα βρίσκεται σε κάποια ακέραια θέση στο δωμάτιο με κάτω αριστερά γωνία (i,j), i,j \in {\mathbf Z}).

Advertisements

2 Σχόλια »

  1. Αν δεν κάνω λάθος, μια απόδειξη βασίζεται στην επαγωγική μέθοδο. Συγκεκριμένα, για n=1 προφανώς το ζητούμενο ισχύει. Έστω οτι ισχύει για n=k. Τότε μπορούμε να δείξουμε οτι ισχύει και για n=k+1 ως εξής: κόβοντας το 2^{k+1}x2^{k+1} τετράγωνο σε τέσσερα 2^{k}x2^{k} «υπο»-τετράγωνα, τότε το ένα από τέσσερα περιέχει την κολώνα και με βάση την επαγωγική υπόθεση ικανοποιεί το ζητούμενο. Για τα άλλα τρία μπορούμε να τα πλακοστρώσουμε με ένα L-πλακάκι, όπως αυτού του σχήματος, ώστε καθένα από τα τρία πλακάκια του L-πλακακίου θα πλακοστρώνει ένα τετράγωνακι 1×1 από τα τρία «υπο»-τετράγωνα (εκεί στο σύνορο).
    Έτσι τώρα τα άλλα 3 2^{k}x2^{k} «υπο»-τετράγωνα θα ικανοποιούν την επαγωγική υπόθεση, γιατί βάζοντας το ένα L-πλακάκι και στα τρία είναι σαν να έχουν τώρα μια κολώνα.
    Μια ζωγραφιά θα ήταν πιθανώς πολύ καλύτερη από την παραπάνω περιγραφή.

    Μου αρέσει!

    Σχόλιο από Charalampos Tsourakakis — Ιουλίου 13, 2009 @ 8:20 μμ

  2. Πολύ σωστά, έστω και χωρίς ζωγραφιά.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 13, 2009 @ 9:39 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: