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

Valaki le tudná írni az A585 feladat megoldását? Segítségét előre is köszönöm. BERTALAN ZOLTÁN.

IMC 2013/1. nap 4. feladat

A társszerző: Victoria Powers.

Szerintem a quartic.pdf jelenleg itt található:

http://www.math.uiuc.edu/~reznick/quartic.pdf

(Bruce Reznick: Notes towards a constructive proof of Hilbert's Theorem on ternary quartics)

Igazad van, nem tudok olvasni, a "two" valahogy lemaradt:

Iwaniec showed that there are infinitely many numbers of the form &tex;\displaystyle n^2+1&xet; with at most two prime factors.

Megoldásvázlat az A.643.-ra.

1. lemma: [triviális] Ha &tex;\displaystyle p&xet; páratlan prím, és &tex;\displaystyle p|n^2+1&xet; valamely &tex;\displaystyle n&xet;-re, akkor alkalmas &tex;\displaystyle 0<a(p)<\frac p2&xet; pozitív egészre pontosan azokra az &tex;\displaystyle n&xet; pozitív egészekre lesz &tex;\displaystyle p|n^2+1&xet;, melyekre

&tex;\displaystyle n\in\{a,a+p,a+2p,\dots\}\cup \{p-a,2p-a,3p-a,\dots\}.&xet;

Itt még jegyezzük meg, hogy automatikusan &tex;\displaystyle P(a)=P(p-a)=p&xet;.

2. lemma: Tetszőleges &tex;\displaystyle x&xet; tetszőleges pozitív egészre

&tex;\displaystyle P(x^2+x+1)=\max\{P(x),P(x+1)\},&xet;

&tex;\displaystyle P(2x^2)=\max\{P(2x-1),P(2x+1)\}.&xet;

Bizonyítás: alkalmazzuk az &tex;\displaystyle (A,B)=(x+1,x)&xet;, illetve &tex;\displaystyle (A,B)=(2x+1,2x-1)&xet; helyettesítéseket az alábbi azonosságba.

&tex;\displaystyle (A^2+1)(B^2+1)=(AB)^2+A^2+B^2+1=(AB+1)^2+(A-B)^2&xet;

3. lemma: Végtelen sok &tex;\displaystyle n&xet; pozitív egész számra &tex;\displaystyle P(2n-1)\le P(2n+1)&xet; és &tex;\displaystyle P(2n+3)\le P(2n+1)&xet;.

Bizonyítás: Ha &tex;\displaystyle p_n=P(2n+1)&xet;, akkor amennyiben csak véges sok &tex;\displaystyle n&xet;-re lesz &tex;\displaystyle p_{n-1}\le p_n\ge p_{n+1}&xet;, fennáll, hogy elég nagy &tex;\displaystyle k&xet;-ra &tex;\displaystyle p_k<p_{k+1}<p_{k+2}<\dots&xet;. Mivel a &tex;\displaystyle P&xet; függvény értékkészlete a &tex;\displaystyle 2&xet; és a &tex;\displaystyle 4\ell+1&xet; alakú prímek, ezért innen &tex;\displaystyle \lim \frac{p_k}k=4&xet;, ami ellentmond annak, hogy a 2. lemma szerint

&tex;\displaystyle p_{\frac{a^2+a}2}=P(a^2+a+1)\le (a+1)^2+1&xet;

bármely &tex;\displaystyle a&xet; pozitív egészre.

&tex;\displaystyle &xet;

Indirekt feltesszük, hogy véges sok számnégyes választható ki, legyen &tex;\displaystyle N&xet; nagyobb, mint ezen számnégyesek összes tagja; belátjuk, hogy van &tex;\displaystyle N&xet; feletti tagú számnégyes.

Válasszunk egy olyan &tex;\displaystyle n>N&xet; olyan pozitív egészt (ha zavarnának a nagyságviszonyok, még &tex;\displaystyle n>10^5&xet; is legyen), amelyre &tex;\displaystyle P(2n-1)\le P(2n+1)\ge P(2n+3)&xet; (3. lemma). Ekkor a 2. lemma szerint fennáll, hogy

&tex;\displaystyle P(2n^2)=P(2(n+1)^2)=P(2n+1)=:p.&xet;

Miközben &tex;\displaystyle 2n+1<2n^2<2(n+1)^2&xet;. Dehát az 1. lemma szerint ott az az &tex;\displaystyle a(p)&xet; és az a &tex;\displaystyle p-a(p)&xet; adhatna még egyet: nem engedhetjük meg ezt a galádságot, így &tex;\displaystyle 2n+1=a(p)&xet; és &tex;\displaystyle p-a(p)=2n^2&xet; kell, szó ami szó, &tex;\displaystyle p=2n^2+2n+1&xet;, azaz &tex;\displaystyle 2p=(2n+1)^2+1&xet;.

Hát ez nem ellentmondás, de ha &tex;\displaystyle P(2n)\le P(2n+1)&xet; vagy &tex;\displaystyle P(2n+2)\le P(2n+1)&xet;, akkor pl. az első esetben a 2. lemma szerint &tex;\displaystyle P(4n^2+2n+1)=\max\{P(2n),P(2n+1)\}=P(2n+1)=p&xet; lesz, és ezért &tex;\displaystyle \{a<b<c<d\}=\{2n+1<2n^2<2(n+1)^2<4n^2+2n+1\}&xet; választással ellentmondást kapunk. Marad, hogy

&tex;\displaystyle P(2n)>P(2n+1)\ge P(2n-1),\quad P(2n+2)>P(2n+1)\ge P(2n+3).&xet;

Most azt kaptuk, hogy &tex;\displaystyle P(2n)&xet; nagyobb a &tex;\displaystyle P(2n-1),P(2n+1)&xet; mennyiségeknél és &tex;\displaystyle P(2n+2)>P(2n+1),P(2n+3)&xet;, s így a 2. lemmából

&tex;\displaystyle P(2n)=P(4n^2-2n+1)=P(4n^2+2n+1)=:q,&xet;

&tex;\displaystyle P(2n+2)=P((2n+2)(2n+1)+1)=P((2n+2)(2n+3)+1)=:q'&xet;

adódik. Az 1. lemma csak akkor nem nyugtat meg minket, hogyha &tex;\displaystyle a(q)=2n&xet; és &tex;\displaystyle q-a(q)=4n^2-2n+1&xet;, vagyis &tex;\displaystyle q=(2n)^2+1&xet;. Meg aztán ha &tex;\displaystyle q'=(2n+2)^2+1&xet;.

&tex;\displaystyle &xet;

A kegyelemdöfést modulo &tex;\displaystyle 5&xet; fogjuk megtenni, hisz mivel &tex;\displaystyle p,q,q'&xet; sem lehet &tex;\displaystyle 5&xet;, így

&tex;\displaystyle (2n)^2+1,\quad (2n+1)^2+1,\quad (2n+2)^2+1&xet;

sem osztható &tex;\displaystyle 5&xet;-tel, amiből &tex;\displaystyle 2n,2n+1,2n+2&xet; rendre &tex;\displaystyle -1,0,1&xet; modulo &tex;\displaystyle 5&xet;. Visszaidézve &tex;\displaystyle q&xet;-t, látjuk, hogy &tex;\displaystyle q=(2n)^2+1\equiv 2&xet; mod &tex;\displaystyle 5&xet;, és hogy &tex;\displaystyle 2n\equiv -1&xet; mod &tex;\displaystyle 5&xet;. Tudjuk, hogy &tex;\displaystyle a(q)=2n&xet;.

Tekintsük még a &tex;\displaystyle d=a(q)+2q&xet; számot, ő lesz A negyedik. Ő páros, mert &tex;\displaystyle a(q)=2n&xet; páros. És még &tex;\displaystyle d\equiv -1+2\cdot 2=3&xet; modulo &tex;\displaystyle 5&xet;, ahonnan &tex;\displaystyle 5|d^2+1&xet;. Vagyis &tex;\displaystyle d^2+1&xet; osztható a páronként különböző &tex;\displaystyle 2<5<q&xet; prímekkel, így a szorzatukkal is osztható, &tex;\displaystyle 10q|d^2+1&xet;.

A &tex;\displaystyle d^2+1&xet; szám összes többi osztója a &tex;\displaystyle \frac{d^2+1}{10q}&xet; szám osztója. Mivelhogy erre a számra

&tex;\displaystyle \frac{d^2+1}{10q}=\frac{(a(q)+2q)^2+1}{10q}<\frac{(3q)^2+1}{10q}<\frac{9q^2+q^2}{10q}=q,&xet;

így nem lehet neki &tex;\displaystyle q&xet;-nál nagyobb prímosztója. Ez maga után vonja, hogy &tex;\displaystyle P(d)=q&xet;.

Ami ellentmondás az indirekt feltevéssel, így ezzel a feladat állítása bizonyítást nyert.

"A643-ra létezik olyan megoldás, amelyik nem azt használja ki, hogy végtelen sok &tex;\displaystyle n^2+1&xet; alakú prím létezik?"

Nem használhatja, hiszen ez tudtommal még megoldatlan sejtés.

Két tagra nem olyan nehéz: végtelen sok poz. egész a,b-re: a<b, P(a)=P(b). Ismeretes, hogy végtelen sok p=4k+1 alakú prím van, ezekre &tex;\displaystyle x^2+1 \equiv 0 \mod p&xet; megoldható, legyen &tex;\displaystyle r&xet; a legkisebb nemnegatív egész megoldás, ekkor r!=p-r (mert p ptlan), és &tex;\displaystyle r^2+1&xet; és &tex;\displaystyle (p-r)^2+1&xet; oszthatóak p-vel, de &tex;\displaystyle p^2&xet;-nél kisebbek, így a legnagyobb prímosztójuk p, azaz P(r)=P(p-r)=p, ami kellett (r>0 és p-r>0 triviálisan).

ha jól látom, akkor a jobb oldal is maximális ebben az esetben, így nem biztos, hogy jó lesz amit az előzőben írtam

Legyenek tehát rendre az adott x-ek sinalfa1,2...6 (elnézést, a TeX tanfolyamot még nem végeztem el, igyekszem úgy írni hogy minél kevésbé legyen csúnya). Ekkor a bal oldalon az adott szögek koszinuszának abszolútértékének háromszorosát kapjuk, a jobb oldalon pedig a gyök alatt álló kifejezéseket. A bal oldal akkor vesz fel maximumot, ha az összes koszinusz értéke 1, ekkor minden szög egyenlő k2pi-vel, ekkor van egyenlőség is, mivel a bal oldal 3+3+3+3+3, a jobb oldal pedig 5*gyök9. Mivel egyenlőség akkor áll fenn, ha a bal oldal maximális, ezért minden más értékre a jobb oldal lesz nagyobb. Az egyenlőséget x1=x2=...=x6=0-ra kapjuk. Lehet, hogy hibás a gondolatmenet, javítsatok kérlek ha így van

Igazad van, eleinte különböző szögeket vettem mindenhol, aztán jutott eszembe a lent írt gondolat, de ezek szerint nem véletlenül írtam fel először különbözőkkel :D Valóban, így viszont már jóval nehezebb bármit is kezdeni ezzel az ötlettel(bár a bal oldali kifejezések még így is elég szimpatikusak lehetnek)

... legyenek a páratlan indexű tagok egy szög szinuszai, a következő tag pedig ugyanannak a szögnek a koszinuszai...

Ez hibás kiindulás, ugyanis a feltételek nem garantálják, hogy pld. &tex;\displaystyle x_1^2+x_2^2=1&xet;.

A B4703. feladattal kapcsolatban gondolkoztam egy olyan megoldáson, ami trigonometrikus helyettesítést használ. Mivel minden xi-re fennáll -1<=xi<=1, ezért legyenek a páratlan indexű tagok egy szög szinuszai, a következő tag pedig ugyanannak a szögnek a koszinuszai. Ekkor a bal oldali gyökös kifejezésekben ki lehet használni a trigonometrikus Pit. tételt, és az adott oldalon ugyanazoknak a szögeknek a szinuszainak és koszinuszainak abszolútértéke marad 3mal szorozva, ill. lesz egy szög, aminek csak a szinusza áll majd a bal oldalon egy 3s szorzóval. A jobb oldalon marad 3 olyan tag, amelynek minimuma gyök7, illetve 3, aminek minimuma gyök5. Sajnos ezek a becslések elég durvák, és nem is használtuk ki, hogy a 6 tag összege 0. Viszont nem sok hiányzik hozzá, szerintem egy kis finomítással lehetne értelme egy ilyen bizonyításnak. Ötletek?

A643-ra létezik olyan megoldás, amelyik nem azt használja ki, hogy végtelen sok &tex;\displaystyle n^2+1&xet; alakú prím létezik?

Vegyük észre, hogy

&tex;\displaystyle (n+1)A^2B+(n-2)B^2 -A^4-(2n-2)AC= 2\sum_{i,j,k}(x_ix_j-x_ix_k)^2+2\sum_{i,j,k,t}x_jx_k(x_i-x_t)^2&xet;

A kérdés persze az, hogy ezt hogy vesszük észre. Először is kivonjuk a baloldalt, majd kiszámoljuk, hogy pont mennyi a különbség. Erre az adódik, hogy

&tex;\displaystyle (4n-8)\sum x_i^2x_j^2+(2n-10)\sum x_i^2x_jx_k-12\sum x_ix_jx_kx_t.&xet;

Én úgy szoktam kiszámolni, hogy készítek egy táblázatot, amely sorai a homogén negyedfokú monomok: &tex;\displaystyle x_i^4, x_i^3x_j, x_i^2x_j^2, x_i^2x_jx_k,x_ix_jx_kx_t &xet;, oszlopai a kifejezéseim, és mindnhova beírom, hogy miből mennyi van. A szimmetria miatt megúsztam az egészet egy 5-ször 4-es táblázattal. Utána összeadom az oszlopokat, és megvan a különbség.

Bátorítólag hat rám, hogy az &tex;\displaystyle x_i^4&xet;-es és az &tex;\displaystyle x_i^3x_j&xet;-s tagok kiestek.

Most tudom, hogy a feladat nemnegatív valós számokról szól, ezért ha minden &tex;\displaystyle x_i&xet; helyébe &tex;\displaystyle x_i^2&xet;-et írok, akkor egy olyan egyenlőtlenséget kapok, ami már minden valós számra igaz. Most, Hilbert tétele alapján, ez a polinom (amennyiben tényleg pozitív mindenütt) előáll racionális törtfüggvények négyzeteinek összegeként. Én persze reménykedem, hogy előáll polinomok négyzetösszegeként is. Ilyenkor van biztos módszer, a szisztematikus teljes négyzetté alakítás MINDIG működik. A konkrét esetben a polinom olyannyira szimmertrikus, hogy megpróbálom szimmetrikus módon előállítani négyzetösszegként. A első próbálkozás bejött.

Ha valaki szeretné látni, hogy hogyan lehet megkeresni a legkevesebb négyzetösszeggé való alakítást, az találhat rá EGY módszert itt:

http://www.math.uiuc.edu/ reznick/quartic.pdf

Aki ellenpéldát szeretne arra, hogy hogyan néz ki egy polinom, ami mindig pozitív, de nem polinomok, hanem csak racionális törtfüggvények négyzetösszege, annak íme:

http://www.math.uiuc.edu/documenta/vol-ismp/61_schmuedgen-konrad.pdf

Jogos, annyi módosítás kell, hogy legyen &tex;\displaystyle k&xet; a &tex;\displaystyle 0&xet; változók száma, &tex;\displaystyle n=n_1+k&xet;, és a szimmetrikus részt csak a pozitívakra definiáljuk, mert a &tex;\displaystyle 0&xet;-s tényezős tagok úgyis kiesnek. Kell:

&tex;\displaystyle -A^4+A^2 B (k+n_1+1)-2 A C (k+n_1-1)+B^2 (k+n_1-2)\geq 0&xet;

Módosításokkal átrendezve:

&tex;\displaystyle (n-1) n^2 \left((n_1-1)(k+n_1-2) \sigma_{n_1,2}^2-(n_1-2)(k+n_1-1) \sigma_{n_1,1}\sigma_{n_1,3}\right)\geq 0&xet;

És &tex;\displaystyle (n_1-1) (k+n_1-2)-(n_1-2) (k+n_1-1)=k&xet; miatt Newtonnal kész. (ettől csak gyengébb lett)

A B4703 szövege így kezdődik: Tegyük föl, hogy az &tex;\displaystyle x_1,x_2,x_3,x_4,x_5,x_6&xet; számok abszolút értéke legfeljebb 1, összegük pedig 0.

Az eredeti javaslatom pontosan ugyanez a feladat volt, csak úgy, hogy ennek a mondatnak a helyén a következő mondat volt: Tegyük föl, hogy az &tex;\displaystyle x_1,x_2,x_3,x_4,x_5&xet; számok abszolút értéke legfeljebb &tex;\displaystyle 1&xet;, összegük pedig &tex;\displaystyle 0&xet;, és legyen &tex;\displaystyle x_6=x_1&xet;.

A Szerkesztőség úgy fest, az eredeti kitűzést túl könnyűnek ítélte (amúgy tényleg kedves, egyszerű), és csavart rajta, nem is keveset. Vagy elszúrták a kitűzést és mivel így is igaz volt, nem volt kedvük vele törődni. Mindenesetre állítólag így is igaz.

Sokat dolgoztam azon, hogy legalább én megoldjam azt a feladatot, amihez a nevem van odaírva, de végül csak abban az esetben sikerült belátnom, hogy &tex;\displaystyle \sqrt{1-a_1^2}\le 4\sqrt 2-4\sqrt 3+\sqrt 5\approx 0,9647&xet;.

A B.4703-et hogyan sikerult igy?

Egy zavaró körülmény: az A. 642.-ben akkor is egyenlőség van, ha &tex;\displaystyle x_1=1&xet; és &tex;\displaystyle x_2=\dots=x_n=0&xet;.

A belinkelt oldal hibás. Ha a változók között szerepel a &tex;\displaystyle 0&xet;, akkor nem tudjuk elérni, hogy a szorzat &tex;\displaystyle 1&xet; legyen.

A Wikipedia oldal még rosszabb...

A.642

&tex;\displaystyle \sigma_{n,k}:=\binom{n}{k}^{-1}\sum_{1\leq i_1<...<i_k\leq n} \prod_{r=1}^k x_{i_r} &xet;

&tex;\displaystyle n&xet; elemhez tartozó &tex;\displaystyle k&xet;-adrendű normált szimmetrikus polinomok. Ekkor:

&tex;\displaystyle A=n\sigma_{n,1}\qquad B=n^2\sigma_{n,1}^2-n(n-1)\sigma_{n,2}\qquad C=n^3\sigma_{n,1}^3-\frac{3}{2}n^2(n-1)\sigma_{n,1}\sigma_{n,2}+\frac{1}{2}n(n-1)(n-2)\sigma_{n,3} &xet;

Azt kell belátnunk tehát, hogy:

&tex;\displaystyle (n+1)A^2B+(n-2)B^2\geq A^4+2(n-1)AC&xet;

&tex;\displaystyle (n+1)\left(n\sigma_{n,1}\right)^2\left(n^2\sigma_{n,1}^2-n(n-1)\sigma_{n,2}\right)+(n-2)\left(n^2\sigma_{n,1}^2-n(n-1)\sigma_{n,2}\right)^2\geq\left(n\sigma_{n,1}\right)^4+(n-1)\left(2n^3\sigma_{n,1}^3-3n^2(n-1)\sigma_{n,1}\sigma_{n,2}+n(n-1)(n-2)\sigma_{n,3}\right)&xet;

Kibontva és átrendezve:

&tex;\displaystyle n^5 \sigma_{n,2}^2-n^5 \sigma_{n,1} \sigma_{n,3}-4 n^4 \sigma_{n,2}^2+4 n^4 \sigma_{n,1} \sigma_{n,3}+5 n^3 \sigma_{n,2}^2-5 n^3 \sigma_{n,1} \sigma_{n,3}-2 n^2 \sigma_{n,2}^2+2 n^2 \sigma_{n,1}\sigma_{n,3}\geq 0 &xet;

És szorzattá alakítva:

&tex;\displaystyle (n-2) (n-1)^2 n^2 \left(\sigma_{n,2}^2-\sigma_{n,1} \sigma_{n,3}\right)\geq 0&xet;

Viszont ez éppen a Newton-féle egyenlőtlenség: &tex;\displaystyle \sigma_{n,k}^2\geq \sigma_{n,k-1}\sigma_{n,k+1}&xet; miatt igaz (bizonyítást elemien lásd a Sklarszkij-Jaglom-Csencov könyvben, analízist használva itt) , egyenlőség csak akkor áll, ha &tex;\displaystyle x_1=x_2=...=x_n&xet;.

"Mondjuk a B4694-es olyan ocsmány volt, hogy semmi kedvem volt vele már órákat vesződni,......."

Pont Rád gondoltam, nézvén a pontszámaidat :)

