Evitare le L bianche!

[Il_Russo]

Essendo scaduti i termini per la spedizione degli esercizi per la telematica dell'Enriques posto qui il combinatorio (cioè il 4)

Si consideri una scacchiera quadrata di lato 2n+1, consistente quindi di $ {(2n+1)}^2 $ caselle, inizialmente tutte di colore nero. Qual è il numero massimo di caselle che possono essere colorate di bianco , senza che vi sia nessuna “L” (come quella della figura sottostante o delle tre configurazioni ottenute ruotando la figura di multipli di 90 gradi) costituita da tre caselle bianche?

Non è difficile ma neanche banale

Buon $ lavoro^3 $

[Pigkappa]

La nostra soluzione è abbastanza brutta, prima di postarla aspetto qualche giorno per vedere se c'è di meglio

[Gatto]

Il numero di caselle totali in ogni caso viene quindi un quadrato perfetto dispari, provo ad azzardare una risposta:

$ (2n + 1)(n + 1) $?

[giove]

Anch'io aspetto allora
Non credo che la nostra sia meglio di quella dei carraresi

[salva90]

Anch'io aspetto allora
Non credo che la nostra sia meglio di quella dei carraresi

dei carraresi? di pigkappa vuoi dire, visto che ha praticamente fatto tutto lui

$ \textrf{squadra\ di\ carrara}\to \textrf{Pigkappa} $

[¬[ƒ(Gabriel)³²¹º]¼+½=¾]

Il numero di caselle totali in ogni caso viene quindi un quadrato perfetto dispari, provo ad azzardare una risposta:

$ (2n + 1)(n + 1) $?

si la risposta è quella, il problema è dimostrarlo formalmente

[darkcrystal]

Io i giochi non li ho fatti... questa è quella che mi è venuta in mente, date pure anche giudizi estetici, a questo punto

EDIT: Mi fa giustamente notare jordan che questo post non si capisce granchè: voglio dimostrare quello che già qualcun altro ha scritto, che il valore richiesto è $ (n+1)(2n+1) $

Osservazione: preso un qualunque quadrato 2x2, questo contiene al massimo 2 caselle bianche (per ovvi motivi)
LEMMA: considero una grossa L, di quelle che si ottengono levando da un quadrato (2n+1)x(2n+1) un quadrato (2n-1)x(2n-1). Questa non contiene più di 4n+1 caselle bianche.
Dividiamola infatti in quadratoni 2x2 come spero si capisca dalla figura che allego.
Resta scoperta una sola casella, e quanti sono i quadratoni? Sono $ \frac{2(2n+1)-2}{4} \cdot 2 $, ed ognuno contiene al massimo 2 caselle bianche per quanto detto sopra. Perciò le caselle bianche sono al massimo 1 (scoperta) + 2 per numero dei quadratoni, ossia $ 1+2\frac{2(2n+1)-2}{4} \cdot 2=4n+1 $.

Ok, forti del nostro grande lemma ( ) andiamo avanti.
Per un quadrato 1x1 la relazione già scritta da altri (vedi EDIT) è abbastanza vera; per quadrati più grandi, taglio un quadrato (2n-1)x(2n-1) dall'angolo in alto a sinistra

Dunque, per il lemma e per induzione, il quadrato $ (2n+1) \times (2n+1) $ contiene al massimo $ (2(n-1)+1)(n-1+1) $ caselle bianche nel quadrato $ (2n-1) \times (2n-1) $ in alto a sinistra, e 4n+1 altre caselle bianche nella grossa L a sud-est. Ma allora in totale le caselle bianche in tutto il quadrato non sono più di $ (2n-1)(n)+4n+1=2n^2+3n+1=(2n+1)(n+1) $, c.v.d.

Il fatto che questo numero di caselle si possa effettivamente colorare rispettando le condizioni imposte è immediato: o coloro di bianco una riga si e una riga no, o, se preferite, a scacchiera, con più caselle bianche che nere.

Ciao!

[jordan]

..., o, se preferite, a scacchiera, con più caselle bianche che nere.

bella dimostr, ma la conclusione?

[darkcrystal]

Il numero di caselle totali in ogni caso viene quindi un quadrato perfetto dispari, provo ad azzardare una risposta:

$ (2n + 1)(n + 1) $?

si la risposta è quella, il problema è dimostrarlo formalmente

Ecco, si, il mio scopo era "dimostrarlo formalmente"... per quello ad un certo punto ho scritto "la relazione già scritta da altri", intendevo quella che ho quotato

[jordan]

no, dai si capiva anche prima

quello che volevo dirti è fai attenzione a quello che ho riportato nel riquadro bianco!!!