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

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

$\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$

Módosításokkal átrendezve:

$\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$

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

A B4703 szövege így kezdődik: Tegyük föl, hogy az $\displaystyle x_1,x_2,x_3,x_4,x_5,x_6$ 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 $\displaystyle x_1,x_2,x_3,x_4,x_5$ számok abszolút értéke legfeljebb $\displaystyle 1$, összegük pedig $\displaystyle 0$, és legyen $\displaystyle x_6=x_1$.

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 $\displaystyle \sqrt{1-a_1^2}\le 4\sqrt 2-4\sqrt 3+\sqrt 5\approx 0,9647$.

A B.4703-et hogyan sikerult igy?

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

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

A Wikipedia oldal még rosszabb...

A.642

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

$\displaystyle n$ elemhez tartozó $\displaystyle k$-adrendű normált szimmetrikus polinomok. Ekkor:

$\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}$

Azt kell belátnunk tehát, hogy:

$\displaystyle (n+1)A^2B+(n-2)B^2\geq A^4+2(n-1)AC$

$\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)$

Kibontva és átrendezve:

$\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$

És szorzattá alakítva:

$\displaystyle (n-2) (n-1)^2 n^2 \left(\sigma_{n,2}^2-\sigma_{n,1} \sigma_{n,3}\right)\geq 0$

Viszont ez éppen a Newton-féle egyenlőtlenség: $\displaystyle \sigma_{n,k}^2\geq \sigma_{n,k-1}\sigma_{n,k+1}$ 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 $\displaystyle x_1=x_2=...=x_n$.

"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 $\displaystyle \varphi$ szögétől.

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

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

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

Gondolom azt a jól bevált módszert használod, hogy rekurzívan megjelölöd a nyerő és vesztő helyzeteket. Csinálj egy jó nagy ilyen (k,n)-es táblázatot (mondjuk 20x25-öst), mely mezőibe beírod, hogy nyerő vagy vesztő. Majd pedig keress mintát. (A játékok gyakran szeretik a kettes számrendszert. A minta csak kicsit bonyolult.)

A. 620. Artúrnak és Benőnek van egy k×n-es csokoládéja, ezzel a következő játékot játsszák. Felváltva esznek egy-egy darabot a csokoládéból, Artúr kezd. Minden lépésben a soron következő játékos a vonalak mentén két kisebb téglalap alakú darabra töri szét a csokoládét, és megeszi a kisebbik darabot. (Ha történetesen a két darab ugyanakkora, akkor szabadon választhat, hogy melyiket eszi meg.) Aki először eszik valamelyik lépésben egyetlen csokoládékockát, veszít, a másik játékos nyer.

Határozzuk meg mindazokat a (k,n) párokat, amikre Artúrnak van nyerő stratégiája.

1xn,2xn,3xn...7xn-re van vélhetően jó megoldásom.

Általános kxn-re nekem nem jött össze. Aki tudja írja meg!

A lap hivatalos megoldásában, csak a megoldók neve szerepel. A megoldás nem.

Én is így indultam ki (nagyjából). Megjegyzem, ehhez hasonló módszerrel ki is jön a $\displaystyle k=2,3$ eset ($\displaystyle n^{k-\epsilon}$-nal), hiszen akkor

$\displaystyle [a,b]=\frac{ab}{(a,b)},\qquad [a,b,c]\ge \frac{abc}{(a,b)(b,c)(c,a)}.$

(Ezeknek azt hiszem, annyi a jelentősége, hogy legfeljebb $\displaystyle k$ tényezővel kell visszaosztani. De most már nem emlékszem pontosan a kezdő kísérletekre, ha érdekel valakit, megpróbálom kifejteni. Egyébként kicsit gyanús volt, hogy pont már $\displaystyle k=4$-re nem működik ez a módszer.)

Szerintem igaz. Egy gyengébb állítást belátok: minden L>0-ra létezik $\displaystyle c(L,k)>0$, hogy, ha az n különböző pozitív egész mindegyike kisebb, mint L*n, akkor kiválasztható k darab ($\displaystyle n\ge k$ esetén), hogy azok lkktje nagyobb, mint $\displaystyle c(L,k)*n^k$.

