|
|
|
|
[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 |
|