Un vecchio cesenatico con una griglia

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Un vecchio cesenatico con una griglia

Messaggio da amatrix92 » 27 apr 2011, 21:43

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?
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Un vecchio cesenatico con una griglia

Messaggio da Mist » 28 apr 2011, 17:40

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$
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Un vecchio cesenatico con una griglia

Messaggio da staffo » 28 apr 2011, 18:32

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....
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Valenash
Messaggi: 223
Iscritto il: 21 giu 2010, 16:31
Località: In provincia di pi greco
Contatta:

Re: Un vecchio cesenatico con una griglia

Messaggio da Valenash » 28 apr 2011, 18:44

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
Ho sempre pensato che la serie armonica non divergesse..poi ho scoperto che non è così...
Ho sempre pensato che l'infinito fosse un numero..grande ma un numero.. poi ho scoperto che non è così...
E' inutile.. la matematica non da' certezze e nuoce gravemente alla sanità mentale..xDxD

Immagine
Scopri il mondo di Ogame.

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Un vecchio cesenatico con una griglia

Messaggio da staffo » 28 apr 2011, 19:36

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

si capisce cosa dico?
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Valenash
Messaggi: 223
Iscritto il: 21 giu 2010, 16:31
Località: In provincia di pi greco
Contatta:

Re: Un vecchio cesenatico con una griglia

Messaggio da Valenash » 28 apr 2011, 19:44

Okok adesso ho capito.. sì funziona, basta contare quanti sono i pezzi che rimangono sul contorno allora =P
Ho sempre pensato che la serie armonica non divergesse..poi ho scoperto che non è così...
Ho sempre pensato che l'infinito fosse un numero..grande ma un numero.. poi ho scoperto che non è così...
E' inutile.. la matematica non da' certezze e nuoce gravemente alla sanità mentale..xDxD

Immagine
Scopri il mondo di Ogame.

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Un vecchio cesenatico con una griglia

Messaggio da staffo » 28 apr 2011, 19:46

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...
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Un vecchio cesenatico con una griglia

Messaggio da Mist » 28 apr 2011, 23:09

D: ma che cazz, non me ne esce uno che sia uno sul forum :?
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

flexwifi
Messaggi: 90
Iscritto il: 11 giu 2007, 22:04

Re: Un vecchio cesenatico con una griglia

Messaggio da flexwifi » 29 apr 2011, 17:49

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
Messaggi: 223
Iscritto il: 21 giu 2010, 16:31
Località: In provincia di pi greco
Contatta:

Re: Un vecchio cesenatico con una griglia

Messaggio da Valenash » 29 apr 2011, 19:12

flexwifi ha scritto: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 ;)
Ho sempre pensato che la serie armonica non divergesse..poi ho scoperto che non è così...
Ho sempre pensato che l'infinito fosse un numero..grande ma un numero.. poi ho scoperto che non è così...
E' inutile.. la matematica non da' certezze e nuoce gravemente alla sanità mentale..xDxD

Immagine
Scopri il mondo di Ogame.

flexwifi
Messaggi: 90
Iscritto il: 11 giu 2007, 22:04

Re: Un vecchio cesenatico con una griglia

Messaggio da flexwifi » 30 apr 2011, 01:09

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
Messaggi: 90
Iscritto il: 11 giu 2007, 22:04

Re: Un vecchio cesenatico con una griglia

Messaggio da flexwifi » 30 apr 2011, 10:15

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
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Un vecchio cesenatico con una griglia

Messaggio da staffo » 30 apr 2011, 13:06

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.
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Valenash
Messaggi: 223
Iscritto il: 21 giu 2010, 16:31
Località: In provincia di pi greco
Contatta:

Re: Un vecchio cesenatico con una griglia

Messaggio da Valenash » 30 apr 2011, 15:38

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??
Ho sempre pensato che la serie armonica non divergesse..poi ho scoperto che non è così...
Ho sempre pensato che l'infinito fosse un numero..grande ma un numero.. poi ho scoperto che non è così...
E' inutile.. la matematica non da' certezze e nuoce gravemente alla sanità mentale..xDxD

Immagine
Scopri il mondo di Ogame.

Rispondi