Legyen $\displaystyle H=\frac {\prod_{i=1}^k c_i}{\prod_{1\le i<j\le k}lnko(c_i,c_j)}$, ugyan H nem mindig egész (k<4-re viszont egész), de mindig igaz, hogy $\displaystyle H\le lkkt(c_1,..,c_k)$ (használjuk az lnko,lkkt prímtényezős alakját). Az $\displaystyle a_1,..,a_n$ számok közül dobjuk ki az $\displaystyle \frac n2$-nél kisebbeket, marad legalább $\displaystyle \frac n2$ szám az $\displaystyle [\frac n2,Ln]$ intervallumból. Az egyszerűség kedvéért legyen n osztható $\displaystyle k$-val, és tekintsük az $\displaystyle (u*L*k,(u+1)*L*k]$ intervallumokat $\displaystyle u=0,..,\frac{n}{k}-1$-re. Ezek uniója lefedi $\displaystyle [\frac n2,Ln]$-et, így skatulyaelv alapján van olyan intervallum, amibe legalább k darab $\displaystyle a_i$ szám esik. Válasszunk ki ezek közül k darabot: $\displaystyle c_1,..,c_k$, ekkor $\displaystyle \frac n2\le c_i$ és létezik S, hogy $\displaystyle S< c_i \le S+r$, ahol $\displaystyle r=L*k$ konstans, de akkor $\displaystyle i\neq j$-re $\displaystyle lnko(c_i,c_j)<r$, így $\displaystyle H\ge \frac {({\frac n2})^k}{r^{\frac{k(k-1)}{2}}}=const*n^k$, ami kellett.

Az eredeti problémánál anno még pont így indultam ki.

Ügyes vagy, [-1,1]-en értelmezett fv-nek olvastam.

Engem jobban érdekelne egy $\displaystyle \varepsilon$ nélküli megoldás: $\displaystyle n^{k-\varepsilon}$ helyett $\displaystyle cn^k$ valamilyen pozitív $\displaystyle c$ konstanssal.

$\displaystyle k=2$-re mutatok egyet. Az egyszerűség kedvéért legyen $\displaystyle n$ páros, $\displaystyle n=2m$. Vegyük a számok nagyobbik felét: legyen $\displaystyle a_1,a_2,\dots,a_{m+1}$ az $\displaystyle m+1$ legnagyobb szám. Ezeknél van $\displaystyle m-1$ kisebb, tehát $\displaystyle a_1,a_2,\dots,a_{m+1}\ge m$.

Tekintsük az $\displaystyle \frac1{a_1},\dots,\frac1{a_{m+1}}$ számokat. Ez $\displaystyle m+1$ különböző valós szám a $\displaystyle \left(0,\frac1m\right]$ intervallumban; van tehát közöttük kettő, $\displaystyle a_i$ és $\displaystyle a_j$ aminek a különbsége kisebb, mint $\displaystyle \frac1{m^2}$. Ezekre

$\displaystyle \frac1{m^2} > \left|\frac1{a_i}-\frac1{a_j}\right| \ge \frac1{lkkt(a_i,a_j)};$

$\displaystyle lkkt(a_i,a_j) > m^2 = \frac{n^2}4.$

Az $\displaystyle x^2$ mint korlátos függvény? :-o

Csak egy kis apróság: kérlek, tedd olvashatóvá a megoldásaidat. Lehet, hogy egyedül vagyok ezzel, de nehezen átlátható az, amit írsz, bármennyire is érdekes lehet.

Lehet ezt indukció nélkül is. Leírom - remélem - átlátható(bb)an.

A.633. megoldása.

Felhasználjuk, hogy ha $\displaystyle d(m)$ az $\displaystyle m>0$ egész pozitív osztóinak száma, és $\displaystyle t>0$ adott, akkor van olyan $\displaystyle C(t)$ konstans, melyre $\displaystyle d(m)<C(t)m^t$ teljesül bármely $\displaystyle m>0$ egészre. (Ennek belátása a 2008-as Kürschák 1. feladatához hasonló - utóbbi pl. megtalálható a VersenyVizsga portálon.)

Azt is belátjuk, hogy adott $\displaystyle \epsilon>0$ és $\displaystyle k>1$ egész esetén elég nagy $\displaystyle n$-re bármely $\displaystyle n$ különböző pozitív egész között van $\displaystyle k$ darab, aminek legkisebb közös többszöröse $\displaystyle n^{k-\epsilon}$-nál nagyobb.

