|
[143] w | 2013-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|2[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|(k-1)[logk(N)].
|
Előzmény: [142] Maga Péter, 2013-07-30 08:50:24 |
|
|
|
[140] w | 2013-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 |
|
|
|
|
|
[135] Maga Péter | 2013-07-29 19:42:19 |
A 10. probléma, mind a 3 tagú (Róbert Gidának: nemkonstans:)), mind a k3 tagú sorozatokra ismert olyan alsó becslés, hogy (Tao-Vu: Additive combinatorics könyv 10.1-es fejezete):
rk([1,N])=(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] w | 2013-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 |
|
|
[132] Róbert Gida | 2013-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<tnk 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] w | 2013-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 |
|
|
[129] w | 2013-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] w | 2013-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
, akkor ( [ ]:egészrész, { }:törtrész )
Ha nem, javítsuk ki (a jobb oldalt)!
|
Előzmény: [126] Róbert Gida, 2013-07-29 18:26:24 |
|
|
|
|
[124] w | 2013-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 Gida | 2013-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] w | 2013-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] jonas | 2013-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] w | 2013-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 ?
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 , ahol s(a) a számjegyek összegét jelenti?
7. Van-e PZ[x] polinom, melyre ?
8. Van-e 100-jegyű Niven-szám?
9. Igaz-e, hogy ?
10. Mi az {1;2;...;N} halmaz legbővebb részhalmaza, amely nem tartalmaz számtani sorozatot?
|
|