Domino in scatola

[Mist]

In quanti modi si può riempire una scatola $2\times 2\times n$ con mattoncini $1 \times 1 \times 2$ ?

[OriginalBBB]

Vorrei riaprire il problema, che mi interessa; ci sto lavorando.

Per ora riesco a dire che se C(n) è il numero cercato allora $ 2^n<C(n)<7^n $, che è ben poca cosa. Ci provo!

[OriginalBBB]

Idea

Immaginiamo di porre la scatola in un sistema cartesiano $ 3 $-dimensionale, si estenderà lungo le direzioni $ x,y,z $ assegnando la variabile $ n $ alla direzione $ z $.

Immaginiamo di sezionare la scatola lungo $ z $ Le possibili sezioni che potremo ottenere sono 7, e più precisamente, le seguenti:

Testo nascosto:

A\begin{bmatrix}x & x\\x & x\end{bmatrix} B\begin{bmatrix}x & x\\z & z\end{bmatrix} C\begin{bmatrix}z & z\\x & x\end{bmatrix}
D\begin{bmatrix}z & z\\z & z\end{bmatrix}
E\begin{bmatrix}z & y\\z & y\end{bmatrix}F\begin{bmatrix}y & z\\y & z\end{bmatrix}G\begin{bmatrix}y & y\\y & y\end{bmatrix}

Si tratterà ora di trovare tutte le combinazioni possibili eliminando i casi con sezioni adiacenti che contraddirebbero i casi del problema.

Adiacenze possibili

Troviamo la lunghezza delle sezioni indipendenti (quelle che, tolte in blocco dalla scatola, lasciano due pareti lisce)

1)Le sezioni A e G sono indipendenti per $ \Delta n = 1 $ (2 opzioni)

2)Per $ \Delta n = 2 $ abbiamo DD, AE, EA, AA, EE (5 opzioni)

3)Per $ \Delta n $ = 3 abbiamo BDC, CDB, EDF, FDE, AAA, AAE, AEA, AEE, EAA, EAE, EEA, EEE, DDA, ADD, DDE, EDD, FBG, GBF, FCG, GCF, BFC, CFB, BGC, CGB(24 opzioni)

4)Si noti inoltre che possiamo costruire infinite sezioni indipendenti sostituendo ad una sezione D, 2k+1 sezioni D con k naturale.

Tiriamo le fila del discorso

Se $ n \equiv 0 (mod 3) $ allora ho almeno $ 24 ^ {n/3} $ possibilità

Se $ n \equiv 1 (mod 3) $ allora ho almeno $ 24 ^ {(n-1)/3} * 2 $ possibilità

Se $ n \equiv 2 (mod 3) $ allora ho almeno $ 24 ^ {(n-2)/3} * 5 $ possibilità

Essendo 24 ^ {n/3} < 7 ^ n questa parte è coerente con la mia prima congettura e posso modificarla anzi così.

se C(n) è il numero cercato allora $ 24 ^ {n/3}<C(n)<7^n $

Sono sicuro che avete capito il significato degli almeno prima di me stesso, per la 4) per esempio, o per altri casi che al momento mi sfuggono. Continuo a provarci, la 4) necessiterebbe forse solo di uno sforzo di formalizzazione ma probabilmente ci sono altri casi che non considero ancora. Sarebbe più facile avendo a disposizione una vera scatola di domino.

[FrancescoVeneziano]

Prova a cercare una ricorrenza per $C(n)$.

[stergiosss]

Hint

Testo nascosto:

Segui l'hint di Veneziano, e prova a ragionare sulle "fratture". Quanti modi ci sono di riempire la scatola senza "fratture"? Cioè in modo che ogni piano orizzontale che tagli la scatola tagli almeno un mattoncino?
Cerco di spiegare meglio cosa intendo per frattura: se nel primo strato della scatola metti due mattoncini "sdraiati" hai una frattura già al primo strato. Se metti 4 mattoncini in piedi hai una frattura al secondo strato.

[stergiosss]

Ah comunque io ho trovato la soluzione (cioè una formula chiusa che esprime $ C(n) $ in funzione di $ n $), è l'ho dimostrata per induzione. Però il modo con cui l'ho trovata è un po' rude e poco rigoroso ma se può interessare la posto lo stesso

[Mist]

è ovvio che interessa postalo

[FrancescoVeneziano]