A megoldáshoz legyen $\displaystyle t>0$ adott (később megválasztjuk), és írjuk le egy listában mind a $\displaystyle \binom nk$ legkisebb közös többszöröst. Legyen a kapott lista $\displaystyle L$, és jelölje $\displaystyle x$ a benne előforduló különböző számok számát. Bármely $\displaystyle m\in L$-re jelölje $\displaystyle E(m)$ az $\displaystyle m$ előfordulását $\displaystyle L$-ben. Ekkor felírhatjuk, hogy

Hogyha van olyan $\displaystyle m\in L$, melyre $\displaystyle m\ge n^k$, akkor teljesül az állítás. Tegyük most fel, hogy bármely listabeli szám legfeljebb $\displaystyle n^k$.

Hogyha $\displaystyle k$ darab szám legkisebb közös többszöröse $\displaystyle m$, akkor ezek mind osztják $\displaystyle m$-et, vagyis $\displaystyle d(m)$-félék lehetnek. Ebből következik, hogy

$\displaystyle E(m)\le \binom{d(m)}k\le$

Másfelől, hogyha $\displaystyle n\ge 2k$, akkor

Beleírva $\displaystyle (2)$-t és $\displaystyle (3)$-at $\displaystyle (1)$-be, $\displaystyle n\ge 2k$-ra

$\displaystyle \frac1{2^k\cdot k!}n^k<x\cdot C(t)^k(n^k)^{tk},$

ahol $\displaystyle c(t)=\frac1{2^k\cdot k!\cdot C(t)^k}$. Most válasszunk $\displaystyle t=\frac{\epsilon}{2k^2}$-et, és tegyük fel, hogy $\displaystyle n>c(t)^{-2/\epsilon}$: ekkor $\displaystyle (4)$-ből adódik:

$\displaystyle x>c(t)n^{\epsilon/2}\cdot n^{k-\epsilon}>n^{k-\epsilon},$

tehát a legnagyobb a legkisebb közös többszörösök közül $\displaystyle n^{k-\epsilon}$-nál nagyobb lesz.

Tehát ha $\displaystyle n> \max\left\{2k,c\left(\frac{\epsilon}{2k^2}\right)^{-2/\epsilon}\right\}$, akkor mindenképpen lesz $\displaystyle n$ különböző pozitív egész között $\displaystyle k$, aminek legkisebb közös többszöröse $\displaystyle n^{k-\epsilon}$-nál nagyobb.

$\displaystyle {\bf a633.}$ megoldása: Többet látok be. Minden pozitív k egészre és c>0 valós számra igaz, hogy létezik N(k,c), hogy n>N(k,c) esetén n különböző pozitív egész szám közül kiválasztható k, hogy azok lkkt-je nagyobb, mint $\displaystyle n^{k-c}$(a feladat N(4,0.01) létezéséről szól).

Az állítás $\displaystyle k=1$-re trivi, N(1,c)=1 megfelelő (egyetlen szám lkkt-je maga a szám). Teljes indukció. Ha $\displaystyle (k-1)$-re és minden $\displaystyle c>0$-ra igaz az állítás, akkor kell $\displaystyle k$-ra. Legyen $\displaystyle n\ge k$ (hogy egyáltalán tudjunk k számot választani). Legyenek a számaink $\displaystyle a_1,..,a_n$, ha létezik köztük nagyobb, mint $\displaystyle n^k$, akkor készen vagyunk (válasszunk még ezen szám mellé (k-1)-et tetszelőgesen). Így feltehető $\displaystyle a_i\le n^k$ minden $\displaystyle i$-re. Legyen $\displaystyle m$ az $\displaystyle a_i$ számok legnagyobbika, ekkor persze $\displaystyle n\le m\le n^k$ teljesül.

