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]  

Szeretnél hozzászólni? Jelentkezz be.
[3254] bily712010-02-16 20:06:05

Erre majd később válaszolok, most nincs időm.

Előzmény: [3252] Fálesz Mihály, 2010-02-15 10:16:52
[3253] bily712010-02-16 20:04:32

Ez a kongruenciarendszer minden természetes számot lefed a 0-án kívül, tehát részleges lefedőrendszer. Változtassunk egy kicsit a szabályokon. Legyen az x_n\equiv\left[\frac{p_n}{6}\right]~(\mod{p_n}) kongruenciáknak megfelelő számtani sorozatok első eleme p_n+\left[\frac{p_n}{6}\right], az x_m\equiv-\left[\frac{p_m}{6}\right]~(\mod{p_m}) kongruenciáknak megfelelőeknek pedig változatlanul -\left[\frac{p_m}{6}\right].

Nevezzük az ilyen rendszereket, ahol a kongruenciáknak megfelelő számok sorozata nem a maradékosztályt reprezentáló legkisebb elemtől indul, számtani sorozatok lefedőrendszerének, ha minden természetes szám tagja legalább egy sorozatnak. Számtani sorozatok részleges lefedőrendszerének pedig akkor, ha létezik k>0 természetes szám, úgy, hogy a rendszer minden k-nál nagyobb számot lefed.

Utolsó kérdésem e témában: 1. Az így kapott számtani sorozatok rendszere részleges lefedőrendszer-e, vagyis a le nem fedett számok halmaza véges, avagy végtelen?

Mégegyszer elnézést kérek a témakör érdektelenségéért.

Előzmény: [3248] bily71, 2010-02-14 23:10:38
[3252] Fálesz Mihály2010-02-15 10:16:52

Következő gondolkodnivaló: Legyen most a egy 0-tól különböző maradék modulo p, és párosítsuk össze a modulo p maradékokat úgy, hogy minden párban a legyen a szorzat.

Előzmény: [3251] Fálesz Mihály, 2010-02-15 10:16:11
[3251] Fálesz Mihály2010-02-15 10:16:11

Én pontosan fordítva szervezném a számolást:

1. eset: a -1 nem kvadradikus maradék mod p, azaz minden pár két különböző maradékból áll. A párok száma (p-1)/2. A Wilson-tételt is alkalmazva,


-1 \equiv (p-1)! = 
\bigg(1\cdot(p-1)\bigg)\cdot\bigg(2\cdot\frac{p-1}2\bigg)\cdot\dots
\equiv (-1)^{(p-1)/2}.~ ~(\mod p)
(1)

Mivel p>2, a +1 és -1 maradékok különbözőek, a -1\equiv(-1)(p-1)/2 (mod p) kongruencia akkor teljesül, ha (p-1)/2 páratlan, azaz p 4k+3 alakú.

2. eset: a -1 kvadradikus maradék mod p, azaz létezik egy a maradék, amire a2\equiv-1(mod p). Ilyen maradék a -a is, a két maradék külöböző, mert p páratlan, és több nincs.

Az (1)-beli szorzatból hagyjuk el a (a,a) és a (-a,-a) párokat, és helyettük vegyük hozzá a szorzathoz az (a,-a) párt (ahol a.(-a)=-a2\equiv+1(mod p)):

-1\equiv(p-1)!=(a.(-a)).(1.(p-1))....\equiv(-1)(p-3)/2.  (mod p)(2)

A -1\equiv(-1)(p-3)/2 (mod p) kongruencia akkor teljesül, ha (p-3)/2 páratlan, azaz p 4k+1 alakú.

Összességében az derült ki, hogy a -1 akkor és csak akkor kvadradikus maradék mod p, ha p 4k+1 alakú.

Előzmény: [3250] bily71, 2010-02-14 23:27:08
[3250] bily712010-02-14 23:27:08

Bocsánat, elírtam a második esetnél, tehát mégegyszer, helyesen: ha a2\equiv-1(mod p),

