KöMaL - Középiskolai Matematikai és Fizikai Lapok
English Információ A lap Pontverseny Cikkekről Távoktatás Hírek Fórum Internetes Tesztverseny
Játékszabályok
Technikai információk
TeX tanfolyam
Regisztráció
Témák

 

Rendelje meg a KöMaL-t!

Támogatóink:

tehetseg.hu

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Reklám:

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Ön még nem jelentkezett be.
Név:
Jelszó:
Ha a témához hozzá kíván szólni, először regisztrálnia kell magát.
[15] w2013-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 Ákos2013-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: hn-hn-1=l-in-1-1/mn Ennek bizonyítása egyszerű a skatulyaelvet használja. Továbbá: igen, a hk-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] w2013-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 ik sorozat értelmes. A hk sorozat bevezetése kicsit furcsa, jobb volna ik maximalitását megkövetelni, de még nem hibás a megoldás.

"Megadok egy rekurzió a kn sorozatra" - itt nem hk-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 hn=(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 Ákos2013-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 m1 számhoz létezik olyan kongruenciarendszer, aminek minden. [m1,m2,...,mn]-nél kisebb(természetes) szám megoldása.

3)Definiálok egy sorozatot,in-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 m1 számhoz olyan m1 kezdőmodulusú (n-tagú)rendszer, amelyre a in egyenlő a modulusok l.k.k.t-jével

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

6)Megadok egy rekurzió a kn sorozatra.

7)Nyilvánvaló, hogy kn<[m1,...,mn].

8)Majd levezetem hogy ez csak akkor lehetséges, ha in=[m1,...,mn].Tehát in=[m1,...,mn], 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] w2013-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, a1<a2<...<an, 1<m1<m2<...<mn pozitív egész számok, melyekre ak<mk, az Ak={ak+mk\ell:\ell\inN} halmazok (k=1,2,...,n) páronként diszjunktak, és A1\cupA2\cup...\cupAn=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éter2013-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] w2013-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 Ákos2013-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] w2013-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 Ákos2013-06-28 00:01:16

Sziasztok! Azt hiszem, sikerült egy bizonyítást konstruálnom arra, hogy bármely m1 természetes számhoz létezik m1 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 Gida2013-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] w2013-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 Ákos2012-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] Zine2012-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 a1a2,..., an egészek, m1, ..., mn pozitív egészek.

x\equivai mod mi

Ha ez nem fedő, akkor az 1, 2,... 2n 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 Ákos2012-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?

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Támogatóink:   Ericsson   Google   Szerencsejáték Zrt.   Emberi Erőforrások Minisztériuma   Emberi Erőforrás Támogatáskezelő   Oktatáskutató és Fejlesztő Intézet   ELTE   Nemzeti Tehetség Program   Nemzeti
Kulturális Alap