Fórum: A kongruenciarendszerek lefedőségének feltételei

Szeretnél hozzászólni? Jelentkezz be.

[15] w	2013-07-24 11:00:26
Igen , én is így gondoltam. Általában is érdemes vigyázni, amikor triviális éredmények után hirtelen hatalmas lépést teszünk.
Előzmény: [14] Kőrösi Ákos, 2013-07-23 16:18:43

[14] Kőrösi Ákos	2013-07-23 16:18:43
A hibát megtaláltam én is. Elvi hiba,mint sejtetted. A rekurzió szó egy kicsit átverés én ugyanis a sorozat differencia sorozatát adtam meg: h_n-h_n-1=l-i_n-1-1/m_n Ennek bizonyítása egyszerű a skatulyaelvet használja. Továbbá: igen, a h_k-ra gondolok. Egyébként a 7-ből nem következik a 8.pont, csupán a 8.lépés kihasználja a 7. állítást.A hiba 8-ban van. Remélem ez válasz a kérdéseidre.
Előzmény: [13] w, 2013-07-08 00:50:54

[13] w

2013-07-08 00:50:54

Most éppen a hibát próbálom keresni, ami valószínűleg elvi hiba. Az 1) tétel és a 2) következménye triviális. A 2) állításodhoz megjegyezném, hogy egy kongruenciarendszer megoldása a kongruenciák egyszerre való teljesülésekor keletkezik, míg te a kongruenciák 'úniójáról' beszélsz. Az i_k sorozat értelmes. A h_k sorozat bevezetése kicsit furcsa, jobb volna i_k maximalitását megkövetelni, de még nem hibás a megoldás.

"Megadok egy rekurzió a k_n sorozatra" - itt nem h_k-ra gondolsz? Kérdéses egy ilyen rekurzió létezése, és ez kulcsfontosságú lépés volna, ezért kérlek írd le a rekurzió megteremtését kicsit részletesebben! A 8) állítás 7)-ből való következése a legérthetetlenebb, nem arra van szükség, hogy h_n=(lkkt)-1?

Ha begépeled a részletes gondolatmenetet, az 1-4) részeket szerintem kihagyhatod.

Előzmény: [12] Kőrösi Ákos, 2013-07-07 23:30:32

[12] Kőrösi Ákos

2013-07-07 23:30:32

Meglehetősen hosszú a "bizonyításom". Vázlat:

1)Kimondom és bizonyítom azt a tételt, miszerint egy kongruenciarendszer lefedő, ha minden számot lefed,ami kisebb mint a modulusok legkisebb közös többszöröse.

2)A fenti tétel értelmében átfogalmazom a bizonyítandó állítást:azt kell bizonyítani hogy bármely m₁ számhoz létezik olyan kongruenciarendszer, aminek minden. [m₁,m₂,...,m_n]-nél kisebb(természetes) szám megoldása.

3)Definiálok egy sorozatot,i_n-t, amelynek: k-adik tagja egyenlő az 1.,2.,...,k-adik kongruenciák alkotta rendszer megoldásainak számával.

4)Tehát azt kell bizonyítanom, hogy megadható minden m₁ számhoz olyan m₁ kezdőmodulusú (n-tagú)rendszer, amelyre a i_n egyenlő a modulusok l.k.k.t-jével

5)Definiálok egy újabb sorozatot:h_n-t, amelyre igaz a következő állítás: megadható úgy a k-adik kongruencia, hogy h_k<i_k teljesüljön.(Gondolom nyilvánvaló, hogy i_k értéke függ a k-adik kongruenciától, ezt egyébként le is vezettem.)A második kritérium: h_k a legnagyobb ilyen szám. Tehát gyakorlatilag olyan értékeket tartalmaz ez a sorozat,hogy elérhető az ,hogy i_k nagyobb legyen azoknál.

6)Megadok egy rekurzió a k_n sorozatra.

7)Nyilvánvaló, hogy k_n<[m₁,...,m_n].

8)Majd levezetem hogy ez csak akkor lehetséges, ha i_n=[m₁,...,m_n].Tehát i_n=[m₁,...,m_n], azaz a fenti tétel értelmében ez egy lefedőrendszer.

Remélem érthető voltam.A hibát még nem találom,de igyekszem feltölteni a "bizonyítást" amint tudom, erre valószínűleg a közeljövőben nem érek rá.

Előzmény: [11] w, 2013-07-07 06:39:57

[11] w

2013-07-07 06:39:57

Nagyszerű hír!

Ennek ellenére Ákos (hibás) gondolatmenetére is kíváncsi volnék, ha nem túl hosszú.

Egy feladatot korábban talán felvetettem:

Léteznek-e n, a₁<a₂<...<a_n, 1<m₁<m₂<...<m_n pozitív egész számok, melyekre a_k<m_k, az A_k={a_k+m_k $\ell$ : $\ell$ $\in$ N} halmazok (k=1,2,...,n) páronként diszjunktak, és A₁ $\cup$ A₂ $\cup$ ... $\cup$ A_n=Z⁺?

A(z egyik) megoldás, akit érdekel, itt van.

Előzmény: [10] Erben Péter, 2013-07-05 11:58:17

[10] Erben Péter

2013-07-05 11:58:17

Ha a kezdőmodulus azt jelenti, hogy a rendszer legkisebb modulusa, akkor úgy tűnik, nem igaz az állítás.

Friss eredmény: The least modulus of a covering system,

a cikk itt: selectedpapers.net/arxiv

Előzmény: [6] Kőrösi Ákos, 2013-06-28 00:01:16

[9] w	2013-07-04 01:43:11
Egy megoldásvázlat is jó volna (azaz 1. állítás: xyz, biz.: nagyjából így megy $\implies$ 2. állítás stb. módon).
Előzmény: [8] Kőrösi Ákos, 2013-07-02 12:54:42

[8] Kőrösi Ákos	2013-07-02 12:54:42
Szia! Hát nekem egyelőre úgy tűnik,helyes. Sajnos papírra van leírva, időbe telik legépelni,de igyekszem feltölteni,amint tudom.
Előzmény: [7] w, 2013-07-02 07:39:54

[7] w	2013-07-02 07:39:54
Szia! Remélem, hogy jó a bizonyítás, ha nem találsz benne hibát, szerintem töltsd fel ide. Lehet, hogy van egy nagyon finom kis hiba. (Több hibás bizonyítás is volt nehéz állításokra a fórum történetében.) Üdvözlettel: W.
Előzmény: [6] Kőrösi Ákos, 2013-06-28 00:01:16

[6] Kőrösi Ákos

2013-06-28 00:01:16

Sziasztok! Azt hiszem, sikerült egy bizonyítást konstruálnom arra, hogy bármely m₁ természetes számhoz létezik m₁ kezdőmodulusú lefedő kongruenciarendszer. A bizonyítást még most nézem át, azaz nem biztos, hogy hibátlan. De ha kiderülne, hogy nincs benne hiba, akkor mit tegyek. Érdekes téma ez ahhoz hogy cikk formájában közzétegyem valahol? A válaszokat előre is köszönöm.

Kőrösi Ákos

Előzmény: [5] Róbert Gida, 2013-03-13 22:48:39

[5] Róbert Gida	2013-03-13 22:48:39
Nemrégi részeredmény: A covering system whose smallest modulus is 40.
Előzmény: [4] w, 2013-03-13 21:55:38

[4] w

2013-03-13 21:55:38

A lefedő kongruenciarendszerekkel most bajlódni nem volna nagyon érdemes: a problémakör teljes megoldása $1000-t érne (Erdős-probléma), a legjobb matematikusok sem bírják megoldani.

Kezdésképpen érdekes volna igazolni, hogy nincs olyan különböző modulusú kongruenciarendszer, sőt, egész differenciájú számtanisorozat-csoport sem, mely minden pozitív egészt pontosan egyszer tartalmazna.

[3] Kőrösi Ákos	2012-12-23 20:28:26
Írnál néhány ilyen triviális feltételt?Köszönöm.
Előzmény: [2] Zine, 2012-12-23 12:43:50

[2] Zine

2012-12-23 12:43:50

Tudtommal triviális elégséges feltételeknél nem nagyon van jobb. Szükséges feltételeket lehet mondani.

Legyenek a₁, a₂,..., a_n egészek, m₁, ..., m_n pozitív egészek.

x $\equiv$ a_i mod m_i

Ha ez nem fedő, akkor az 1, 2,... 2ⁿ számok egyikét sem fedi le.

$\sum_{i=1}^n \frac{1}{m_i}\geq 1$

Ebből következik, hogy nem lehet mind négyzetszám. Az is igaz, hogy nem lehetnek mind különböző prímek. Stb. Majd ír valaki olyan is, aki jobban ért hozzá:)

Előzmény: [1] Kőrösi Ákos, 2012-12-23 00:06:04

[1] Kőrösi Ákos	2012-12-23 00:06:04
Tegyük fel,hogy van egy kongruenciarendszerünk. Mi az ismert legszűkebb szükséges és elégséges feltétele annak,hogy a rendszer lefedő legyen?

Már regisztráltál?
Új vendég vagy?