106. Cerchi , troppi cerchi

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

106. Cerchi , troppi cerchi

Messaggioda lucaboss98 » 08/01/2016, 18:34

Sia $n>1$ un intero . Nel piano ci sono $n$ cerchi che si intersecano a due a due in due punti distinti e tali che non esiste nessun punto che appartenga a tre cerchi distinti. $Federico$ e $Viola$ giocano al seguente gioco, alternandosi: si colora un punto di intersezione tra due cerchi distinti non ancora colorato e che non appartiene ad uno dei cerchi usati nella mossa immediatamente precedente dall'avversario (la prima mossa è "libera"). Inizia $Federico$. Perde chi non può fare nessuna mossa. Determinare per quali $n$ vince $Viola$.
(Ps: non ho la soluzione ufficiale, spero che la mia sia giusta :D)
Ultima modifica di lucaboss98 il 08/01/2016, 19:48, modificato 1 volta in totale.
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: 106. Cerchi , troppi cerchi

Messaggioda Ale99 » 08/01/2016, 18:37

Emh ( anche se posso immaginarlo ) .. come si vince ?
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: 106. Cerchi , troppi cerchi

Messaggioda lucaboss98 » 08/01/2016, 19:48

Ale99 ha scritto:Emh ( anche se posso immaginarlo ) .. come si vince ?

Si, me lo dimentico sempre: sistemato
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: 106. Cerchi , troppi cerchi

Messaggioda lucaboss98 » 10/01/2016, 1:22

Nessuno? Davvero? Eppure sembra fattibile..
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: 106. Cerchi , troppi cerchi

Messaggioda bern1-16-4-13 » 10/01/2016, 3:35

Ogni coppia di cerchi ha due punti in comune.
Consideriamo un grafo dove ogni cerchio rappresenta un vertice, e ogni punto di intersezione fra due cerchi corrisponde a un arco che collega i rispettivi vertici nel grafo. Ogni coppia di vertici sarà quindi collegata da due archi.

Colorare un punto di intersezione di due circonferenze nel disegno equivale quindi a colorare nel grafo uno dei due archi che collega i due vertici corrispondenti a tali circonferenze (è indifferente quale dei due archi).

Il fatto che subito dopo aver colorato un punto di intersezione di due circonferenze nel disegno si debba colorare un punto di intersezione tra due circonferenze distinte dalle precedenti si può ritradurre nel fatto che nel grafo non possiamo colorare consecutivamente due archi che abbiano almeno un vertice in comune.


LEMMA:
dato un grafo a $n$ vertici dove ogni coppia di vertici è collegata da due archi (nel corso del lemma ogni volta che si parlerà di grafo si intenderà un grafo di questo tipo a meno di ulteriori specificazioni), è possibile raggruppare a coppie tutti gli archi del grafo in modo che due archi interni a una stessa coppia non abbiano estremi in comune.
Questo fatto si dimostra facilmente per induzione.
Definiamo "raggruppamento intelligente" un raggruppamento a coppie degli archi di un grafo in modo che due archi interni a una stessa coppia non abbiano estremi in comune.
Prendiamo come passi base della dimostrazione i grafi con $4,5,6,7$ vertici dove gli archi sono facilmente raggruppabili intelligentemente, quindi cerchiamo di passare dal caso [tex]k[/tex] vertici al caso [tex]k+4[/tex] vertici per dimostrare il passo induttivo.
Numeriamo da [tex]1[/tex] a $k$ i [tex]k[/tex] vertici che abbiamo nel grafo dell'ipotesi induttiva. Quindi numeriamo da $1$ a $4$ i quattro vertici aggiuntivi. Poiché per ipotesi induttiva è possibile un raggruppamento intelligente nel grafo con $k$ vertici, raggruppiamo intelligentemente tutti gli archi interni al grafo dell'ipotesi induttiva con $k$ vertici. Dopodiché raggruppiamo intelligentemente anche gli archi interni al grafo composto dai $4$ vertici aggiuntivi. Non ci resta che raggruppare intelligentemente anche gli archi che collegano un vertice dell'insieme dei $4$ vertici aggiuntivi con uno di quelli dell'insieme dei $k$ vertici iniziali. Per far questo chiamiamo $u_1,u_2,u_3,u_4$ i quattro vertici aggiuntivi, mentre chiamiamo $v_1,v_2,...,v_k$ i $k$ vertici iniziali. Abbiniamo ciascuno dei due archi $u_1v_j$ (ricordiamo che nel tipo di grafi di cui stiamo parlando ogni coppia di vertici definisce due archi) a uno dei due archi $u_2v_{j+1}$ (in modo che non siano abbinati entrambi allo stesso arco), mentre abbiniamo ognuno dei due archi $u_3v_j$ con uno dei due archi $u_4v_{j+1}$ (in modo che non siano abbinati entrambi allo stesso arco).
NB (i pedici sono visti modulo $k$).
Ed ecco dimostrato il passo induttivo.

