Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Érdekes matekfeladatok

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]  

Szeretnél hozzászólni? Jelentkezz be.
[3664] Róbert Gida2013-02-01 01:02:20

Helyes. A módszerről, amivel ezt polinom időben meg lehet kapni: http://en.wikipedia.org/wiki/Modular_exponentiation Right-to-left binary method bekezdése. 3123456789123456789 utolsó 20 számjegye éppen a hatvány m=1020-al vett osztási maradéka amit 1 ezredmásodpercbe sem telik kiszámolni egy átlagos gépen.

Enélkül például az RSA sem lenne gyors, így nagyon fontos ez a módszer, http://en.wikipedia.org/wiki/RSA_(algorithm)

Előzmény: [3663] jonas, 2013-01-31 23:47:10
[3663] jonas2013-01-31 23:47:10

27270130915225122483.

Előzmény: [3661] Róbert Gida, 2013-01-31 20:59:37
[3662] w2013-01-31 21:17:18

Nem tudok programozni, de gondolom, sok időbe tartana megkeresni a 20 jegyet. Brutális magasságokba szárnyalhat a periódus hossza, az általad említett példában nem is biztos, hogy lesz 123456789123456789-ig valamilyen periódus (akár 4.1019 hosszú is lehetne). Köszönöm a hozzászólást, ebben tévedtem, mert 4545 utolsó négy számjegye is talán az első periódusban van. Amúgy általában az a tapasztalat, hogy a periódus a becsültnél sokkal rövidebb (persze akkor, ha maximumot becslünk :) ), erről ki is lehetne dolgozni egy kisebb elméletet... De egyenlőre ez engem nem izgat.

Előzmény: [3661] Róbert Gida, 2013-01-31 20:59:37
[3661] Róbert Gida2013-01-31 20:59:37

Mi 3123456789123456789 utolsó 20 számjegye? Mennyi időben/memóriában számolnád ezt ki?

Előzmény: [3657] w, 2013-01-31 19:16:02
[3660] Hajba Károly2013-01-31 20:04:05

Igen. Én is így okoskodtam.

Előzmény: [3657] w, 2013-01-31 19:16:02
[3659] Hajba Károly2013-01-31 20:03:26

Köszi. Ennek ismeretében már nem is olyan bonyolult.

Előzmény: [3655] m2mm, 2013-01-31 18:30:09
[3658] w2013-01-31 19:21:02

Minden bizonnyal a Te megoldásod a legelegánsabb, mert direkt úton visszavezeti a teljes négyzet-egyenlőtlenségre. Helyette próbáld a közepek közötti egyenlőtlenségekkel igazolni a feladatot (természetesebb is az adható megoldás).

Persze rendezési tétellel azonnal látszik ennek a megoldása, de nem működik az általános verzióra határértékek nélkül.

Előzmény: [3653] ibiro, 2013-01-31 13:48:15
[3657] w2013-01-31 19:16:02

Lehet, hogy van rá egyszerűbb okoskodás, de az utolsó négy számjegyet a hatványok utolsó n számjegyének periodikus ismétlődésével meghatározhatjuk (ezt a 4545-re használjuk, az 5454 meg számológéppel megadható).

Előzmény: [3654] Hajba Károly, 2013-01-31 17:14:38
[3656] w2013-01-31 19:11:43

Igen, a Sophie Germaine-féle azonosságra gondoltam.

Előzmény: [3655] m2mm, 2013-01-31 18:30:09
[3655] m2mm2013-01-31 18:30:09

Az eredeti egy tipikus feladat az x4+4y4=(x2+2xy+2y2)(x2-2xy+2y2) azonosságra.

Előzmény: [3654] Hajba Károly, 2013-01-31 17:14:38
[3654] Hajba Károly2013-01-31 17:14:38

A válasz meghaladja a jelenlegi tudásomat, de kiegészíteném egy másik feladattal. Mi lehet ezen szám utolsó 4 számjegye?

Előzmény: [3646] w, 2012-12-08 20:48:35
[3653] ibiro2013-01-31 13:48:15

Kezdetnek nem rossz, de engem legalábbis nem visz közelebb az általánosabb megoldáshoz, megszorozzuk 4-el mindkét oldalt majd ilyen alakba lehet írni : 2(a2-bc)2+2(b2-ac)2+2(c2-ab)2+(a2-b2)2+(b2-c2)2+(c2-a2)2>=0

Előzmény: [3652] w, 2013-01-30 17:26:13
[3652] w2013-01-30 17:26:13

Kezdésképpen igazoljuk, hogy

a4+b4+c4\gea2bc+b2ca+c2ab.

[3651] w2013-01-30 16:12:37

Köszönöm a pontosítást: igen, a becsléshez pozitív súlyok kellenek. Emellett n nyilván pozitív egész.

Előzmény: [3650] ibiro, 2013-01-30 13:30:19
[3650] ibiro2013-01-30 13:30:19

A "tetszőleges xi>0, si valós számokra" kifejezés azt jelenti hogy si>0 ??? Ha igen akkor lehet gondolkozni a feladaton, ha pedig lehetnek negatív számok is, akkor nem igaz az egyenlőtlenség: n=2, x1=1, x2=2, s1=2,s2=-1 .

