40
Cred ca la inceput de saptamana cand nici iarba nu creste, un imbold primit din partea unor probleme de logica ar fi binevenit pentru “demarajul” mintal necesar unei noi saptamani. Sper sa fiti mai inspirati decat sunt eu lunea.
Problema 1
Cum putem gasi (relativ usor) o secventa de un milion de numere intregi consecutive care sa nu contina niciun numar prim?
Problema 2
Daca jucam un joc de X si O cu cineva, cu regula putin schimbata, in sensul ca fiecare are voie sa foloseasca oricare dintre cele doua semne, iar castigatorul este primul care reuseste sa formeze un rand de 3 semne identice pe linie, coloana sau diagonala, exista vreo posibilitate de a realiza pentru vreunul dintre jucatori o strategie, pentru vreunul dintre jucatori, care sa asigure castigul, indiferent ce joaca celalalt?
Problema 3
Daca ar trebui sa realizam o emisie monetara in tara noastra, astfel incat orice suma de la 1 la 100 de bani sa poate fi platita cu maxim 2 monede, care este numarul minim de monede diferite care trebuie sa fie emise?
19 Comentarii
P1.
noiembrie 1, 2010 - 9:30 amFie n = 1000001. Numerele n!+2, n!+3, … n!+n sunt compuse, deci nu sunt prime.(n!+k este divizibil prin k).
La problema 3 cred ca putem emite monede de valoarea numerelor prime de la 1 la 100 (25 numere) si in plus monedele de valorile 1,si 4 deci in total 27 de monede diferite
noiembrie 1, 2010 - 10:01 amP2.
Primul jucator are strategie de castig: va pune X in centrul zonei de joc, dupa care, daca nu poate incheia jocul, va pune simetric fata de centru, aceeasi semn pe care il pune adversarul.
Dupa punerea primului X in centru, jucatorul 2 este fortat sa foloseasca numai O deoarece toate celelalte patratele pot fi conectate cu patratul central pt a forma o linie, o coloana sau o diagonala.
Jocul simetric ii asigura jucatorului 1 faptul ca nu poate pierde, deoarece de fiecare data el lasa o configuratie simetrica, si daca jucatorul 2 a putut muta fara sa piarda, datorita simetriei in careul de joc, si el va putea muta fara sa piarda.
Asadar jucatorul 1 nu poate pierde si se va juca numai cu O-uri dupa prima mutare. La un moment dat vor aparea 2 O-uri pe aceeasi linie sau coloana si deci jucatorul 1 va castiga.
noiembrie 1, 2010 - 10:04 amCred ca in varianta mea de la problema 3 sunt 28 de monede de fapt.
noiembrie 1, 2010 - 10:18 amAvem nevoie si de 6 (95=89 prim+6)
18 monede doar 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90
noiembrie 1, 2010 - 10:49 am18 monede doar 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90
noiembrie 1, 2010 - 10:51 amp1 Luam o secventa de nr intregi negative
noiembrie 1, 2010 - 6:30 pmp3 Luam cele 25 de valori prime de la 1 la 100 plus valorile 4 si 95. Stim k orice nr par de la 1 la 100 poate fi scris ca suma a 2 nr prime, iar restul de nr impare se obtin din adaugarea valorii 2 sau 4 celui mai apropiat nr prim mai mic decat respectivul nr impar, cu exceptia nr 95 pt care am facut moneda speciala. In total 27 monede
noiembrie 1, 2010 - 6:54 pmUitasem de valoarea 1. Deci 28 monede.
noiembrie 1, 2010 - 6:57 pmCorecta solutia la P1. Interesant sirul de numere (mai mici decat in solutia pe care ai dat-o) care satiface de asemenea cerinta problemei… n!-2, n!-3,… n!-n.
Corecta si rezolvarea la P2. Primul jucator trebuie sa ocupe centrul, dupa care are castigul asigurat.
La Problema 3, exista posibilitatea ca emitand numai 16 tipuri de monede (poate ca exista si o solutie mai mica de o gaseste cineva) sa se poata obtine valorile de la 1 la 100 (trebuie luat in calcul ca la emiterea de monede numarul celor de acelasi fel este destul de mare. Spre exemplificare suma de 2 bani se poate obtine cu 2 monede de cate 1 ban).
noiembrie 1, 2010 - 9:02 pmo solutie din 18 monede poate fi si 1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99… cu schim de monede am putea,probabil,renunta la 6,7,8,… cam atat, poate si 9 😉
noiembrie 7, 2010 - 12:50 pmo solutie din 18 monede poate fi si 1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99… cu schim de monede am putea,probabil,renunta la 6,7,8,… cam atat, poate si 9 ;))
noiembrie 7, 2010 - 12:55 pmsirul de numere 2,3,4,….n, contine doar n-1 numere, deci consider ca Domnul Pit nu “s-a complicat inutil”… sper sa nu imi fie luat in nume de rau acest detaliu 🙂
noiembrie 7, 2010 - 2:51 pmsa incerc 15 numere “pentru eternitate” 🙂 in problema P3: 1 to 5 n 10 to 100 LOL
noiembrie 7, 2010 - 2:53 pmin principiu, cu ajutorul schimbului de monede , s-ar putea incerca chiar solutii mai… performante, cea indicata avand doar meritul ca face apel la numere relativ cunoscute/remarcabile… 🙂
noiembrie 7, 2010 - 2:57 pmpentru problema P3, o cautare exhaustiva , cu ajutorul bktrk este prohibitiva la timp, solutii polinomiale in timp, de tip programare dinamica, ar putea fi disponibile, aici este un bktrk ce se taraie destul de greu peste n=50 monede
‘ cu accelerare pe fwd sau bktrk
DEFINT A-Z
CONST n = 50
CONST m = 12
DIM a(m, 2) AS INTEGER
v1 = 100
pc = 1
mc = 1
myfwd:
GOSUB test1
numar2 = m – pc + 1
total = numar1 + numar2 * (numar2 + pc – 1)
IF total >= n THEN
GOTO et2
ELSE
GOTO et1
END IF
et2:
test = 0
FOR i = 1 TO pc – 1
IF a(i, 1) = mc THEN
test = 1
END IF
NEXT i
IF test = 0 THEN
a(pc, 1) = mc
a(pc, 2) = 0
END IF
mc = mc + 1
IF mc > n THEN PRINT “fatal error”: GOTO endprg
IF test = 1 THEN GOTO myfwd
entry:
pc = pc + 1
IF pc <= m THEN GOTO myfwd
abc:
'LOCATE 10, 10
'FOR i = 1 TO m: PRINT a(i, 1); : NEXT i
sr = n
FOR i = 1 TO n
FOR j = 1 TO m
FOR k = j TO m
IF i = a(j, 1) + a(k, 1) OR i = a(j, 1) THEN
sr = sr – 1
GOTO nexti
END IF
NEXT k: NEXT j
nexti: NEXT i
IF sr = 0 THEN
PRINT "solutie:"
FOR i = 1 TO m: PRINT a(i, 1); : NEXT i
GOTO endprg
END IF
IF sr = n THEN
GOTO et3
ELSE
GOTO et1
END IF
et3:
IF a(pc, 2) = 0 THEN
mc = 1
ELSE
mc = a(pc, 1) + 1
IF mc > n THEN GOTO et1
END IF
FOR i = mc TO n
FOR j = 1 TO pc – 1
FOR k = j TO pc – 1
IF i = a(j, 1) + a(k, 2) THEN
testvar = 1
ELSE
testvar = 0
GOTO mytest
END IF
NEXT k: NEXT j: NEXT i
mytest: IF testvar = 1 THEN GOTO et1
a(pc, 1) = i
a(pc, 2) = 1
mc = 1
GOTO entry
et1:
pc = pc – 1
IF pc = 0 THEN
PRINT “end cautari”
GOTO endprg
ELSE
GOTO mybktrk
END IF
test1:
noiembrie 8, 2010 - 1:56 amDIM b(1 TO n) AS INTEGER
FOR t = 1 TO n: b(t) = 0: NEXT t
numar1 = 0
FOR j = 1 TO pc – 1
b(a(j, 1)) = 1
FOR k = j TO pc – 1
nn = a(j, 1) + a(k, 1)
IF nn <= n THEN b(nn) = 1
NEXT k
NEXT j
FOR k = 1 TO n
IF b(k) 0 THEN numar1 = numar1 + 1:
NEXT k
RETURN
endprg:
aici ar trebuie sa fie un “one sshot only” greedy ce merge acceptabil, programele ar putea fi modificate pentru forma cu shimb de monede, despre o “strategie de rezolvare” cat mai buna, ceva mai jos…
DEFINT A-Z
CONST n = 100
CONST m = 19
DIM a(1 TO m) AS INTEGER
a(1) = 1: a(2) = 2: a(3) = 3: ‘a(4) = 4
pc = 4
alfa:
lastbestnn = 0
lastbestpc = 0
FOR i = 1 TO n
myerr = 0
FOR j = 1 TO pc – 1
IF i = a(j) THEN myerr = 1
NEXT j
IF myerr = 1 THEN GOTO nexti
DIM b(1 TO n) AS INTEGER
FOR k = 1 TO n: b(k) = 0: NEXT k
FOR ii = 1 TO pc – 1
FOR jj = 1 TO pc – 1
nn = i
b(nn) = 1
nn = a(ii)
b(nn) = 1
nn = i + a(ii)
IF nn <= n THEN b(nn) = 1
nn = a(ii) + a(jj)
IF nn lastbestnn THEN
lastbestnn = numar
lastbestpc = i
END IF
nexti:
NEXT i
noiembrie 8, 2010 - 1:59 ama(pc) = lastbestpc
pc = pc + 1
IF pc <= m THEN GOTO alfa
FOR i = 1 TO m: PRINT a(i); : NEXT i
PRINT , lastbestnn
o cheie de rezolvare a P3 ar putea fi urmatoarea: se observa ca daca avem toate monedele 1-k, sa zicem k=9, apare oportunitatea descrisa de mai multi aici de a obtine o solutie cu 18 monede. urmatorul pas ar fi ca, in cazul in care omitem o moneda ,sau mai multe din grupul 1-k, sa vedem cu ce oportunitati ramanem. ideea ar putea fi valabila si pentru varianta cu schimb de monede care,personal, nu mi se pare chiar de neluat in seama, macar “teoretic” 😉
noiembrie 8, 2010 - 2:05 amidee de neglijat nu mi se pare nici cea cu numerele negative “consecutive”, stiindu-se, sau poate gresesc, ca numerele prime sunt pozitive, insa pentru o rezolvare de tip “stil solid” consider ca este de dorit a fi dublata de cea cu factorial….. si cu aceasta am mai monopolizat inca un site LOL
noiembrie 8, 2010 - 2:12 am