Fórum: Számelméleti érdekességek

Azért a te konstrukciód sem rossz, az 1983-as IMO 5-ös feladatát megoldja:).

Igen, és sokkal szebb módon.

Behrendé sokkal nagyobb halmazt ad, minden x^c-nél lassabban, de minden pol(log(x))-nél gyorsabban nő.

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

Ez szép!

A két konstrukciót érdemes összehasonlítani. Az általam írt megoldásra megadhatjuk a (pontatlan) |A|2^[log₃(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 |A_k|(k-1)^[log_k(N)].

Nézd meg ezt!

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

Jelölje a_n a H_n={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 a_n-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.

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

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

Ez meglep, de érdekel.

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

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):

r_k([1,N])=(N*exp(-O_k(log N)^{1/(1+[log₂(k-1)])})).

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

r₃([1,N])=O(N(log N)^-c),

c<2/3.

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

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.

Bocsi tényleg.

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

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 10⁵, no three of which are consecutive terms of an arithmetic progression?"

Jó kérdés!

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.

Jól hangzik. Hadd javítsalak ki: a példa a₁=d=n^k-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)!

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

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

8. akkor legyen n=2*10⁹⁹

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

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).

4.: végtelen hosszú is van, legyen a_n=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.: 10⁹⁹ jó példa.

10.: Az üres halmaz.