Fórum: Érdekes matekfeladatok

Adott egy háromszög, melynek szögei: &tex;\displaystyle A&xet;, &tex;\displaystyle B&xet; és &tex;\displaystyle C&xet;. Vezessük be a következő jelölést:

&tex;\displaystyle S_a=\cos^2 B+\cos^2 C+2\sin B\sin C\cos A,&xet;

és ciklikusan permutálva a szögeket adjuk meg &tex;\displaystyle S_b&xet; és &tex;\displaystyle S_c&xet; kifejezéseket.

Adott &tex;\displaystyle S_a&xet; és &tex;\displaystyle S_b&xet;. Határozzuk meg &tex;\displaystyle S_c&xet; értékét!

Leírok egy megoldásvázlatot a feladatra (aztán kiderült, hogy a Skljarszkij-Csencov-Jaglomban is pont ez szerepel).

Legyen &tex;\displaystyle p&xet; tetszőleges prímszám. Belátjuk, hogy &tex;\displaystyle p&xet; kitevője &tex;\displaystyle C=\prod_{1\le i<j\le n}(j-i)&xet;-ben legalább annyi, mint &tex;\displaystyle p&xet; kitevője &tex;\displaystyle P=\prod_{1\le i<j\le n}(a_j-a_i)&xet;-ben.

Jelölje minden &tex;\displaystyle r=0,1,\dots,p-1&xet;-re &tex;\displaystyle k_r&xet; azt, hogy hány &tex;\displaystyle a_i&xet; ad &tex;\displaystyle r&xet; maradékot &tex;\displaystyle p&xet;-vel osztva. Ekkor &tex;\displaystyle p&xet; kitevője &tex;\displaystyle P&xet;-ben az &tex;\displaystyle \binom 12=\binom 02=0&xet; jelöléssel

&tex;\displaystyle \sum_{r=0}^{p-1}\binom{k_r}2.&xet;

Ennek a minimumát keressük &tex;\displaystyle k_0+k_1+\dots+k_{p-1}=n&xet; feltétel mellett (&tex;\displaystyle k_r&xet; természetes szám). Ha valamely két &tex;\displaystyle k_r&xet; eltérése legalább &tex;\displaystyle 2&xet;, akkor azokat egymás felé mozgatva, az összeg csökkenni fog; ebből következik, hogy a minimális összeget akkor érhetjük el, amikor bármely két &tex;\displaystyle k_r&xet; eltérése legfeljebb &tex;\displaystyle 1&xet;. Ez éppen a &tex;\displaystyle C&xet;-ben előforduló &tex;\displaystyle p&xet;-kitevőnek felel meg.

Talán mégiscsak ez a legegyszerűbb megközelítés. Habár determinánsokkal kétségtelenül elegánsabb.

Aha, a te bizonyításod egyszerűbb. Eltér az enyémtől, mert te nem jobbról, hanem balról szorzod meg valamivel a Vandermonde determinánst, mégpedig egy Stirling-számokból álló háromszög-mátrixszal.

Szerintem nem olyan nehéz megsejteni a választ: az &tex;\displaystyle 0,1,2,\dots,n-1&xet; számokból készített szorzat (a legkisebb pozitív szorzat), vagyis &tex;\displaystyle 1!\cdot 2!\cdot\dots\cdot (n-1)!&xet; a legnagyobb közös osztó.

Szerintem nagyon természetes a bizonyításod. (Az elején nyilván nem &tex;\displaystyle \prod (l-k)&xet;, hanem &tex;\displaystyle \prod (a_l-a_k)&xet; van, de ez nem zavaró.)

Én eredetileg picit máshogy olvastam:

&tex;\displaystyle \prod_{1\le i<j\le n}\frac{a_j-a_i}{j-i}=\frac{\prod_{1\le i<j\le n}(a_j-a_i)}{\prod_{k=0}^{n-1} k!}=\left(\prod_{k=0}^{n-1}k!\right)^{-1}\cdot \left|\matrix{a_1^0 & a_2^0 & \dots & a_n^0\cr a_1^1 & a_2^1 & \dots & a_n^1 \cr a_1^2 & a_2^2 & \dots & a_n^2 \cr \dots & & & \dots \cr a_1^{n-1} & a_2^{n-1} & \dots & a_n^{n-1} }\right|=&xet;

