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

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?

B.4521-re első körben F₁, F₂, F₃, M C egy körön vannak: ez trivi, kb szögszámolgatás, innét szerintem legegyszerűbb a C-re való inverzió, ekkor a két kis kör két párhuzamos egyenes lesz, a nagy kör meg ezeket érinti belülről, az érintő kör meg vele egyenlő sugarú lesz, és érinti ezeket. Innét minimális számolással (a C-n átmenő kör egyenes lesz) adódik az állítás.

Pontosítás: a konstans-együttható nulla.

B.4520-hoz nem kell Titu-lemma, van könnyebb megoldás is. Legyen p:=(y+z)/2, q:=(z+x)/2, r:=(x+y)/2. Ha ezekkel számolunk, a közepek közötti becslések nem lesznek olyan élesek. Átírva a feladatbeli kifejezést:

Ezt háromszor AM-GM-mel becsüljük, ekkor a, b, c háromszögoldalak mellett teljesül az összefüggés. (További vizsgálat a hivatalos megoldás szerint.)

B.4515 megoldása.

Tekinthetjük a második dobást (1+2+3+4+5+6)/6=3,5-nek. Ugyanis a nyeremény várható értéke még egy dobás esetén ennek felel meg. Így elég csak az első dobással foglalkozni, illetve annak következményeivel. Feltehető még, hogy a játékos stratégikusan játszik.

Legyen az első dobás eredménye "a", a zseton ára "x". A játékos elméletileg választhat: 100a-x, vagy 350a-2x legyen a nyeresége. Akkor dob másodszor, ha 100a-x<350a-2x, azaz x/250<a.

Innen próbálgatással kapható, hogy 500<x<750. Tehát összességében a következő egyenletet elég megoldani:

100(1+2)-2x+350(3+4+5+6)-8x=0

6600=10x, x=660.

Ha a zseton ára 660 pénzegység, az üzemeltetőnek pont nulla a várható nyeresége. Tehát ennél nagyobb árú zsetonok kellenek.

-

Megjegyzés Róbert Gidának: a pénzegységet én választom meg :P (a játékot nyilván forintra találták ki) amúgy ha szigorúan vesszük igazad van :-) Azért nem így írtam a beküldött dolgozatban.

g-nek nincs konstansegyütthatója, így osztható x-szel. Mellesleg, minden értéke p-vel osztható.

Először bizonyítsuk be, hogy f és f^* konstans tagja ugyanaz. Milyen szükséges feltételt kapunk ebből g-re?

Fent van már a megoldás. Bár attól elég távol van, arról sokat nem ír, hogy hogyan jött ki a megoldás. Javítóként ilyenre 0 pontot adtam volna másolás gyanúja miatt.

Egyébként az általános esetben is mindig van optimális tiszta stratégia, azaz olyan, hogy minden x-re p_x az nulla vagy egy. (Ezt könnyű látni).

Forintot meg ne írj, a feladat nem beszélt forintról, a megoldás sem.