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: Lejárt határidejű KÖMAL feladatokról

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]  

Szeretnél hozzászólni? Jelentkezz be.
[1072] Róbert Gida2018-03-13 18:58:22

Lejárt A717. megoldása: legyenek a számaink \(\displaystyle 2^\alpha 3^\beta\) alakúak, ahol \(\displaystyle \alpha,\beta\ge 0\), és tegyük fel indirekte, hogy valamilyen \(\displaystyle K>0\) egészre van három ilyen alakú szám \(\displaystyle K^2\) és \(\displaystyle (K+1)^2\) között. Ekkor \(\displaystyle 2\) ilyen alakú szám különbsége: \(\displaystyle 2^a 3^b-2^c 3^d=2^{min(a,c)} 3^{min(b,d)} (u-v)=min(2^a,2^c)min(3^b,3^d)(u-v)\), ahol \(\displaystyle u,v\) persze maga is lusta szám, azaz \(\displaystyle 2^\alpha 3^\beta\) alakú. A számaink \(\displaystyle K^2\)-nél nagyobbak, és 2 hatvány szorzataként állnak elő, így (legalább) az egyik tag legalább \(\displaystyle K\); de 3 ilyen számunk van, ezért (skatulyaelv miatt) van olyan két szám, amiben a 2 hatványok (vagy a 3 hatványok) legalább K-ak, azaz írhatjuk:

\(\displaystyle 2K>|n1-n2|=min(2^a,2^c)min(3^b,3^d) |u-v|>=K |u-v|\), de \(\displaystyle u!=v\) mivel 2 különböző számról van szó (és mivel egész), ezért csak \(\displaystyle |u-v|=1\) lehet, azaz írhatjuk:

\(\displaystyle 2^\alpha 3^\beta -2^\gamma 3^\delta =\pm 1\), amiből kapjuk, hogy \(\displaystyle \alpha, \gamma \) nem lehet egyszerre pozitív, különben a bal oldal páros, hasonló igaz \(\displaystyle \beta,\delta\)-ra. Azaz \(\displaystyle 2^x-3^y=\pm 1\), ennek az egész megoldásai viszont ismertek: \(\displaystyle \{x,y\}\in \{\{1,0\},\{1,1\},\{2,1\},\{3,2\}\}\), ez a Catalan-sejtés (ami ma már tétel) egy 600 éve ismert ultra spec. esete. Azaz kapjuk, hogy \(\displaystyle \frac{(K+1)^2}{K^2}>|\frac {max(n1,n2)}{min(n1,n2)}|\ge \frac98\), ami látványosan hamis nagy K-ra, kicsikre meg külön ellenőriztem.

[1071] Lpont2018-02-04 18:46:04

Köszönöm a megfejtést, álmomban sem jutott volna eszembe, hogy ugyanazzal a jelöléssel két különböző változót/kifejezést is jelölünk :(

Előzmény: [1070] Erben Péter, 2018-02-02 06:27:37
[1070] Erben Péter2018-02-02 06:27:37

Ahol egy sorban (egy egyenlő(tlen)ség két oldalán) le van írva, ott ugyanazt jelöli:

\(\displaystyle a_1a_2+3a_3a_4+\dots+(2n-1)a_{2n-1}a_{2n}=a_1^2+3a_3^2+\dots+(2n-1)a_{2n-1}^2\leq \ldots\)

De az előző egyenlőség csak azután igaz, amikor már megtörtént, hogy minden \(\displaystyle k\)-ra, hogy \(\displaystyle a_{2k−1}\)-et és \(\displaystyle a_{2k}\)-t kicseréltük \(\displaystyle \frac{a_{2k−1}+a_{2k}}{2}\)-re.

Tehát az ,,új'' \(\displaystyle a_1\) a ,,régi'' \(\displaystyle a_1\) és a ,,régi'' \(\displaystyle a_2\) átlaga.

Gondolom a megoldás szerzője el akarta kerülni, hogy ilyeneket kelljen írnia:

\(\displaystyle a_1a_2+3a_3a_4+\dots+(2n-1)a_{2n-1}a_{2n} \leq \left(\frac{a_{1}+a_{2}}{2}\right)^2+ 3\left(\frac{a_{3}+a_{4}}{2}\right)^2+ \ldots \)

vagy ilyeneket

\(\displaystyle a_1'a_2'+3a_3'a_4'+\dots+(2n-1)a_{2n-1}'a_{2n}'=a_1'^2+3a_3'^2+\dots+(2n-1)a_{2n-1}'^2\leq \ldots \)

Előzmény: [1069] Lpont, 2018-02-02 04:27:09
[1069] Lpont2018-02-02 04:27:09

Akkor a bizonyításban a bal oldalon lévő a1 nem ugyanaz, mint a feltételből adódó és jobb oldalra írt a1?

Előzmény: [1068] Erben Péter, 2018-02-01 23:38:45
[1068] Erben Péter2018-02-01 23:38:45

Szerintem nem azt állítja a közölt megoldás, hogy \(\displaystyle a_1^2+a_3^2+\ldots\) felső becslés, hanem azt, hogy miután kicseréltük a szomszédos elemeket közös átlagukkal, azután így néz ki az összeg.

Kicsit talán zavaró, hogy ez az \(\displaystyle a_1\) már nem az eredeti \(\displaystyle a_1\).

Tehát amikor az első elem több, mint 0,5, akkor a második már kisebb, mint 0,5, az összeg miatt, ezért átlaguk kevesebb, mint fél, így nincs ellentmondás.

Amúgy érdemes lerajzolni a feladatot, a geometriai reprezentáció szépen elvezet az algebrai megoldásban használt becslésekhez.

Előzmény: [1067] Lpont, 2018-02-01 18:27:53
[1067] Lpont2018-02-01 18:27:53

Hovatovább, ha a sorozat első eleme nagyobb, mint 0,5; akkor ennek négyzete nagyobb, mint 0,25.

Előzmény: [1066] Lpont, 2018-02-01 16:13:26
[1066] Lpont2018-02-01 16:13:26

A lejárt novemberi B. 4905. feladat hivatalos megoldásához:

A bizonyítandó egyenlőtlenség bal oldalát felülről becsülni próbáló kifejezés annyira "laza", hogy már az első két összeadandó összege is áteshet a bizonyítani kívánt 0,25 értékű felső korláton.

Pl: az első három eleme a sorozatnak legyen rendre 0,4; 0,3; 0,2; míg a maradék 0,1-en osztozzanak a sorozat további tagjai monoton csökkenő összegekben.

Ekkor 04*04+3*0,2*0,2=0,16+0,12=0,28>0,25

A javítás során milyen megoldásra támaszkodott a javító? Mindössze 10db max. pontszám született, ez egy 4 pontos B-s feladatnál szokatlanul kevés.

Feltenne vki egy korrekt megoldást?

[1065] atimaly2017-10-11 17:17:55

Valaki tudna segíteni az A. 701., A. 702. -es feladatokban. A segítséget előre köszönöm.

[1064] Róbert Gida2017-05-15 01:05:31

C.1417. megoldása végtelenül túl van bonyolítva. A 2. esetben, ha a+b=c+d !=0, akkor leoszthatunk vele, amiből \(\displaystyle ab=cd\), de akkor \(\displaystyle a+b=c+d\) miatt ugyanannak a másodfokú egyenletnek a gyökei, ezért \(\displaystyle \{a,b\}=\{c,d\}\).

[1063] otto2017-05-10 14:46:39

A K.535 feladat megoldásában olyan versenyző megoldását közlik, aki a 6-ból 5 pontot kapott a megoldására. Lehetséges lenne az, hogy a közölt megoldás(ok) olyanok legyenek, amik a maximális pontszámot érik? Sokat lehetne tanulni abból, hogy milyen részletezettségű indoklást várnak el a javítók a maximális pontszám érdekében.

Lehet, hogy rosszul gondolom, de úgy látom, hogy sok esetben a közölt megoldásokat megoldásként beküldve jó pár pontot levonnának a versenyzőktől.

A C.1408 feladat megoldása úgy látszik kemény dió a kitűzőnek, mindenestre 30 nappal a beküldési határidő után még nem közölték a megoldást.

[1060] Róbert Gida2017-03-27 23:56:06

Van egy ismert csapda ezen példáknál: amire alkalmazni akarod az ötletet az nem feltétlenül egészegyütthatós polinom. \(\displaystyle f(x)=\frac {x^2+x}{2}\) pont ilyen, és erre az "ötlet" nem igaz: \(\displaystyle x_0=0;t=1;p=2\) ellenpélda rá. De javítható a bizonyítás: legyen \(\displaystyle g=n!*f\), ekkor \(\displaystyle g\) már egészegyütthatós, és csak a \(\displaystyle p>n\) prímeket nézzük.

Előzmény: [1062] w, 2017-03-27 21:29:29
[1062] w2017-03-27 21:29:29

A.489. megoldása:

Ötlet. Minden \(\displaystyle f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_0\) polinomhoz rendeljük hozzá a deriváltját, amit a következőképpen definiálunk:

\(\displaystyle f'(x):=(na_n)x^{n-1}+((n-1)a_{n-1})x^{n-2}+\dots+a_1. \)

Ekkor, mint a két oldal kifejtésével könnyen ellenőrizhető, bármely \(\displaystyle p\) prímszámra

\(\displaystyle f(x_0+tp)\equiv f(x_0)+f'(x_0)\cdot (tp)\pmod{p^2}. \)

(Megjegyzés érdeklődőknek: ez a Taylor-sorfejtés p-adikus változatából adódik.)

Ebből következik, hogy ha \(\displaystyle p|f(x_0)\) és \(\displaystyle p\not|f'(x_0)\), akkor alkalmas \(\displaystyle t\) esetén \(\displaystyle p^2|f(x_0+tp)\).

Befejezés. Tegyük fel, hogy \(\displaystyle f(x)\) minden egész helyen négyzetmentes egész értéket vesz fel. Ha valamikor \(\displaystyle p|f(x_0)\), de \(\displaystyle p\not| f'(x_0)\), akkor az 1. ötlettel együtt adódik, hogy nincs ilyen \(\displaystyle f\).

Tegyük fel indirekt, hogy valahányszor \(\displaystyle p|f(x)\), teljesül \(\displaystyle p|f'(x)\) is. Mivel \(\displaystyle f(x)\) négyzetmentes, ezért ebből következik, hogy mindig \(\displaystyle f(x)|f'(x)\), és így \(\displaystyle \frac{f'(x)}{f(x)}\) minden egész \(\displaystyle x\)-re egész értékű. Mivel azonban könnyű látni, hogy elég nagy \(\displaystyle x\)-re \(\displaystyle |f'(x)|<\frac12 |f(x)|\), ezért elég nagy \(\displaystyle x\)-re \(\displaystyle f'(x)=0\), így \(\displaystyle f'\) zéruspolinom és \(\displaystyle f\) konstans.

Tehát nincs a feltételeknek eleget tevő nem konstans polinom.

*****

Feladat. Bizonyítsuk be, hogy nem létezik olyan \(\displaystyle f\) irreducibilis egész együtthatós polinom, melynek minden pozitív egész helyen felvett értéke teljes hatvány.

[1059] w2017-03-16 16:36:32

Az A.689. feladat megoldása.

Az \(\displaystyle a_1,a_2,\dots\) sorozatot egy végtelen papírcsíkra írt számlistaként képzeljük el. Egy algoritmussal fogjuk létrehozni a sorozatot, és az algoritmus minden lépése során további számokat írunk a lista végére. Úgy fogjuk ezt tenni, hogy minden lépés végén a meglévő számsorozat összege \(\displaystyle 0\), és hogy az \(\displaystyle N\)-edik lépésben \(\displaystyle r_N:=\frac1{N}\)-nél kisebb részletösszegek keletkezzenek \(\displaystyle (1)\): így elérjük, hogy \(\displaystyle \sum_{n=1}^\infty a_n\) konvergens legyen (sőt, \(\displaystyle 0\)-val egyenlő).

Ismert, hogy a pozitív egész számpárok felsorolhatók, mondjuk úgy, hogy előbb a \(\displaystyle 2\) összegűeket, majd a \(\displaystyle 3\) összegűeket soroljuk fel stb.:

\(\displaystyle (1,1), \quad (1,2), (2,1), \quad (1,3), (2,2), (3,1),\quad \dots. \)

Legyen itt az \(\displaystyle N\)-edik számpár \(\displaystyle (k_N,i_N)\).

Azt fogjuk garantálni, hogy az \(\displaystyle N\)-edik lépés végére az \(\displaystyle f_{k_N}\) függvényhez tartozó részletösszeg (tehát a \(\displaystyle \sum_n f_{k_N}(a_n)\) összeg a már meglévő \(\displaystyle a_n\)-eken) nagysága elég nagy legyen, mondjuk \(\displaystyle 10^{i_N}\)-nél nagyobb \(\displaystyle (2)\). Ha ezt elérjük, akkor a végeredményben kapott \(\displaystyle (a_n)\) sorozatra teljesülni fog, hogy minden \(\displaystyle k\)-ra a \(\displaystyle \sum_{n=1}^\infty f_k(a_n)\) sornak lesz egy végtelen divergens részletösszeg-sorozata, és így maga a sor is divergálni kényszerül. (Ugyanis minden \(\displaystyle (k,i)\) pozitív egész számpárhoz tartozik lépés, és a \(\displaystyle (k,1)\), \(\displaystyle (k,2)\), \(\displaystyle \dots\) párokkal elvégzett lépés egyre nagyobb nagyságú részletösszegeket biztosít a \(\displaystyle \sum_n f_k(a_n)\) sorba.) Marad annak belátása, hogy létezik \(\displaystyle (1)\) és \(\displaystyle (2)\)-nek megfelelő algoritmus.

Az algoritmus a következő. Az \(\displaystyle N\)-edik lépésben tekintjük \(\displaystyle k=k_N\)-et, \(\displaystyle K=10^{i_N}\)-et, \(\displaystyle r=r_N\)-et és \(\displaystyle f=f_k\)-t. Célunk a lépés során úgy folytatni az \(\displaystyle (a_n)\) sorozatot, hogy \(\displaystyle (1)\)-nek megfelelően \(\displaystyle r\)-nél kisebb részletösszegek képződjenek és hogy \(\displaystyle (2)\)-nek megfelelően az \(\displaystyle f\)-nek lépésünk előtti \(\displaystyle S\) részletösszegét legalább \(\displaystyle K\) nagyságúra növeljük.

Rövid kitérőben belátjuk, hogy létezik (nem feltétlen különböző) \(\displaystyle x,y,z\in (r;-r)\), melyre \(\displaystyle x+y+z=0\) és \(\displaystyle f(x)+f(y)+f(z)\neq 0\).

Tegyük fel ugyanis indirekt, hogy \(\displaystyle x+y+z=0\) esetén \(\displaystyle f(x)+f(y)+f(z)=0\) teljesül minden \(\displaystyle x,y,z\in (r;-r)\) esetén. Például \(\displaystyle x=y=z=0\) választásból \(\displaystyle f(0)=0\) adódik. Ekkor \(\displaystyle z=0\) helyettesítéssel \(\displaystyle f(-x)=-f(x)\) adódik, és így mivel mindig \(\displaystyle z=-x-y\), ezért \(\displaystyle f(x)+f(y)=f(x+y)\) következik minden \(\displaystyle x,y,x+y\in (-r;r)\) esetén. Ebből \(\displaystyle m\) szerinti teljes indukcióval \(\displaystyle m=1,2,\dots\)-ra \(\displaystyle f(mx)=mf(x)\) adódik (\(\displaystyle mx\in (-r;r)\) esetén): az állítás ugyanis \(\displaystyle m=1\)-re triviális, és ha \(\displaystyle m\)-re igaz, akkor \(\displaystyle (m+1)\)-re \(\displaystyle f(x)+f(mx)=f((m+1)x)\) miatt igazolt. Tehát pozitív egész \(\displaystyle p,q\)-ra

\(\displaystyle f\left(\frac{p}{q}x\right)=\frac{p}{q}\cdot q f\left(\frac1q x\right)=\frac{p}{q}f(x), \)

ha \(\displaystyle x,\frac pq x\in (-r;r)\). Ezért ha rögzítünk egy \(\displaystyle (0;r)\)-beli \(\displaystyle x\) racionális számot, akkor amennyiben \(\displaystyle c=\frac{f(x)}{x}\), annyiban bármely \(\displaystyle y\in (0;r)\) racionális számra \(\displaystyle f(y)=y/x\cdot f(x)=cy\), és \(\displaystyle f(-X)=-f(X)\) miatt \(\displaystyle f(y)=cy\), ha \(\displaystyle y\in(-r;0)\) racionális. Innen \(\displaystyle f(x)=cx\) minden \(\displaystyle (-r;r)\)-beli racionális \(\displaystyle x\)-re (a \(\displaystyle 0\)-t is beleértve). Mivel pedig \(\displaystyle f\) folytonos, így megadva bármely \(\displaystyle x\in (-r;r)\)-hez egy \(\displaystyle x_1,x_2,\dots\to x\) racionális számokból álló sorozatot (ilyet meg lehet adni, hisz az \(\displaystyle \frac{a}{b}\) alakú törtek közül van \(\displaystyle x\)-től \(\displaystyle \frac1{b}\)-nél közelebbre), kapjuk bármely \(\displaystyle x\in (-r;r)\)-re, hogy \(\displaystyle f(x)=\lim f(x_j)=\lim cx_j=cx\). De ekkor \(\displaystyle f(x)=cx\) minden \(\displaystyle x\in (-r;r)\)-re, ami ellentmond a feladat feltételének.

Visszatérve az \(\displaystyle N\)-edik lépés megadásához, válasszunk olyan \(\displaystyle x,y,z\in (-r;r)\)-et, melyre \(\displaystyle x+y+z=0\) és \(\displaystyle f(x)+f(y)+f(z)=s\neq 0\). Most pedig egyszerűen folytassuk az \(\displaystyle (a_n)\) sorozatot az alábbi sorozattal:

\(\displaystyle x,y,z,x,y,z,\dots,x,y,z, \)

ahol az \(\displaystyle x,y,z\) hármast \(\displaystyle L\)-szer ismételjük meg (\(\displaystyle L\) pozitív egész). Ekkor \(\displaystyle (1)\) teljesül, hisz \(\displaystyle \sum a_n\) új részletösszegei \(\displaystyle x,-z,0\) értékűek, és ezek mind \(\displaystyle r\)-nél kisebb nagyságúak. Emellett \(\displaystyle (2)\) is elérhető, hisz a \(\displaystyle \sum f(a_n)\) sor részletösszege \(\displaystyle S\)-ről \(\displaystyle S+L\cdot s\)-re változik: ha \(\displaystyle s>0\), elég nagy \(\displaystyle L\)-re \(\displaystyle S+Ls>K\), ha \(\displaystyle s<0\), elég nagy \(\displaystyle L\)-re \(\displaystyle S+Ls<-K\) garantálható.

Megadva minden \(\displaystyle N\)-re az \(\displaystyle N\)-edik lépését, beláttuk, hogy létezik \(\displaystyle (1)\)-nek és \(\displaystyle (2)\)-nek megfelelő algoritmus, és így megkapjuk a kívánt \(\displaystyle (a_n)\) sorozatot.

[1058] w2017-03-16 16:35:36

A.689. Legyen \(\displaystyle f_1,f_2,\dots\) folytonos \(\displaystyle \mathbb{R}\to\mathbb{R}\) függvényeknek egy végtelen sorozata úgy, hogy bármely \(\displaystyle k\) pozitív egészhez és bármely \(\displaystyle r>0\) és \(\displaystyle c\) valós számokhoz létezik olyan \(\displaystyle x\in (−r,r)\) szám, amelyre \(\displaystyle f_k(x)\neq cx\). Mutassuk meg, hogy létezik olyan \(\displaystyle a_1,a_2,\dots\) valós számsorozat, amelyre \(\displaystyle \sum_{n=1}^\infty a_n\) konvergens, de bármely \(\displaystyle k\) pozitív egész esetén \(\displaystyle \sum_{n=1}^\infty f_k(a_n)\) divergens.

Megjegyzések. Ez a feladat szerintem egy kifejezetten jó tanulópélda: jól mélyíti a konvergenciafogalmat (vegyítve a "végtelennel való visszaéléssel"), hisz a megoldás kulcsa, hogy lényegesen szabadabban kezdjük el megkonstruálni a sorozatunkat. Viszont könnyűnek mondanám, mert miután már kellőképpen szabadan gondolkozunk a feladaton, automatikus, hogy mit kell csinálni: az \(\displaystyle a_1,a_2,\dots\) sorozatot úgy megadni, hogy minden \(\displaystyle f_i\) sorozatban végtelen sok \(\displaystyle n\)-re legyen \(\displaystyle \left|\sum_{k\le n}f_i(a_k)\right|\) nagy, de eközben az \(\displaystyle (a_k)\) sorozat bármely \(\displaystyle r>0\)-ra egy idő után nem lép ki a \(\displaystyle (-r;r)\) intervallumból. (Sőt, nem nehéz meggondolni, hogy elegendő abban az esetben megoldani a feladatot, hogy \(\displaystyle f_1=f_2=\dots\), tehát ahol csak egy függvény van.)

[1057] w2017-03-14 16:54:18

Szerintem nem veszítünk semmit, ha a feladatot kicsit lényeglátóbban oldjuk meg (tehát a megoldást nem teszi egyszerűbbé, ha az alapötletet bináris számrendszeres konstrukcióval valósítjuk meg):

Legyenek a számaink \(\displaystyle x_1,x_2,\dots,x_n,y\) (most \(\displaystyle n+1\)-re oldjuk meg). Ekkor az \(\displaystyle x_i\) számok összegeinek listája (az üres összeg \(\displaystyle 0\)-val együtt)

\(\displaystyle s_1\le s_2\le s_3\le \dots\le s_{2^n}. \)

Ha az \(\displaystyle x_i\) számok mondjuk kettőhatványok (vagy \(\displaystyle \mathbb{Q}\) felett lineárisan független pozitív számok), akkor szigorú egyenlőtlenség is elérhető az összegek között, és minden összeg \(\displaystyle \ge 0\).

Ilyenkor az \(\displaystyle x_1,x_2,\dots,x_n,y\) számok összegeinek listája az előbbi \(\displaystyle \{0=s_1<\dots<s_{2^n}\}\) halmaz, és a halmaz \(\displaystyle +y\)-nal való eltoltja. Ezért \(\displaystyle y\) értékét \(\displaystyle +\infty\)-tól \(\displaystyle -\infty\) felé mozgatva, a pozitív összegek száma \(\displaystyle 2^{n+1}-1\)-ről \(\displaystyle 2^n-1\)-re csökken le. (Méghozzá \(\displaystyle (2^{n+1}-1)-k\) darab pozitív összeg van, ha \(\displaystyle s_k\le -y<s_{k+1}\).) Az \(\displaystyle x_i\) számokat \(\displaystyle -x_i\)-re cserélve pedig \(\displaystyle 0\) és \(\displaystyle 2^n\) közötti számú pozitív összeg állítható elő \(\displaystyle y\) mozgatásával.

Ezért minden \(\displaystyle 0\) és \(\displaystyle 2^{n+1}-1\) közötti egész szám lehet a pozitív összegek száma.

Előzmény: [1056] Róbert Gida, 2017-03-13 21:52:12
[1056] Róbert Gida2017-03-13 21:52:12

B.4854. indukció nélkül is megy:

legyen \(\displaystyle 0\le k <2^n\) tetszőleges egész, szeretnénk \(\displaystyle n\) valós számot megadni, hogy a belőlük képzett nemüres pozitív összegek száma k. Ekkor van \(\displaystyle k\)-nak ilyen felírása: \(\displaystyle k=\sum_{i=0}^{n-1}c_i*2^i\) (lényegében kettes számrendszerbeli felírása) , ahol \(\displaystyle c_i=0\) vagy \(\displaystyle 1\); legyen \(\displaystyle a_i=e_i*2^i\), ahol \(\displaystyle e_i=1\), ha \(\displaystyle c_i=1\) egyébként \(\displaystyle e_i=-1\) (az \(\displaystyle a\)-k indexe kezdödjön nullától). Legyen \(\displaystyle s\) egy tetszőleges nemüres összeg, ha \(\displaystyle a_t\) legnagyobb indexű tag benne, akkor triviálisan \(\displaystyle s>0\), ha \(\displaystyle c_t=1\); egyébként \(\displaystyle s<0\) (, ha \(\displaystyle c_t=0\)), rögzített \(\displaystyle t\)-re ez így \(\displaystyle c_t*2^t\) darab pozitív összeget jelent. Összesen pedig a pozitív összegek száma: \(\displaystyle \sum_{t=0}^{n-1}c_t*2^t=k\), ami kellett.

[1055] Róbert Gida2017-03-11 23:44:19

Igen könnyű feladat volt. A rengeteg hármas is árulkodó a feladatban.

A pontos feltétel amikor igaz a feladat állítása: \(\displaystyle a_1>3\) vagy \(\displaystyle a_1<-1\) (ez utóbbi esetben a sorozat tagjai negatívak). Egyébként a sorozatban ekkor \(\displaystyle a_n\) nem lehet 3 hatvány, ha \(\displaystyle n>1\): Ha \(\displaystyle a_1\) nem osztható \(\displaystyle 3\)-mal, akkor \(\displaystyle a_2\) sem, indukcióval \(\displaystyle a_n\) sem. Ha \(\displaystyle a_1\) osztható \(\displaystyle 3\)-mal, akkor meg minden tag 3-mal osztható, de 9-cel nem. Szig. monotonitásból meg \(\displaystyle |a_n|>3\), így egyik esetben sem lehet 3-hatvány (vagy annak ellentettje) az \(\displaystyle a_n\).

Hasonló, még egyszerűbb a bizonyítás a Fermat számokra: \(\displaystyle a_0=3\) és legyen: \(\displaystyle a_n=a_{n-1}^2-2a_{n-1}+2\), ekkor a közös prímosztó csak a 2 lehet, de a sorozat minden tagja páratlan, így a tagok relatív prímek, bármely prímosztója \(\displaystyle a_n\)-nek jó lesz. (itt persze \(\displaystyle a_n=2^{2^n}+1=F_n\)).

Előzmény: [1054] w, 2017-03-11 17:56:17
[1054] w2017-03-11 17:56:17

A feladat kitűzője lehet, túlbonyolította az A.691. feladatot: nem kell a \(\displaystyle c^2-1\) alakú kezdőérték.

A megoldás hátterében az áll, hogy az \(\displaystyle f(x)=x^3-3x^2+3\) polinomra \(\displaystyle f(3)=3\) teljesül. Ezért könnyű látni, hogy \(\displaystyle a_{n+1}\equiv 3\pmod{a_n^2}\), és így tovább, \(\displaystyle a_m\equiv3\pmod{a_n^2}\), ha \(\displaystyle m>n\).

Tehát ha \(\displaystyle p|a_m\) és \(\displaystyle p|a_n\) (\(\displaystyle m>n\)), akkor \(\displaystyle p|3\) is teljesül. Vagyis ha egy \(\displaystyle a_m\) számnak nincs olyan prímosztója, mely \(\displaystyle a_0,a_1,\dots,a_{m-1}\) egyikének sem osztója, akkor \(\displaystyle a_m\) csak a \(\displaystyle 3\) lehet prímosztója, vagyis \(\displaystyle a_m\) \(\displaystyle 3\)-hatvány.

A \(\displaystyle 3\)-hatvány \(\displaystyle a_m\) tagoknak pedig a \(\displaystyle 3\) lesz ez az \(\displaystyle a_0,\dots,a_{m-1}\)-et nem osztó prímosztója, hiszen ha van \(\displaystyle n<m\), melyre \(\displaystyle 3|a_n\), akkor \(\displaystyle a_m\equiv 3\pmod{a_n^2}\) miatt \(\displaystyle a_m\) nem osztható \(\displaystyle 9\)-cel, így \(\displaystyle a_m\le 3\). Viszont mivel \(\displaystyle a_0>3\), ezért a sorozat minden tagja \(\displaystyle 3\)-nál nagyobb, és ez ellentmondás.

[1053] w2017-02-14 19:30:25

A.578. Minden \(\displaystyle n\ge2\) egészre legyen \(\displaystyle P(n)\) az összes

\(\displaystyle \pm\sqrt1 \pm\sqrt2 \pm\sqrt3 \pm\ldots \pm\sqrt{n} \)

alakú kifejezés szorzata, ahol az egyes tagok előjelét tetszőlegesen megválaszthatjuk.

(a) Bizonyítsuk be, hogy \(\displaystyle P(n)\) pozitív egész.

(b) Bizonyítsuk be, hogy tetszőleges \(\displaystyle \varepsilon>0\)-hoz van olyan \(\displaystyle n_0\), hogy \(\displaystyle n>n_0\) esetén \(\displaystyle P(n)\) minden prímosztója kisebb, mint \(\displaystyle 2^{2^{\varepsilon n}}\).

—————————————————————————————

Megoldás. (a) Legyen \(\displaystyle f(x_1,x_2,\dots,x_k)\) egész együtthatós polinom, és vegyük az összes \(\displaystyle 2^k\) darab lehetséges előjelkombinációval a

\(\displaystyle \prod f(\pm x_1,\pm x_2,\dots,\pm x_k) \)

szorzatot. Azt állítjuk, hogy ez a szorzat \(\displaystyle F(x_1^2,x_2^2,\dots,x_k^2)\) alakú, ahol \(\displaystyle F\) egész együtthatós polinom. Ezt könnyű látni: azért lesz minden \(\displaystyle x_i\) változót tartalmazó tag kitevőjének foka páros, mert ha csak a \(\displaystyle 2^{k-1}\) darab \(\displaystyle +x_i\) előjelű tagot vesszük, azok szorzata \(\displaystyle A(\dots,x_i^2)+B(\dots,x_i^2)x_i\) alakú (ahol \(\displaystyle A,B\) is \(\displaystyle k\)-változós polinomok), míg ha a \(\displaystyle -x_i\) előjelű tagokat vesszük, azok szorzata kellőképp \(\displaystyle A(\dots,x_i^2)-B(\dots,x_i^2)x_i\) lesz, így a kettőt összeszorozva, egy polinomot kapunk \(\displaystyle x_i^2\)-ben.

Az \(\displaystyle f(x_1,x_2,\dots,x_n)=x_1+x_2+\dots+x_n\) polinomra alkalmazva ezt az állítást, kapjuk, hogy \(\displaystyle P(n)\) egész szám. Nyilván nem negatív. Marad belátni, hogy nem nulla. Ehhez felhasználunk egy segédtételt, melyet másutt bizonyítunk: ha \(\displaystyle n_1,n_2,\dots,n_k\) páronként különböző pozitív négyzetmentes számok, akkor \(\displaystyle a_1,a_2,\dots,a_k\) racionális számokra pontosan akkor teljesül

\(\displaystyle a_1\sqrt{n_1}+a_2\sqrt{n_2}+\dots+a_k\sqrt{n_k}=0, \)

hogyha \(\displaystyle a_1=a_2=\dots=a_k=0\) (vagyis a négyzetgyökök \(\displaystyle \mathbb{Q}\) felett lineárisan függetlenek). Ebből már adódik, hogy

\(\displaystyle \pm \sqrt{1}\pm \sqrt{2}\pm\dots\pm\sqrt{n} \)

sosem \(\displaystyle 0\) (az is adódik, hogy irracionális), mert felírható négyzetmentesek gyökeinek lineáris kombinációjaként, melyben a \(\displaystyle \sqrt{p}\) nem nulla (hanem \(\displaystyle \pm 1\)) együtthatóval rendelkezik. Itt \(\displaystyle p\) olyan prím, melyre \(\displaystyle \frac{n}{2}<p\le n\); ilyen a Csebisev-tétel szerint létezik.

(b) Legyen \(\displaystyle k=\pi(n)\) az \(\displaystyle [1;n]\) intervallumbeli prímszámok száma, és az \(\displaystyle [1;n]\)-beli prímek \(\displaystyle p_1,p_2,\dots,p_k\). Világos, hogy bármely \(\displaystyle E\) előjelválasztáshoz létezik olyan \(\displaystyle f_E(x_1,\dots,x_k)\) egész együtthatós polinom, melyre

\(\displaystyle f_E(\sqrt{p_1},\sqrt{p_2},\dots,\sqrt{p_k})=\pm \sqrt{1}\pm \sqrt{2}\pm \dots\pm \sqrt{n}. \)

Ekkor, mint beláttuk,

\(\displaystyle P_E=\prod f(\pm \sqrt{p_1},\dots,\pm\sqrt{p_k})\in\mathbb{Z}. \)

Most vegyük azt a \(\displaystyle 2^{n-k}\) darab \(\displaystyle f_E\) polinomot, melyben az összes \(\displaystyle \sqrt{p_i}\) pozitív előjellel szerepel a definíció jobb oldalán. Ekkor

\(\displaystyle P(n)=\prod_E P_E. \)

Mivel \(\displaystyle P_E\) minden tényezője \(\displaystyle \pm \sqrt{1}\pm\dots\pm\sqrt{n}\) alakú, ezért a tényezőinek nagysága kisebb, mint \(\displaystyle n\sqrt{n}<n^2\), vagyis

\(\displaystyle |P_E|\le (n^2)^{2^k}. \)

Ezt, és a Prímszámtételt felhasználva, mely szerint elég nagy \(\displaystyle n\)-re \(\displaystyle k<2\cdot \frac{n}{\log n}\), következik, hogy elég nagy \(\displaystyle n\)-re \(\displaystyle |P_E|<2^{2^{\varepsilon n}}\) minden \(\displaystyle E\)-re, ha \(\displaystyle \varepsilon>0\) előre rögzített szám. Ebből következik, hogy ilyenkor \(\displaystyle P(n)\) minden prímtényezője \(\displaystyle 2^{2^{\varepsilon n}}\)-nél kisebb lesz.

Megjegyzés. Természetesen általánosan is igaz a \(\displaystyle P(n)\neq 0\) belátásához szükséges megjegyzés. Vagyis legyenek \(\displaystyle (n_1,k_1)\), \(\displaystyle (n_2,k_2)\), \(\displaystyle \dots\), \(\displaystyle (n_r,k_r)\) olyan páronként különböző pozitív egész számpárok, melyekben \(\displaystyle k_i\ge 2\) és \(\displaystyle n_i\) minden prímtényezőjének kitevője kisebb, mint \(\displaystyle k_i\). Ekkor ha \(\displaystyle a_1,a_2,\dots,a_r\) racionálisokra

\(\displaystyle a_1\root {k_1}\of {n_1}+\dots+a_r\root {k_r}\of {n_r}=0, \)

akkor \(\displaystyle a_1=a_2=\dots=a_r=0\). (Megpróbálom majd valamikor leírni a bizonyítást.)

Előzmény: [758] Fálesz Mihály, 2013-02-26 09:08:35
[1052] w2016-11-27 20:52:25

Szívesen! :) Nem, nem én írtam, csak régebben írtam egy-két Wikipédia-cikkre kiegészítést, amikor voltam annyira fiatal, hogy nagyon büszke legyek magamra érte.

(Ha ironizálni akartál ezzel, azzal magyarázkodnék, hogy jónak tartom azt az elvet, hogy nehezebb okfejtéseket is elérhetővé teszünk kevesebb előismerettel rendelkező olvasók számára. Én például nyolcadikosan nagyon sokat profitáltam régi Kömal-megoldások linkjeiből, és bár előbb-utóbb megtanultam, hogy Google segít, ha nem értek valamit, kezdetben ezek a linkek megérték azt az egy-két percet, amibe került az írónak őket belerakni a megoldásába.)

Előzmény: [1051] csábos, 2016-11-27 20:07:51
[1051] csábos2016-11-27 20:07:51

Köszönjük a linket a gyöktényezőkhöz a wikipédián. Ma is tanultunk valamit. Te írtad?

Előzmény: [1050] w, 2016-11-27 14:31:27
[1050] w2016-11-27 14:31:27

Szeretnék az A.675. feladatról néhány szót ejteni.

\(\displaystyle (p(x))^3+q(x^2)=r(x)\)\(\displaystyle (1) \)

Szerintem ez egy technikai feladat. Kevés lényegi ötlet van: [1] olyan lesz a háttérben, hogy \(\displaystyle n\) darab gyöktényező \(\displaystyle \le 2^n\) módon osztható szét, [2] az összefüggésben \(\displaystyle p\) adható meg nehezen, így \(\displaystyle q\)-t érdemes kiejteni (gondoljunk erre akár úgy, mint egy diofantoszi egyenletre). Az a nehéz, hogy helyesen alkalmazzuk ezeket az ötleteket.

Nagyon könnyű erre elvi hibás megoldást adni. ITT is található néhány hibás próbálkozás. A hivatalos megoldás alapos átgondolása kell a \(\displaystyle 2^n\)-es korlátoz.

A rossz megoldások, amikről tudok, tipikusan a következő lépésnél hibáznak. Eljutunk egy \(\displaystyle f(x)g(x)=A(x)\) alakú egyenlethez, ahol \(\displaystyle A(x)\) fix, \(\displaystyle m\) fokú polinom; itt az [1] ötlet szerint \(\displaystyle f,g\) között \(\displaystyle \le 2^m\) módon osztható ki \(\displaystyle A\)-nak az \(\displaystyle m\) darab gyöktényezője. A hiba ott jelentkezik, hogy a megoldó azt állítja, hogy minden lehetséges gyöktényező-szétosztáshoz csakis egy \(\displaystyle f,g\) pár tartozik, vagy pedig felismeri annak lehetőségét, hogy \(\displaystyle (f,g)\) mellett \(\displaystyle (f\lambda,g/\lambda)\) is működhet (és akár végtelen sok lehetőséget adhatna), de ezt a lehetőséget hibásan zárja ki (valamilyen rossz együttható-vizsgálattal).

[1049] w2016-07-06 05:46:52

Megjegyzés: ezt a "négy háromszög tételét" a nemzetközi matekozgatásokban Miquel-tételnek szokás nevezni [ejtsd: Mikel]. (Jó, ha egységesek az elnevezések.)

B.4800.-ra még egy érdekes megközelítés (talán ezt a megoldást javasoltam):

Elég belátni, hogy &tex;\displaystyle BCKL&xet; húrnégyszög (onnan hatványpont miatt kész). Ha belegondolunk, &tex;\displaystyle ABC&xet;-t rögzítve, csupán a &tex;\displaystyle KL&xet; egyenes irányától függ ez az állítás.

Vagyis elég belátni, hogy van &tex;\displaystyle K'\in AB&xet;, &tex;\displaystyle L'\in AC&xet;, amire &tex;\displaystyle K'L'&xet; és &tex;\displaystyle KL&xet; párhuzamos, és &tex;\displaystyle BCK'L'&xet; húrnégyszög.

Ehhez elég venni a &tex;\displaystyle B&xet;-magasság &tex;\displaystyle L'&xet; és a &tex;\displaystyle C&xet;-magasság &tex;\displaystyle K'&xet; talppontját. Ugyebár ha &tex;\displaystyle H&xet; az &tex;\displaystyle ABC&xet; magasságpontja, úgy &tex;\displaystyle AK'L'&xet; kör éppen &tex;\displaystyle AH&xet; Thalesz-köre. Mivel e kör középpontja &tex;\displaystyle AT&xet; egyenesen van, így &tex;\displaystyle A&xet;-ból a &tex;\displaystyle T&xet; körüli &tex;\displaystyle AKL&xet; körbe nagyítható. Így &tex;\displaystyle K'L'&xet; és &tex;\displaystyle KL&xet; is párhuzamos.

Most pedig &tex;\displaystyle BCK'L'&xet; éppen a &tex;\displaystyle BC&xet; szakasz Thalesz-köre.

Előzmény: [1048] Lpont, 2016-07-05 20:44:11
[1048] Lpont2016-07-05 20:44:11

A B.4800. feladat egy másik (kevesebb körrel) lehetséges megoldása:

Diszkusszió nélkül, a honlapon közölt megoldás jelöléseit megtartva

1. Belátjuk, hogy ACB=AKL (szögeket jelölök ACB-vel és AKL-lel).

Az ATC derékszögű háromszögben TAC=90-ACT=90-ACB, valamint AT=TL=r miatt az ATL egyenlőszárú háromszög szárszöge 180-2(90-ACT)=2ACT=2ACB. k körben az AL (ábra szerinti rövidebb) ívhez tartozó AKL kerületi szög fele az ATL középponti szögnek, azaz nagysága pont ACB.

2. Jelölje X a BC és KL egyenesek metszéspontját( X létezik a származtatás miatt, hiszen K és L a BC egyenes különböző partján található). Megmutatjuk, hogy MX egyenese azonos MA egyenesével.

2.a A négy háromszög tételét alkalmazva (lásd pl.: Reiman István: Geometria és határterületei c. munkáját), az ABC, AKL, BKX és CLX háromszögek köré írt körei egy ponton mennek át, ami nem más, mint az M pont. Így CLXM és XBKM négyszögek húrnégyszögek. Kapjuk, hogy LCX=ACB=LMX, másrészt XMB=XKB=AKL, de 1. miatt XMB=XML vagyis MX felezi LMB-t.

2.b k körben a kisebb AL ívhez tartozó kerületi szögek egyenlőek, tehát AKL=AML, hasonlóan c körben AB ívhez tartozó ACB és AMB kerületi szögek is megegyeznek, innen ACB=AKL miatt AMB=AML, ami azt jelenti, hogy AM szintén belső szögfelezője LMB-nek, ilyen szögfelező csak egy lehet, AM egyenese azonos XM egyenesével, AM átmegy BC és KL X metszéspontján.

Ezt akartuk bizonyítani.

[1047] Graffalo2016-07-03 20:12:56

Elnézést az előbbiért, a B.4793. b) végét elszámoltam, azért nem egyezett az eredmény.

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]