La formula chiusa si può ricavare dalla relazione di ricorrenza con un po' di Teoria, senza bisogno di "indovinarla". Naturalmente se sai già quale deve essere ed hai la ricorrenza, la dimostrazione è una banale induzione.

[stergiosss]

La formula chiusa si può ricavare dalla relazione di ricorrenza con un po' di Teoria, senza bisogno di "indovinarla".

Be' io non è che l'ho trovata tirando a caso c'è alla base un po' di teoria, un po' di "occhio" e un po' di fortuna.


Scrivo la formula
$ \displaystyle C(n)=\frac{(2+\sqrt{3})^{n+1}+(2-\sqrt{3})^{n+1}+(-1)^n \cdot2}{6} $

e vado a spiegare come l'ho trovata.


Ho già spiegato prima cosa intendo per fratture. Voglio contare in quanti modi posso costruire una torre senza fratture.

Osservo che, qualunque sia $n \geq 3$, ho sempre e solo 4 modi per costruire una torre alta $n$ senza fratture. Infatti il primo strato non può essere composto da due mattoncini "sdraiati", perché avrei una frattura dopo il primo strato, e non può essere composto da quattro mattoncini "in piedi", perché avrei una frattura dopo il secondo strato.
Quindi il primo strato deve necessariamente essere composto da un mattoncino "sdraiato" e due "in piedi", e questo lo posso fare in 4 modi diversi (il mattoncino sdraiato può essere attaccato a uno dei 4 lati del quadrato di base).
Se voglio che la mia torre sia senza fratture, di qui in avanti ho le mosse obbligate. Infatti sul secondo strato mi ritrovo un buco 2x1 (sopra il mattoncino sdraiato), e questo buco non posso riempirlo con un altro mattoncino sdraiato perché creerei una frattura, quindi va riempito per forza con due mattoncini in piedi, e da qui fino al penultimo strato la situazione è sempre uguale. Per completare l'ultimo strato invece dovrò piazzare proprio il mattoncino sdraiato.
Conclusione 1.1: qualunque sia $n \geq 3$, ho sempre e solo 4 modi per costruire una torre alta $n$ senza fratture

Analizzo ora i casi piccoli rimasti:
Per $n=1$ non ha senso parlare di torre con fratture o senza fratture, in ogni caso i modi per disporre i mattoncini sono 2.
Per $n=2$ i modi sono 5: 4 sono quelli ottenuti con la stessa tecnica descritta per la torre alta più di tre mattoncini, e in più c'è il caso in cui dispongo quattro mattoncini in piedi. Totale 5.
Conclusione 1.2: per $n=1$ ho 2 modi di disporre i mattoncini, per $n=2$ ho 5 modi di costruire una torre senza fratture.
Conclusione 1: Detto $F(n)$ il numero di modi di costruire una torre alta $n$ senza fratture ho che:
$F(1)=2$
$F(2)=5$
$F(n)=4 \forall n \geq 3$

