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

Ιουνίου 29, 2009

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

Κατηγορίες: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 3:55 μμ

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

l-shape

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

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 για τα σχόλια του άρθρου. TrackBack URI

Γράψτε ένα σχόλιο

Για να σχολιάσετε πρέπει να συνδεθείτε.

Blog στο WordPress.com.