Ottima chiarezza espositiva. I commenti inoltre evidenziano i percorsi mentali dandone la giusta connessione col procedimento matematico evitando quindi la confusione tra le due cose. Un'educazione al corretto approccio ai problemi crea basi solide.
Grazie mille per l'apprezzamento. È proprio quello che cerco di fare. Sono importanti sia l'intuizione matematica, che la scrittura corretta della dimostrazione.
Non so se a distanza di un anno qualcuno leggerà questo commento, ma per il punto (a) ho un dubbio enorme. Il loop di quattro elementi è solo il più piccolo e semplice di tutti i loop possibili: come si fa a dimostrare (e prima ancora ad intuire... :D ) che se non ci sono loop "minimali" allora non ci sono loop di alcun tipo? Data una qualsiasi tabella 2nx2n e visualizzati gli n^2 "cassetti" da 4 caselle che la compongono, per me non è per nulla banale riuscire prima ad intuire e poi a dimostrare in maniera rigorosa che è sempre possibile sistemare 3 oggetti in ciascuno dei "cassetti" in modo che non si formino loop di alcun tipo. Ho provato a pensare ad esempi concreti con l'intenzione di individuare uno schema ricorrente/algoritmo che mi permettesse di costruire un tale insieme per una generica tabella 2nx2n, ma già per n=2 (tabella 6x6) non riesco a costruire un esempio esplicito di insieme di 27 oggetti senza loop (a partire da un paio di esempi relativi alla tabella 4x4). Non so, io trovo che sia questa la parte "difficile", poi da lì dimostrare che posso avere al massimo 3*n^2 oggetti è immediato. Sono giorni che sto provando a risolvere la prima domanda, e prima di guardare la soluzione avevo cercato di sfruttare il principio di induzione per dimostrare che una qualsiasi tabella 2nx2n senza loop di alcun tipo può avere al massimo 3*n^2 oggetti, ma non ci sono riuscita...
Mi rendo conto solo ora che il testo chiede di dimostrare che S labirintico non può avere più di 3*n^2 elementi, e non che S labirintico può sempre avere al massimo 3*n^2 elementi... Che vergogna 😓. Beh, almeno ho l'occasione per complimentarmi con lei, professore, per il bel canale, e ringraziarla per ciò che fa.
@@enzaottaviano6938 grazie. Non ho fatto in tempo a leggere, che già ho visto la risposta al commento... Capita, di leggere una cosa per un'altra... (nessuna vergogna, ci mancherebbe) In effetti i loop ci possono bene essere! Se ben ricordo, nella costruzione dell'esempio con 12 casselle nello schema 4x4, mostro che se sono le caselle della cornice c'è un loop.
Non penso di spoilerare il resto dell'esercizio se dico che il punto (d) chiede proprio di far vedere che per n=10 tale insieme labirintico di 3n^2 caselle non esiste... ;-)
Bellissimo video Alberto! Chissà se esiste una formula chiusa in n che conti quanti sono i diversi percorsi labirintici in una griglia 2nx2n a meno di simmetrie. Mi sa di roba abbastanza convoluta.
Grazie per l'apprezzamento! Mi sembra una cosa decisamente complicata, quella che proponi... Anche il più semplice "quante caselle ha l'insieme labirintico piu grande in una griglia 2n×2n?" mi pare decisamente complesso...
Scusami, per curiosità, nel punto c) come fai a dire sicuramente che si possa togliere una casella tale che l'insieme rimanga labirintico? Non mi veniva immediatamente un modo e quindi nella mia testa mi ero detto che presa una casella a caso da un insieme labirintico, il numero di caselle adiacenti coincide con sottoinsiemi labirintici che si formavano togliendo tale casella (questo mi sembrava più chiaro) e poi usando l'ipotesi induttiva per ciascuna componente concludevo come te.
In effetti buona anche l'idea di usare un'induzione generalizzata, ma mi sembrava più complicato. Per la tua domanda: un insieme labirintico è un albero (è connesso e non ha cicli). Pertanto basta togliere una foglia (una casella estremale del grafo) e resta un albero, ovvero un insieme labirintico. Diciamo che anche se non dico esplicitamente che si può trovare (e hai ragione, andrebbe fatto), nel passaggio dopo, quando mostro che proprietà ha la casella che tolgo, mostro che fondamentalmente sto togliendo una foglia dell'albero.
Ottima chiarezza espositiva. I commenti inoltre evidenziano i percorsi mentali dandone la giusta connessione col procedimento matematico evitando quindi la confusione tra le due cose. Un'educazione al corretto approccio ai problemi crea basi solide.
Grazie mille per l'apprezzamento.
È proprio quello che cerco di fare. Sono importanti sia l'intuizione matematica, che la scrittura corretta della dimostrazione.
Non so se a distanza di un anno qualcuno leggerà questo commento, ma per il punto (a) ho un dubbio enorme.
Il loop di quattro elementi è solo il più piccolo e semplice di tutti i loop possibili: come si fa a dimostrare (e prima ancora ad intuire... :D ) che se non ci sono loop "minimali" allora non ci sono loop di alcun tipo?
Data una qualsiasi tabella 2nx2n e visualizzati gli n^2 "cassetti" da 4 caselle che la compongono, per me non è per nulla banale riuscire prima ad intuire e poi a dimostrare in maniera rigorosa che è sempre possibile sistemare 3 oggetti in ciascuno dei "cassetti" in modo che non si formino loop di alcun tipo.
Ho provato a pensare ad esempi concreti con l'intenzione di individuare uno schema ricorrente/algoritmo che mi permettesse di costruire un tale insieme per una generica tabella 2nx2n, ma già per n=2 (tabella 6x6) non riesco a costruire un esempio esplicito di insieme di 27 oggetti senza loop (a partire da un paio di esempi relativi alla tabella 4x4).
Non so, io trovo che sia questa la parte "difficile", poi da lì dimostrare che posso avere al massimo 3*n^2 oggetti è immediato.
Sono giorni che sto provando a risolvere la prima domanda, e prima di guardare la soluzione avevo cercato di sfruttare il principio di induzione per dimostrare che una qualsiasi tabella 2nx2n senza loop di alcun tipo può avere al massimo 3*n^2 oggetti, ma non ci sono riuscita...
Mi rendo conto solo ora che il testo chiede di dimostrare che S labirintico non può avere più di 3*n^2 elementi, e non che S labirintico può sempre avere al massimo 3*n^2 elementi... Che vergogna 😓.
Beh, almeno ho l'occasione per complimentarmi con lei, professore, per il bel canale, e ringraziarla per ciò che fa.
@@enzaottaviano6938 grazie. Non ho fatto in tempo a leggere, che già ho visto la risposta al commento... Capita, di leggere una cosa per un'altra... (nessuna vergogna, ci mancherebbe) In effetti i loop ci possono bene essere! Se ben ricordo, nella costruzione dell'esempio con 12 casselle nello schema 4x4, mostro che se sono le caselle della cornice c'è un loop.
Non penso di spoilerare il resto dell'esercizio se dico che il punto (d) chiede proprio di far vedere che per n=10 tale insieme labirintico di 3n^2 caselle non esiste... ;-)
@@AlbertoSaraccoGrazie mille!
Bellissimo video Alberto! Chissà se esiste una formula chiusa in n che conti quanti sono i diversi percorsi labirintici in una griglia 2nx2n a meno di simmetrie. Mi sa di roba abbastanza convoluta.
Grazie per l'apprezzamento!
Mi sembra una cosa decisamente complicata, quella che proponi...
Anche il più semplice "quante caselle ha l'insieme labirintico piu grande in una griglia 2n×2n?" mi pare decisamente complesso...
Tra l'altro, quando ti rimetti a fare video, tu?
Scusami, per curiosità, nel punto c) come fai a dire sicuramente che si possa togliere una casella tale che l'insieme rimanga labirintico? Non mi veniva immediatamente un modo e quindi nella mia testa mi ero detto che presa una casella a caso da un insieme labirintico, il numero di caselle adiacenti coincide con sottoinsiemi labirintici che si formavano togliendo tale casella (questo mi sembrava più chiaro) e poi usando l'ipotesi induttiva per ciascuna componente concludevo come te.
In effetti buona anche l'idea di usare un'induzione generalizzata, ma mi sembrava più complicato. Per la tua domanda: un insieme labirintico è un albero (è connesso e non ha cicli). Pertanto basta togliere una foglia (una casella estremale del grafo) e resta un albero, ovvero un insieme labirintico. Diciamo che anche se non dico esplicitamente che si può trovare (e hai ragione, andrebbe fatto), nel passaggio dopo, quando mostro che proprietà ha la casella che tolgo, mostro che fondamentalmente sto togliendo una foglia dell'albero.