II gara UNIMI

[Duilio]

Qualcuno di voi era presente alla II gara dell\'unimi?
<BR>Mi premerebbe sapere alcune delle soluzioni inviate, in particolare sull\'esercizio del quadrilatero diviso in 4 parti, sui sottoinsiemi Ai, nonché sull\'ultimo.
<BR>
<BR>A me questa è andata verosimilmente da schifo....

[Antimateria]

Duilio, è andata verosimilmente da schifo un po\' a tutti...
<BR>
<BR>Per il quadrilatero, veniva che d può valere a+b-c, a-b+c e -a+b+c. In pratica tracci il parallelogrammo che ha vertici nei punti medi dei lati, tracci le diagonali del quadrilatero e dimostri che la somma delle aree opposte dev\'essere uguale.
<BR>
<BR>L\'ultimo si faceva dicendo che, a meno dei segni, ci sono k=2^n² configurazioni per la matrice. Quindi, detta X la somma totale degli elementi della matrice, X può assumere al più k valori distinti. Ora, se prendi una riga o colonna con somma negativa e la cambi di segno, X diventa strettamente maggiore. Ma siccome vi sono solo un numero finito di possibili valori per X, dopo al più k mosse non potrai più trovare righe o colonne con somma negativa.
<BR>
<BR>Quello sui sottoinsiemi Ai è ancora avvolto nel mistero. <IMG SRC="images/forum/icons/icon24.gif"> [addsig]

[ReKaio]

uno scan dei testi, per chi si volesse cimentare
<BR>
<BR><!-- BBCode Start --><A HREF="http://kayo.altervista.org/milano_II.jpg" TARGET="_blank">kayo.altervista.org/milano_II.jpg</A><!-- BBCode End -->
<BR>
<BR>graficamente fanno schifo, per via della correzione neppure della stessa larghezza
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: ReKaio il 13-02-2004 12:07 ]

[LB]

Per i sottoinsiemi, si fa per induzione.
<BR>
<BR>Consideriamo tutti gli A_k che non contegono alcun x in {1 ... n - 1}.
<BR>Se ce ne sono almeno due, essi sono ambedue uguali a {n}, essendo non vuoti, e abbiamo finito.
<BR>Altrimenti, se ne esiste almeno uno, sia d il suo indice.
<BR>Se non ne esiste nessuno sia d l\'indice di un insieme che contiene n, se ne esiste almeno uno o un indice qualsiasi altrimenti.
<BR>
<BR>Si risolva ora il problema relativamente agli A_k con k != d, considerando i primi n - 1 elementi e siano I\' e J\' la soluzione.
<BR>
<BR>Se I\' e J\' e\' soluzione anche del caso con n abbiamo finito.
<BR>Altrimenti, vuol dire che una delle due unioni contiene l\'elemento n e l\'altra no.
<BR>In tal caso aggiungiamo A_d a quella che non lo contiene.
<BR>
<BR>Il caso base per n = 2 e\' ovvio.
<BR>
<BR>Nota: le argomentazioni di Antimateria sono corrette: <!-- BBCode Start --><B>questa soluzione non funziona</B><!-- BBCode End -->.
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: LB il 14-02-2004 14:03 ]

[Antimateria]

Scusa LB, non ho capito bene quello che dici.
<BR>
<BR>Supponiamo che n=3, A₁={1,3}, A₂={2,3}, A₃={1}, A₄={2}.
<BR>
<BR>Ora, il tuo algoritmo può scegliere d=1 o d=2.
<BR>
<BR>Nel caso d=1, togliamo A₁ e risolviamo il problema per n=2: l\'unico modo è prendere da una parte A₂ e dall\'altra A₄. Ma adesso, rimettendo n=3, abbiamo da una parte {2,3} e dall\'altra {2}. Dunque, sempre secondo il tuo algoritmo, dovremmo aggiungere A₁={1,3} a {2}, che ci fa ottenere {1,2,3}, che però è diverso da {2,3}.
<BR>
<BR>Il caso d=2 è esattamente simmetrico, e porta anch\'esso ad ottenere {1,2,3} da una parte e {1,3} dall\'altra.
<BR>
<BR>Forse ho capito male la tua spiegazione?[addsig]

