OliForum Matematico

Alice e Bob tracciano a turno una diagonale interna di un $1998-agono$ regolare. Possono connettere due vertici (non appartenenti allo stesso lato) solo se nel farlo non creano intersezioni con diagonali tracciate precedentemente. Perde chi non può più tracciare diagonali che non ne intersechino altre. Alice gioca per prima. Chi vince?



Vi dico quel che ho fatto io ma temo ci sia un errore..

-Dirò che una diagonale che unisce due vertici $V_1$ e $V_2$ "separa $n$ vertici del poligono" quando contando in senso orario i vertici che ci sono tra $V_1$ e $V_2$ , esclusi $V_1$ e $V_2$, ottengo $n$.
-Dirò che due diagonali $V_1V_2$ e $V_1V_3$ (cioè che hanno un vertice in comune) comprendono $n$ punti, quando contando in senso orario i vertici che ci sono tra $V_2$ e $V_3$ ottengo $n$.

Vado a considerare quante diagonali si possono tracciare in una parte $n$-separata del poligono, e dimostro che in una parte $n$-separata si possono tracciare in ogni caso esattamente $(n-1)$ diagonali che non si intersecano. Lo dimostro (o almeno spero) per induzione:

-In una parte 1-separata naturalmente si possono tracciare 0 diagonali che non si intersecano, quindi la tesi è valida nel caso base.
-In una parte 2-separata naturalmente si può tracciare una sola diagonale aggiuntiva.
-Ipotesi induttiva: in una parte $n$-separata si possono tracciare altre $n-1$ diagonali, e lo stesso dicasi per tutti gli $m<n$ con $m$ intero positivo.
-Passo induttivo:
Considero una parte $(n+1)$-separata; Tracciando la prima diagonale interna a questa parte $(n+1)$-separata, ho 2 casi:
1) La prima diagonale interna $d_1$ ha un vertice in comune con la diagonale $d_B$ che ha "creato la parte $(n+1)$-separata.
2) La prima diagonale interna $d_1$ NON ha un vertice in comune con la diagonale $d_B$ che ha "creato la parte $(n+1)$-separata.

caso 1:
i)$d_1$ e $d_B$ comprendono $k$ elementi ($k<n$). $d_1$ crea un'ulteriore parte $n_1$ separata ($n_1<n$). Dal momento che $d_1$ occupa esattamente un vertice interno alla parte $(n+1)$ separata, vale la relazione $n_1=(n+1)-k-1$
Per ipotesi induttiva, la parte $n_1$-separata contiene quindi $n-k-1$ diagonali.
ii) Dobbiamo dimostrare ora che nella parte comprendente $k$ elementi, ci posso tracciare esattamente $k$ diagonali. Ora non ho voglia di scrivere per bene questa parte, però il concetto è che quando traccio una diagonale interna a questa parte, ho altri due casi : A) la diagonale divide in una parte $n_j$ separata B)la diagonale ha in comune un vertice con $d_1$ e $d_B$, da cui mi posso ricondurre di volta in volta al caso A, o al massimo non mi ci riconduco mai ottenendo un "fascio" di diagonali" che non si intrecciano e hanno tutte un vertice in comune con $d_1$ e $d_B$ e l'altro vertice è uno dei $k$ vertici , presi in fila. Alla fine contando le diagonali ottengo $k$.
Quindi sommando le diagonali interne a una parte $(n+1)-separata$ ottengo nel caso 1 $d(n+1)=(n-k-1)+k+1=n$ (ne aggiungo una in fondo che è $d_1$).

caso 2:
identico al punto ii), solo che lo faccio fin dall'inizio....anche qui $d(n+1)=n$.

Allora vale tesi.

Tornando al gioco, Alice traccia la prima diagonale, dividendo il poligono in una parte $m$-separata e in una parte $l$-separata, dove $m+l=1998-2=1996$.
Vale il fatto che $d(m)=m-1$ e $d(l)=l-1$. Per cui durante il gioco prima di incappare in unasituazione dove non si possono piu tracciare diagonali, si tracceranno $d(1998)=d(m)+d(l)+1=m+l-2+1=1995$ diagonali. Alice traccia tutte le diagonali "dispari", pertanto traccerà anche l'ultima diagonale, e vince sempre il gioco qualunque sia la strategia di Bob.


SOLUZIONE UFFICIALE: (cortissima, tranquilli )
Alice traccia la prima diagonale, Bob la seconda. D'ora in poi basta che Alice tracci la simmetrica rispetto al centro di quella che traccia Bob e vincerà sempre il gioco.