Előzmény: [3649] w, 2013-01-13 21:25:23
[3649] w2013-01-13 21:25:23

Mutassuk meg, hogy tetszőleges xi>0, si valós számokra fennáll (i=1, 2, ..., n):

\sum_{i=1}^nx_i^{s_1+s_2+...+s_n}\ge x_1^{s_1}x_2^{s_2}...x_n^{s_n}+x_1^{s_2}x_2^{s_3}...x_n^{s_1}+...+x_1^{s_n}x_2^{s_1}...x_n^{s_{n-1}}.

[3648] ibiro2012-12-08 22:26:04

Az algoritmus remek és tényleg megérti egy hetedikes is, de biztos nem igy kapjuk meg a legkevesebb számú lépést (12,36,324,26244,26243,...,2012) és az algoritmus szerint ez az egyetlen megoldás, a valóságban pedig több is van.

Előzmény: [3647] w, 2012-12-08 21:14:42
[3647] w2012-12-08 21:14:42

Mi választjuk-e meg a-t és b-t?

Erre egy trviális algoritmus: páros n=2k-ból k2 képezhető, ahol k2>2k, ha (k-1)2>1, k>2, n>4; páratlan n=2k+1-ből k(k+1) képezhető, itt k(k+1)=k2+k>2k+1, ha (k-\frac12)^2>\frac54, k>\frac{\sqrt5+1}2, n>\sqrt5+2. Tehát szig. mon. növ. sorozatot képezhetünk n0>4 esetén, végül n=n-1+1 -ből n-1 képezhető, elég nagy sorozattag választásával így lecsökkenthetünk a szükséges számra. N>4-re tetszőleges M elérhető, de az is látszik, hogy N\le4 esetén csak M\leN érhető el.

Ilyen módon ez könnyen hetedikes szint. A megoldások és lépések minimális száma nem ilyen egyszerű, finoman fogalmazva.

Előzmény: [3645] ibiro, 2012-12-08 11:45:22
[3646] w2012-12-08 20:48:35

Prímszám-e: 4545+5454?

[3645] ibiro2012-12-08 11:45:22

"Ha az n természetes számot felirjuk n=a+b alakba (ahol a,b szintén természetes szám), akkor helyettesitjük n-t az ab szorzattal és folytassuk az eljárást. Elindulva 12-vel, eljutunk-e 2012-ig ?". Én ismerek két megoldást (próbálkozással), de vajon hány megoldása van a feladatnak és átalánosan. ha elindulunk N-től eljutunk-e M-ig ? Minimálisan hány lépésben ? Megjegyzem, az eredeti feladat VII. osztályosoknak volt feladva.

[3644] Róbert Gida2012-12-01 00:10:20

"Az ellenpéldádtól csak úgy szabadulok meg ha még hozzáadom "a és b természetes számok és ab>1"."

Akkor az a=1;b=3-at mondom ellenpéldának. De, hogy valamit mondjak is: a,b>1-et célszerű feltenni, és akkor már igaz lesz az állításod (valamivel kevesebb is elég, de nem lényeges). Wilson tételből jön ki:

(p-1)!\equiv-1mod p, ha p prím. Az is igaz, hogy összetett n-re: (n-1)!\equiv0mod n, kivéve, ha n=4, ez jelent is egy külön esetet majd a feladatban.

Előzmény: [3643] ibiro, 2012-11-30 21:25:20
[3643] ibiro2012-11-30 21:25:20

Ismét igazad van. Az ellenpéldádtól csak úgy szabadulok meg ha még hozzáadom "a és b természetes számok és ab>1". Bevallom, az eredeti tételt én írtam át a és b formába, de ezek szerint nem figyeltem oda eléggé és eltorzult a dolog. Ime itt az eredeti: "Let p and p+k be positive integers, with (p, p+k) = 1. Then: p and p+k are both prime iff (p-1)!(p+k) + (p+k-1)!p + 2p+k is congruent to 0 (mod p(p+k))". Sajnos innen is kihagyták hogy p>=1 és k>0. Az is igaz hogy (mod 1)-et csak ellenpéldáknál szokták használni ! Azért érdekesnek tartom most is ezt a tételt.

Előzmény: [3641] Róbert Gida, 2012-11-29 18:17:51
[3642] Blinki Bill2012-11-29 19:27:45

Róbert Gida a "vissza irányra" gondolt. Azért mert 1 osztja 4-et, azért még az 1 nem prím :)

Előzmény: [3639] ibiro, 2012-11-29 09:24:51
[3641] Róbert Gida2012-11-29 18:17:51

"Mégegyszer utánanéztem és kihagytam az "(a,b)=1" feltételt."

Akkor még az a=b=1 ellenpélda marad.

Előzmény: [3640] ibiro, 2012-11-29 11:44:50
[3640] ibiro2012-11-29 11:44:50

Igazad van, nem teljesül még elég sok párra. Mégegyszer utánanéztem és kihagytam az "(a,b)=1" feltételt.

Előzmény: [3638] Róbert Gida, 2012-11-28 20:07:18

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]