Un muratore dispone di piastrelle di dimensioni $2\times1$ e si chiede in quanti modi possa piastrellare un corridoio di dimensioni $3\times2n$.
L'esperienza gli suggerisce che il corridoio "vuoto" può essere piastrellato in 1 modo solo (piastrellazione vuota), mentre un corridoio $3\times2$ può essere piastrellato in 3 modi. Chiamiamo $P(n)$ il numero di modi di piastrellare un corridoio $3\times2n$.
Il capocantiere gli rivela che esistono quattro reali $a,b,c,d$ tali che $$P(n) = a\cdot b^n + c\cdot d^n$$Determinare $a,b,c,d$.
43. Dilemma da murari
Re: 43. Dilemma da murari
È carina l'idea combinatorica, anche se è abbastanza usata.. Comunque a me è piaciuto..
Re: 43. Dilemma da murari
spero di non sbagliarmi
$P(n)= 3P(n-1)+2p(n-2)+2P(n-3)+...=P(n-1) +2 \sum_{k=0} ^{n-1} {P(k)} $
$ \Rightarrow P(n+2)-P(n+1)=P(n+1) +2 \sum_{k=0} ^{n+1} {P(k)} - P(n) -2 \sum_{k=0} ^{n} {P(k)} = 3P(n+1) +2 \sum_{k=0} ^{n} {P(k)} - P(n) -2 \sum_{k=0} ^{n} {P(k)} = 3P(n+1) - P(n) $
$\Leftrightarrow P(n+2)= 4P(n+1) - P(n) $
con $P(0)=1$ e $P(1)=3$
$\Rightarrow P(n)= (\frac{1}{2}+\frac{1}{2 \sqrt{3} }) {(2+ \sqrt{3})}^n+ (\frac{1}{2}-\frac{1}{2 \sqrt{3} }) {(2- \sqrt{3})}^n $
da cui si ricava
$a=\frac{1}{2}+\frac{1}{2 \sqrt{3} } $
$b=2+ \sqrt{3} $
$c=\frac{1}{2}-\frac{1}{2 \sqrt{3} } $
$d=2- \sqrt{3} $
$P(n)= 3P(n-1)+2p(n-2)+2P(n-3)+...=P(n-1) +2 \sum_{k=0} ^{n-1} {P(k)} $
$ \Rightarrow P(n+2)-P(n+1)=P(n+1) +2 \sum_{k=0} ^{n+1} {P(k)} - P(n) -2 \sum_{k=0} ^{n} {P(k)} = 3P(n+1) +2 \sum_{k=0} ^{n} {P(k)} - P(n) -2 \sum_{k=0} ^{n} {P(k)} = 3P(n+1) - P(n) $
$\Leftrightarrow P(n+2)= 4P(n+1) - P(n) $
con $P(0)=1$ e $P(1)=3$
$\Rightarrow P(n)= (\frac{1}{2}+\frac{1}{2 \sqrt{3} }) {(2+ \sqrt{3})}^n+ (\frac{1}{2}-\frac{1}{2 \sqrt{3} }) {(2- \sqrt{3})}^n $
da cui si ricava
$a=\frac{1}{2}+\frac{1}{2 \sqrt{3} } $
$b=2+ \sqrt{3} $
$c=\frac{1}{2}-\frac{1}{2 \sqrt{3} } $
$d=2- \sqrt{3} $
Re: 43. Dilemma da murari
Vabbè proviamo...
Abbiamo due casi:
-Oltre a essere piastrellato correttamente il corridoio lungo $ 2n $, è piastrellato correttamente anche il corridoio lungo $ 2(n-1) $. Nel senso che se togliamo le ultime due righe otteniamo una configurazione valida per il caso $ n-1 $.
-Non abbiamo la situazione precedente. Facendo un po' di prove si nota che le configurazioni possibili sono 2 e simmetriche, abbiamo due piastrelle vicine disposte parallelamente al corridoio posizionate una sul bordo e una centralmente tali che si trovano sia nell'ultimo blocco da 6 caselle sia nel corridoio del caso $ n-1 $. La tassellazione totale poi è univocamente determinata. (Esempio: un corridoio lungo 8, ogni casella si indica con la coppia di interi $ (i,j) $ con $ 1\leq i \leq 3 $ e $ 1 \leq j \leq 8 $. Se il corridoio considerato $ j \leq 6 $ non ha una disposizione valida avremo delle piastrelle che dal corridoio $ 3 \times 6 $ sforeranno nell'ultimo pezzetto $ 3 \times 2 $. Con un po' di prove vediamo che le piastrelle sono per forza 2 e che si trovano o nella colonna 1 e nella colonna 2 oppure si trovano nella colonna 2 e nella colonna 3.)
Considerando il numero di disposizioni $ P'(n) $ considerando il primo caso e $ P''(n) $ considerando il secondo caso. (Ovviamente $ P'(n)+P''(n)=P(n) $)
Poichè l'ultimo blocchetto $ 3 \times 2 $ si può tassellare in 3 modi avremo:
$ P'(n)=3 P(n-1) $
Ora ci chiediamo quante disposizioni ci sono tali che avremo le due piastrelle sporgenti verso l'ultimo rettangolo $ 3 \times 2 $. Possiamo creare una biezione tra le disposizioni valide nei corridoi lunghi $ 2(n-1) $ con le disposizioni che ci interessano: infatti se consideriamo i casi in cui nella riga finale abbiamo una piastrella perpendicolare al corridoio (diciamo appoggiata sul lato lungo al lato corto del corridoio) possiamo sostituirla con due piastrelle orientate perpendicolarmente e "sforanti" verso il corridoio lungo $ 2n $. Purtroppo però la biezione non è correttissima... se il corridoio non termina con una piastrella perpendicolare al suo senso non abbiamo un corrispondente caso "di sforatura"... Tuttavia basta sottrarre il numero di queste disposizioni, ossia quelle che terminano con tre piastrelle parallele al corridoio l'una di fianco all'altra. Questa disposizione da togliere però rende valido anche il corridoio del caso $ n-2 $ e abbiamo una biezione sul numero di casi da togliere con il numero di corridoi validi del caso $ n-2 $. Pertanto:
$ P''(n)=P(n-1)-P(n-2) $
Da cui: $ P(n) - 4P(n-1) + P(n-2) = 0 $
Qui chiedo aiuto alla teoria del Basic del Senior (spero me la consentiate
), usando il teorema delle successioni per ricorrenza lineari e facendo qualche conto ottengo:
$ \displaystyle P(n)= \frac{3+\sqrt 3}{6} (2+ \sqrt 3 )^n + \frac{3-\sqrt 3}{6} (2- \sqrt 3 )^n $
La quaterna richiesta è quindi:
$ \displaystyle (\frac{3+\sqrt 3}{6}, 2+ \sqrt 3, \frac{3-\sqrt 3}{6}, 2- \sqrt 3) $
(e ovviamente la commutata
)
Spero sia giusto e se lo è mi permetto di dire che sarebbe stato molto figo in una gara a squadre chiedere la somma $ a+b+c+d $
Abbiamo due casi:
-Oltre a essere piastrellato correttamente il corridoio lungo $ 2n $, è piastrellato correttamente anche il corridoio lungo $ 2(n-1) $. Nel senso che se togliamo le ultime due righe otteniamo una configurazione valida per il caso $ n-1 $.
-Non abbiamo la situazione precedente. Facendo un po' di prove si nota che le configurazioni possibili sono 2 e simmetriche, abbiamo due piastrelle vicine disposte parallelamente al corridoio posizionate una sul bordo e una centralmente tali che si trovano sia nell'ultimo blocco da 6 caselle sia nel corridoio del caso $ n-1 $. La tassellazione totale poi è univocamente determinata. (Esempio: un corridoio lungo 8, ogni casella si indica con la coppia di interi $ (i,j) $ con $ 1\leq i \leq 3 $ e $ 1 \leq j \leq 8 $. Se il corridoio considerato $ j \leq 6 $ non ha una disposizione valida avremo delle piastrelle che dal corridoio $ 3 \times 6 $ sforeranno nell'ultimo pezzetto $ 3 \times 2 $. Con un po' di prove vediamo che le piastrelle sono per forza 2 e che si trovano o nella colonna 1 e nella colonna 2 oppure si trovano nella colonna 2 e nella colonna 3.)
Considerando il numero di disposizioni $ P'(n) $ considerando il primo caso e $ P''(n) $ considerando il secondo caso. (Ovviamente $ P'(n)+P''(n)=P(n) $)
Poichè l'ultimo blocchetto $ 3 \times 2 $ si può tassellare in 3 modi avremo:
$ P'(n)=3 P(n-1) $
Ora ci chiediamo quante disposizioni ci sono tali che avremo le due piastrelle sporgenti verso l'ultimo rettangolo $ 3 \times 2 $. Possiamo creare una biezione tra le disposizioni valide nei corridoi lunghi $ 2(n-1) $ con le disposizioni che ci interessano: infatti se consideriamo i casi in cui nella riga finale abbiamo una piastrella perpendicolare al corridoio (diciamo appoggiata sul lato lungo al lato corto del corridoio) possiamo sostituirla con due piastrelle orientate perpendicolarmente e "sforanti" verso il corridoio lungo $ 2n $. Purtroppo però la biezione non è correttissima... se il corridoio non termina con una piastrella perpendicolare al suo senso non abbiamo un corrispondente caso "di sforatura"... Tuttavia basta sottrarre il numero di queste disposizioni, ossia quelle che terminano con tre piastrelle parallele al corridoio l'una di fianco all'altra. Questa disposizione da togliere però rende valido anche il corridoio del caso $ n-2 $ e abbiamo una biezione sul numero di casi da togliere con il numero di corridoi validi del caso $ n-2 $. Pertanto:
$ P''(n)=P(n-1)-P(n-2) $
Da cui: $ P(n) - 4P(n-1) + P(n-2) = 0 $
Qui chiedo aiuto alla teoria del Basic del Senior (spero me la consentiate
), usando il teorema delle successioni per ricorrenza lineari e facendo qualche conto ottengo:$ \displaystyle P(n)= \frac{3+\sqrt 3}{6} (2+ \sqrt 3 )^n + \frac{3-\sqrt 3}{6} (2- \sqrt 3 )^n $
La quaterna richiesta è quindi:
$ \displaystyle (\frac{3+\sqrt 3}{6}, 2+ \sqrt 3, \frac{3-\sqrt 3}{6}, 2- \sqrt 3) $
(e ovviamente la commutata
)Spero sia giusto e se lo è mi permetto di dire che sarebbe stato molto figo in una gara a squadre chiedere la somma $ a+b+c+d $
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: 43. Dilemma da murari
Anticipato 
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
