Domino in scatola

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Domino in scatola

Messaggio da Mist » 17 lug 2011, 18:28

In quanti modi si può riempire una scatola $2\times 2\times n$ con mattoncini $1 \times 1 \times 2$ ?
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

OriginalBBB
Messaggi: 69
Iscritto il: 09 nov 2009, 14:25

Re: Domino in scatola

Messaggio da OriginalBBB » 02 ott 2011, 18:30

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
Messaggi: 69
Iscritto il: 09 nov 2009, 14:25

Re: Domino in scatola

Messaggio da OriginalBBB » 02 ott 2011, 19:59

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.

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 603
Iscritto il: 01 gen 1970, 01:00
Località: Genova
Contatta:

Re: Domino in scatola

Messaggio da FrancescoVeneziano » 02 ott 2011, 22:07

Prova a cercare una ricorrenza per $C(n)$.
Wir müssen wissen. Wir werden wissen.

stergiosss
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 03 ott 2011, 15:50

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
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 03 ott 2011, 15:55

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 :wink:

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Domino in scatola

Messaggio da Mist » 03 ott 2011, 16:39

è ovvio che interessa :D postalo
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 603
Iscritto il: 01 gen 1970, 01:00
Località: Genova
Contatta:

Re: Domino in scatola

Messaggio da FrancescoVeneziano » 03 ott 2011, 19:28

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.
Wir müssen wissen. Wir werden wissen.

stergiosss
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 03 ott 2011, 21:20

FrancescoVeneziano ha scritto: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 :P 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
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 03 ott 2011, 21:49

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 :P
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 :D )

fph
Site Admin
Messaggi: 3814
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Domino in scatola

Messaggio da fph » 03 ott 2011, 22:26

stergiosss ha scritto:$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$?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 603
Iscritto il: 01 gen 1970, 01:00
Località: Genova
Contatta:

Re: Domino in scatola

Messaggio da FrancescoVeneziano » 03 ott 2011, 22:42

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.
Wir müssen wissen. Wir werden wissen.

stergiosss
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 03 ott 2011, 22:49

fph ha scritto:
stergiosss ha scritto:$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 :D ) 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
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 03 ott 2011, 23:06

FrancescoVeneziano ha scritto: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 :oops:
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" :oops:

fph
Site Admin
Messaggi: 3814
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Domino in scatola

Messaggio da fph » 03 ott 2011, 23:46

stergiosss ha scritto: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
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi