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 !
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?
e il resto lo fai uguale =)