gioco stupido from SNS 2000

[piever]

Mi pare non sia ancora stato postato qui (non sono molto pratico con la funzione cerca, pero' non lo ho trovato), ma e' abbastanza divertente:

Alberto e Barbara fanno questo gioco:

prima disegnano su un foglio un grafo finito. Ogni mossa consiste in una delle due possibilita' qui sotto:

1) se AB, BC e CA sono archi, cancellarli tutti e tre (la scelta dei vertici A, B e C spetta al giocatore che deve muovere)

2) se AB e BC sono archi, ma CA non e' un arco, cancellare AB e BC e tracciare CA (al solito, la scelta dei vertici A, B e C spetta al giocatore che deve muovere).

Perde chi non puo' piu' muovere, Alberto inizia.

Perche' e' un gioco stupido? TESI: il vincitore dipende solo dalla configurazione iniziale, e non dalla strategia di alberto e barbara, che potrebbero quindi muovere a caso, oppure, piu' intelligentemente, cambiare gioco.. Beh, dimostrate la tesi...

Bonne chance

[Nonno Bassotto]

Uno dei miei problemi preferiti!
È stato dato l'anno che sono entrato io.

[ramsey]

Beh dai sarebbe stato molto peggio se i nostri $ Alberto $ e $ Barbara $ si fossero messi a smanettare col sudoku!!!
Da cosa nasce cosa.


p.s. avrei una soluzione un pò banale che posterò quando un pò di gente avrà avuto modo di leggere il testo.

[Nonno Bassotto]

Soluzione banale? La soluzione che ho trovato io è del tutto elementare, ma richiede qualche passo (per carità, abbastanza standard quando uno conosce il tipo di problema). Non so se ne esiste una sofisticata.

[mattilgale]

Contiamo quante V nel grafo si cancellano ad ogni mossa

dati due lati che partono da un vertice, se d è il grado di quel vertice il numero di V che "usano" almeno uno dei lati in quel vertice è $ 2(d-2)+1 $, pertanto si vede banalmnente che ad ogni mossa vengono cancellate un numero dispari di V dal grafo e quindi per entrambi i partecipanti la parità del numero di V al proprio turno è invariante e poiché perde chi si troverà al proprio turno con 0 V, questo gioco è veramente moooolto stupido

comunque, questo è il mio primo post from Linux Ubuntu!!!!

[edriv]

Altra soluzione (son sempre invarianti eh...): la parità del grado di ciascun nodo è invariante, e la parità del numero di archi è invariante per ciascun giocatore. Nella situazione finale però il numero di archi sarà la metà del numero di nodi di grado dispari, quindi chi ha la congruenza giusta all'inizio... perde

Conseguenze filosofiche: il sapere può annullare il divertimento.

[mattilgale]

boia come mi sono complicato la vita, mi è sembrata la cosa più banale cercare le V

[edriv]

ho risposto perchè anche io mi ero messo a contare le V ma mi sembrava troppo complicato e impossibile da fare