UTAG la \(u_1=max\{u_i\}\) og \(u_2=max\{u_i\}\). Dermed har vi
\begin{align*}
0 &\geq \sum_{i=1}^{2019} (u_1-u_i)(u_2-u_i) \\
&= 2019u_1u_2-(u_1+u_2)\sum_{i=1}^{2019} u_i +\sum_{i=1}^{2019} u_{i}^{2}\\
&=2019u_1u_2+1
\end{align*}
Dette impliserer ulikheten i oppgaven.
Ulikhetmaraton
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Ny ulikhet:
La \(n\geq 2\) være et heltall og la \(a_1,a_2,...,a_n>1\) være reelle tall. Vis at
\[\prod_{i=1}^{n}\left ( a_{i}a_{i+1}-\frac{1}{a_{i}a_{i+1}} \right )\geq 2^n \prod_{i=1}^{n}\left (a_i -\frac{1}{a_i} \right ) \]
Her er \(a_{n+1}=a_1\).
La \(n\geq 2\) være et heltall og la \(a_1,a_2,...,a_n>1\) være reelle tall. Vis at
\[\prod_{i=1}^{n}\left ( a_{i}a_{i+1}-\frac{1}{a_{i}a_{i+1}} \right )\geq 2^n \prod_{i=1}^{n}\left (a_i -\frac{1}{a_i} \right ) \]
Her er \(a_{n+1}=a_1\).
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Påstand 1: Vi har \(xy-\frac{1}{xy} \geqslant 2\sqrt{(x-\frac{1}{x})(y-\frac{1}{y})}\) når \(x,y>1\)
Bevis:
\[(x-1)(y-1)\geqslant (\frac{1}{x}-1)(\frac{1}{y}-1)\Longleftrightarrow xy-x-y\geqslant \frac{1}{xy}-\frac{1}{x}-\frac{1}{y}\Longleftrightarrow xy-\frac{1}{xy}\geqslant x-\frac{1}{x}+y-\frac{1}{y}\]
Den første ulikheten er åpenbar, så resten følger også. Så nå har vi:
\[xy-\frac{1}{xy}\geqslant x-\frac{1}{x}+y-\frac{1}{y}\geqslant 2\sqrt{(x-\frac{1}{x})(y-\frac{1}{y})}\]
som var det vi ville vise.
Nå, bruker vi påstand 1 på alle \(a_ia_{i+1}\) og da har vi følgene:
\[\prod_{i=1}^{n}\left ( a_{i}a_{i+1}-\frac{1}{a_{i}a_{i+1}} \right )\geqslant \prod_{i=1}^{n} 2\sqrt{(a_i-\frac{1}{a_i})(a_{i+1}-\frac{1}{a_{i+1}})} = 2^n \prod_{i=1}^{n}\left (a_i -\frac{1}{a_i} \right ) \]
Yippie!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Bevis:
\[(x-1)(y-1)\geqslant (\frac{1}{x}-1)(\frac{1}{y}-1)\Longleftrightarrow xy-x-y\geqslant \frac{1}{xy}-\frac{1}{x}-\frac{1}{y}\Longleftrightarrow xy-\frac{1}{xy}\geqslant x-\frac{1}{x}+y-\frac{1}{y}\]
Den første ulikheten er åpenbar, så resten følger også. Så nå har vi:
\[xy-\frac{1}{xy}\geqslant x-\frac{1}{x}+y-\frac{1}{y}\geqslant 2\sqrt{(x-\frac{1}{x})(y-\frac{1}{y})}\]
som var det vi ville vise.
Nå, bruker vi påstand 1 på alle \(a_ia_{i+1}\) og da har vi følgene:
\[\prod_{i=1}^{n}\left ( a_{i}a_{i+1}-\frac{1}{a_{i}a_{i+1}} \right )\geqslant \prod_{i=1}^{n} 2\sqrt{(a_i-\frac{1}{a_i})(a_{i+1}-\frac{1}{a_{i+1}})} = 2^n \prod_{i=1}^{n}\left (a_i -\frac{1}{a_i} \right ) \]
Yippie!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Prove that for any real numbers \(a,b,c,d \geq \frac{1}{3}\) the following inequality holds:
$$\sqrt{\frac{a^6}{b^4+c^3}+\frac{b^6}{c^4+d^3}+\frac{c^6}{d^4+a^3}+\frac{d^6}{a^4+b^3}}\geq \frac{a+b+c+d}{4}$$
$$\sqrt{\frac{a^6}{b^4+c^3}+\frac{b^6}{c^4+d^3}+\frac{c^6}{d^4+a^3}+\frac{d^6}{a^4+b^3}}\geq \frac{a+b+c+d}{4}$$
La $p_i=\sum_cyc a^{i}$ være den i-te potenssummen. Av T2 lemma har vi at
\[
\sum_{cyc} \frac{a^6}{b^4+c^3} \geq \frac{p_3^2}{p_4+p_3}
\]
Vi ønsker nå å vise at $\frac{p_3}{\sqrt{p_4+p_3}} \geq \frac{p_1}{4}$. Dette er ekvivalent med $16p_3^2\geq p_1^2(p_4+p_3)$.
Vi ser først på $p_4+p_3$. UTAG la $a\geq b\geq c\geq d$:
\[
p_4+p_3=\sum_{cyc} a^3(a+1) \leq (a+1)\sum_{cyc} a^3 \leq p_1p_3
\]
Den siste ulikheten ovenfor følger av at $a,b,c,d\geq \frac{1}{3}$. Av Muirhead følger det at $16p_3\geq p_1^3$. Dermed har vi
\[
p_1^2(p_4+p_3)\leq p_1^3p_3 \leq 16p_3^2
\]
som skulle vises.
\[
\sum_{cyc} \frac{a^6}{b^4+c^3} \geq \frac{p_3^2}{p_4+p_3}
\]
Vi ønsker nå å vise at $\frac{p_3}{\sqrt{p_4+p_3}} \geq \frac{p_1}{4}$. Dette er ekvivalent med $16p_3^2\geq p_1^2(p_4+p_3)$.
Vi ser først på $p_4+p_3$. UTAG la $a\geq b\geq c\geq d$:
\[
p_4+p_3=\sum_{cyc} a^3(a+1) \leq (a+1)\sum_{cyc} a^3 \leq p_1p_3
\]
Den siste ulikheten ovenfor følger av at $a,b,c,d\geq \frac{1}{3}$. Av Muirhead følger det at $16p_3\geq p_1^3$. Dermed har vi
\[
p_1^2(p_4+p_3)\leq p_1^3p_3 \leq 16p_3^2
\]
som skulle vises.
Vi utsletter oppgaven med lagranges multiplikatormetode.
Vi fikserer a,b,c, og lar x,y,z variere.
La [tex]a' = \frac{a}{b+c}[/tex].
Observer at om en av variablene x,y,z blir arbitrert stor, er ulikheten åpenbart sann. Om z = 0, får vi at xy = 3.
Vi ønsker nå å vise
[tex] \frac{(a'+c')y+(b'+c')x}{2} \geq \frac{3}{2}[/tex]
Ved am gm har vi
[tex] \frac{(a'+c')y+(b'+c')x}{2} \geq \sqrt{xy(a'+c')(b'+c')} = \sqrt{3} \sqrt{(a'+c')(b'+c')} [/tex]
Ved å kvadrere og dele på 3 ser vi at vi bare ønsker å vise at
[tex](a'+c')(b'+c') \geq \frac{3}{4}[/tex]
Som ved definisjonen av a',b',c' og ganging med (a+b)(b+c)(a+c) er ekvivalent med å vise
[tex]4(ab(a+b)+bc(b+c)+ac(a+c)) + 4 \frac{c^2 (b+c)(a+c}{(a+b)} \geq 3(a+b)(b+c)(c+a)[/tex]
Hvis vi glemmer c^2greia ser vi at hver side har 24 terms, og venstresiden majoriserer åpenbart høyresiden. Dermed følger oppgaven av muirhead.
Vi løser nå det generelle tilfellet. La a,b,c være fikserte. La f være venstresiden som funksjon av x,y,z, og la g=xy+yz+xz. Da vil minimal og maksimalverdier til f opptre når
[tex]y+z = \lambda (b'+c'), x+z = \lambda (a'+c'), y+x = \lambda (a'+b')[/tex]
Av linear algebra får vi [tex]x=\lambda a',y=\lambda b',z=\lambda c'[/tex].
Plugger vi dette inn i g ser vi at:
[tex]a'b' +a'c'+b'c' = \frac{3}{\lambda^2}[/tex]
Og om vi plugger det inn i f får vi at vi ønsker å vise.
[tex]\lambda( 2a'b'+2b'c'+2a'c') \geq 3[/tex]
Vi plugger in g og ser at det reduserer til å vise:
[tex]\lambda \leq 2[/tex]
Anta for motsigelse [tex]\lambda > 2[/tex], da får vi ved å plugge inn i g at:
[tex](a'b'+b'c'+c'a') < \frac{3}{2}[/tex]
Som ved å gange med (a+b)(b+c)(a+c) gir at:
[tex]2(ab(a+b)+bc(b+c)+ac(a+c))<3(a+b)(b+c)(a+c)[/tex]
Som er en klar motsigelse, siden vi allerede har vist med muirhead at dette ikke stemmer.
Vi fikserer a,b,c, og lar x,y,z variere.
La [tex]a' = \frac{a}{b+c}[/tex].
Observer at om en av variablene x,y,z blir arbitrert stor, er ulikheten åpenbart sann. Om z = 0, får vi at xy = 3.
Vi ønsker nå å vise
[tex] \frac{(a'+c')y+(b'+c')x}{2} \geq \frac{3}{2}[/tex]
Ved am gm har vi
[tex] \frac{(a'+c')y+(b'+c')x}{2} \geq \sqrt{xy(a'+c')(b'+c')} = \sqrt{3} \sqrt{(a'+c')(b'+c')} [/tex]
Ved å kvadrere og dele på 3 ser vi at vi bare ønsker å vise at
[tex](a'+c')(b'+c') \geq \frac{3}{4}[/tex]
Som ved definisjonen av a',b',c' og ganging med (a+b)(b+c)(a+c) er ekvivalent med å vise
[tex]4(ab(a+b)+bc(b+c)+ac(a+c)) + 4 \frac{c^2 (b+c)(a+c}{(a+b)} \geq 3(a+b)(b+c)(c+a)[/tex]
Hvis vi glemmer c^2greia ser vi at hver side har 24 terms, og venstresiden majoriserer åpenbart høyresiden. Dermed følger oppgaven av muirhead.
Vi løser nå det generelle tilfellet. La a,b,c være fikserte. La f være venstresiden som funksjon av x,y,z, og la g=xy+yz+xz. Da vil minimal og maksimalverdier til f opptre når
[tex]y+z = \lambda (b'+c'), x+z = \lambda (a'+c'), y+x = \lambda (a'+b')[/tex]
Av linear algebra får vi [tex]x=\lambda a',y=\lambda b',z=\lambda c'[/tex].
Plugger vi dette inn i g ser vi at:
[tex]a'b' +a'c'+b'c' = \frac{3}{\lambda^2}[/tex]
Og om vi plugger det inn i f får vi at vi ønsker å vise.
[tex]\lambda( 2a'b'+2b'c'+2a'c') \geq 3[/tex]
Vi plugger in g og ser at det reduserer til å vise:
[tex]\lambda \leq 2[/tex]
Anta for motsigelse [tex]\lambda > 2[/tex], da får vi ved å plugge inn i g at:
[tex](a'b'+b'c'+c'a') < \frac{3}{2}[/tex]
Som ved å gange med (a+b)(b+c)(a+c) gir at:
[tex]2(ab(a+b)+bc(b+c)+ac(a+c))<3(a+b)(b+c)(a+c)[/tex]
Som er en klar motsigelse, siden vi allerede har vist med muirhead at dette ikke stemmer.
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Først har vi følgene lemma som vi bruker. \(\frac{n+2}{k+2}<\frac{n+1}{k+1}\) hvis \(n\geqslant k\). Dette følger av utvidelse.
Vi viser oppgaven via induksjon, hvor base case er trivelt, siden \(a_1=\frac{1}{2}\).
Anta at alt til \(a_i\) er positivt for \(i=1,2,\cdots ,n\) Vi viser at \(a_{n+1}\) må være positivt. Av den rekursive likningen har vi:
\[S_1=\sum_{k=0}^{n} \frac{a_{n-k}}{k+1}=0 \]
\[S_2=\sum_{k=1}^{n+1} \frac{a_{n+1-k}}{k+1}=-a_{n+1}\]
Hvis vi nå ser på
\[(n+2)a_{n+1}=(n+1)S_1-(n+2)S_2 = \sum_{k=0}^{n-1} (\frac{n+1}{k+1}a_{n-k}-\frac{n+2}{k+2}a_{n-k})=\sum_{k=0}^{n-1} a_{n-k}(\frac{n+1}{k+1}-\frac{n+2}{k+2})>0\]
siden alle \(a_i\) er positive, og alle \(\frac{n+1}{k+1}-\frac{n+2}{k+2}\) er positive av lemma, så vi er ferdige.
Vi viser oppgaven via induksjon, hvor base case er trivelt, siden \(a_1=\frac{1}{2}\).
Anta at alt til \(a_i\) er positivt for \(i=1,2,\cdots ,n\) Vi viser at \(a_{n+1}\) må være positivt. Av den rekursive likningen har vi:
\[S_1=\sum_{k=0}^{n} \frac{a_{n-k}}{k+1}=0 \]
\[S_2=\sum_{k=1}^{n+1} \frac{a_{n+1-k}}{k+1}=-a_{n+1}\]
Hvis vi nå ser på
\[(n+2)a_{n+1}=(n+1)S_1-(n+2)S_2 = \sum_{k=0}^{n-1} (\frac{n+1}{k+1}a_{n-k}-\frac{n+2}{k+2}a_{n-k})=\sum_{k=0}^{n-1} a_{n-k}(\frac{n+1}{k+1}-\frac{n+2}{k+2})>0\]
siden alle \(a_i\) er positive, og alle \(\frac{n+1}{k+1}-\frac{n+2}{k+2}\) er positive av lemma, så vi er ferdige.
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Ny lett ulikhet:
La \(a,b>1\) være heltall. Vis at følgene ulikhet holder:
\[\frac{1}{gcd(a,b-1)}+\frac{1}{gcd(a-1,b)}\geqslant \frac{2}{\sqrt{a+b-1}}\]
La \(a,b>1\) være heltall. Vis at følgene ulikhet holder:
\[\frac{1}{gcd(a,b-1)}+\frac{1}{gcd(a-1,b)}\geqslant \frac{2}{\sqrt{a+b-1}}\]
Vi skriver om ulikheten til
[tex]\sqrt{a+b-1}(gcd(a-1,b)+gcd(a,b-1)) \geq2 gcd(a,b-1) gcd(a-1,b)[/tex]
Av AMGM er
[tex] gcd(a-1,b)+gcd(a,b-1) > 2 \sqrt{gcd(a,b-1)*gcd(a-1,b)} [/tex]
Dette har likhet når de to termsa er like, men som enhver oppegående, velfungerende person vet vil ikke det skje.
Dermed kan vi redusere oppgaven til:
[tex]\sqrt{a+b-1} \geq \sqrt{gcd(a,b-1)*gcd(a-1,b)}[/tex]
[tex]a+b-1 \geq gcd(a,b-1)*gcd(a-1,b) [/tex]
Som vi nå skal vise.
La gcd(a,b-1) = k, da er a=kq, b-1 = kr.
Videre ser vi da at [tex]gcd(a-1,b) = gcd(kq-1, kr+1) = gcd(kq+kr, kr+1) = gcd(r+q, kr+1) \leq r +q[/tex]
Dermed får vi [tex]gcd(a,b-1)*gcd(a-1,b) \leq kq+kr = a+b-1[/tex]
Og oppgaven er løst
[tex]\sqrt{a+b-1}(gcd(a-1,b)+gcd(a,b-1)) \geq2 gcd(a,b-1) gcd(a-1,b)[/tex]
Av AMGM er
[tex] gcd(a-1,b)+gcd(a,b-1) > 2 \sqrt{gcd(a,b-1)*gcd(a-1,b)} [/tex]
Dette har likhet når de to termsa er like, men som enhver oppegående, velfungerende person vet vil ikke det skje.
Dermed kan vi redusere oppgaven til:
[tex]\sqrt{a+b-1} \geq \sqrt{gcd(a,b-1)*gcd(a-1,b)}[/tex]
[tex]a+b-1 \geq gcd(a,b-1)*gcd(a-1,b) [/tex]
Som vi nå skal vise.
La gcd(a,b-1) = k, da er a=kq, b-1 = kr.
Videre ser vi da at [tex]gcd(a-1,b) = gcd(kq-1, kr+1) = gcd(kq+kr, kr+1) = gcd(r+q, kr+1) \leq r +q[/tex]
Dermed får vi [tex]gcd(a,b-1)*gcd(a-1,b) \leq kq+kr = a+b-1[/tex]
Og oppgaven er løst
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Vi starter først med et lemma: I en trekant, så er lengden av medianen mindre en gjennomsnittet av lengden av de \(2\) sidene som går uti fra samme hjørne som medianen. Dette følger siden hvis vi reflekterer dette hjørnet over midpunktet, får vi et parallelogram og vi er ferdige via trekantulikheten.
La \(D,E,F\) være midpunktene i trekanten \(ABC\). Vi vet at \(M\) ligger enten i \(ABD\) eller \(ACD\), WLOG at \(M\) ligger i \(ABD\). Da har vi at \(AM+BM<AD+BD<\frac{BC}{2}+\frac{AC}{2}+\frac{AB}{2}=s\). Her er \(s\) halvparten av omkreksten som vanlig. Videre ser vi på trekantene \(ACE\) og \(BCE\) og ser om \(M\) ligger i en av de, og derfra med samme argument får man at enten \(CM+BM<s\) eller \(AM+CM<s\). Uansett hvilken som stemmer, kan vi summere den sammen med den orginale vi fikk og vi får resultatet.
La \(D,E,F\) være midpunktene i trekanten \(ABC\). Vi vet at \(M\) ligger enten i \(ABD\) eller \(ACD\), WLOG at \(M\) ligger i \(ABD\). Da har vi at \(AM+BM<AD+BD<\frac{BC}{2}+\frac{AC}{2}+\frac{AB}{2}=s\). Her er \(s\) halvparten av omkreksten som vanlig. Videre ser vi på trekantene \(ACE\) og \(BCE\) og ser om \(M\) ligger i en av de, og derfra med samme argument får man at enten \(CM+BM<s\) eller \(AM+CM<s\). Uansett hvilken som stemmer, kan vi summere den sammen med den orginale vi fikk og vi får resultatet.
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
In a contest, there are $m$ candidates and $n$ judges, where $n\geq 3$ is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most $k$ candidates. Prove that \[{\frac{k}{m}} \geq {\frac{n-1}{2n}}\].
Legg merke til at kravene i oppgaven er ekvivalent med: Vi har $n$ binærstrenger av lengde $m$ som all innbyrdes har hammingavstand større eller lik $m-k$. For hver binærstreng $s^{(i)}$ definerer vi korresponderende vektorer $v^{(i)}\in \{-1,1\}^m$ for $1\leq i \leq n$, der $v_k^{(i)}$ er lik $-1$ hvis $s_k^{(i)} = 0$ og $v_k^{(i)}=1$ hvis $s_k^{(i)}=1$. Vi har da at $v_k^{(i)}v_k^{(j)}=-1$ hviss de $s_k^{(i)}\neq s_k^{(j)}$. Vi bruker vanlig euklidsk indreprodukt videre i løsningen. La $d_H$ være hamming distansen mellom to binærstrenger. Vi har
\begin{align*}
\langle v^{(i)}, v^{(j)}\rangle
&= \text{(# plasser der $s_k^{(i)} = s_k^{(j)}$)} - \text{(# plasser der $s_k^{(i)} \neq s_k^{(j)}$)}
&= m-2d_H(s^{(i)},s^{(i)})
\end{align*}
For $i\neq j$ har vi da $\langle v^{(i)}, v^{(j)}\rangle = m-2d_H(s^{(i)},s^{(i)}) \leq m -2(m-k) =2k-m$. Hvis $i=j$, så er $\langle v^{(i)}, v^{(j)}\rangle = m$. Det er $n(n-1)$ ordnede par av $i$ og $j$. Vi får dermed følgende sum
\[
\begin{align*}
\sum_{1\leq i,j\leq n} \langle v^{(i)}, v^{(j)}\rangle &= \sum_{i=1}^n \langle v^{(i)}, v^{(i)}\rangle + \sum_{i\neq j} \langle v^{(i)}, v^{(j)}\rangle \\
&\leq nm + n(n-1)(2k-m)
\end{align*}
\]
La $S=\sum_{i=1}^n v^{(i)}$. Siden $n$ er odde kan ikke $S_i = 0$. Dermed er $S_i^2\geq 1$. Videre har vi da at
\[
\sum_{1\leq i,j\leq n} \langle v^{(i)}, v^{(j)}\rangle = \left \langle \sum_{i=1}^n v^{(i)}, \sum_{j=1}^n v^{(j)} \right \rangle = \left \lVert S \right \rVert ^2 \geq m
\]
Vi kombinerer disse to ulikhetene til $nm + n(n-1)(2k-m)\geq m$. Vi utvider og forenkler til $2kn(n-1)\geq m(n-1)^2$. Til slutt får vi $\frac{k}{m}\geq \frac{n-1}{2(n)}$.
$\square$
Kommentar: Når $n$ ikke er odde, så har vi den svakere ulikheten $\frac{k}{m}\geq \frac{n-2}{2(n-1)}$
\begin{align*}
\langle v^{(i)}, v^{(j)}\rangle
&= \text{(# plasser der $s_k^{(i)} = s_k^{(j)}$)} - \text{(# plasser der $s_k^{(i)} \neq s_k^{(j)}$)}
&= m-2d_H(s^{(i)},s^{(i)})
\end{align*}
For $i\neq j$ har vi da $\langle v^{(i)}, v^{(j)}\rangle = m-2d_H(s^{(i)},s^{(i)}) \leq m -2(m-k) =2k-m$. Hvis $i=j$, så er $\langle v^{(i)}, v^{(j)}\rangle = m$. Det er $n(n-1)$ ordnede par av $i$ og $j$. Vi får dermed følgende sum
\[
\begin{align*}
\sum_{1\leq i,j\leq n} \langle v^{(i)}, v^{(j)}\rangle &= \sum_{i=1}^n \langle v^{(i)}, v^{(i)}\rangle + \sum_{i\neq j} \langle v^{(i)}, v^{(j)}\rangle \\
&\leq nm + n(n-1)(2k-m)
\end{align*}
\]
La $S=\sum_{i=1}^n v^{(i)}$. Siden $n$ er odde kan ikke $S_i = 0$. Dermed er $S_i^2\geq 1$. Videre har vi da at
\[
\sum_{1\leq i,j\leq n} \langle v^{(i)}, v^{(j)}\rangle = \left \langle \sum_{i=1}^n v^{(i)}, \sum_{j=1}^n v^{(j)} \right \rangle = \left \lVert S \right \rVert ^2 \geq m
\]
Vi kombinerer disse to ulikhetene til $nm + n(n-1)(2k-m)\geq m$. Vi utvider og forenkler til $2kn(n-1)\geq m(n-1)^2$. Til slutt får vi $\frac{k}{m}\geq \frac{n-1}{2(n)}$.
$\square$
Kommentar: Når $n$ ikke er odde, så har vi den svakere ulikheten $\frac{k}{m}\geq \frac{n-2}{2(n-1)}$