&tex;\displaystyle =\quad \left|\matrix{\frac{a_1^0}{0!} & \frac{a_2^0}{0!} & \dots & \frac{a_n^0}{0!}\cr \frac{a_1^1}{1!} & \frac{a_2^1}{1!} & \dots & \frac{a_n^1}{1!} \cr \frac{a_1^2}{2!} & \frac{a_2^2}{2!} & \dots & \frac{a_n^2}{2!} \cr \dots & & & \dots \cr \frac{a_1^{n-1}}{(n-1)!} & \frac{a_2^{n-1}}{(n-1)!} & \dots & \frac{a_n^{n-1}}{(n-1)!} }\right|\quad =\quad \left|\matrix{\binom{a_1}0 & \binom{a_2}0 & \dots & \binom{a_n}0 \cr \binom{a_1}1 & \binom{a_2}1 & \dots & \binom{a_n}1 \cr \binom{a_1}2 & \binom{a_2}2 & \dots & \binom{a_n}2 \cr \dots & & & \dots \cr \binom{a_1}{n-1} & \binom{a_2}{n-1} & \dots & \binom{a_n}{n-1} }\right|\quad \in Z.&xet;

De a feladat megoldható Vandermonde-determinánsok nélkül is.

Megsejteni nehéz, de ha már tudom, hogy mi a várt megoldás, akkor nem olyan nehéz bebizonyítani. Mutatok egy vázlatot. Ez elég ronda, szeretnék látni szebb bizonyítást.

Először írjuk fel az általad kért szorzatot Vandermonde-determináns alakban.

&tex;\displaystyle {\rm det} {\bf V} = \prod_{1\le k<l\le n} (l-k) = \left|\matrix{ a_1^0 & a_2^0 & \dots & a_n^0 \cr a_1^1 & a_2^1 & \dots & a_n^1 \cr a_1^2 & a_2^2 & \dots & a_n^2 \cr \dots & & & \dots \cr a_1^{n-1} & a_2^{n-1} & \dots & a_n^{n-1} \cr }\right| &xet;

Speciálisan írjuk fel a nevezőt is ilyen alakban.

&tex;\displaystyle {\rm det} {\bf S} = \prod_{1\le k<l\le n} (l-k) = \left|\matrix{ 1^0 & 2^0 & \dots & n^0 \cr 1^1 & 2^1 & \dots & n^1 \cr 1^2 & 2^2 & \dots & n^2 \cr \dots & & & \dots \cr 1^{n-1} & 2^{n-1} & \dots & n^{n-1} \cr }\right| &xet;

Most a célunk belátni, hogy bármilyen &tex;\displaystyle a &xet; egész számra a &tex;\displaystyle {\bf g}_a = {(}a^0, a^1, a^2, \dots, a^{n-1}{)}^{\rm T} &xet; vektort fel lehet írni az utóbbi determináns oszlopvektoraiból egész együtthatós lineáris kombinációként. Ezt teljes indukcióval lehet belátni. Vegyük észre ugyanis, hogy bármely &tex;\displaystyle 0 \le k < n &xet; egész kitevőre

&tex;\displaystyle 0 = \sum_{0\le l\le n} (-1)^l \binom{n}{l} (a-l)^k &xet;

ez ugyanis az &tex;\displaystyle a^k &xet; sorozat &tex;\displaystyle n &xet;-edik különbségsorozatának az &tex;\displaystyle a &xet; indexű eleme. Ebből

&tex;\displaystyle 0 = \sum_{0\le l\le n} (-1)^l \binom{n}{l} {\bf g}_{a-l}. &xet;

Ebben az összegben az együtthatók egészek, és a két szélső vektor, &tex;\displaystyle {\bf g}_a &xet; és &tex;\displaystyle {\bf g}_{a-n} &xet; éppen &tex;\displaystyle \pm1 &xet; együtthatóval szerepel. Ha kivonjuk a szélső tagot, akkor a maradék összeg megadja a &tex;\displaystyle {\bf g}_a &xet; illetve &tex;\displaystyle {\bf g}_{a-n} &xet; vektort az előző &tex;\displaystyle n &xet; illetve a következő &tex;\displaystyle n &xet; vektor egész együtthatós kombinációjaként. Így minden &tex;\displaystyle {\bf g}_n &xet; vektort rekurzívan kifejthetünk előre (ha &tex;\displaystyle n &xet; pozitív) vagy hátra (ha &tex;\displaystyle n &xet; nem pozitív) addig, hogy csak a &tex;\displaystyle {\bf g}_1, \dots, {\bf g}_n &xet; vektorok kombinációiból álljon, és ebben az együtthatók egészek lesznek.

Ha ezt a &tex;\displaystyle {\bf V} &xet; mátrix minden oszlopára megtesszük, akkor &tex;\displaystyle {\bf V} &xet;-t felírtuk &tex;\displaystyle {\bf S} &xet; és egy egész együtthatós mátrix szorzataként, innen &tex;\displaystyle {\rm det} {\bf V} &xet; többszöröse &tex;\displaystyle {\rm det} {\bf S} &xet;-nek.

Igen, ez a megoldás. A feladat más szóval azt kéri, hogy bizonyítsuk be, hogy

&tex;\displaystyle \prod_{1\le i<j\le n}\frac{a_j-a_i}{j-i}&xet;

egész szám bármely &tex;\displaystyle a_1,a_2,\dots,a_n&xet; egész számokra.

Kíváncsi vagyok, hogy milyen megoldási ötleteket fogtok találni.

Nem ismertem, de érdekes feladat. Szerintem ez a sorozat a megoldás rá.

Kíváncsi vagyok, hányan ismerik:

Legyen &tex;\displaystyle n&xet; pozitív egész szám, és tekintsük bármely &tex;\displaystyle S=(a_0,\dots,a_n)&xet; egész számokból álló sorozathoz a

&tex;\displaystyle f(S)=\prod_{0\le i<j\le n}(a_j-a_i)&xet;

szorzatot. Ezzel az összes ilyen számsorozathoz egy-egy egész számot rendeltünk. Mi a legnagyobb olyan pozitív egész, amely minden &tex;\displaystyle f(S)&xet; számot osztja?

Erre lényegét tekintve csak egyetlen bizonyítást ismerek, de jó meggondolni, hogy hányféleképpen mondható el. Talán a legrövidebb magyarázat a következő.

Vegyük észre, hogy az egyenlet ekvivalens a következő nyilvánvaló ténnyel:

Megjegyzés. Ha nadorp gondolatmenetét akarjuk átvinni, a következő szemléletesebb modellel lehet a legérdekesebb elmondani (lásd akár a 2013-as IMO shortlist A4 feladatát). Rajzoljunk egy oszlopdiagramot a derékszögű koordinátarendszer első síknegyedébe, méghozzá úgy, hogy az &tex;\displaystyle x&xet;-tengelyen a &tex;\displaystyle k&xet;-adik egységszakasz fölé &tex;\displaystyle \left[\frac{x}{k^{1/t}}\right]&xet; magasságú oszlopot rajzolunk. Az oszlopok együttes területe így a jobb oldalt adja ki, és persze az oszlopok "ereszkednek". Most képzeljük el mindezt, mint egy sordiagramot: nézzük meg, hogy milyen hosszú sor lóg ki az &tex;\displaystyle y&xet;-tengely &tex;\displaystyle k&xet;-adik egységszakaszán. Ez a sor éppen addig tart, amíg az &tex;\displaystyle a&xet;-adik oszlop magassága legalább &tex;\displaystyle k&xet;, avagy amíg

&tex;\displaystyle \left[\frac{x}{a^{1/t}}\right]\ge k,&xet;

&tex;\displaystyle \frac{x}{a^{1/t}}\ge k,&xet;

&tex;\displaystyle \frac{x^t}{k^t}\ge a,&xet;

&tex;\displaystyle \left[\frac{x^t}{k^t}\right]\ge a.&xet;

Más szóval, az (alulról) &tex;\displaystyle k&xet;-adik sor hossza éppen &tex;\displaystyle \left[\frac{x^t}{k^t}\right]&xet;, és ezzel kaptuk, hogy a bal oldali összeg is a diagram területét adja ki.