Un vecchio cesenatico con una griglia

[amatrix92]

Un saldatore dispone di sbarrette metalliche di lunghezza 2, e vuole costruire una griglia costituita da $ n \cdot n $ quadratini di lato 1. Gli è permesso segare a metà le sbarrette e saldarle fra loro, ma senza sovrapporle o incrociarle. Qual'è il minimo numero di sbarrette che occorre segare per ottenere la grglia?

La soluzione che propongono è scritta a metà e non mi convince per nulla; io ne ho trovata un'altra che porta a risultati diversi. Voi come lo fareste?

[Mist]

Due considerazioni iniziali: se $n=2$ allora la barretta spezzata è solo una. Chiameremo questo caso "quadratone"; se $n=1$ allora le barrette da spezzare sono 2. Chiameremo questo caso "quadratino"

Se $2|n=2k$ allora si ha che incrementando il lato di due quadratini si andranno a costruire $2k+1$ quadratoni e quindi si vanno ad aggiungere $2k+1$ barrette spezzate. in altre parole, detto $a_n$ il numero minimo di barrette che si vanno a spezzare costruendo un quadrato grigliato come richiesto, $a_{2k} = a_{2(k-1)} +2k+1 = a_{2[k-(k-1)]}+2(k-1)+\sum_{h=2}^{k}2a-1 = 1+k^2+2k-2 = k^2+2k-2$

Se invece $2\nmid n=2k+1$ si ha che aggiungendo due quadratini al lato del quadrato si vanno a creare $2k+1$ quadratoni e $4$ quadratini più piccoli che vanno a completare quella sorta di cornice di quadratini più piccoli che si va sempre a formare nel caso in cui $n$ sia dispari. In tutto quindi si vanno ad aggiungere $2k+5$ barrette spezzate. In altre parole si ha quindi che
$a_{2k+1} = a_{2(k-1)+1} +2k+5 = a_1+2\frac{k(k+1)}{2}+5k = k^2+6k+2$

[staffo]

c'è un caso migliore del "quadratone", cioè disporre le barrette del tipo scalate, cioè la prima orizzontale dal primo punto, la seconda sotto orizzontale spostata di uno, e così via, in modo tale da incastrarle tutte senza tagliarne nessuna, fatta eccezione per un po' di bordi;

il problema è che non riesco a dimostrare che questa è effettivamente la configurazione migliore....

[Valenash]

Se ho capito cosa intendi questa è comunque peggiore del quadratone, perchè ti rimangono un sacco di barrette da 1cm da sistemare in mezzo..più che a fare un quadratone

[staffo]

allora non hai capito, in mezzo non mi rimane nemmeno una barretta da sistemare,

si capisce cosa dico?

[Valenash]

Okok adesso ho capito.. sì funziona, basta contare quanti sono i pezzi che rimangono sul contorno allora =P

[staffo]

si, questo sarebbe ok per un quesito a risposta multipla, ma il problema è che non posso dimostrare che questa è effettivamente la configurazione migliore, perchè potrebbe esistere un'altra configurazione che non considero, contarli è banale, non ci vuole molto, però credo che valga nemmeno un 20% del problema...

[Mist]

D: ma che cazz, non me ne esce uno che sia uno sul forum

[flexwifi]

Con l'algoritmo di staffo il numero minimo di pezzi da tagliare dovrebbe essere $ (n+1) $ ma non riesco a dimostrare che effettivamente e' il caso migliore.

[Valenash]

Con l'algoritmo di staffo il numero minimo di pezzi da tagliare dovrebbe essere $ (n+1) $ ma non riesco a dimostrare che effettivamente e' il caso migliore.

