Un problema di Parigi

Presentiamo qui di seguito testo e soluzione del gioco n. 16 dell’ultima edizione dei Campionati Internazionali di Giochi Matematici, appena tenutisi a Parigi. La soluzione è stata curata da Giorgio Dendi.

Testo

Su una quadrettatura regolare e orientata, si ricoprono dei rettangoli o quadrati 2xn solamente con rettangoli 1×2 o 2×1 e quadrati 1×1. Per esempio, il quadrato 2×2 può venir ricoperto in 7 modi diversi, come indicato in figura. In quanti modi diversi può esser ricoperto un rettangolo 2×7?

 

Soluzione

Immagino che la soluzione sia un numero “abbastanza grande”, e non sia possibile calcolare uno per uno i vari casi, quindi cerco il sistema per dividere il problema in zone più piccole, e più “malleabili”. Mi disegno per prima cosa il rettangolo che devo ricoprire, e la mia attenzione sarà indirizzata alle due caselle della colonna 4.

Queste due caselle possono far parte della tassellatura finale in 5 modi diversi:

A seconda della scelta, a destra e a sinistra rimarranno delle zone di 4, 5 o 6 caselle da ricoprire. Ci viene detto nel testo che una figura 2×2 si può ricoprire in 7 modi diversi; dalle figure qui sotto scopriamo che una figura di 5 caselle si può ricoprire in 10 modi diversi, e un rettangolo 2×3 si può ricoprire in 22 modi diversi.

Esaminiamo ora le 5 diverse tassellature della colonna 4.

A destra c’è un rettangolo 2×3, ricopribile in 22 modi diversi, e così anche a sinistra, per un totale di 22 x 22 = 484 ricoperture diverse.

Il rettangolo di colonna 4 viene diviso in due quadrati, ma ci sono sempre 22 ricoperture a destra e così anche a sinistra, per un totale di 22 x 22 = 484 ricoperture diverse.

La colonna 4 è formata da due rettangolini 1×2, entrambi uscenti dallo stesso lato destro (oppure sinistro): la figura viene divisa in due rettangoli, uno di dimensione 2×2, ricopribile in 7 modi diversi, e uno di dimensione 2×3, ricopribile in 22 modi diversi; si moltiplica per 2 in quanto i due rettangolini possono uscire a destra o a sinistra. In tutto 2 x 7 x 22 = 308 ricoperture diverse.

La colonna 4 è formata da un quadratino 1×1 e un rettangolino 1×2, che può stare di sopra o di sotto, e può uscire a destra oppure a sinistra: la figura viene divisa in un rettangolo 2×3, ricopribile in 22 modi diversi e una figura di area 5, ricopribile in 10 modi diversi; si moltiplica per 4 in quanto il rettangolo può stare sopra o sotto, girato verso destra o verso sinistra. In tutto 4 x 10 x 22 = 880 ricoperture diverse.

La colonna 4 è formata da due rettangolini 1×2, uscenti uno a destra e uno a sinistra: la figura viene divisa in due altre figure di area 5, ricopribili ciascuna in 10 modi diversi; si moltiplica per 2 in quanto il rettangolino che esce a destra può stare sopra o sotto. In tutto 2 x 10 x 10 = 200 ricoperture diverse.

Facciamo il totale: 484 + 484 + 308 + 880 +200 = 2356, che è la soluzione voluta.

Commento

Forse il mio procedimento è meno completo di quelle canonico, che trova la regola per ricorrenza per poter calcolare il numero di tassellature diverse per ogni rettangolo 2xn, ma ritengo che sia il più semplice ai fini della soluzione del problema. Ricordo che siamo in gara, e si ha poco tempo da dedicare ad ogni problema.

3 pensieri su “Un problema di Parigi

  1. Bella Giorgio ! In effetti ho provato a risolverlo prima di leggere la soluzione ma mi sono impantanato… con la ricorsione non ho trovato un metodo veloce.

  2. Con la ricorsione ce ne è una quasi veloce (quella che ho trovato in gara) e intreccia tre semplici successioni, da cui si arriva a mano alla 2×7. Consiste nello sviluppare il rettangolo a partire dalla 2×2 e permette di “estendere verso l’alto” un 1×1 per farlo diventare un 2×1, oppure di aggiungerci sopra un 1×1 o un 2×1 in orizzontale. L’idea quindi è sostanzialmente di crescere un piano alla volta. partendo dai 7 possibili 2×2 e concentrandosi su quanti 1×1 abbia il piano più alto. A seconda di questo numero (0, 1, 2) ottengo le tre diverse successioni che alla fine sommerò.

  3. Bravo Giorgio, credo che la tua soluzione sia la più veloce.

    La mia è invece simile a quella di Giuseppe, a parte che lui ha espanso verso l’alto e io verso il basso, però ora la spiego espandendo verso destra così i disegni di Giorgio aiutano.

    L’idea è quella che ogni rettangolo 2×3 contiene nella sua parte sinistra un quadrato 2×2, “espanso” con altri due quadretti sulla destra.
    Per fare l’espansione può essere necessario aprire il quadrato 2×2 sul lato destro.

    Ora, i sette quadrati 2×2 si dividono in:
    – Non apribili (N) come il primo, il secondo e il sesto del disegno. Questi possono essere espansi solamente aggiungendo 2 quadratini 1×1 oppure un rettangolo verticale 2×1.
    – Parzialmente apribili (P) come il terzo e il quinto del disegno. Questi possono essere espansi come sopra (con 2 quadratini 1×1 o un rettangolo verticale 2×1) ma anche aprendo il lato destro in corrispondenza del quadratino isolato, trasformandolo così in un rettangolo orizzontale 1×2, e ovviamente aggiungendo il quadratino 1×1 mancante.
    – Apribili (A) come il quarto e il settimo del disegno. Questi possono essere espansi come quelli N, oppure aprendo il lato destro in un punto (come i P, ma in due modi diversi), oppure aprendo tutto il lato destro e trasformando quindi i quadratini 1×1 in rettangoli orizzontali 1×2.

    Ricapitolando:
    – Ogni 2×2 di tipo N genera un 2×3 di tipo A e un 2×3 di tipo N.
    – Ogni 2×2 di tipo P genera un 2×3 di tipo A, un 2×3 di tipo N e un 2×3 di tipo P.
    – Ogni 2×2 di tipo A genera un 2×3 di tipo A, due 2×3 di tipo N e due 2×3 di tipo P.
    Ma la stessa cosa vale per generare rettangoli 2×4 a partire da rettangoli 2×3, e così via fino a 2×7.

    Quindi facendo i conti:
    2×2 = 2A + 3N + 2P
    2×3 = 7A + 9N + 6P
    2×4 = 22A + 29N + 20P
    2×5 = 71A + 93N + 64P
    2×6 = 228A + 299N + 206P
    2×7 = 733A + 961N + 662P = 2356.

    Probabilmente esiste una formula generale (parente di Fibonacci, immagino) per trovare il numero di suddivisioni dei rettangoli 2xL, ma con L=7 il fattore tempo spinge a fare i conti a mano per il caso particolare. Per L=2011 magari avrei cercato la formula 🙂

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *