Fórum: Lejárt határidejű KÖMAL feladatokról

Hasonlítsuk össze: A.542 és B.4525

Szerintem ezek ugyanolyan nehezek. (Igaz, tavaly nem volt 6 pontos B-jelű feladat.)

Senki? Fontos kiindulási adat, hogy az a₁, a₂, a₃, a₄ sorozat és az A₁, A₂, A₃, A₄ sorozat azonosan rendezett, enélkül talán nem is igaz az egyenlőtlenségem (?).

Bocs, elírtam valóban: A.586 (nem egy aktív feladatra gondolok :).

A.588 (?) könnyítés:

Igazoljuk, hogy , ahol a két négyszög oldalai azonosan rendezettek.

De a mostani B.4525 is mehetett volna az A-ba. Nehéz konstrukciót találni. A következő pl. szerintem jó:

Rekurzív. Tfh. 2n-1 3-szög lefedi az (n-1) felvett belső pontú 3-szöget. Az n-edik P_n ponton át ||-t húztunk T oldalával (p_n), a levágott 3-szög lefedhető (2n-1)-gyel. A maradó réteget úgy fedjük le, hogy meghosszabbítjuk a lefedők oldalait T oldaláig. A kapott háromszögek ha tartalmazzák P_n-et, húzzunk P_n-nel még két T-oldalirányban ||-t. A legnagyobb kétféle ilyet vegyük, mint új háromszög. Ez jó is lesz, mert lefedik a p_n T-be eső részét a generálás módja miatt, és így a 3-szögek állásából lefedik az új "réteget".

Az ellenpélda n db pont egy T oldalával nem || egyenesen, ki-ki lássa be.

Egyetértek, ingadozó nehézségű A-jelű problémák vannak. Szerintem azt a feladatot azért tűzték ki, hogy kiszűrjék azokat, akik bemisztifikálják az A-feladatokat. Egyébként meg nem természetes, hogy most már négy olyan feladat is volt, melyre egyáltalán nem született megoldás. (Igaz, a mezőny sem olyan erős.) Sok olyan B-jelű 6 pontos feladatot látni, amely bőven méltó lenne az A-pontversenybe: B.4510, B.4511, B.4520, B.4521.

Tudja valaki miért volt A.581 "A" feladat? Nekem a "Projektív geometria" téma [41] végén is leírt módon elég egyszerűnek tűnt.

A B4511-hez a hivatalosnál valamivel rövidebb megoldás:

Először azt látom be, hogy PUVT egy körön vannak: TP V-ből és U-ból is a KP szakasz k körre való irányított látószögéből látszik: PUT=PUK=PVL=PVT (lásd ábra, irányított nyilak)

Aztán azt látom be, hogy PU*LT is egy körön van (U* UL és K metszése): PL T-ből és U*-ból is PV szakasz PUVT körre való irányítot szögéből látszik: PTL=PTV=PUV=PU*U=PU*L (lásd ábra, dupla íves szögek)

L-ből egy olyan inverzió, ami k-t fixen hagyja UK-ból U*PL-t csinál, de UK-nak is része T, U*PL-nek is, tehát T csak UK és U*PL valamelyik metszéspontján lehet, ami meg eleme a merőleges körnek is.

A.569, A.571, A.573, A.574, A.580

Hasonlítsuk össze ezzel.

"hogy ha g polinom fokszámánál több megoldása van" ez igaz, de itt mennyi is az f-f* fokszáma? Tipikusan legalább p, azaz nem is lehet neked több megoldásod.

Miért lenne g minden együtthatója p-vel osztható?

Az világos, egy korábbi hozzászólásomra utaltam, ami szerint igazoltam, hogy g fokszáma nem lehet p-nél kisebb. Nos, átgondoltam, és találtam benne elvi hibát. Azonban még áll az az ellentmondás, hogy g tetszőleges 0 konstans tagú lehet-e vagy g minden együtthatója p-vel osztható-e.

A "megoldásokon" nem egész számokat, hanem mod p maradékosztályokat kell érteni.

Az f^*(x)-f(x)0 (mod p) kongruenciának csak p különböző mod p maradékosztály megoldása.

Még mindig vannak az A582-vel kételyeim. Most szakirodalmat is találtam, ami azt állítja, hogy ha g polinom fokszámánál több megoldása van a g(x)0 (mod p) kongruenciának, akkor annak minden együtthatója p-vel osztható. Ugyebár Kis-Fermat szerint p|f^*-f.

Ha találtok hibát, szóljatok.

A. 582. Legyen p rögzített pozitív prímszám. Tetszőleges f(x) egész együtthatós polinomra legyen

f^*(x)=f((1+x)p-1).

Határozzuk meg mindazokat a g egész együtthatós polinomokat, amelyekre teljesül a következő: minden pozitív egész n-hez van olyan f egész együtthatós polinom, amelyre a g-(f-f^*) polinom n-nél kisebb fokú együtthatói mind oszthatók pⁿ-nel.

Javasolta: Maga Péter (Budapest)

Megoldás. Először is látszik, hogy g-(f-f^*) konstans tagja g konstans tagjával egyezik meg. Az egyetlen olyan egész szám, amely tetszőlegesen nagy számmal osztható, a nulla. Tehát g konstans tagja zérus.

Konstruálni fogunk minden ilyen polinomhoz egy-egy megfelelő f polinomot.

Vezessük be a c_j(h) jelölést: ez a h polinom j fokú együtthatója lesz. A h-->h^* képzés v-szer egymás utáni elvégeztekor kapott polinom legyen h^(v) (v>0 egész).

Lemma. Legyen h egész együtthatós polinom úgy, hogy p^m|c_j(h), ha j=0,1,...,k-1, illetve p^m-1|c_k(h), de p^m³c_k(h) (m>0 egész). Ekkor p^m|c_i(h^*) (i=0,1,2,...,k).

Bizonyítás. Az állítás i=0,1,2,...,k-1 esetén nyilvánvaló. Mivel a binomiális tétel szerint

,

ezért a h^* polinom képzelt alakjában c_k(h^*) a h polinom k-nál kisebb fokú együtthatóinak többszöröseiből tevődik össze, és még hozzáadódik p^.c_k(h) többszöröse. Így p^m|c_k(h^*).

Alkalmazzuk a Lemmát h=g, k=1, m=1-re! Kapjuk, hogy p|c₁(g⁽¹⁾), mert c₀(g)=c₀(g^(v))=0. Tegyük fel, hogy valamely k-ra p|c_j(g^(k-1)) minden j=0,1,2,…,k-1 esetén, ekkor a Lemma szerint p|c_k(g^(k)). A teljes indukció elveinek megfelelően kapjuk, hogy ez bármely k-ra igaz lesz, így például p|c_i(g⁽ⁿ⁾) minden i=0,1,…,n –re.

Ezután alkalmazzuk a Lemmát h=g⁽ⁿ⁾, k=1, m=2-re: p²|c₁(g⁽ⁿ⁺¹⁾). Az előzőhöz hasonlóan ismét folytathatunk k szerinti indukciót, amiből p²|c_j(g^(n+k)), ha j=0,1,…,k. Ennek eredményeként p²|c_i(g⁽²ⁿ⁾) (i=0,1,…,n).

Tehát m szerinti teljes indukcióval, lépésenként k szerinti indukciót alkalmazva adódik, hogy

pⁿ|c_i(g⁽ⁿ²⁾) (i=0,1,…,n).

Válasszuk meg f polinomot úgy, hogy

f=g+g⁽¹⁾+g⁽²⁾+…+g^(n2-1).

Ekkor

f^*=g⁽¹⁾+g⁽²⁾+g⁽³⁾+…+g⁽ⁿ²⁾, azaz

g-(f-f^*)=g-(g-g⁽ⁿ²⁾)=g⁽ⁿ²⁾, és ez teljesíti a feltételeket.

Tehát pontosan azok a g polinomok felelnek meg, melyeknek konstans tagjuk nulla.

Szép feladat, gratulálok! :-)

Aminek a konstans tagja 0.

És ez nekünk elég is.

Tehát minden polinom megfelelő?

g^(l).

Tehát ha g konstans tagja 0, akkor g^(l) n-nél kisebb fokú együtthatói pⁿ-nel oszthatók. Legyen f=g⁽⁰⁾+g⁽¹⁾+...+g^(l-1). Mennyi ekkor g-(f-f^*)?

m=1, k=1: cf_0,1(g^*)0 (mod p¹)

Tehát már m=2-re működik:

cf_0,1(g⁽²⁾)0 (mod p²).

Indukcióval

cf_0,1(g^(k))0 (mod p^k).

(1)-ből kiindulva, m=2-re áttérve

cf_0,1,2(g⁽²⁾)0 (mod p¹),

így m, és "ezen belül" k szerinti indukcióval

cf_0,1,...,m-1(g^(m+k))0 (mod p^k).

Az látszik ebből, hogy a minimális szám, melyre n-nél kisebb fokú együtthatói biztos pⁿ-nel oszthatók, az =2n.

Megpróbálom összefoglalni. Ha f olyan, hogy a konstans tagja 0, és benne a k-nál kisebb fokú együtthatók mind oszthatók p^m-nel, és a pontosan k fokú együttható osztható p^m-1-nel, akkor f^*-ban a legfeljebb k fokú együtthatók mind oszthatók p^m-nel.

Most azt bizonyítsd be, hogy ha g konstans tagja 0, akkor (rögzített n mellett) ha elég sokszor alkalmazzuk rá a *-ot, egy olyan polinomot kapunk, amelyben az n-nél kisebb fokú együtthatók pⁿ-nel oszthatók. Tehát mondjuk legyen g⁽⁰⁾=g, g⁽¹⁾=g^*, általában g^(k)=(g^(k-1))^*. Bizonyítsd be, hogy ha g konstans tagja 0, akkor elég nagy N-re (n előre rögzített), g^(N) n-nél kisebb fokú együtthatói pⁿ-nel oszthatók.

Jelölje cf_i(h) az h polinom i fokú együtthatóját.

Nyilván h=f^* és i=1,2,3,...,k-1 esetén ez p^m-mel osztható. Tekintsük cf_k(f^*)-t. A k-adfokú tagot a kisebb fokú tagok hozzák létre (0 mod p^m), és még hozzáadódik az együtthatóhoz a_kp, ami ugyanezt teljesíti. cf_k+1(f^*) következik. Korábbi fokú tagok, a_k is benne van, de a_k+1p miatt semmit sem tudunk már erről (és nem is kell róla) mondani.

Érdekes lépés. Végtelen leszállással próbáltam megközelíteni, de túlegyszerűsítettem a dolgot. Úgy látszik, itt is ez lesz.

Az f(x) polinom elég, ha n-edfokú (talán pár nulla "együtthatóval").

Tegyük fel, hogy f(x)=a_Nx^N+...+a_kx^k+...+a₁x, ahol a₁,...,a_k-1 mind oszthatók p^m-nel, a_k pedig nem osztható p^m-nel, de osztható p^m-1-gyel. Mit tudunk mondani f^* kis fokú együtthatóiról a p^m-nel való oszthatóságot illetően?