Szükségem lesz a következő ismert tételre: minden $\displaystyle \epsilon >0$-ra létezik $\displaystyle M(\epsilon)$, hogy $\displaystyle m>M(\epsilon)$ esetén $\displaystyle m$-nek kevesebb, mint $\displaystyle m^{\epsilon}$ (pozitív) osztója van. Nyilvánvalóan minden i-re $\displaystyle d=lnko(m,a_i)$ az m egy osztója, amire az előző tétel alapján rögzített t-re csupán $\displaystyle m^t\le n^{k*t}$ lehetőség van. De akkor a skatulyaelv alapján van olyan d, ami legalább $\displaystyle \frac{n-1}{n^{kt}}>n^{1-2*k*t}$-szer szerepel. A számunkra érdekes eset persze az, amikor $\displaystyle 1-2kt>0$. Válasszuk ki ezen $\displaystyle b_1,..,b_s$ számokat az $\displaystyle a_i$ számok közül ($\displaystyle s>n^{1-2kt}$). Vegyük észre, hogy, ha ezen számok közül (k-1)-et kiválasztunk $\displaystyle c_1..,c_{k-1}$, akkor $\displaystyle lkkt(m,c_1,..c_{k-1})=lkkt(d\frac md,d\frac {c_1}{d},..,d\frac{c_{k-1}}{d})=d*lkkt(\frac md,\frac {c_1}{d},..,\frac{c_{k-1}}{d})$ $\displaystyle =d\frac md lkkt(\frac {c_1}{d},..,\frac{c_{k-1}}{d})=m*lkkt(e_1,..e_{k-1})\ge n*lkkt(e_1,..,e_{k-1})$, ahol használtuk, hogy $\displaystyle lnko(m,c_i)=d$ miatt $\displaystyle \frac md,\frac {c_i}{d}$ rel. prímek, és azt, hogy $\displaystyle m\ge n$, és itt $\displaystyle e_i$ egész. Most lehet indukciózni, rögzített $\displaystyle u>0$-ra, ha s elég nagy (azaz $\displaystyle n$ elég nagy), akkor kiválasztható a különböző(!) $\displaystyle b_1,..,b_s$ számok közül (k-1) úgy, hogy $\displaystyle lkkt(c_1,..,c_{k-1})>s^{k-1-u}$, na de ekkor $\displaystyle lkkt(m,c_1,..c_{k-1})>n^{1+(1-2kt)(k-1-u)}$, ha ez nagyobb, mint $\displaystyle n^{k-c}$, akkor vagyunk készen. Azaz kell:

$\displaystyle 1+(1-2kt)(k-1-u)>k-c$, azaz k-2k(k-1)t-u+2ktu>k-c, tehát $\displaystyle c>2k(k-1)t+u-2ktu$, de $\displaystyle 2ktu>0$ így elég: $\displaystyle c>2k(k-1)t+u$, de ekkor $\displaystyle u=\frac {c}{4}$ és $\displaystyle t=min(\frac{1}{4k},\frac{c}{8k(k-1)})>0$ jó választás, mert így $\displaystyle 2k(k-1)t+u\le \frac c4+\frac c4<c$, és a jóval korábbi $\displaystyle 1-2kt>0$ egyenlőtlenség is teljesül. Ezzel a feladat állítását beláttuk.

$\displaystyle {\bf a634.}$ megoldása: az állítás hamis, $\displaystyle n=2;f(x)=x^2$ egy trivi ellenpélda. Mindegy, majd újra kitűzitek.

A.630. hivatalos megoldása megjelent, szép, tetszik.

Két megoldást találtam, egyik sem az, úgyhogy miért is ne gyorsan leírom őket. Szerintem érdekesek. (Az eleje, hogy megnézzük az érintőszakaszokat, nálam is ugyanaz.)

Nézzük a $\displaystyle P$-ből $\displaystyle FG$-re állított merőlegest. Triviálisan $\displaystyle Q$ rajta van ezen. Tehát ha belátjuk, hogy $\displaystyle IP$ is merőleges $\displaystyle FG$-re, készen vagyunk.

1. befejezés: ez ismert módon ekvivalens azzal, hogy $\displaystyle IF^2+PG^2=IG^2+PF^2$. Ami pedig nyilvánvaló, hisz mindkét oldal az $\displaystyle F$-ből és $\displaystyle G$-ből a beírt körhöz húzott érintőszakasznak, illetve a beírt kör sugarának a négyzetösszege.

2. befejezés: tekintsük a $\displaystyle P$ elfajuló kört és a beírt kört. Az $\displaystyle F$ pont és $\displaystyle G$ pont hatványa mindkét körre megegyezik, így $\displaystyle FG$ a hatványvonaluk, ami merőleges az $\displaystyle IP$ centrálisra.

[talán mindhárom megoldás átalakítható egymásba, de különböző megközelítésűek]

Köszönöm!

A fórumon kétféle megoldás is szerepelt: ez és ez.

Tudna valaki megoldást/segítséget mutatni az A.536-hoz? A feladat szövege megtalálható itt.