Általában a B-feladatok nehézségi sorrendje egy hónapon belül nem követi a pontértéksorrendet. Ebben szerintem benne lehet, hogy a szerkesztők mást ítélnek könnyű vagy nehéz feladatnak, mint a megoldók, vagy nagyobb eséllyel az, hogy néhány könnyebb feladatnak nagyobb pontértéket adván juttat versenyzőket sikerélményhez, ami kedvet ad arra, hogy foglalkozzanak a nehezebb feladatokkal is.

Mondjuk a B4694-es olyan ocsmány volt, hogy semmi kedvem volt vele már órákat vesződni, míg végigmennek a számítások. Azért valaki írhatna megoldást. Érdekességnek mondjuk jó volt kitűzni. Tehát személyesen örültem, hogy a hónapban nem volt a 6 legtöbb pontot érő feladatban.

Mi a véleményetek a B. 4711. feladat pontozásáról (5pont)?

Egyszerű számolással látható, hogyha x+y=1, akkor f(x)+f(y)=1, így a kérdéses összeg elejéről-hátuljáról párosítva az összeadandókat, az eredmény 1008.

Eközben a B.4694. feladat csupán 4 pontot ér és a beérkezett/4 pontos megoldások aránya 15/2 a statisztika alapján.

Vagy: a gömb középpontjából vetítünk egy, vele párhuzamos síkra, és akkor azt kapjuk hogy van egy kör. őt érintő négy egyenes, meg mondjuk ezek metszései valahogy. A szög változása a kör sugarának változásának felel meg, az érintőegyenesek irányai maradnak. De a nagyítás az euklideszi sík egy hasonlósága, mindent megtart.

