[PS283b] Par – impar

Autor: Macalestear POTW 971
Concurs: Problema saptamanii (#37/2007)
URL: http://egovbus.net/rdl/potw/potw6.doc

***

Motto: Nu tot ce-i vechi e sfânt; şi praful de pe masă trebuie şters. (IPS Flavian)

Săptămâna 283:
B. (Par – impar):

Considerăm următoarea expresie (unde & reprezintă operaţia de adunare sau de înmulţire, iar ? este o cifră între 0 şi 9):

(((((((((? & ?) & ?) & ?) & ?) & ?) & ?) & ?) & ?) & ?)

Alice face prima mutare, şi înlocuieşte cel mai din stânga ? cu o cifră.

Apoi Bob înlocuieşte primul & cu unul din operatorii + (adunare) sau * (înmulţire), precum şi primul ? (rămas după acţiunea lui Alice) cu o cifră neutilizată încă.

Urmează Alice, care înlocuieşte primele caractere &,? rămase, cu + sau * şi respectiv cu o cifră neutilizată încă.

După ce Bob face ultima mutare, ceea ce rămâne este o expresie aritmetică în care apar cele 10 cifre 0,1,..,9 (fiecare o singură dată), precum şi operatorii +,*.

Se evaluează expresia.

Dacă rezultatul este un număr par, Alice câştigă jocul. Dacă este impar, câştigător este Bob.

Nu este posibilă o remiză.

Are Alice strategie de câştig în acest joc ?

Sursă: Macalestear Problem of the Week 971