Problema 2

[Cosimo.14]

Problema 2

Data una scacchiera 5x5 si possono colorare i suoi elementi di 2 colori differenti in modo che uno stesso colore non abbia più di un lato in comune, quante sono le combinazioni possibili?

Problema 2+

Generalizzare.

------------------------------------------------------------------------------------------------

Per il problema 2+ credo di aver trovato una regola, stavo provando a dimostrarla per induzione ma non ci sono ancora riuscito, vi chiedo di risolverlo sotto un altro spoliler in modo che riesca ad avere ancora un pò di tempo per provarci.

Per il problema 2 io ho seguito questa strada:

Sono partito da una scacchiera 2x2 per poi passare ad una 3x3 ed ho usato dei grafi per schematizzare le "forme" che possono ricoprire sulla scacchiera ed arrivare velocemente a soluzione anche per scacchiere più grandi, questo mi ha permesso di dividere le soluzioni in "gruppi" che poi ho moltiplicato per opportuni fattori a seconda delle loro simmetrie, il problema del mio ragionamento è che per ogni rappresentante di questi gruppi devo completarlo a mano e vedere le sue estensioni ad una scacchiera più grande, la soluzione che ho è corretta, ma non saprei come formalizzarla dato che in parte è per tentativi, non avendo un programma per costruire dei grafi non so nemmeno come postarla, in caso se c'è bisogno posto una foto.

[Quinzio]

La soluzione che cerchi e' abbastanza semplice:
$S_{n \times n} = -2 + 4F_{n+1}$

dove $F_n$ e' la sequenza di Fibonacci: $F_2 = 1, F_3 = 2, F_4 = 3$ ecc.

[Cosimo.14]

Sbagliata.

[Quinzio]

Pardon, avevo ricordato male la soluzione che avevo pensato ore fa.
Adesso dovrebbe essere corretta.

[Cosimo.14]

"Quinzio":Pardon, avevo ricordato male la soluzione che avevo pensato ore fa.
Adesso dovrebbe essere corretta.

[strike]Rimane errata [/strike]

No, scusa così è corretta ho letto male i termini Fn , io avevo risolto in questo modo:

\(\displaystyle S_1 = 2 + 4F_0 \)
\(\displaystyle S_n = S_{n-1} + 4F_{n-1} \)

Ma non riesco con la dimostrazione per induzione

[Quinzio]

La dimostrazione per induzione e' simile a quella di questo post:
https://www.matematicamente.it/forum/vi ... 7&t=242295

Anche li c'entra la successione di Fibonacci.