akkor (p-a)2\equiv-1(mod p).

Előzmény: [3247] bily71, 2010-02-14 22:12:36
[3249] bily712010-02-14 23:19:10

Ez megoldható, legyen x1\equiv0(mod p1).

Előzmény: [3245] Róbert Gida, 2010-02-14 16:09:01
[3248] bily712010-02-14 23:10:38

Tehát, ha jól értem azt állítod, hogy az

x1\equivm(mod p1)

x2\equivm(mod p2)

...

xn\equivm(mod pn)

végtelen kongruenciarendszer lefedőrendszer?

Szerintem nem.

Bármelyik számot fedem le az összes kongruenciával, az ugyanaz, mintha a 0-át fedném le. Az eratoszthenészi szita működik akkor is, ha nem a 0-ról indítjuk a lépéseket, hanem m-ről, hiszen minden modulus prím, csak ebben az esetben nem a pl. 5-tel osztható számokat húzzuk le, hanem m-től minden 5k-adik számot.

Ha pedig arra gondoltál, hogy minden kongruenciával másik számot fedünk le, azt egy esetként írtam le, vagyis a végtelen sok megoldást egy típusba soroltam.

De mi a helyzet akkor, ha minden 3-nál nagyobb prímet kétszer használunk fel, és ha a lefedett szám függ a modulustól, mint a következő rendszerben:

x1\equiv1(mod 5)

x2\equiv-1(mod 5)

x3\equiv1(mod 7)

x4\equiv-1(mod 7)

x5\equiv2(mod 11)

...

x_n\equiv\left[\frac{p_n}{6}\right](\mod{p_n})

x_{n+1}\equiv-\left[\frac{p_n}{6}\right](\mod{p_n}),

ahol ha pn=6k+1, akkor \left[\frac{p_n}{6}\right] az alsó egészrészt jelöli, ha pn=6k-1, akkor pedig a felsőt? Lehet-e ez a rendszer részleges lefedőrendszer, tehát létezik-e olyan természetes szám, hogy minden nála nagyobbat lefed a rendszer?

Előzmény: [3246] jonas, 2010-02-14 17:18:58
[3247] bily712010-02-14 22:12:36

Ezt kapjuk:

(p-1)\equiv2\frac{p-1}{2}\equiv3\frac{p-1}{2}\equiv...\equiv\frac{p-1}{2}\frac{p-1}{\frac{p-1}{2}}\equiv-1(\mod{p}

.

Két eset lehetséges, első:

2 | \frac{p-1}{2}, ekkor van \frac{p-1}{2} darab számpárunk, amelyek szorzata ab\equiv-1(mod p), ha behelyettesítünk, akkor ezt kapjuk:

(p-1)!\equiv(-1)^{\frac{p-1}{2}}\equiv-1(\mod{p})

.

Második:

2|\frac{p-1}{2}, ekkor létezik a, hogy a2\equiv-1(mod p), de akkor (p-1)2\equiv-1(mod p). Így kapunk \frac{p-1}{2}+1 darab számpárt, amelyek szorzata ab\equiv-1(mod p), és mivel 2 | \frac{p-1}{2}+1, ezért, ha behelyettesítünk, ezt kapjuk:

(p-1)!\equiv(-1)^{\frac{p-1}{2}+1}\equiv-1(\mod{p})

.

Előzmény: [3243] Fálesz Mihály, 2010-02-13 12:38:17
[3246] jonas2010-02-14 17:18:58

Ne viccelj már. Ha végtelen sok kongruenciát használhatsz, és csak a modulusokra van megkötés, akkor nagyon sok megoldás van, mert akár minden kongruenciával elég egy egész számot lefedned.

Előzmény: [3244] bily71, 2010-02-13 12:46:49
[3245] Róbert Gida2010-02-14 16:09:01

A 0-t nem fedted le, ha p(n) az n-edik prím.

Előzmény: [3244] bily71, 2010-02-13 12:46:49
[3244] bily712010-02-13 12:46:49

Triviális megoldás az

x1\equiv1(mod p1)

x2\equiv2(mod p2)

...

xn\equivn(mod pn),

kongruenciarendszer, ahol n végig fut a természetes számokon, pn>n és a prímek páronkét különböznek.

A p1<p2<...<pn nem szükséges feltétel, pn itt nem az n-edik prímet jelöli és nem szükséges minden prímet felhasználni, akár végtelen sok is kimaradhat.

Egy másik:

x1\equiva1(mod p1)

x2\equiva2(mod p2)

x3\equiva3(mod p3)

...

xm\equivam(mod pm)

xm+1\equivb1(mod pm+1)

...

xm+n\equivbn(mod pm+n),

ahol bi pi valamely maradékosztálya, bi és bj nem feltétlenül különböző számok, bn<pm+n és bn az n-edik olyan természetes szám, amely nem elégít ki p1-től pm-ig egy kongruenciát sem, pm nem az m-edik prím és p1<p2<...<pm+n itt sem szükséges feltétel, és itt sem szükséges minden prímet felhasználni.

1. Van-e több megoldás?

(Szerintem nincs a jonas által [3239]-ben ismertetett okok miatt.)

Nevezzünk részleges lefedőrendszernek egy olyan kongruenciarendszert, ahol létezik k természetes szám, hogy a k-nál nagyobb természetes számok mindegyike kielégít valamely kongruenciát, azaz k fölött a rendszer minden számot lefed.

2. Konstruálható-e véges, vagy végtelen részleges inkongruens lefedőrendszer, ha minden modulus prím?

3. Konstruálható-e véges, vagy végtelen részleges lefedőrendszer, ha minden modulus prím, és minden prímet kétszer használunk fel?

Elnézést, ha bárkit is untatok.

Előzmény: [3241] bily71, 2010-02-12 22:53:59
[3243] Fálesz Mihály2010-02-13 12:38:17

Új gondolkodnivaló.

Legyen ismét p prím. A Wilson-tétel mintájára, párosítsuk össze azokat a modulo p maradékokat, amelyek szorzata -1:


1 \cdot (p-1) \equiv 2 \cdot \frac{p-1}{2} \equiv ... \equiv -1 ~ (\mod p).

Milyen eredményt kapunk ebből?

Előzmény: [3234] bily71, 2010-02-11 17:28:19
[3242] Fálesz Mihály2010-02-13 12:12:33

Írjuk inkább így:


a = \frac{(x-z)y^\alpha + (y-x)z^\alpha + (z-y)x^\alpha}{
(y-x)(z-x)(z-y)}.

Ha 0<x<y<z, akkor a nevező pozitív.

Ha \alpha\le0 vagy \alpha\ge0, akkor az x^\alpha függvény konvex, a három pontra illesztett parabola felfelé áll, tehát a\ge0.

Ha pedig 0\le\alpha\le1, akkor x^\alpha konkáv, a parabola lefelé áll, tehát a\le0.

Előzmény: [3240] Lóczi Lajos, 2010-02-12 22:03:59
[3241] bily712010-02-12 22:53:59

És ha végtelen sok kongruenciából álló rendszerről van szó ugyanezen feltételekkel?

Előzmény: [3239] jonas, 2010-02-12 21:57:23
[3240] Lóczi Lajos2010-02-12 22:03:59

a=-\frac{-y x^{\alpha }+z x^{\alpha }+x y^{\alpha }-x z^{\alpha }-z y^{\alpha }+y z^{\alpha }}{(x-y) (x-z) (y-z)}

Előzmény: [3237] Fálesz Mihály, 2010-02-12 11:31:26
[3239] jonas2010-02-12 21:57:23

Nyilván nem, mert a modulusok relatív prímek, így mindegyik sorozat tagjaihoz egyet hozzáadva a kapott sorozatoknak van metszetük, és az ebben lévő számok egyik eredeti sorozatban sincs benne.

Előzmény: [3238] bily71, 2010-02-12 21:01:37
[3238] bily712010-02-12 21:01:37

Konstruálható-e inkongruens lefedőrendszer csak prím modulusú tagokból?

[3237] Fálesz Mihály2010-02-12 11:31:26

Sikerült valakinek kifejezni az a együtthatót az x,y,z,\alpha számokkal?

Előzmény: [3226] Fálesz Mihály, 2010-02-10 10:41:39
[3236] Róbert Gida2010-02-12 00:44:36

De, halálismert. Specmatos gimnáziumban is ugyanezt a bizonyítást mondják el, latinnégyzetes rizsa nélkül.

Előzmény: [3231] bily71, 2010-02-11 12:49:08
[3235] Sirpi2010-02-11 18:03:18

m2mm úgy érti, hogy a bizonyítás ilyen hosszúságban elmondható (gyakorlatilag változatlan formában) úgy, hogy nem ejted ki azt a szót, hogy latin négyzet. Mellesleg én is ezt a bizonyítást ismerem a tétel "alap" bizonyításának.

Előzmény: [3234] bily71, 2010-02-11 17:28:19
[3234] bily712010-02-11 17:28:19

Annyi köze van a latin négyzetekhez, hogy ha nem latin négyzetekről lenne szó, akkor nem biztos, hogy tudnánk párokat képezni, ugyanis nem lenne biztosított, hogy minden sorban szerepeljen az egyes, főleg, hogy csak egyszer, biztosítva a párok egyértelműségét, elvégre definíció szerint egy n×n-es latin négyzet az 1-től n-ig terjedő egész számokat tartalmazza úgy, hogy minden sorában és oszlopában egy szám csak egyszer szerepel.

Előzmény: [3233] m2mm, 2010-02-11 14:52:08
[3233] m2mm2010-02-11 14:52:08

Ez korrekt megoldás, de ennek valójában semmi köze a latin négyzetekhez. Egyszerűen párokat képezel, ez az egyik legismertebb bizonyítása a tételnek.

Előzmény: [3231] bily71, 2010-02-11 12:49:08
[3232] bily712010-02-11 13:01:12

Valóban elegánsabb megfogalmazás.

Előzmény: [3230] Róbert Gida, 2010-02-10 22:46:58
[3231] bily712010-02-11 12:49:08

Ha életedben nem hallottad, hogy a latin négyzetek segítségével a Wilson-tétel bizonyítható, ez bizonyára érdekes lesz számodra, és legalább nem "halál ismert", legalábbis általad, (itt most az idézőjel nem iróniát, hanem tényleges idézést jelöl).

Legyen p\inP, azaz prím. Képezzünk p maradékosztályaiból, a 0-át kihagyva szorzótáblát. Ekkor a táblázat latin négyzet, ezt már [3187]-ben beláttuk.

Ennek az a következménye, hogy minden a-hoz létezik egy, és csakis egy b szám, hogy

ab\equiv1(mod p),

ahol a és b p egy-egy maradékosztálya.

Az a=b csak a=1, vagy a=p-1 esetén fordulhat elő, minden más esetben a\neb, ugyanis, ha

a2\equiv1(mod p),

akkor

a2-1\equiv0(mod p),

de akkor p nem lehet prím, mert

a2-1=(a-1)(a+1)\equiv0(mod p).

Ennek az a következménye, hogy az 1<a<p-1 maradékosztályok párokba rendezhetőek, így lesz \frac{p-3}{2} darab olyan számpárunk, hogy

aibj\equiv1(mod p).

Ezeket a számpárokat helyettesíthetjük 1-gyel, így a következőt kapjuk:

(p-1)!=1.2.3...(p-3)(p-2)(p-1)=1.1...1.1(p-1)\equivp-1(mod p).

Q.E.D.

Előzmény: [3186] Róbert Gida, 2010-02-01 17:11:09
[3230] Róbert Gida2010-02-10 22:46:58

Igazán nem kötekedés akar lenni, de jobban szeretik úgy mondani, hogy p legyen páratlan prím.

Előzmény: [3216] bily71, 2010-02-07 22:31:14

  [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]