Ora vediamo in quanti modi posso costruire una torre alta $n \geq 4$.
Una volta completata, la torre può avere zero, una o più fratture. Abbiamo 4 modi di costruirla senza fratture (l'abbiamo già detto prima). Dobbiamo trovare quanti sono i modi di costruirla con fratture.
La prima frattura sarà dopo $i$ strati, con $i \in \{1, 2, ... , n-1\}$. Quindi la torre si può dividere in due torri, una alta $i$, senza fratture, e l'altra alta $n-i$, generica. Quindi il numero di modi di costruire una torre alta $n$ con la prima frattura dopo $i$ strati è uguale a $F(i) \cdot C(n-i)$
Quindi $C(n)$ è uguale alla sommatoria, per $i \in \{1, 2, ... , n-1\}$ di $F(i) \cdot C(n-i)$, a cui devo sommare 4 (i modi di costruirla senza fratture). Trasformando il tutto in simboli, e sostituendo i valori noti di $F(n)$, posso scrivere che:

$ \displaystyle C(n) = 2C(n-1)+5C(n-2)+ \sum_{i=1}^{n-3} 4 \cdot C(i) +4 $

A questo punto mi trovo a mano i valori piccoli di $C(n)$, e definisco per mia comodità $C(0) = 1$, per poter includere il "+4" finale della formula nella sommatoria.

Il risultato è che posso scrivere la ricorrenza di $C(n)$ in questo modo:
$C(0) = 1$
$C(1) = 2$
$C(2) = 9$
$C(3) = 32$
$ \displaystyle C(n) = 2C(n-1)+5C(n-2)+ 4 \sum_{i=0}^{n-3} C(i) $

[stergiosss]

Ora, io non conosco (se esiste) un modo comodo ed elegante di trovare il termine generico di questa successione, quindi qui entra in gioco la parte "rude" della mia dimostrazione. Mi cerco a mano i valori "piccoli" di $C(n)$, diciamo per $n \leq 10$, e trovo questi:

Testo nascosto:

$C(0) = 1$
$C(1) = 2$
$C(2) = 9$
$C(3) = 32$
$C(4) = 121$
$C(5) = 450$
$C(6) = 1681$
$C(7) = 6272$
$C(8) = 23409$
$C(9) = 87362$
$C(10) = 326041$

Qui entra in gioco l'occhio. Noto che i termini di posto pari sono tutti quadrati perfetti e che quelli di posto dispari sono tutti il doppio di un quadrato.


Mi concentro su quelli di posto pari:

Testo nascosto:

$C(2 \cdot 0) = 1^2$
$C(2 \cdot 1) = 3^2$
$C(2 \cdot 2) = 11^2$
$C(2 \cdot 3) = 41^2$
$C(2 \cdot 4) = 153^2$
$C(2 \cdot 5) = 571^2$

Qui entra di nuovo in gioco l'occhio. Noto che ogni termine è uguale al quadruplo del precedente, meno il termine due posti prima.
In simboli, posto $C(2n) = x_n^2$, noto che: $x_{n+1}=4x_n - x_{n-1}$

Ho una nuova successione, di cui so calcolare il termine generico. Vi risparmio i calcoli e vi dico il risultato, che è:
$ \displaystyle x_n = \frac{(\sqrt{3} + 1)(2 + \sqrt{3})^n+(\sqrt{3} - 1)(2 - \sqrt{3})^n}{2 \sqrt{3}} $

e quindi
$ \displaystyle C(2n) = x_n^2 = \frac{[(\sqrt{3} + 1)(2 + \sqrt{3})^n+(\sqrt{3} - 1)(2 - \sqrt{3})^n]^2}{12} = \frac{(2 + \sqrt{3})^{2n+1}+(2 - \sqrt{3})^{2n+1} + 2}{6} $


Ora mi concentro sui termini di posto dispari:

Testo nascosto:

$C(2 \cdot 0 + 1) = 2 \cdot 1^2$
$C(2 \cdot 1 + 1) = 2 \cdot 4^2$
$C(2 \cdot 2 + 1) = 2 \cdot 15^2$
$C(2 \cdot 3 + 1) = 2 \cdot 56^2$
$C(2 \cdot 4 + 1) = 2 \cdot 209^2$

Ragiono come prima, e posto $C(2n + 1) = 2 \cdot y_n^2$, noto che: $y_{n+1}=4y_n - y_{n-1}$

Vi risparmio nuovamente i calcoli e vi dico che:
$ \displaystyle y_n = \frac{(2 + \sqrt{3})^{n+1}+(2 - \sqrt{3})^{n+1}}{2 \sqrt{3}} $

e quindi
$ \displaystyle C(2n + 1) = 2 \cdot y_n^2 = \frac{[(2 + \sqrt{3})^{n+1}+(2 - \sqrt{3})^{n+1}]^2}{6} = \frac{(2 + \sqrt{3})^{2n+2}+(2 - \sqrt{3})^{2n+2} - 2}{6} $


A questo punto il gioco è fatto: noto che le formule ottenute per $C(2n)$ e $C(2n+1)$ sono quasi identiche, e le inglobo nella formula già anticipata prima:
$ \displaystyle C(n)=\frac{(2+\sqrt{3})^{n+1}+(2-\sqrt{3})^{n+1}+(-1)^n \cdot2}{6} $

Ora bisogna solo controllare che la formula funzioni veramente, visto che io l'ho dedotta solo in base ai primi 10 termini e nessuno mi assicura che il comportamento non cambi per $n$ più grandi.
La prova si fa "facilmente" per induzione, io l'ho fatta su carta (dividendo i casi $n$ pari o dispari) ma non ho la minima intenzione di trascriverla in LaTeX
E la prova ci dice che l'osservazione fatta per valori piccoli di $n$ vale per ogni $n$ (e qui entra in gioco la fortuna )

[fph]

$C(0) = 1$
$C(1) = 2$
$C(2) = 9$
$C(3) = 32$
$ \displaystyle C(n) = 2C(n-1)+5C(n-2)+ 4 \sum_{i=0}^{n-3} C(i) $
Ora, io non conosco (se esiste) un modo comodo ed elegante di trovare il termine generico di questa successione

È un trucco che si trova anche nei "vecchi" esercizi di Pisa 2002 che vengono ancora dati agli stage senior: prova a porre $S_n:=\sum_{i=0}^n C_i$. Come si scrive $C_n$ in funzione delle sole $S_i$, $i \leq n$? Quindi, che relazione per ricorrenza soddisfano le $S_n$?

[FrancescoVeneziano]

Oppure vai di serie generatrici. Definisci $C(x)=\sum_{n=0}^\infty C(n)x^n$, prendi la relazione per ricorrenza e da quella ricavi una relazione polinomiale soddisfatta da C(x). Risolvi per C(x) e la trovi espliciamente (è una funzione razionale di terzo grado). Sviluppi in frazioni parziali, sbrogli le geometriche, e sei alla fine.

[stergiosss]

$C(0) = 1$
$C(1) = 2$
$C(2) = 9$
$C(3) = 32$
$ \displaystyle C(n) = 2C(n-1)+5C(n-2)+ 4 \sum_{i=0}^{n-3} C(i) $
Ora, io non conosco (se esiste) un modo comodo ed elegante di trovare il termine generico di questa successione

È un trucco che si trova anche nei "vecchi" esercizi di Pisa 2002 che vengono ancora dati agli stage senior: prova a porre $S_n:=\sum_{i=0}^n C_i$. Come si scrive $C_n$ in funzione delle sole $S_i$, $i \leq n$? Quindi, che relazione per ricorrenza soddisfano le $S_n$?

Grazie della dritta (posso fare una critica? non mi piace questo smile, sembra un ghigno più che un sorriso)

Sostituendo $C(n) = S_n - S_{n-1}$ nella relazione $ \displaystyle C(n) = 2C(n-1)+5C(n-2)+ 4 \sum_{i=0}^{n-3} C(i) $


Ottengo la formula molto più snella
$S_n = 3S_{n-1}+3S_{n-2}-S_{n-3}$

Da cui uno bravo (che non sono io ) potrebbe ricavare più o meno facilmente il termine generico di $S_n$, e quindi di $C(n)$

Io è già tanto se so ricavare il termine generico in una successione in cui ogni termine è legato ai due precedenti (l'ho imparato giusto qualche giorno fa qui sul forum). Con ogni termine legato ai tre precedenti non so davvero che fare.
Immagino che possa tornare utile risolvere la cubica associata (in questo caso, guarda caso, le radici sono $(2-\sqrt{3})$, $(2+\sqrt{3})$ e $(-1)$)...

[stergiosss]

Oppure vai di serie generatrici. Definisci $C(x)=\sum_{n=0}^\infty C(n)x^n$, prendi la relazione per ricorrenza e da quella ricavi una relazione polinomiale soddisfatta da C(x). Risolvi per C(x) e la trovi espliciamente (è una funzione razionale di terzo grado). Sviluppi in frazioni parziali, sbrogli le geometriche, e sei alla fine.

Ehm, questo non mi aiuta
In particolare non capisco cosa intendi nel passaggio "prendi la relazione per ricorrenza e da quella ricavi una relazione polinomiale soddisfatta da C(x). Risolvi per C(x) e la trovi espliciamente"

[fph]

Io è già tanto se so ricavare il termine generico in una successione in cui ogni termine è legato ai due precedenti (l'ho imparato giusto qualche giorno fa qui sul forum). Con ogni termine legato ai tre precedenti non so davvero che fare.
Immagino che possa tornare utile risolvere la cubica associata (in questo caso, guarda caso, le radici sono $(2-\sqrt{3})$, $(2+\sqrt{3})$ e $(-1)$)...

Esatto --- funziona tutto esattamente nello stesso modo anche in gradi più alti, la soluzione generica è una somma pesata degli $x_i^n$ (almeno se le radici sono tutte distinte).
Se vuoi una trattazione più completa, incluso cosa succede quando ci sono radici ripetute, guardati la lezione C3 del senior di un anno qualunque, il primo pezzo è sempre sulle successioni per ricorrenza.

EDIT: A3, non C3