Palline bulgare

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Azarus
Messaggi: 580
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Palline bulgare

Messaggio da Azarus » 08 ago 2005, 00:49

Avevo promesso a Poloni che lo avrei postato, direttamente da un libro bulgaro:

There are 2000 white balls in a box. There are also sufficiently many white, green, and red balls. The following operations are allowed:

1) Replacement of two white balls by a green ball
2) Replacement of two red balls by a green ball
3) Replacement of two green balls by a white ball and a red ball
4) Replacement of a white ball and a green ball by a red ball
5) Replacement of a green ball and a red ball by a white ball

a) After finitely many of the aboev operations there are three balls left in the box. Prove that at least one of them is green.

b) Is it possibile to have only one ball left in the box after finitely many operations?

NB: è tratto da una gara per la prima media.

Chi lo risolve potrebbe gentilmente occultare la risposta in un qualche modo?

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 08 ago 2005, 14:13

Ma sul serio è al livello prima media (secondo me è oltre Cesenatico..certo che sono avanti i Bulgari)???
posto qui la soluzione (presunta tale) del punto 1..se ho tempo poi guardo anche il secondo..


Dimostro ora che:
Se il numero di palle presenti è a e il numero di palle verdi presenti v allora avrò che:
$ a\equiv v (mod 2) $
all'inizio $ a,v\equiv 0 (mod 2) $. le mosse "calanti(1,2,4,5) cambiano parità sia di a che di v.la mossa 3 è invariante modulo 2 sia rispetto ad a che a v.
quindi è dimostrato che $ a \equiv v (mod 2) $
Per ciò se a=3 allora v=1,3 e non 0 (visto che nessuna mossa ha il potere di fare diventare negativo il numero di palle verdi).

PS aiuto non mi ricordo più come si fa ad occultare..

EDIT: effettuati due inutili tentativi di occultamento :(
EDIT risolto..tranne per il tex ma non credo che le formulazze in tex dicano troppo sulla soluzione :wink:
Ultima modifica di enomis_costa88 il 08 ago 2005, 17:59, modificato 3 volte in totale.

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 08 ago 2005, 15:26

enomis_costa88 ha scritto: PS aiuto non mi ricordo più come si fa ad occultare..
Scrivi la soluzione in un colore che si legga poco sullo sfondo (per esempio bianco) :D
Ovviamente devi NON scrivere le formule usando il supporto TeX.

Forse ho capito male il testo inglese; da dove si deduce che inizialmnte $ \displaystyle a,v \equiv 0 \left(mod 2\right) $?

EDIT: Fai finta che non ho chiesto nulla, la soluzione è giusta, ho appena riletto il testo :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 08 ago 2005, 17:06

parte 2:


Per quanto dimostrato sopra per a=1 $ v \equiv 1 (mod 2) $ e quindi v=1.
sia k la quantità B-R (palle bianche - palle rosse).
le mosse si comportano come segue rispetto a k:
1)-2
2)+2
3)0
4)-2
5)+2
inoltre la 3 è invariante rispetto ad a e non fa calare il numero totale di palle e oltretutto è invariante rispetto a k quindi il valore di k dipende unicamente dalle altre mosse (che chiamo "calanti").
si verifica facilmente che per $ a \equiv 0 (mod 2) $ $ k \equiv 0 (mod 4) $ e per a dispari $ k \equiv 2 (mod 4) $ .
Questo perchè le mosse calanti modificano di due(e sarà alternativamente 0e2) il rappresentante di k modulo 4(e k inizialmente è $ \equiv 0 (mod 4) $e le mosse calanti fatte per arrivare a una palla sono 1999).
la rischiesta è se è possibile arrivare a: a=1 e v=1 k=0 che è impossibile.

EDIT: forse risolto il problema del colore!
Grazie moebius :wink:

Azarus
Messaggi: 580
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Azarus » 09 ago 2005, 16:33

enomis_costa88 ha scritto:Ma sul serio è al livello prima media (secondo me è oltre Cesenatico..certo che sono avanti i Bulgari)???
Hai ragione: è tratto da una gara per la terza media. :D

Comunque entrambe le soluzioni funzionano ed i risultati sono entrambi giusti.

La soluzione originale usa in realtà un altro invariante un pochino più elaborato, ma con il quale è in grado di dare una soluzione in 2 righe per ogni quesito. :D

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 09 ago 2005, 17:01

Sarebbe interessante sapere lo scoreboard di quella gara... :shock:
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

fph
Site Admin
Messaggi: 3694
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 11 ago 2005, 18:35

Grazie Azarus.
Carino, l'ho guardato solo ora.
Soluzione: bianche+ 2 * verdi + 3*rosse == 0 (mod 4).
era questo, vero? (credo che tutto sommato anche l'idea che ha proposto Enomis si riconduca a questo inva)

A me tutto sommato sembra fattibile per una terza media. Il primo punto si fa, magari dopo aver fatto un po' di mosse di "prova" se uno non lo vede subito. Il secondo punto è un po' piu' ostico ma se ti hanno gia' spiegato cos'e' un invariante in terza media e ci hai gia' fatto dei problemi su (in Bulgaria "trainano" i ragazzi gia' in giovane eta'), allora ti puo' venire. Non e' un esercizio facile (come tutti quelli in cui "o ti viene l'idea o non ti viene") ma e' indipendente dall'eta' dei contestant.

Io ci avrei aggiunto anche un terzo punto in cui bisogna utilizzare il fatto che l'invariante in realta' e' un "mono-variant", nel senso che il suo valore puo' solo diminuire.

(e, comunque, e' il primo gioco di questo tipo che sfugge a una "strategia meccanica generale per trovare gli invarianti" che avevo inventato & congetturato che funzionasse sempre per un certo tipo di giochi... Invece trova solo l'invariante del punto (a) e non quello del (b) che ho dovuto fare a mano. Dovrei studiare piu' seriamente quest'argomento, merita).

ciao!
--f
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Azarus
Messaggi: 580
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Azarus » 12 ago 2005, 01:16

Yes, esatto, l'invariante è proprio quello.

...ma ora devi dirci qual è la "strategia meccanica generale per trovare gli invarianti"! :D

fph
Site Admin
Messaggi: 3694
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 13 ago 2005, 18:52

Azarus ha scritto: ...ma ora devi dirci qual è la "strategia meccanica generale per trovare gli invarianti"! :D
E' un po' difficile da spiegare senza aver fatto algebra lineare... cmq le idee sono:
(quello che segue e' "matematica non elementare")
1) in problemi di quel tipo (hai un "vettore", una mossa e' sommare uno a scelta tra un po' di "vettori" fissi, in questo caso (2000 0 0) e i vettori fissi sono (1 1 -2), (1 -1 1) e cosi' via), gli invarianti sono tutti somme pesate degli elementi dei vettori (k_1 a_1+k_2 a_2 +... ), eventualmente modulo qualcosa
2) tutti i moduli "buoni" sono divisori dei determinanti dellle matrici che si ottengono accostando i "vettori fissi".
3) se si fa una matriciona accostando tutti i "vettori fissi" e la si riempie con zeri per farla diventare quadrata, alcuni (io pensavo tutti, ma questo problema fa eccezione) moduli buoni sono gli autovalori (quando sono interi, notare che se sono razionali sono automaticamente interi) e i "pesi" delle somme sono gli autovettori relativi (che possono essere sempre scelti a coefficienti interi)

magari approfondisco... nel frattempo non fregatemi l'argomento :-D

ciao,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi