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: Számelméleti érdekességek

  [1]    [2]    [3]    [4]    [5]    [6]    [7]  

Szeretnél hozzászólni? Jelentkezz be.
[144] w2013-07-30 14:16:20

Egyébként teljesen mindegy, hogy a {1,2,...,n} vagy a {0,1,...,n-1} halmazról van szó. :-)

Előzmény: [143] w, 2013-07-30 14:13:00
[143] w2013-07-30 14:13:00

Ez szép!

A két konstrukciót érdemes összehasonlítani. Az általam írt megoldásra megadhatjuk a (pontatlan) |A|\ge2[log3(N)] becslést, tehát a két becslés hasonló jellegű. Egyik skatulya-elvre támaszkodik, másik pedig algebrai tulajdonságokra. Viszont mindkettő megoldás kulcsfontosságú, és azt gondolom, feltétlenül szükséges (vagy mégsem?) eleme a számrendszer alkalmazása.

Ha k hosszú számtani sorozatokat szeretnénk csak mellőzni, akkor |Ak|\ge(k-1)[logk(N)].

Előzmény: [142] Maga Péter, 2013-07-30 08:50:24
[142] Maga Péter2013-07-30 08:50:24

Nézd meg ezt!

Előzmény: [140] w, 2013-07-29 21:48:30
[141] Maga Péter2013-07-29 22:40:13

Ez nem optimális, de már későre jár, holnap mutatok jobbat.

Előzmény: [140] w, 2013-07-29 21:48:30
[140] w2013-07-29 21:48:30

Jelölje an a Hn={1;2;...;n} halmazban előforduló lehető leghosszabb számtani sorozatot.

Engedjük rá a mohó algoritmust. Az első néhány generált szám a következő: 0, 1, 3, 4, 9, 10, 12, 13, 27. Most írjuk át ezeket a hármas számrendszerbe: 0, 1, 10, 11, 100, 101, 110, 101, 1000. Szabályosság ismerhető fel. Egyszerűen megmutatható, hogy nincs számtani sorozat a 0 és 1-ből álló számok között a 3-as számrendszerben. Innen jön a becslés an-re, ami ezek szerint nem optimális. Világos viszont, hogy ez a becslés egyszerű módon átírható k elemű számtani sorozatokra.

Azt gondolom, hogy nem lehet különösen nehéz továbbgondolni a konstrukciót. Indukcióval lehetne optimalitási megfontolásokat tenni.

Előzmény: [139] w, 2013-07-29 21:28:01
[139] w2013-07-29 21:28:01

Ja. Szerintem 0-tól n-ig voltak a számok. Elnézést.

Előzmény: [137] Maga Péter, 2013-07-29 20:35:57
[138] w2013-07-29 21:22:29

Még ellenőriznem kell, hogy optimális-e az általam ismert konstrukció, de most úgy látszik, nem az. Folyt. köv.

Előzmény: [137] Maga Péter, 2013-07-29 20:35:57
[137] Maga Péter2013-07-29 20:35:57

Ez meglep, de érdekel.

Előzmény: [136] w, 2013-07-29 19:51:54
[136] w2013-07-29 19:51:54

Hm. Nekem úgy tűnik, hogy végtelen sok speciális esetre pontos megoldás is adható, de akkor lehet, hogy tévedek.

Előzmény: [135] Maga Péter, 2013-07-29 19:42:19
[135] Maga Péter2013-07-29 19:42:19

A 10. probléma, mind a 3 tagú (Róbert Gidának: nemkonstans:)), mind a k\geq3 tagú sorozatokra ismert olyan alsó becslés, hogy (Tao-Vu: Additive combinatorics könyv 10.1-es fejezete):

rk([1,N])=\Omega(N*exp(-Ok(log N)1/(1+[log2(k-1)]))).

Felső becslést olyat találok hirtelen, hogy

r3([1,N])=O(N(log N)-c),

c<2/3.

Nem hiszem, hogy ez megoldott lenne, de sokat kutatott terület.

Előzmény: [130] w, 2013-07-29 18:57:23
[134] w2013-07-29 19:13:53

8. feladat. Wikipédia: "Although the sequence of factorials starts with Harshad numbers in base 10, not all factorials are Harshad numbers. 432! is the first that is not."

Ezek szerint a 70! alkalmas Niven-szám lesz.

Előzmény: [125] Róbert Gida, 2013-07-29 18:12:10
[133] w2013-07-29 19:11:25

Bocsi tényleg.

Előzmény: [132] Róbert Gida, 2013-07-29 19:07:11
[132] Róbert Gida2013-07-29 19:07:11

Bizonyítás (bár szerintem ez triviális): belátom, hogy s(t*(nk-1))=k*(n-1), ha 0<t\lenk egész, itt s(x) az x számjegyösszege n alapú számrendszerben. Ugyanis: s(t*(nk-1))=s((t-1)*nk+(nk-t))=s((t-1)*nk)+s(nk-t)=s(t-1)+s(nk-t)=k*(n-1), ez utóbbi könnyen látható, ha észrevesszük, hogy: (t-1)+(nk-t)=nk-1, és s(nk-1)=k*(n-1).

Előzmény: [128] w, 2013-07-29 18:52:05
[131] w2013-07-29 19:06:05

Infinitezimális segítséget adnék a 10. kérdéssel kapcsolatban, ha még nem oldottad meg.

Feladat (IMO 1983/5.): "Is it possible to choose 1983 distinct positive integers, all less than or equal to 105, no three of which are consecutive terms of an arithmetic progression?"

Előzmény: [127] Sinobi, 2013-07-29 18:51:01
[130] w2013-07-29 18:57:23

Jó kérdés!

Előzmény: [127] Sinobi, 2013-07-29 18:51:01
[129] w2013-07-29 18:56:59

Ezzel (is) megtámogatva az az érzésem van, hogy számtani sorozatok legalább három tagból szoktak állni.

Kértelek, hogy vedd figyelembe a trivialitások iránti érdeklődésem teljes hiányát.

Előzmény: [125] Róbert Gida, 2013-07-29 18:12:10
[128] w2013-07-29 18:52:05

Jól hangzik. Hadd javítsalak ki: a példa a1=d=nk-1, ahol n a számrendszer alapszáma. Nem árt a pontosság.

Amúgy egy bizonyítás is jó volna.

Hasznos lehet (vagy nem) a következő képlet.

Igaz-e, hogy ha

x=\overline{a_\ell a_{\ell-1}\dots a_0}_{(n)}, akkor ( [ ]:egészrész, { }:törtrész )

s(x)=\sum_{i=0}^\ell n\cdot\left\{ \frac{\left[x/ (n^{i})\right]} {n^{\ell-i+1}} \right\}

Ha nem, javítsuk ki (a jobb oldalt)!

Előzmény: [126] Róbert Gida, 2013-07-29 18:26:24
[127] Sinobi2013-07-29 18:51:01

10: és ami nem tartalmaz k hosszú számtani sorozatot?

Előzmény: [125] Róbert Gida, 2013-07-29 18:12:10
[126] Róbert Gida2013-07-29 18:26:24

4. Tetszőleges k pozitív egészre 10k tagú számtani sorozatra példa: legyen a1=d=10k-1. És ez tetszőleges számrendszerben működik.

Előzmény: [124] w, 2013-07-29 17:03:22
[125] Róbert Gida2013-07-29 18:12:10

8. akkor legyen n=2*1099

10. az üres halmaz még mindig a legjobb. Egyetlen egész is számtani sorozat d>0-val.

Előzmény: [124] w, 2013-07-29 17:03:22
[124] w2013-07-29 17:03:22

Igazad van, szokás szerint nem írtam le a kérdéseket elég pontosan. Minden esetben nemtriviális dolgok értendők: számtani sorozaton d>0 differenciájút értettem, a 8. feladatban pedig nem 10-hatványt. Elnézést a félreértésért.

Az 5. kérdés tudomásom szerint valóban nyitott, érdekes, hogy csak 5 darab ilyet ismernek (Fermat-prím íze van a dolognak).

Előzmény: [123] Róbert Gida, 2013-07-29 16:41:19
[123] Róbert Gida2013-07-29 16:41:19

4.: végtelen hosszú is van, legyen an=c (konstans egész).

5.: 2, 4, 8, 64, 2048 az ismert 2 hatványok csupa páros jeggyel. Ez szerintem nyitott probléma, hogy van-e más (Sloane adatbázisa szerint is).

8.: 1099 jó példa.

10.: Az üres halmaz.

Előzmény: [121] jonas, 2013-07-29 14:29:21
[122] w2013-07-29 14:46:06

Igen. Nézzük sorra a feladatokat. Aki nem akar segítséget hallani, ne olvasson tovább. Az 1. feladat tényleg ismert/könnyű. A 2. feladat lényege (azaz van-e n2=10a1+10a2+...+10ak, a1<a2<...<ak, k>1) még nyitott kérdés. A 3., 4., 6., 7., 8., 10. szerintem megoldott feladat, némelyik egyszerű és elemi bizonyítással rendelkezik. A 9. viszont komoly nyitott probléma.

Előzmény: [121] jonas, 2013-07-29 14:29:21
[121] jonas2013-07-29 14:29:21

Pár megjegyzés.

1. Ezt ismerem, úgyhogy nem lőném le. Szerintem valamelyik versenyen is szerepelt egy változata.

2. Van: 0, 1, 100, 10000, 1000000. Vicces, hogy (1/3)2-ben szintén csak ezek a számjegyek vannak.

4. Végtelen hosszú biztos nincs, ugyanazért, amit az 1. feladatból tanultunk: egy számtani sorozat számai közt bármilyen kezdő számjegysorozat előfordul, ezért tetszőlegesen nagy számjegyösszegű szám is lesz. n alapú számrendszerben n számtani sorozat biztos van ilyen, pl. 9, 18, 27, 36, 45, 54, 63, 72, 81, 90. Az a kérdés ezért, hogy ugyanabban a számrendszerben lehet-e tetszőlegesen hosszú sorozat.

7. Nem tudom, de ha van, akkor kell benne negatív együtthatónak lennie.

Előzmény: [120] w, 2013-07-29 13:54:53
[120] w2013-07-29 13:54:53

Néhány további számelméleti érdekesség/kérdés:

1. Igaz-e, hogy van olyan kettőhatvány, amely 10-es számrendszerben két darab 1-es számjeggyel kezdődik? Kezdődhet akárhány 1-essel egy kettőhatvány (k alapú szr.-ben)? Mi a helyzet más számjegyek vagy hatványalapok esetén?

2. Van-e csak 0-kból és 1-esekből álló négyzetszám (10-es számrendszer)?

3. Konvergál-e az xn:=sin (n2)+sin (n3) sorozat? És a_n:=\sin(n^k)+\sin(n^\ell)?

4. Van-e tetszőlegesen hosszú számtani sorozat egyenlő számjegyösszegű számokkal (akármilyen szr.-ben)? És végtelen hosszú számtani sorozat?

5. Melyik a legnagyobb 2-hatvány (ha van), melynek minden számjegye páros?

6. Van-e egyszerű bizonyítás arra, hogy \lim_{n\to\infty} s(2^n)=\infty, ahol s(a) a számjegyek összegét jelenti?

7. Van-e P\inZ[x] polinom, melyre \lim_{n\to\infty}s(P(n))=\infty?

8. Van-e 100-jegyű Niven-szám?

9. Igaz-e, hogy \lim_{n\to\infty} \frac{s(2^n)}{\ln n}=\infty?

10. Mi az {1;2;...;N} halmaz legbővebb részhalmaza, amely nem tartalmaz számtani sorozatot?

  [1]    [2]    [3]    [4]    [5]    [6]    [7]