Forse hai contato male.
Facendo come dice staffo, ad esempio, per n=2 puoi fare un quadratone che usa 1 solo taglio.
In generale, mi pare che con il suo metodo siano sufficienti $n-1$ tagli per $n$ pari, e $n+1$ tagli per $n$ dispari (ma ho fatto la figura molto male, potrei essermi sbagliato a contare).
E forse sono anche in grado di dimostrare che sia il modo migliore..ma non ne sono certo, nel senso che non son sicuro che una cosa simile la possano accettare come dimostrazione rigorosa.. tu dici, ad esempio per $n$ dispari, che comunque sia ogni riga e ogni colonna devono avere almeno un taglio poichè le barre son da due, dunque almeno $n+1$ tagli in tutto ($2n+2$ pezzi da uno, perchè ci sono $n+1$ righe e $n+1$ colonne, per avere una scacchiera $n$ x $n$, poichè una riga della scacchiera è contenuta tra due righe fatte con le sbarre). Ovviamente dopo gli devi mostrare che esiste un modo per farlo, allora gli proponi il modo di mettere le sbarre che ha detto staffo.

In quella pari non son certo di come dimostrare che sia la cosa migliore da fare.. ma penso che con un ragionamento simile, ovviamente adattato al fatto che $n$ sia pari, ci si possa riuscire =)
Ad esempio, provando a dire che o in un senso o nell'altro ci dovranno essere delle barre tagliate, perchè altrimenti si scontrerebbero..e proseguendo col ragionamento

[flexwifi]

Si scusa... In effetti non avevo tenuto conto che nel caso 2x2 hai un quadratone e quindi basta un solo taglio. Ma come risolveresti il caso 4x4? Col metodo di staffo a me viene fuori che servirebbero almeno 5 tagli. Se invece vedi la griglia 4x4 come 4 quadratoni bastano solo 4 tagli. Tu riesci a trovare una configurazione nella griglia 4x4 che funziona con solo con 3 tagli? Sto cercando di risolvere le griglie piccole per trovare una regola più generale...

[flexwifi]

Ho trovato una configurazione che funziona con la griglia 4x4 con solo 3 tagli. In pratica basta usare la tecnica di staffo come se la griglia fosse 3x3 e poi si aggiunge una "cornice" esterna di sbarrette da 2 (lo posso fare perchè $ n $ è pari). A questo punto per completare basta aggiungere 6 pezzettini da 1 che ottieni con esattamente 3 tagli. Questa tecnica in effetti la posso usare per ogni $ n $ pari e mi assicura di ottenere la griglia con $ (n-1) $ tagli. Adesso però chi ci assicura che questa è la configurazione migliore possibile?

[staffo]

Allora, chiariamo un attimo le cose.
Per le configurazioni di caselle dispari la dimostrazione di Valenash è giusta, e questo è indiscutibile.

Per le configurazioni pari, non continuate a sparare numeri, che tanto non è utile, cercate piuttosto un metodo per dire che è proprio quella la migliore.

[Valenash]

Beh, avevo dato l'input di come iniziare il ragionamento per quella pari..
comunque, direi che in quel caso si possa ragionare così: dato che anche mettendo tutte le sbarre in fila senza doverne tagliare per ottenere lati di lunghezza pari, occorrerebbero molti tagli per ogni riga e ogni colonna in quanto altrimenti le sbarre si sovrapporrebbero. Questo ci fa quindi capire che è necessario almeno un taglio per ogni riga e uno per ogni colonna. Perchè?? ma perchè se prendiamo una riga senza tagli, allora necessariamente vi si scontreranno tutte le colonne (o si scontreranno tutte nella riga prima), ottenendo un sacco di tagli (precisamente $ \frac {n}{2}$). Dunque possiamo ridurre sino a fare solo un taglio per riga e uno per colonna (eccetto quelle esterne) ottenendo il famoso $n-1$.

EDIT: ho controllato la soluzione ufficiale (senza leggerla), e conferma i valori che abbiamo trovato.
Ad ogni modo, la mia dimostrazione del punto $n$ pari pensate potrebbe andare o non è abbastanza rigorosa e dunque farebbe perdere dei punti??