|
|
[3262] Alma | 2010-02-25 17:12:18 |
Szerintem függ, hogy melyik az az adott elem k-as. Vegyük például azt a leegyszerűsített esetet, hogy a kockának két oldala van: 1,2 és n=3szor dobunk.
Azok a számsorok, melyekben az 11 elemkettes pontosan egyszer fordul elő: 112 és 211.
Azok a számsorok, melyekben a 12 elemkettes pontosan egyszer fordul elő: 112, 121, 122, 212.
A két eseménynek nem egyenlő a valószínűsége.
|
Előzmény: [3261] Láda19, 2010-02-25 16:21:43 |
|
[3261] Láda19 | 2010-02-25 16:21:43 |
Lenne egy valószínűségszámítási probléma, amit a napokban kérdeztek tőlem, de még nem tudtam megoldani. Szeretném, ha valaki segítene.
Egy dobókockával n-szer dobunk, majd a dobások eredményét leírjuk egymás mellé. Mennyi a valószínűsége annak, hogy az 1, 2, 3, 4, 5, 6 számokból képezett, adott elem k-as (k<n) pontosan egyszer előfordul az n hosszúságú számsorban?
|
|
|
|
[3258] Fálesz Mihály | 2010-02-19 12:41:32 |
Számomra inkább az érdekes, hogy ezzel a módszerrel primitív gyökök felhasználása nélkül is ilyen röviden be lehet bizonyítani azt, hogy a akkor és csak akkor kvadradikus maradék mod p, ha a(p-1)/21(mod p), különben a(p-1)/2-1.
(A kis Fermat-tétel párosítgatás és Wilson-tétel nélkül is kijön a szokásos bizonyítással: összeszorozzuk az a,2a,...,(p-1)a maradékokat.)
|
Előzmény: [3256] bily71, 2010-02-17 23:30:28 |
|
[3257] bily71 | 2010-02-18 21:45:01 |
Én arra jutottam, hogy a le nem fedett számok halmaza végtelen. Gondoltmenetem a következő:
Vonjuk össze az egy modulushoz tartozó számtani sorozatokat, így minden 3-nál nagyobb prímhez kapunk egy olyan számsorozatot, amelyben két differencia váltja egymást. Írjuk fel a sorokat egymás után képzeletben. A sorok táblázatba rendezhetőek, a táblázatban a számok a prímek szorzata egyhatodának alsó, vagy felső egészrészének felelnek meg. Ezt a táblázatot azt hiszem már jól ismerjük.
Ha a le nem fedett számok halmaza véges lenne, akkor létezne k természetes szám, hogy e szám nem, de minden nála nagyobb fedett. Ez csak úgy lehetséges, ha minden új sorozat legkisebb olyan tagja, amely eddig egyik sorozatnak sem volt tagja fedi a k után következő olyan számot, amelyet az előző sorozatok nem fedtek le, (remélem eddig érthetően fogalmaztam).
Jelölje an az n-edik le nem fedett számot, bn pedig az n-edik sorozat azon legkisebb tagját, amely nem szerepelt egyik eddigi sorozatban sem. Mivel a táblázat a főátlóra szimmetrikus, ezért , ebből következik, hogy an<bn, így soha nem fedheti, mert az an=bn soha nem teljesül.
Jól következtettem? Eléggé tömören fogalmaztam, ha nem érthető, bővebben kifejtem.
A nem fedett számok egy nevezetes számsorozat tagjaival egyértelműen megfeleltethetőek .
|
Előzmény: [3253] bily71, 2010-02-16 20:04:32 |
|
[3256] bily71 | 2010-02-17 23:30:28 |
Két eset lehetséges:
1. a nem kvadratikus maradék modulo p. Ekkor a Wilson-tétel miatt
ebből
ap-11 (mod p),
ebből
apa (mod p).
2. a kvadratikus maradék modulo p. Ekkor a Wilson-tétel miatt
ebből
ebből ugyancsak a kis Fermat-tételt kapjuk.
(Az előző megoldásom második része részben hibás).
|
Előzmény: [3252] Fálesz Mihály, 2010-02-15 10:16:52 |
|
[3255] jonas | 2010-02-16 20:54:36 |
Nem, én azt állítom, hogy a következő egy lefedő rendszer:
x00(mod p0)
x11(mod p1)
x2-1(mod p2)
x32(mod p3)
x4-2(mod p4)
x53(mod p5)
stb, ahol pi mondjuk a prímszámok sorozata.
Ez akkor is működik, ha mondjuk pi=10i+1: ilyenkor a kongruenciák közül bármelyik véges sok együtt csak a természetes számok legfeljebb egy kilenced részét fedi le, mégis az összes kongruencia együtt már lefedi az összes egész számot.
|
Előzmény: [3248] bily71, 2010-02-14 23:10:38 |
|
|
[3253] bily71 | 2010-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 kongruenciáknak megfelelő számtani sorozatok első eleme , az kongruenciáknak megfelelőeknek pedig változatlanul .
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 |
|
|
[3251] Fálesz Mihály | 2010-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) |
Mivel p>2, a +1 és -1 maradékok különbözőek, a -1(-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-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+1(mod p)):
-1(p-1)!=(a.(-a)).(1.(p-1))....(-1)(p-3)/2. (mod p) | (2) |
A -1(-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 |
|
|
|
[3248] bily71 | 2010-02-14 23:10:38 |
Tehát, ha jól értem azt állítod, hogy az
x1m(mod p1)
x2m(mod p2)
...
xnm(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:
x11(mod 5)
x2-1(mod 5)
x31(mod 7)
x4-1(mod 7)
x52(mod 11)
...
ahol ha pn=6k+1, akkor 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] bily71 | 2010-02-14 22:12:36 |
Ezt kapjuk:
.
Két eset lehetséges, első:
2 | , ekkor van darab számpárunk, amelyek szorzata ab-1(mod p), ha behelyettesítünk, akkor ezt kapjuk:
.
Második:
, ekkor létezik a, hogy a2-1(mod p), de akkor (p-1)2-1(mod p). Így kapunk darab számpárt, amelyek szorzata ab-1(mod p), és mivel 2 | , ezért, ha behelyettesítünk, ezt kapjuk:
.
|
Előzmény: [3243] Fálesz Mihály, 2010-02-13 12:38:17 |
|
[3246] jonas | 2010-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 |
|
|
[3244] bily71 | 2010-02-13 12:46:49 |
Triviális megoldás az
x11(mod p1)
x22(mod p2)
...
xnn(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:
x1a1(mod p1)
x2a2(mod p2)
x3a3(mod p3)
...
xmam(mod pm)
xm+1b1(mod pm+1)
...
xm+nbn(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 |
|
|
|
|
|