=> akárhány félegyenes akármilyen illeszkedésrendszere esetén igaz lesz, hogy a kapott sík metszése az alapsíkkal nem függ a forgatás &tex;\displaystyle \varphi&xet; szögétől.

B.4698. megoldása: először is ha &tex;\displaystyle H^*_n&xet; jelöli az &tex;\displaystyle \frac1n,\frac2n,\dots,\frac nn&xet; törtek halmazát, akkor jól láthatóan &tex;\displaystyle |H^*_n|=n&xet; és &tex;\displaystyle H^*_n\cap H^*_k=H^*_{(n,k)}&xet;. Ha pedig &tex;\displaystyle f&xet; bijekció a racionális számok és pozitív egészek között, akkor &tex;\displaystyle H_n&xet; halmazok, mint &tex;\displaystyle H^*_n&xet; képei &tex;\displaystyle f&xet; után, meg fognak felelni.

Közölt a635. megoldásánál jónéhány helyen &tex;\displaystyle \sigma (\varphi(n))&xet; szerepel &tex;\displaystyle \varphi (\sigma (n))&xet; helyett

Egyébként felcserélve elég érdektelen lett volna a feladat: legyen &tex;\displaystyle n=p=k*T!+1&xet; alakú prím (Dirichlet tétele miatt lesz ilyen prím), és ez jó lesz, ha &tex;\displaystyle T&xet;-t elég nagynak választjuk.