[Antimateria]

Ok, finalmente sono usciti risultati+soluzioni.
<BR>
<BR>Anzitutto, complimenti a LB per aver letteralmente stracciato la concorrenza di entrambe le categorie!
<BR>
<BR>Poi, riguardo al famigerato problema 4... quando ho visto quella soluzione così corta mi è venuto un attacco di depressione acuta, ma poi mi sono accorto che il metodo proposto non funziona affatto, o almeno ha bisogno di qualche ritocco.
<BR>
<BR>Date un\'occhiata anche voi, e ditemi che ne pensate.
<BR>Per i testi: <!-- BBCode Start --><A HREF="http://users.mat.unimi.it/users/giochi/0304/0304II.pdf" TARGET="_blank">http://users.mat.unimi.it/users/giochi/ ... 4II.pdf</A><!-- BBCode End -->
<BR>Per le soluzioni: <!-- BBCode Start --><A HREF="http://users.mat.unimi.it/users/giochi/ ... 4IIsol.pdf" TARGET="_blank">http://users.mat.unimi.it/users/giochi/ ... sol.pdf</A><!-- BBCode End -->
<BR>[addsig]

[Antimateria]

Va bene, va bene, copio qui testo e soluzione ufficiale del 4:
<BR>
<BR>
<BR><!-- BBCode Start --><B>Testo</B><!-- BBCode End -->
<BR>Sia n un numero maggiore di 1 e si considerino n+1 sottoinsiemi non vuoti A₁, A₂, ..., A_n+1 dell\'insieme X={1, 2, ..., n}. Dimostrare che esistono due sottoinsiemi disgiunti e non vuoti I, J dell\'insieme ={1, 2, ..., n+1} tali che l\'unione degli insiemi A_i, al variare di i in I, coincida con l\'unione degli insiemi A_j, al variare di j in J.
<BR>
<BR><!-- BBCode Start --><B>Soluzione ufficiale</B><!-- BBCode End -->
<BR>Il numero di sottoinsiemi non vuoti di X è 2ⁿ-1 mentre il numero delle possibili unioni di sottoinsiemi è 2ⁿ⁺¹-1 in quanto X ha n+1 elementi. Quindi troveremo due unioni fra loro coincidenti e se eliminiamo i sottoinsiemi in comune troviamo due unioni composte di sottoinsiemi corrispondenti a indici diversi, cioè esattamente la tesi.
<BR>
<BR>
<BR>Ecco, al di là di quel \"X ha n+1 elemeni\", dove ovviamente al posto di X dovrebbe esserci l\'insieme dei sottoinsiemi A_k, quello che non capisco è come si escluda il caso in cui alle due unioni trovate con il pigeonhole corrispondano due insiemi di A_k, di cui uno è contenuto nell\'altro (rispetto agli indici). Infatti, se così fosse, eliminando i sottoinsiemi comuni ci ritroveremmo con un insieme vuoto! E in ogni caso, non è affatto detto che eliminando i sottoinsiemi comuni, si preservi l\'identità delle unioni!
<BR>Non ho idea di come sistemare questo dettaglio con poche modifiche alla soluzione. Pensavo che in realtà, per il pigeonhole si possono trovare addirittura 3 unioni di A_k coincidenti, ma anche qui può capitare che siano tutte \"incapsulate\" l\'una nell\'altra rispetto agli indici, o comunque che il giochetto dell\'eliminare gli A_k comuni non preservi l\'unione.
<BR>
<BR>Qualche idea?[addsig]

[Marco]

