Feladat:	B.4973	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Beke Csongor ,  Dobák Dániel ,  Füredi Erik Benjámin ,  Győrffy Ágoston ,  Hegedűs Dániel ,  Jedlovszky Pál ,  Márton Dénes ,  Molnár Bálint ,  Nagy Nándor ,  Szabó Dávid ,  Tóth Balázs ,  Tubak Dániel ,  Várkonyi Zsombor ,  Weisz Máté
Füzet:	2020/február, 91 - 94. oldal		PDF  |  MathML
Témakör(ök):	Szélsőérték-feladatok, Feladat
Hivatkozás(ok):	Feladatok: 2018/szeptember: B.4973

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Először belátjuk, hogy a legnagyobb összeg elérhető olyan $a_i$ számokkal, amelyekre igaz a következő: ha $a_i$ és $a_j$ pozitív számok, és $i<j$, akkor $i\mid j$. Legyen $S$ egy olyan összeg, amelynél van olyan $i$ és $j$, hogy $i\nmid j$, $j\nmid i$, de $a_i>0$ és $a_j>0$. Egy olyan ,,cserét'' fogunk definiálni, ami az $S$ összeget nem csökkenti. Legyen $s_i$, illetve $s_j$ azon $a_k$ számok összege, melyeknek indexével $i$, illetve $j$ valódi osztó, vagy valódi többszörös relációban áll, azaz $$\begin{gathered} \begin{array}{c}{\displaystyle s_i=\sum _{k\ne i \\ \left(i\mid k\vee k\mid i\right)}^{}{a}_k\mathrm{,}\text{illetve}{s}_j=\sum _{k\ne j \\ \left(j\mid k\vee k\mid j\right)}^{}{a}_k\mathrm{.}}\end{array} \end{gathered}$$ Ekkor $i\nmid j$ és $j\nmid i$ miatt $s_i$-ben nem szerepel $a_j$, és $s_j$-ben nem szerepel $a_i$. Legyen $s_i\ge s_j$. Az $$\begin{gathered} \begin{array}{c}{\displaystyle S=\sum _{k\ne l \\ k\mid l}^{}{a}_k{a}_l}\end{array} \end{gathered}$$ összeget bontsuk három részre; az első részben legyenek azok a kéttényezős szorzatok, amelyeknek valamely tényezője $a_i$, a másodikban azok, melyeknek valamely tényezője $a_j$, míg a harmadik ,,maradék'' rész álljon azokból a szorzatokból, amelyeknek egyik tényezője sem $a_i$ vagy $a_j$, azaz $\begin{array}{c}{\displaystyle S=a_i{s}_i+a_j{s}_j+\sum _{\text{,,maradék''}}^{}{a}_k{a}_l\mathrm{.}}\end{array}$ Ha most $a_i$-t kicseréljük $a_i\text{'}=a_i+a_j$-re, míg $a_j$-t $a_j\text{'}=0$-ra, akkor az új $S\text{'}$ összegre (mivel a maradék, $i\mathrm{,}j$-től független rész nem változik) $\begin{array}{c}{\displaystyle S\text{'}-S=a_i\text{'}{s}_i+a_j\text{'}{s}_j-a_i{s}_i-a_j{s}_j=\left(a_i+a_j\right)s_i-a_i{s}_i-a_j{s}_j=a_j\left(s_i-s_j\right)\ge \mathrm{0,}}\end{array}$ tehát az $S$ összeget nem csökkentettük. Mindaddig, amíg van olyan $i$ és $j$, hogy $i\nmid j$, $j\nmid i$, de $a_i>0$ és $a_j>0$, hajtsuk végre a fent definiált cserét. A cserék nem folytatódhatnak a végtelenségig, mivel a pozitív $a_k$-k száma minden csere során $1$-gyel csökken; emiatt legfeljebb $2017$ lépés után nem tudunk többet cserélni. Ekkor valóban teljesül, hogy ha $a_i$ és $a_j$ 0-tól különböző számok, és $i<j$, akkor $i\mid j$. A továbbiakban már csak ezzel az esettel fogunk foglalkozni. Legyenek a pozitív $a_i$ számok indexei növekedő sorrendben $i_1\mathrm{,}{i}_2\mathrm{,}\text{...}\mathrm{,}{i}_k$. Pozitív számok körében ha $j$ valódi többszöröse $i$-nek, akkor $2\cdot i\le j$. Emiatt az $i_1\mathrm{,}{i}_2\mathrm{,}\text{...}\mathrm{,}{i}_k$ index-sorozatnak legfeljebb $11$ tagja lehet, hiszen $1=2^0\le i_1$; $2=2^1\le i_2$; $4=2^2\le i_3$; $\text{...}$; $1024=2^{10}\le i_{11}$ és a 12-edik tag esetén $2018<2048\le i_{12}$ lenne. Tizenegy ilyen tag viszont kiválasztható, ha például a 2018-nál kisebb 2-hatványokat vesszük; ekkor a pozitív tagok: $a_1\mathrm{,}{a}_2\mathrm{,}{a}_4\mathrm{,}\text{...}\mathrm{,}{a}_{2^n}\mathrm{,}\text{...};a_{1024}$. Vizsgáljuk meg, hogy $1\le k\le 11$ darab pozitív $a_i$ tag esetén mekkora a maximális ($k$-tól függő) $S=S_k$ összeg. Fel fogjuk használni a számtani és a négyzetes közép közötti összefüggést. Ennek alapján a nemnegatív, 1 összegű $c_i$ számokra: $\begin{array}{c}{\displaystyle \frac{1}{n}=\frac{c_1+c_2+\text{...}+c_n}{n}\le \sqrt[]{\frac{c_1^2+c_2^2+\text{...}+c_n^2}{n}}\mathrm{,}}\end{array}$ innen rendezéssel adódik: $\begin{array}{c}{\displaystyle \frac{1}{n}\le c_1^2+c_2^2+\text{...}+c_n^2}\end{array}$ (és az egyenlőség pontosan akkor teljesül, ha $c_1=c_2=\text{...}=c_n=\frac{1}{n}$.) ${\displaystyle \begin{array}{cc}\hfill {\displaystyle S_k}& {\displaystyle =a_{i_1}{a}_{i_2}+a_{i_1}{a}_{i_3}+\text{...}+a_{i_{k-1}}{a}_{i_k}=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\frac{{\left(a_{i_1}+a_{i_2}+a_{i_3}+\text{...}+a_{i_k}\right)}^2-\left(a_{i_1}^2+a_{i_2}^2+a_{i_3}^2+\text{...}+a_{i_k}^2\right)}{2}=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\frac{1-\left(a_{i_1}^2+a_{i_2}^2+a_{i_3}^2+\text{...}+a_{i_k}^2\right)}{2}\le \frac{1-\frac{1}{k}}{2}\mathrm{.}}\hfill \end{array}}$ Mivel nyilván $S_k<S_{k+1}$, akkor kapjuk a lehető legnagyobb $S$-et, ha a lehető legtöbb, azaz pontosan $11$ pozitív $a_i$ tagunk van. Ekkor $\begin{array}{c}{\displaystyle S=S_{11}\le \frac{1-\frac{1}{11}}{2}=\frac{5}{11}}\end{array}$ és az egyenlőség pontosan akkor teljesül, ha mind a 11 pozitív $a_i$ tagra $a_i=\frac{1}{11}$. Összegezve: $S$ maximuma $\frac{5}{11}$ és ez meg is valósítható, ha $a_1=a_2=a_4=\text{...}=a_{2^n}=\text{...}=a_{1024}=\frac{1}{11}$.    Molnár Bálint (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. évf.)  dolgozata alapján     II. megoldás. Soroljuk az $\mathrm{1,2,3,}\text{...}\mathrm{,2017,2018}$ számokat a $H_0\mathrm{,}{H}_1\mathrm{,}\text{...}\mathrm{,}{H}_{10}$ csoportokba aszerint, hogy multiplicitással számolva hány prímosztójuk van. Az $1$ kerüljön $H_0$-ba, a prímszámok $H_1$-be, a prímszámok négyzetei, és azok a számok, amelyek két különböző prím szorzataként állnak elő kerüljenek $H_2$-be és így tovább. (Például $24=2^3\cdot 3^1$ a $H_4$-be kerül, és ha egy $n$ összetett szám prímfelbontása $n=p_1^{k_1}\cdot p_2^{k_2}\cdot \text{...}\cdot p_l^{k_l}$, akkor az a $H_{k_1+k_2+\text{...}+k_l}$ csoportba kerül, míg az utolsó csoport: $H_{10}=\left\{2^{10};2^9\cdot 3\right\}=\left\{1024;1536\right\}$.) A csoportok száma valóban 11 lesz, mert $2^{11}=2048>2018$ miatt nincs olyan számunk, melynél a (multiplicitással számolt) prímosztók száma 10-nél több. Ha az $i\ne j$ számokra $i\mid j$, akkor $i$ és $j$ más-más csoportba kerülnek, hiszen $i$-nek (multiplicitással számolva) kevesebb prímosztója van, mint $j$-nek. Legyen $0\le i\le 10$ esetén $b_i=\sum _{j\in H_i}^{}{a}_j$. (Például $b_0=a_1$, $b_1=a_2+a_3+a_5+a_7+\text{...}+a_{2017}$, míg $b_{10}=a_{1024}+a_{1536}$.) Tekintsük a $\begin{array}{c}{\displaystyle B=\sum _{0\le k<l\le 10}^{}{b}_k{b}_l=b_0{b}_1+b_0{b}_2+b_0{b}_3+\text{...}+b_9{b}_{10}}\end{array}$ összeget. Legyen $i\in H_k$; $j\in H_l$; $i\ne j$; $i\mid j$. Ekkor a kéttényezős $a_i{a}_j$ szorzat a $b_k{b}_l=\left(\text{...}+a_i+\text{...}\right)\left(\text{...}+a_j+\text{...}\right)$ zárójel-felbontott alakjának valamely tagja. Emiatt $\begin{array}{c}{\displaystyle S\le B=\sum _{0\le k<l\le 10}^{}{b}_k{b}_l=\frac{{\left(b_0+b_1+\text{...}+b_{10}\right)}^2-\left(b_0^2+b_1^2+\text{...}+b_{10}^2\right)}{2}\mathrm{.}}\end{array}$ Erre az összegre (az előző megoldásban leírt módon) adódik: $\begin{array}{c}{\displaystyle S\le \frac{{\left(b_0+b_1+\text{...}+b_{10}\right)}^2-\left(b_0^2+b_1^2+\text{...}+b_{10}^2\right)}{2}\le \frac{1-\frac{1}{11}}{2}=\frac{5}{11}\mathrm{.}}\end{array}$ Másfelől az $S=\frac{5}{11}$ elérhető az $a_1=a_2=a_4=a_8=\text{...}=a_{2^n}=\text{...}=a_{1024}=\frac{1}{11}$ választással.    Jedlovszky Pál (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. évf.) és  Szabó Dávid (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 12. évf.)  dolgozata alapján   Megjegyzés. Jedlovszky Pál a második megoldással ekvivalens saját megoldásában az ott definiált $H_0\mathrm{,}{H}_1\mathrm{,}\text{...}\mathrm{,}{H}_{10}$ halmazokat úgy vette fel, hogy $H_0=\left\{1\right\}$; $H_1=\left\{2;3\right\}$; $H_2=\left\{4;5;6;7\right\}$; $\text{...}$; $H_{10}=\left\{1024;1025;\text{...};2018\right\}$ legyen, míg Tóth Balázs (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. évf.) egy 2018 csúcsú (1‐2018-ig címkézett) gráf csúcsait színezte meg 11 színnel aszerint, hogy a megfelelő címke-számoknak (multiplicitással számolva) hány prímosztója van.