Probleme de logica la inceput de saptamana (57)

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?


ALTE POSTARI RELEVANTE

19 Comentarii

  • cosminp

    P1.
    Fie n = 1000001. Numerele n!+2, n!+3, … n!+n sunt compuse, deci nu sunt prime.(n!+k este divizibil prin k).

    noiembrie 1, 2010 - 9:30 am Raspunde
  • Marius Vasile

    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 am Raspunde
  • cosminp

    P2.
    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 am Raspunde
  • Marius Vasile

    Cred ca in varianta mea de la problema 3 sunt 28 de monede de fapt.
    Avem nevoie si de 6 (95=89 prim+6)

    noiembrie 1, 2010 - 10:18 am Raspunde
  • Cristi Bugeanu

    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 am Raspunde
  • Mihai P

    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:51 am Raspunde
  • Alex_Ghive

    p1 Luam o secventa de nr intregi negative

    noiembrie 1, 2010 - 6:30 pm Raspunde
  • Alex_Ghive

    p3 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 pm Raspunde
  • Alex_Ghive

    Uitasem de valoarea 1. Deci 28 monede.

    noiembrie 1, 2010 - 6:57 pm Raspunde
  • dan bujor

    Corecta 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 pm Raspunde
  • Matei Florin

    o 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 pm Raspunde
  • Matei Florin

    o 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 pm Raspunde
  • Matei Florin

    sirul 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 pm Raspunde
  • Matei Florin

    sa incerc 15 numere “pentru eternitate” 🙂 in problema P3: 1 to 5 n 10 to 100 LOL

    noiembrie 7, 2010 - 2:53 pm Raspunde
  • Matei Florin

    in 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 pm Raspunde
  • Matei Florin

    pentru 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:
    DIM 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:

    noiembrie 8, 2010 - 1:56 am Raspunde
  • Matei Florin

    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
    a(pc) = lastbestpc
    pc = pc + 1
    IF pc <= m THEN GOTO alfa
    FOR i = 1 TO m: PRINT a(i); : NEXT i
    PRINT , lastbestnn

    noiembrie 8, 2010 - 1:59 am Raspunde
  • Matei Florin

    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 am Raspunde
  • Matei Florin

    idee 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 Raspunde

Lasa un Comentariu

Adresa dvs de email nu va fi publicata.