Tornando a noi, se $n\geq 4$ allora Viola si immaginerà un raggruppamento intelligente degli archi del grafo che ha davanti (abbiamo dimostrato che è sempre fattibile), per cui ogni volta che Federico colorerà uno degli archi lei potrà sempre colorare l'arco a esso abbinato nel raggruppamento intelligente che si immagina.

Gli unici casi in cui Viola perde si hanno quando $1<n<4$.
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: 106. Cerchi , troppi cerchi

Messaggioda lucaboss98 » 10/01/2016, 4:09

È giusta e puoi andare col prossimo, un paio di note: un grafo ha al più un arco tra due nodi, dovresti parlare di multigrafo, ma questa è fuffa. La cosa importante è che come la hai scritta l'induzione è "sbagliata" in quanto non dici che ogni grafo con $k+4$ vertici è ottenibile , in quanto "aggiungi" , dovresti "separare". Ovviamente salti i passi base ma vabbè..
La mia è un pizzico più "elegante", mostro esplicitamente un accoppiamento a seconda di $n \pmod{4}$.
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: 106. Cerchi , troppi cerchi

Messaggioda bern1-16-4-13 » 10/01/2016, 4:12

Si può anche mostrare esplicitamente caso per caso, ma mi stava a fatica :D

Non ho capito perché non va bene l'induzione come l'ho impostata io(?)
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: 106. Cerchi , troppi cerchi

Messaggioda lucaboss98 » 10/01/2016, 4:13

Eh ci metterei un po' a spiegarla.. Guardati pigeonhole e induzione di quest'anno al senior medium, dovrebbero dirlo ad un certo punto..
Cioè in questo caso ci sta anche , ma se al posto di quel tipo fissato di multigrafo avessi avuto un multigrafo a caso no.. Avresti dovuto mostrare che ogni possibile multigrafo che rispetta le ipotesi e $k+4$ nodi è ottenibile in quel modo!
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: 106. Cerchi , troppi cerchi

Messaggioda bern1-16-4-13 » 10/01/2016, 4:21

Io forse ho capito cosa intendi, c'è una lezione che ricordo dove parla di alcuni casi dove bisogna ragionare all'indietro, ma qua non ne vedo la necessità...

Se vuoi posso fare quattro volte un'induzione su una certa classe di resto modulo 4, ma è la stessa cosa...
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: 106. Cerchi , troppi cerchi

Messaggioda lucaboss98 » 10/01/2016, 13:35

bern1-16-4-13 ha scritto:Io forse ho capito cosa intendi, c'è una lezione che ricordo dove parla di alcuni casi dove bisogna ragionare all'indietro, ma qua non ne vedo la necessità...

Se vuoi posso fare quattro volte un'induzione su una certa classe di resto modulo 4, ma è la stessa cosa...

Non sono quattro induzioni il problema, comunque ripeto, qui ci sta, ma bisogna stare molto molto attenti a farla a salire
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti