Muratura di una casa [Senior 2002]

[edriv]

Abbiamo una casa di forma quadrata (ha un solo piano), di lato n metri.

Il suo interno ora è completamente vuoto, ci sono solo le mura esterne e una porta per uscire. L'architetto deve decidere dove mettere le mura interne; per questo disegna un quadrato di lato n diviso in $ ~ n^2 $ quadratini, e colora i lati di qualche quadratino per decidere dove mettere le mura.
Vuole fare in modo che, una volta entrati in casa, si possa raggiungere qualsiasi punto (senza buttar giù le mura possibilmente).

Dimostrare che ci saranno al più $ ~ (n-1)^2 $ metri di mura.

[robbieal]

Provo, ma non mi sembra un granchè come dimostrazione....

Per semplicità consideriamo le linee orizzontali del quadrato maggiore: le possiamo colorare tutte per al massimo $ n-1 $ metri, altrimenti non si può raggiungere ogni punto della casa; per lo stesso motivo non possiamo colorare neanche un metro delle linee verticali. Quindi, poichè le linee orizzontali sono $ n-1 $, si ha che il numero massimo di metri di mura interna è $ (n-1)^2 $.

Aspetto correzioni.

[Marco]

Non torna. Così dimostri solo che i muri orizzontali sono al massimo $ (n-1)^2 $.

Ma non è detto che massimizzando prima i muri orizzontali e poi quelli verticali separatamente arrivi al massimo dei muri totali.

[pic88]

Induzione?
per n=2 è vero.
vero per n, allora nel quadrato di lato n+1 si consideri quello di lato n con un vertice in uno dei quattro. Questo quadrato, di lato n, conterrà al più (n-1)^2 mura, e dovrà essere accessibile alla restante parte del quadrato grande. Quindi potrà essere coperto al più il suo semiperimetro meno una casella, e per farlo useremo 2n-1 metri di muro.
fine.
anche se mi pare troppo facile così...

[darkcrystal]

Carino!

Abbozzata ma dovrebbe tornare. Poniamo in ogni quadratino il vertice di un grafo. Dalla formula di Eulero segue che, dato che c'è una faccia sola (altrimenti potremmo costruire una nuova parete...), v=s+1, cioè s=n^2-1 (almeno). Poichè in tutto i segmenti che l'architetto può colorare sono 2(n^2-n), le pareti sono al massimo 2n^2-2n-(n^2-1)=n^2-2n+1=(n-1)^2

Ciao!

[edriv]

Ok, la mia era più o meno come quella di darkcrystal:

prendiamo i punti sul perimetro da cui parte un muro. Questi punti sono le radici di alberi disgiunti (gli archi degli alberi sarebbero i muri, i nodi i punti della quadrettatura per cui passa un muro). Quindi, se ad ogni nodo associo l'arco che lo avvicina alla radice, ottengo una corrispondenza biunivoca nodi del quadratino interno appartenenti all'albero - pezzi di muro.
Beh, potrebbero anche esserci alberi che non toccano il perimetro esterno, in tal caso scelgo una radice e guadagno addirittura un arco.

Quindi, c'è una corrispondenza biunivoca tra un sottoinsieme dei punti del quadrato interno e i pezzi di muro. Guarda a caso il quadratino interno ha $ ~ (n-1)^2 $ punti.

[Marco]

Questo quadrato, di lato n, conterrà al più (n-1)^2 mura

Non torna nemmeno questa. Il fatto è che stai supponendo che il sottoquadrato sia connesso.

Controesempio: Casa 4x4 e i muri sono tra le case b1-c1, b1-b2, b2-c2, c2-d2, d2-d3, a2-a3, a3-b3, c3-c4, b4-c4. Tutti i quadrati 3x3 hanno 5 muri.