Ciao. [messaggio lungo]
<BR>
<BR>Io non ho partecipato alle gare, ma il problema mi è stato \"allungato\" in un carteggio privato da MindFlyer. Non è stato semplice, ma vi riporto il mio mail di risposta... Dato che ora mi ha detto che il problema è pubblico, posso pubblicare anche la mia risposta, che riporto testualmente...
<BR>
<BR>La soluzione è (si fa per dire) elementare, nel senso che non usa algebra lineare. Suppongo che una vera soluzione semplice non esista (perché esistono ostruzioni non banali che vanno aggirate). Ma almeno mi consolo...
<BR>
<BR>Ok. Pronti? Tenetevi forte...
<BR>
<BR>==========================================
<BR>
<BR>Ciao, Mind.
<BR>
<BR>Ho finito il problema degli insiemetti. Devo ammettere che ho ciancicato abbastanza, prima di trovare la strada giusta. Una bella dimostrazione lapidaria non ce l\'ho, però. Volevo fare una soluzione, ne è uscito un paper. Mi ci è voluta una settimana, due notti insonni e un bel mal di testa (un po\' troppo per qualunque gara). Grrrr. Maledetto MindFlyer! Comunque, beccati questa:
<BR>
<BR>----------------------------------------
<BR>
<BR> On MindFlyer\'s Problem
<BR> - by Marco ***** -
<BR>
<BR>----------------------------------------
<BR>
<BR>Giusto per fare un po\' di scena, comincio con un po\' di
<BR>
<BR>Definizioni
<BR>-----------
<BR>
<BR>Per sveltire la notazione, denoto U_I = \\union{i \\in I}{A_i} e analogamente U_J.
<BR>
<BR>La DIMENSIONE del problema è data dalla cardinalità di X.
<BR>
<BR>Un sottoinsieme Y di X non vuoto, che ha k elementi, scelti in modo tale che compaiono in al più k insiemi A_i tra quelli dati, e non nei restanti A_i, si dice che è un\'ISOLA. k è la GRANDEZZA dell\'isola Y.
<BR>
<BR>Una soluzione (I,J) al problema si dice COPRENTE se X = U_I [ = U_J ]. Si dice SUB-COPRENTE se X \\ U_I è un\'isola.
<BR>
<BR>+++++++
<BR>
<BR>In ogni dimostrazione che si rispetti non possono mancare un po\' di lemmi:
<BR>
<BR>Lemma di Non Banalità
<BR>---------------------
<BR>Posso supporre che ogni elemento di X compaia almeno una volta negli A_i.
<BR>
<BR>Dim.: Il problema ottenuto sostituendo X con \\union{A_i} è equivalente a quello dato. []
<BR>
<BR>Lemma delle Isolette
<BR>--------------------
<BR>
<BR>Se un problema (X, {A_i}) non ha isole, allora ogni x \\in X compare almeno due volte negli A_i.
<BR>
<BR>Dim. Se x comparisse solo al più una volta, {x} sarebbe un\'isola. []
<BR>
<BR>Lemma dei Controesempi
<BR>----------------------
<BR>
<BR>Un controesempio minimale rispetto alla dimensione non possiede isole.
<BR>
<BR>Dim.: Supponiamo sia dato P = (X, {A_i}) un controesempio di dimensione n al problema e Y un\'isola di grandezza k. Considero il problema P\' ottenuto da P cancellando gli elementi di Y e gli al più k A_i che contengono elementi di Y. P\' è un controesempio, perché se non lo fosse, la sua soluzione (I,J) sarebbe anche soluzione di P. Ma P\' ha dimensione n - k < n. Perciò P non è minimale. []
<BR>
<BR>Lemma di Coinvolgimento
<BR>-----------------------
<BR>
<BR>Se una soluzione è coprente, allora esiste una soluzione (necessariamente coprente) che coinvolge tutti gli A_i.
<BR>
<BR>Dim.: Basta assegnare eventuali A_i rimasti fuori dalla soluzione ad una qualunque delle due unioni. []
<BR>
<BR>+++++++
<BR>
<BR>Ok. Fatti i preliminari ora inizia la ciccia.
<BR>
<BR>Lemma di Sub-copertura
<BR>----------------------
<BR>
<BR>Sia n >= 1. Suppongo la tesi del quesito dimostrata fino alla dimensione n-1. Se il problema P = (X, {A_i}), di dimensione n, ha una soluzione (I,J), allora ha anche una soluzione coprente o sub-coprente.
<BR>
<BR>Dim.:
<BR>
<BR>Sia Y = X \\ U_I. Se è vuoto, la soluzione data è coprente. Se non è vuoto, sia k la sua cardinalità. Sia B l\'insieme degli A_i che non compaiono nella soluzione (I,J) e sia k\' la sua cardinalità. Gli elementi di Y, per costruzione non compaiono negli A_i della soluzione.
<BR>Se k >= k\', Y è un\'isola e la soluzione (I,J) è sub-coprente.
<BR>
<BR>Se invece k < k\', considero il sottoproblema (Y, B) (*). Dato che ha dimensione minore, la tesi del quesito è vera, quindi trovo una soluzione (I\',J\'). Ma allora ( I \\union I\' , J \\union J\' ) è una soluzione di P per cui le unioni sono strettamente più grandi di U_I. Posso rifare il ragionamento con questa nuova soluzione. Questo procedimento non può continuare all\'infinito, dato che X è finito, quindi ad un certo punto termina con Y vuoto o isola. []
<BR>
<BR>(*) A rigore, potrebbe darsi che B abbia troppi insiemi, rispetto al quesito iniziale. Questo chiaramente non è un problema, dato che avere più A_i del necessario a disposizione indebolisce la tesi.
<BR>
<BR>Dimostro il seguente enunciato più forte:
<BR>
<BR>Claim
<BR>-----
<BR>
<BR>Sia n > 1. Suppongo la tesi del quesito dimostrata fino alla dimensione n-1. Sia dato un problema P = (X, {A_i}) di dimensione n. Almeno uno degli enunciati (a) e (b) è vero:
<BR>
<BR>(a) P ha una soluzione coprente
<BR>(b) P ha un\'isola
<BR>
<BR>+++++++
<BR>
<BR>Quindi, non solo trovo una soluzione, ma addirittura la trovo coprente, a meno che non possa ridurre la soluzione del problema cancellando isole.
<BR>
<BR>Dato per buono il Claim, il problema si risolve facilmente per induzione sulla dimensione del problema.
<BR>
<BR>n=1. L\'unica possibilità è A_0 = A_1 = X. I = {0} e J = {1} è una soluzione.
<BR>
<BR>Sia ora n > 1. L\'ipotesi induttiva garantisce che il Claim e il Lemma di Sub-copertura si possono applicare. Inoltre, se esiste un controesempio, esso è minimale. Per il Claim dove valere (a) o (b). (b) contraddice il Lemma dei Controesempi, quindi vale (a), e il problema ha una soluzione. []
<BR>
<BR>Dim. del Claim
<BR>--------------
<BR>
<BR>Sia dato P. Se ha isole, vale (b) e ho finito. Supponiamo che non ne abbia. Dimostro che vale (a). Si noti che, per il Lemma di Sub-copertura, se esiste una soluzione, allora ne esiste una necessariamente coprente (dato che non ci sono isole non può essere sub-coprente).
<BR>
<BR>Scelgo arbitrariamente un A_i che chiamo A e x \\in A. Considero il problema P\', ottenuto cancellando A e tutte le occorrenze di x negli A_i.
<BR>
<BR>P\' è un problema di dimensione < n, quindi esiste una soluzione (I,J). Per il Lemma di Sub-copertura, posso supporre tale soluzione sub-coprente oppure coprente.
<BR>
<BR>Caso coprente.
<BR>
<BR>Considero (I,J) anche nel problema P. U_I e U_J contengono già X \\ {x}. Per il Lemma delle Isolette, x deve apparire in qualche A_i =|= A. Per il Lemma di Coinvolgimento, posso supporre che tale A_i compaia nella soluzione. Quindi, x compare in almeno una delle unioni. Aggiungendo A all\'altra unione, ho costruito una soluzione coprente per P. Quindi vale (a).
<BR>
<BR>Caso sub-coprente.
<BR>
<BR>Di nuovo, considero (I,J) anche nel problema P. Sia Y = ( X \\ U_I ). Sia k = card Y. Gli insiemi A_i non utilizzati nella soluzione (I,J) sono più di k. (Altrimenti Y è un\'isola per P). Considero il problema P\", ottenuto tenendo solo gli elementi di Y e gli insiemi fuori dalla soluzione. Per ipotesi induttiva, esiste (L,M) soluzione di P\".
<BR>
<BR>Se x non compare in U_I, la soluzione continua a essere tale anche in P. Quindi vale (a)
<BR>
<BR>Se x compare in U_I e in U_L (pensati in P), posso montare le due soluzioni e ( I \\union L , J \\union M ) è soluzione di P. Quindi vale (a).
<BR>
<BR>Se x compare in U_I, ma non in U_L, allora ( I \\union L , J \\union M ) è una soluzione di P\' in cui compare un numero strettamente maggiore di A_i. Posso quindi ripetere il ragionamento. Dato che le soluzioni via via ottenute coprono sempre di più, questo ciclo può ripetersi solo un numero finito di volte. []
<BR>
<BR>Questo conclude la dimostrazione.
<BR>
<BR>A margine, osservo che la distinzione tra soluzioni coprenti e sub-coprenti non è puramente accademica. La tesi del problema dice che i controesempi sono tutti isole (sono cioè dotati di troppo pochi A_i). Alcune isole hanno soluzioni. Tuttavia esistono effettivamente isole non ricopribili. A parte l\'esempio banale delle isolette di grandezza 1, esistono isole non banali, di grandezza dispari d, che non possono essere ridotte dal Lemma delle Isolette e non ammettono soluzioni. {x_1, x_2}, {x_2, x_3}, ..., {x_d-1, x_d}, {x_d, x_1} è un\'isola siffatta. Quindi, giustapponendo isole non ricopribili ad una soluzione coprente, è sempre possibile ottenere soluzioni non coprenti e non estendibili a soluzioni coprenti.
<BR>
<BR>----------------------------------------
<BR>
<BR>Data la complessità, controllala bene. Ma errori seri non dovrebbero esserci.
<BR>
<BR>E ora sono pronto: se vuoi infierire con una dimostrazione-cavolata in tre passaggi, accomodati pure.
<BR>
<BR>Tre curiosità (che, dato lo sforzo, ora mi devi soddisfare): 1) e 2) i P.S.: del mail precedente: non mi hai ancora detto chi c\'è dietro quel \"ci sfugge\" e che vuol dire TST; 3) come recita la soluzione con l\'Algebra lineare?
<BR>
<BR>Alla prossima.
<BR>
<BR>M.
<BR>
<BR>==================================
<BR>
<BR>Ciao a tutti.
<BR>
<BR>M.[addsig]

