Cancellando triangoli (sns 5-2000)

[enomis_costa88]

Elena e Giulia hanno inventato il seguente gioco: disegnato su un foglio
un insieme di punti a tre a tre non allineati collegati da alcuni segmenti
che non si intersecano se non negli estremi il loro gioco consiste nel modificare
l’insieme dei segmenti, scegliendo a turno una e una sola delle seguenti
mosse:
(a) se tre segmenti formano un triangolo, essi possono essere eliminati
tutti e 3;
(b) se due segmenti sono incidenti in uno stesso punto ma non formano
un triangolo perchè manca il terzo lato, essi possono essere cancellati
e sostituiti con il lato mancante
Perde chi si trova per prima nella situazione di non poter fare alcuna
mossa. Elena muove per prima.

Valeria, che li ha guardati giocare, osserva che l’esito del gioco è determinato
completamente dall’insieme iniziale dei segmenti e non dipende
affatto dalla strategia di gioco di Elena o di Giulia.
Spiegare il motivo dell’osservazione di Valeria e individuare una regola che
consente di determinare in anticipo la vincitrice del gioco.

Buon lavoro, Simone.

[Marco]

Una precisazione: la mossa del secondo tipo può essere fatta anche se si disegna un segmento che ne interseca un altro?

[esempio: 5 punti, A, B, C e P, Q, con P interno al triangolo ABC e Q esterno in modo tale che PQ e AC si intersecherebbero. Segmenti tracciati inizialmente AB e BC e PQ. Può essere giocata la mossa "cancello AB, cancello BC e traccio AC", in questo modo creando un'intersezione tra PQ e AC?]

[enomis_costa88]

Chiamiamo $ P_i $ i punti presenti inizialmente.
Allora possiamo fare la mossa che dici.
Però poi posso operare le mosse a,b solo con segmenti che abbiano come estremi due punti $ P_i $.

Ad esempio, prendendo la tua configurazione, se chiamo Z il punto di intersezione tra PQ e AC allora poi non posso applicare la mossa b per esempio ai segmenti ZQ,QC,CZ (cancellando ZC e ZQ e disegnando QC).

Diciamo che il problema è equivalente al seguente:

Sia dato un grafo (planare);
A turno Elena e Giulia operano una delle seguenti mosse:

a) Scelgo 3 vertici di questo grafo (che chiamo A,B,C) se nel grafo sono presenti i lati AB,BC,CA posso cancellarli tutti e tre.
b) Se sono presenti solo due lati tra AB,BC,CA posso cancellarli e sostituirli con il lato mancante.
Inizia Elena e perde chi non può più muovere

Dimostrare che l’esito del gioco dipende solo dalla configurazione iniziale.
Determinare le situazioni iniziali in cui vince Elena e quelle in cui vince Giulia.

[Marco]

Ok. La formulazione con i grafi è nettamente più chiara: c'era nel testo originale quel "che non si intersecano se non negli estremi" che lasciava adito a dubbi.

Ora mi torna.