Giallo o blu

[axpgn]

Ogni piano di un palazzo deve essere dipinto di giallo o di blu con il vincolo che due piani adiacenti non possono essere entrambi blu (ma gialli sì).

In quanti modi diversi è possibile dipingere un palazzo di $n$ piani?



Cordialmente, Alex

[utente__medio11]

Non so se è corretta, ma ragionando un po' sono giunto alla seguente soluzione (parziale):

Fissato il numero $n$ di piani totali, detto $m_(MAX)=[(n+1)/2]$ il massimo numero di piani blu, e detto $k=n-2(m-1)$ il massimo numero $+1$ di piani gialli consecutivi iniziali compatibili con $n$ e $m$, il valore cercato può essere espresso come:

$1+sum_(m=1)^(m_(MAX))f(k, m)$

dove il $+1$ tiene conto del caso di palazzo interamente giallo e $f(k,m)$, che rappresenta il numero di possibili disposizioni per un dato valore di $m$, è dato dalla somma dei valori delle foglie di un albero caratterizzato da una radice di valore $k$ e da una profondità pari a $m$.

Di seguito un esempio per $f(3,5)=21$:
https://i.postimg.cc/MHPv5QVN/aaa.png

Anche se è tutto sbagliato, qualcuno saprebbe dirmi se è possibile esprimere $f()$ in forma chiusa?

[axpgn]

Premesso che ci ho capito poco, come faccio a sapere dalla tua costruzione quanti modi ci sono di dipingere, per esempio, un palazzo di cinque piani?

[utente__medio11]

Per $n=5$:

$1+sum_(m=1)^3f(k,m)=1+f(5,1)+f(3,2)+f(1,3)=1+5+6+1=13$

Per $n=8$:

$1+sum_(m=1)^4f(k,m)=1+f(8,1)+f(6,2)+f(4,3)+f(2,4)=1+8+21+20+5=55$

I risultati sono giusti?

[axpgn]

Sì, sono giusti ma non mi è chiaro come calcoli $f(k,m)$ ovvero com'è definita in modo preciso?
Peraltro, dato che $k$ dipende da $m$ io la chiamerei solo $f(m)$.
Ma soprattutto non hai dimostrato che valga sempre ovvero per ora è solo una congettura. IMHO

Cordialmente, Alex

[hydro1]

E’ la sequenza di Fibonacci con dati di partenza $2$ e $3$.

[axpgn]

Esatto ... ma va dimostrato


Cordialmente, Alex

[utente__medio11]

"axpgn":Ma soprattutto non hai dimostrato che valga sempre ovvero per ora è solo una congettura. IMHO

Magari poi lo spiegherò meglio, ma si tratta di un semplice metodo di conteggio delle disposizioni valide.

"axpgn":Peraltro, dato che $k$ dipende da $m$ io la chiamerei solo $f(m)$.

Chiamiamola $f(m,n)$ dato che in ultima analisi dipende appunto da $m$ e $n$.

"axpgn":Sì, sono giusti ma non mi è chiaro come calcoli $f(k,m)$ ovvero com'è definita in modo preciso?

Come già detto $f(m,n)$ rappresenta il numero di possibili disposizioni per un dato valore di $m$ ed è dato dalla somma dei valori delle foglie di un albero caratterizzato da una radice di valore $n-2(m-1)$ e da una profondità pari a $m$.
In pratica da ogni nodo di valore $a>1$ si diramano altri $a$ nodi, i cui valori vanno da $1$ ad $a$; detto ciò le uniche informazioni che servono per la costruzione dell'albero sono il valore del nodo radice (quello iniziale) e la profondità dell'albero. A questo punto basta sommare i valori delle foglie e si ottiene $f(m,n)$.

Ho trovato un metodo "semiautomatico" per il calcolo di $f(m,n)$, ma non ancora una soluzione in forma chiusa. Rinnovo quindi la mia richiesta:

"utente__medio":Anche se è tutto sbagliato, qualcuno saprebbe dirmi se è possibile esprimere $ f() $ in forma chiusa?

Magari a quel punto facendo i calcoli e con i giusti passaggi si arriva proprio alla soluzione detta da @hydro.

[axpgn]

@utente_medio

In pratica, li disegni tutti e poi li conti
Però si può fare di meglio

Cordialmente, Alex

[utente__medio11]

"axpgn":In pratica, li disegni tutti e poi li conti
Però si può fare di meglio

Mi sa che ti è sfuggita questa parte:

"utente__medio":Ho trovato un metodo "semiautomatico" per il calcolo di $ f(m,n) $, ma non ancora una soluzione in forma chiusa. Rinnovo quindi la mia richiesta:
[quote="utente__medio"]Anche se è tutto sbagliato, qualcuno saprebbe dirmi se è possibile esprimere $ f() $ in forma chiusa?

Magari a quel punto facendo i calcoli e con i giusti passaggi si arriva proprio alla soluzione detta da @hydro.[/quote]

[axpgn]

No, non mi è sfuggita; c'è una strada molto più corta per giungere a meta, non è necessario "lavorare" ulteriormente su quella

[hydro1]

Dimostrazione:

Chiama $r_n$ il numero di colorazioni ammissibili per $n$ piani. Adesso prendi un grattacielo di $n+1$ piani: se l’ultimo piano è giallo, gli altri si possono colorare in $r_{n}$ modi. Se è blu, quello sotto dev’essere giallo e gli altri si colorano in $r_{n-1}$ modi. Ergo, $r_n=r_{n-1}+r_{n-2}$.

[axpgn]

Perfetto


Cordialmente, Alex

[utente__medio11]

"axpgn":No, non mi è sfuggita; c'è una strada molto più corta per giungere a meta, non è necessario "lavorare" ulteriormente su quella

Non sto dicendo che non mi interessano altri approcci o che non voglio ragionarci ulteriormente, semplicemente chiedevo per una mia curiosità personale se fosse possibile esprimere $f(m, n)$ in forma chiusa, tutto qui...