Pagina 1 di 1

gioco stupido from SNS 2000

Inviato: 20 dic 2007, 16:31
da 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

Inviato: 20 dic 2007, 21:35
da Nonno Bassotto
Uno dei miei problemi preferiti! :)
È stato dato l'anno che sono entrato io.

Inviato: 20 dic 2007, 21:56
da 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.

Inviato: 20 dic 2007, 22:58
da 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.

Inviato: 02 gen 2008, 17:09
da 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 :D

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

Inviato: 02 gen 2008, 21:22
da 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.

Inviato: 02 gen 2008, 23:21
da mattilgale
boia come mi sono complicato la vita, mi è sembrata la cosa più banale cercare le V :oops:

Inviato: 02 gen 2008, 23:46
da edriv
ho risposto perchè anche io mi ero messo a contare le V ma mi sembrava troppo complicato e impossibile da fare :D :D