Există o soluție elegantă pentru următoarea problemă?

Question

Am găsit pe câteva site-uri de gen următorul puzzle matematic, fără vreo rezolvare care să se bazeze exclusiv pe logică:

      $$$  *
        $$
    -------
    $$$$
  $$$$
 ---------
  $$$$$

Este deci o înmulțire a două numere, de trei și respectiv două cifre. Fiecare dintre simbolurile $ care apar în înmulțire, în forma reprezentată mai sus, trebuie înlocuit cu un număr prim de o singură cifră (2, 3, 5 sau 7).

Putem găsi o soluție elegantă, care să nu necesite încercări repetate, așa-numitul ”trial and error”? Iar dacă logica pură nu ne conduce la o soluție, care ar fi numărul minim de încercări de făcut pentru a ajunge la soluție?

Soluția (cele două numere, deînmulțitul și înmulțitorul) este unică, detaliu care nu mi-e clar dacă ajută, dar l-am găsit specificat când am citit problema pe net...

Comments

Testarea tuturor combinațiilor posibile este o metodă perfect logică. Probabil însă nu e și elegantă, deși e greu de definit eleganța în matematică. Uite, asta ar fi o idee de întrebare interesantă: ce înseamnă eleganța matematică?

---

Și ca să dau și un răspuns, pentru mine e suficient de elegantă în cazul de față scrierea unui program care să testeze toate combinațiile posibile în locul meu. Iar rezultatul a fost că într-adevăr problema aceasta are o singură soluție: 775*33.

Metoda încercărilor repetate este considerată neelegantă în matematică pentru că presupune efectuarea unui număr mare de calcule plictisitoare, o muncă lipsită de creativitate. Dar în cazul unui progrămel plictiseala dispare, pentru că ceea ce face rezolvitorul nu e nici repetitiv, nici neoriginal.

Se pune? :-)

---

Este ”next best thing”, dar, deocamdată, în așteptarea altor soluții, să zicem că nu! :)

M-aș mulțumi totuși cu prezentarea unui algoritm cât mai perfomant cu putință. De fapt, a doua parte a întrebării s-ar putea reduce la așa ceva. Un algoritm care să ajungă cât mai repede la răspuns, deci de o complexitate cât mai mică...

---

Păi algoritmul e simplu, iar indiciul cel mai bun e că programul a mers din prima, ceea ce mi se întîmplă rar. Pe scurt, am generat un șir cu toate numerele de trei cifre care se compun numai din cifrele {2, 3, 5, 7} și încă un șir cu numere de două cifre, idem. Apoi am înmulțit pe rînd cîte un număr din primul șir cu cîte unul din al doilea. Am verificat de fiecare dată dacă cele două produse intermediare și cel final se compun numai din cifrele {2, 3, 5, 7} și am afișat cazurile care respectă condiția asta. Adică de fapt cazul, că a ieșit doar unul. Gata.

Inițial am încercat de mînă, dar singurul pas ferm pe care l-am putut face a fost să deduc că cifra unităților din rezultatul final este 5. Am mai eliminat cîteva posibilități pe ici pe colo, de exemplu prima cifră a rezultatului final am dedus că nu poate fi 7, dar prea departe n-am ajuns. Așa că am trecut la the next best thing: forța brută a sclavului electronic.

---

S-ar mai putea reduce numărul de operații pe care trebuie să le execute prin forță brută sclavul dvs. electronic și luând în calcul faptul că, de pildă, ultimele cifre ale celor două numere nu pot fi perechile (2,*), (*,2), (3,3), (3,7), (7,3) și (7,7), care generează cifra de final a rezultatului ne-primă.
Poate cu câteva observații suplimentare de genul acesta venite de ici, de colo, cine știe, ajungem și la o soluție aproape elegantă... :)

---

De acolo am dedus că ultima cifră a rezultatului final trebuie să fie 5. Problema e că dacă introduc astfel de condiții în algoritm programul se complică mult. Și inutil, pentru că nu fac economie nici de memorie, nici de timp. Toată rularea programului durează circa 70 de milisecunde, pe măsurate. Nici nu apăs bine pe F5 că deja se afișează soluția.

---

Cam aveti dreptate. O imbunatatire cred ca ar fi ca atunci cand generati numarul din 2 cifre sa renuntati din start la 2, care nu poate aparea nici la cifra zecilor. Nu stiu daca se poate ajunge la aceeasi idee si pentru deinmultit...

E drept ca mai mult de 3-4 milisecunde nu vad cum ati castiga! :)

---

Eu încă mai sper că se mai gândește cineva și la problema asta. Iată un mic progres...

Folosim următoarea notație:

       ABC *
         DE
  ---------
    FGHJ
  KLMN
-----------
  PQRST
 

Am stabilit că C,D și E nu pot fi 2.
De asemenea, din combinațiile rămase pentru înmulțirea lui C cu E rezultă că J=5. La fel, din D*C rezultă N=5.
H+N=?S, deci H+5=?S, iar cum H și S sunt prime avem doar două variante: H=2, S=7 sau viceversa. Oricum ar fi, PQRST se termină fie în 25, fie în 75, deci rezultatul final este multiplu de 25. De aici mai rezultă și că C=5 (dacă nu ar fi așa, atunci ar fi nevoie ca D și E să fie 5, deci DE = 55, multiplu doar de 5, și cum C nu ar putea fi 0 ori 5, rezultatul final nu ar fi multiplu de 25).

Deci avem, pe lângă alte restricții deduse anterior, și faptul că rezultatul final e multiplu de 25 și că C=5.