[MindFlyer]

Per completezza, riporto la dimostrazione non elementare con l\'algebra lineare.
<BR>
<BR>Consideriamo gli Ai come vettori di R^n, in modo che Ai abbia la componente
<BR>j-esima =1 se j appartiene ad Ai, =0 se non appartiene. Siccome gli Ai sono
<BR>n+1 vettori non nulli, esiste una loro combinazione lineare x1A1+x2A2+...+x(n+1)A(n+1)=0 tale che almeno un xi sia positivo, ed almeno un xi sia negativo (perché le coordinate sono tutte o 0 o 1). Prendiamo I come l\'insieme degli indici i tali che xi>0, e J l\'insieme degli indici i tali che xi<0. I e J sono disgiunti e non vuoti, ed inoltre abbiamo (somma per i in I: xiAi)=(somma per i in J: (-xi)Ai). Presa una coordinata j, nel vettore sommatoria essa è =0 se lo è anche in tutti gli Ai in I ed in J, mentre é positiva se é =1 in qualche Ai in I ed in qualche Ai in J. Quindi I e J sono gli insiemi cercati.

[HiTLeuLeR]

Wow!!! Che figata, marco! Questa me l\'ero proprio perduta, uff... Complimenti, una soluzione \"da prima pagina\"! Uhm... tu quoque dopamina? O più semplicemente teina, caffeina e nicotina? <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>
<BR>\"Miiiiiiiiiiiiiiii...\" - HiTLeuLeR dopo aver letto 4 volte la soluzione di marco