Scusate se scrivo troppo per dire poco ,ma se no non ci si capisce niente senza un disegno Fatemi sapere quante falle ci sono nella mia soluzione !

Non ho controllato per bene la dimostrazione per induzione, ma mi pare che vada tutto bene, semplicemente la tua soluzione è molto più lunga perchè dimostri che Alice vince sempre e comunque..
la soluzione proposta, invece, è corta perchè offre UN MODO per vincere, uno solo, ma che comunque le permette sempre e comunque di arrivare alla vittoria, quindi basta a dimostrare =)

Valenash ha scritto:Non ho controllato per bene la dimostrazione per induzione, ma mi pare che vada tutto bene, semplicemente la tua soluzione è molto più lunga perchè dimostri che Alice vince sempre e comunque..
la soluzione proposta, invece, è corta perchè offre UN MODO per vincere, uno solo, ma che comunque le permette sempre e comunque di arrivare alla vittoria, quindi basta a dimostrare =)

Grazie mille per il chiarimento, effettivamente mi sembrava di essermi complicato la vita xD Anche se così almeno diciamo ho dato "una visione più completa della situazione " xD.
Comunque è proprio l'induzione che non mi convince fino in fondo...Se qualcuno ha la pazienza di leggerla e di cercare di capirci qualcosa mi fa un piacere! Poi se qualcosa non è chiaro chiedete pure

va bene, allora la leggerò per bene e ti dico se noto errori o passaggi che si potrebbero semplificare.. comunque.. il passo base è giusto.. XD

Valenash ha scritto:comunque.. il passo base è giusto.. XD

Ahah evvai! Significa proprio che sarò un IMO-boy xD

LukasEta ha scritto:caso 1:
i)$d_1$ e $d_B$ comprendono $k$ elementi ($k<n$). $d_1$ crea un'ulteriore parte $n_1$ separata ($n_1<n$). Dal momento che $d_1$ occupa esattamente un vertice interno alla parte $(n+1)$ separata, vale la relazione $n_1=(n+1)-k-1$
Per ipotesi induttiva, la parte $n_1$-separata contiene quindi $n-k-1$ diagonali.

Potrei sbagliarmi, ma non mi pare che quel passaggio sia corretto.. certo, ti viene perchè ciò che cerchi di dimostrare è vero, però tu puoi sfuttare solamente il fatto che in una parte $n+1$-separata si tracciano sempre $n-1$ diagonali che non si incontrano, non sai nulla sulle parti $n-k$-separate.
Dovresti scrivere meglio la dimostrazione di questo facendo uso dell'induzione forte.

Valenash ha scritto:Dovresti scrivere meglio la dimostrazione di questo facendo uso dell'induzione forte.

Grazie mille della risposta Però hai invocato uno strumento a me sconosciuto...ho cercato su wikipedia e ho capito più o meno di cosa si tratta e sembra fare proprio al caso mio (mi servono tutti i numeri minori di $n$ per dimostrare $n+1$). Però dice anche che è logicamente equivalente al principio di induzione normale. Cosa dovrei cambiare /dimostrare in aggiunta per utilizzare l'induzione forte?

LukasEta ha scritto:

Valenash ha scritto:Dovresti scrivere meglio la dimostrazione di questo facendo uso dell'induzione forte.

Grazie mille della risposta Però hai invocato uno strumento a me sconosciuto...ho cercato su wikipedia e ho capito più o meno di cosa si tratta e sembra fare proprio al caso mio (mi servono tutti i numeri minori di $n$ per dimostrare $n+1$). Però dice anche che è logicamente equivalente al principio di induzione normale. Cosa dovrei cambiare /dimostrare in aggiunta per utilizzare l'induzione forte?

Non ne ho mai fatto uso in una dimostrazione, comunque l'induzione forte è appunto quello che ti dice wikipedia, ossia un equivalente logico dell'induzione normale in cui però consideri verificata la tua affermazione nell'intervallo ${1, 2, ..., n-1, n}$ e sapendo questo vedi come costruisci l'affermazione per $n+1$ facendo uso di quelle precedenti.
Suppongo (ma potrei sbagliare), che ti basta scrivere che dimostri la tua tesi facendo uso dell'induzione forte, ossia la poni vera per ${1, 2, ..., n-1, n}$ e vedi se con questo riesci a dimostrarlo per $n+1$. A questo punto puoi affermare che $n-k$ contiene $n-k-1$ diagonali per ipotesi induttiva e il resto lo fai uguale =)

Fighissimo ! Grazie mille delle limpide spiegazioni

LukasEta ha scritto:Fighissimo ! Grazie mille delle limpide spiegazioni

Prego!! E' sempre un piacere