Abel maraton

[Lil_Flip39]

Anta for motstigelses skyld at det eksisterer et primtall $p$ slik at $v_p(b)=kn+r,n>r>0$.
Nå har vi $p^{kn+r}\mid b+a_{p^{(k+1)n}}$
Men dette betyr at $p^{kn+r}\mid a_{p^{(k+1)n}}$, og siden $n\mid v_p(a_{p^{(k+1)n}})$ får vi $v_p(a_{p^{(k+1)n}})⩾(k+1)n$.
$p^{(k+1)n}\mid b+a_{p^{(k+1)n}}$, så
$$p^{(k+1)n}\mid b$$
, en motstigelse.

[Lil_Flip39]

Ny oppgave:

Find the smallest constant $C>1$ such that the following statement holds: for every integer $n\ge 2$ and sequence of non-integer positive real numbers $a_1,a_2,\dots ,a_n$ satisfying $$\frac{1}{a_1}+\frac{1}{a_2}+\cdots +\frac{1}{a_n}=1,$$ it's possible to choose positive integers $b_i$ such that
(i) for each $i=1,2,\dots ,n$, either $b_i=\lfloor a_i\rfloor$ or $b_i=\lfloor a_i\rfloor +1$, and
(ii) we have $$1<\frac{1}{b_1}+\frac{1}{b_2}+\cdots +\frac{1}{b_n}\le C.$$
(Here $\lfloor \bullet \rfloor$ denotes the floor function, as usual.)

[lfe]

Svaret er $C=\frac{3}{2}$.
Først viser vi at $\frac{3}{2}$ fungerer.
La $S_i=\sum _{j=1}^i\frac{1}{\lceil a_j\rceil }+\sum _{j=i+1}^n\frac{1}{\lfloor a_j\rfloor }$. Vi vet $S_n<1$ og $S_0>1$.
I tillegg har vi $\frac{1}{\lfloor a_i\rfloor }-\frac{1}{\lceil a_i\rceil }<\frac{1}{2}$.
Dermed må det eksistere en $i$ slik at $0<S_i\le \frac{3}{2}$.

Nå viser vi at $C=\frac{3}{2}$ er minimal. La $a_i=2n-k$, for $1\le i\le n-1$, der $1<k<2$. La $a_n=\frac{1}{1-\frac{n-1}{2n-k}}=\frac{2n-k}{n+1-k}$.
Det følger at $\sum _{i=1}^n\frac{1}{a_i}=1$ og $1<a_n<2$.
Dermed er
$$\sum _{i=1}^{n-1}\frac{1}{\lfloor a_i\rfloor }=\frac{n-1}{2n-2}=\frac{1}{2}$$
$$\sum {i=1}^{n-1}\frac{1}{\lceil a_i\rfloor }=\frac{n-1}{2n-1}<\frac{1}{2}$$
Vi må altså ha $b_n=\lfloor a_n\rfloor =1$.
$S_i$ er åpenbart strengt synkende. Det følger at $1+\frac{n-1}{2n-1}=S_{n-1}\le S_i\le S_0=\frac{3}{2}$. Dersom vi lar $n$ gå mot uendelig, får vi at $S_{n-1}$ går mot $\frac{3}{2}$ nedenfra. Det følger at $C=\frac{3}{2}$ er minimal.

[lfe]

Ny oppgave:
La $S(p)$ være summen av kvadratet til mudulus av koeffisientene til $p\in \mathbb{C}[x]$. Altså $\sum |p_i{|}^2$, der $p_i$ er koeffisientene til $p$. La $f,g,h\in \mathbb{C}[x]$ slik at $fg=h^2$. Vis at $S(f)\cdot S(g)\ge S(h{)}^2$

[Lil_Flip39]

Nøkkelen til oppgaven:
$S(f)=\frac{\sum _{i=0}^{n-1}|f({\omega }^i){|}^2}{n}$ hvor $\omega$ er en enhetsrot for en ekstremt stor $m$
bevis: (Det kan hende at jeg leste meg opp på komplekse tall idag så jeg vet egt ikke helt hva jeg driver med, men jeg bare bruker de greiene som står på wikipedia)
se på polynomet $Q(x)=(f(x)f(\frac{1}{x})$. For å finne summen av kvadratet til koefisenntenne til $f(x)$, ser vi at $a_i{x}^i\times a_i{x}^{-i}=a_i^2$, og da blir konstant-leddet i $Q(x)$ er det vi vil finne, men av enhetsrotfilter og at $m>deg(Q)$ har vi at
konstantleddet i $Q(x)$ er lik:
$$\frac{\sum _{i=0}^{n-1}Q({\omega }^i)}{n}=\frac{\sum _{i=0}^{n-1}f({\omega }^i)f({\omega }^{-i})}{n}=\frac{\sum _{i=0}^{n-1}f({\omega }^i)\overline{f({\omega }^i)}}{n}=\frac{\sum _{i=0}^{n-1}|f({\omega }^i){|}^2}{n}$$
den nest siste likheten holder av av $z^{-1}=z^{n-1}$ hvis det er en enhetsrot og da blir de konjugater, og dette viser nøkkelen til oppgaven.
Nå bruker vi nøkkelen for å åpne låsen:
$$S(f)\times S(g)=(\frac{\sum _{i=0}^{n-1}|f({\omega }^i){|}^2}{n})\times (\frac{\sum _{i=0}^{n-1}|g({\omega }^i){|}^2}{n})⩾(\frac{\sum _{i=0}^{n-1}|f({\omega }^i)||g({\omega }^i)|}{n}{)}^2=(\frac{\sum _{i=0}^{n-1}|h({\omega }^i)|}{n}{)}^2=S(h{)}^2$$ av Cauchy swaruzh, så vi er ferdige.

[Lil_Flip39]

Gitt et $4\times 2018$ rutenett, fargelegger Tristian Amadeus alle rutene, slik at noen er blå og andre er røde. Tristian liker rutenett som oppfyller følgene:
1. Det er like mange røde og blå ruter i hver kolonne
2. Det er like mange røde og blå ruter i hver rad
Tristian kaller en slik fargelegging $flippende$.
Tristian er en god maler, så han fargelegger en $flippende$ fargelegging hvert sekund, og han gjentar seg ikke. Etter $m$ sekunder er han ferdig med alle $flippende$ fargelegginger.
finn $m(\mathrm{mod}2018)$

[noaherkul1234567890]

Svaret er $6$.

Vi løser oppgaven for et generelt $4\times 2p$-rutenett der $p$ er et primtall.

Vi viser først at antall flippende rutenett er lik
$$(\genfrac{}{}{0ex}{}{2p}{p})\sum _{k=0}^p(\genfrac{}{}{0ex}{}{2k}{k})(\genfrac{}{}{0ex}{}{2p}{2k}).$$

Det er klart at det er $(\genfrac{}{}{0ex}{}{2p}{p})$ måter å velge øverste rad på.
Andre rad kan også velges fritt, og for hver måte å velge andre rad på vil det være $2k$ kolonner der de to rutene har forskjellige farger, for en $0\le k\le p$.
For hver slike $k$ kan det skje på $(\genfrac{}{}{0ex}{}{2p}{2k})$ måter.
Videre vil de $2n-2k$ kolonnene der de to øverste radene er likt fargelagt unikt bestemme fargene på de nedesrte radene.
I de $2k$ kolonnene der fargene i de øverste radene er forskjellige må det være nøyaktig én av hver farge i de to nederste radene.
Hver slike fargelegging bestemmes unikt av en vilkårlig fargelegging av de resterende rutene i rad tre, hvorav det er $(\genfrac{}{}{0ex}{}{2k}{k})$.

Så viser vi videre at $(\genfrac{}{}{0ex}{}{2p}{p})\sum _{k=0}^p(\genfrac{}{}{0ex}{}{2k}{k})(\genfrac{}{}{0ex}{}{2p}{2k})\equiv 6(mod2p)$.

Det er klart at $2|(\genfrac{}{}{0ex}{}{2p}{p})$ og at $p|̸(\genfrac{}{}{0ex}{}{2p}{p})$.

Vi har også at $p|(\genfrac{}{}{0ex}{}{2p}{2k})$ for alle $k\ne 0,p$ og dermed er
$$(\genfrac{}{}{0ex}{}{2p}{p})\sum _{k=0}^p(\genfrac{}{}{0ex}{}{2k}{k})(\genfrac{}{}{0ex}{}{2p}{2k})\equiv 2((\genfrac{}{}{0ex}{}{0}{0})(\genfrac{}{}{0ex}{}{2p}{0})+(\genfrac{}{}{0ex}{}{2p}{p})(\genfrac{}{}{0ex}{}{2p}{2p}))\equiv 2(1+2)\equiv 6(modp)$$

Av CRT er det klart at svaret er $6$.

[noaherkul1234567890]

Ny oppgave:

La $ABC$ være en spissvinklet trekant, og la $D$ og $E$ velges på linjestykkene $AB$ og $AC$ slik at $BD=CE$.
Vis at nipunktsenterene til trekantene $ADE$, $ADC$, $ABC$ og $ABE$ danner en rombe.

[Lil_Flip39]

Lemma 0: I et trapes(eller generell konveks firkant) former midtpunktene på sidene et parallelogram, og da følger det også at diagonalene to-deler hverandre.
Bevis: følger av midtlinjer, hvor 2 par av linjer er parallele med diagonalene i firkanten.

lemma 1: Hvis vi har 2 romber som har parvis parallele diagonaler, og tar midtpunktene mellom korrisponderende hjørner i de 2 rombene, danner det også en rombe.
Bevis: La disse 2 rombene være $ABCD$ og $PQRS$, og la midtpunktene være $XYZW$. La senterene av rombene være $O_1,O_2$.Nå bruker vi lemma på $ACPR$ og $BDQS$. Merk at dette impliserer at midtpunktet til $XZ$ er det samme som midtpunktet til $O_1,O_2$, som er det samme som midtpunktet til $YW$, så $XYZW$ danner et parallelogram. Til slutt har vi at $ACPR$ og $BDQS$ er trapeser, som betyr at diagonalene i $XYZW$ er parallele med $ABCD$ sine, som impliserer at $XYZW$ er en rombe.

Tilbake til oppgaven:

La $H_{XYZ}$ betegne ortosenteret til $\mathrm{△}XYZ$, og definer $O_{XYZ},N_{XYZ}$ på samme måte, hvor $O,N$ er omsenter og nipunktsenter.

Påstand 1: $H_{ABC}{H}_{ABE}{H}_{ACD}{H}_{ADE}$ danner en rombe.
Dette følger av at $B-H_{ABC}-H_{ABE}$ danner en linje, og $D-H_{ADE}-H_{ADC}$ også danner en linje, og begge står normale på $AC$, $H_{ABC}{H}_{ABE}\parallel H_{ADE}{H}_{ADC}$, som impliserer at det er et parallelogram.
Nå, ser vi at av $BD=CE$ at siden vinkelen til disse segmentene og $AC,AB$ er projeksjonen av disse lengdene ned på motsatt side i trekanten like lange. Da er det lett å se at $H_{ABC}{H}_{ABE}{H}_{ACD}{H}_{ADE}$ har like lange sider, så påstanden er bevist.

Påstand 2: $O_{ABC}{O}_{ABE}{O}_{ACD}{O}_{ADE}$ danner en rombe.

Se først at $O_{ABC}{O}_{ADC}$ er midtnormalen til $AC$, og at $O_{ADE}{O}_{ABE}$ er midtnormalen til $AE$, sammen med at lengden av segmentet mellom midtpunktene er $\frac{CE}{2}$ følger det at $O_{ABC}{O}_{ABE}{O}_{ACD}{O}_{ADE}$ danner en rombe av samme argument som i påstand 1:

Påstand 3: $O_{ABC}{O}_{ABE}{O}_{ACD}{O}_{ADE}$, $H_{ABC}{H}_{ABE}{H}_{ACD}{H}_{ADE}$ har parallele diagonaler
Bevis:
Åpenbart har $O_{ABC}{O}_{ABE}{O}_{ACD}{O}_{ADE}$, $H_{ABC}{H}_{ABE}{H}_{ACD}{H}_{ADE}$ parallele sider, siden begge sidene er normale på en eller annen linje. Da ser vi at vinkelene i begge rombene må være like, så rombene er formlike. Da følger resultatet av å bruke desargues perspektiv teorem på noen av trekantene som blir dannet av en diagonal og 2 sider i hver av rombene.


Nå er vi ferdige, siden av påstand 3 kan vi bruke lemma 2, siden nipunktsenteret er midtpunktet på ortosenteret og omsenteret.

[Lil_Flip39]

Tristian Amadeus og Lil flip spiller et spill på et $3\times 1001$ brett som har alle ruter hvite. Hver spiller, i hans tur fargelegger 2 ruter i samme rad eller kolonne svart, og de må ikke være intill hverandre. Spilleren som ikke kan spille mer taper. Tristian Amadeus starter. Både Tristan og Lil flip er smarte, så de spiller optimalt. Hvem har en vinnende strategi?

[lfe]

Tristan vinner. Han starter med fylle to ruter av samme kolonne. Videre kan Tristan alltid kontre Lil flip slik at han ender turen med to nye kolonner der bare to av rutene er fylt og de har begge en tom rute i samme rad. Når alle kolonnene er fylt slik er det nøyaktig 500 trekk igjen. Siden Lil flip da starter taper han.

[lfe]

La $a,b,c\in \mathbb{N}$. Gitt at $$\frac{a}{b}+\frac{b}{c}+\frac{c}{a}$$ er et heltall. Vis at $abc$ er et kubikktall.

[Lil_Flip39]

Først anta $gcd(a,b,c)=1$. Merk at påstanden gitt i oppgaven impliserer
$$abc\mid a^{2}c+b^{2}a+c^{2}b$$
la $p\mid abc$. WLOG $p\mid a$ så har vi $p\mid c^{2}b$ men siden $gcd(a,b,c)=1$ har vi at $p$ deler akkurat en av $b,c$, så gitt et primtall som deler $abc$ deler det akkurat 2 av $a,b,c$.
Påstand: $2v_p(a)=v_p(b)$ hvis $p\mid a,b$.
Bevis: Vi viser påstanden via motstigelse.
Anta $v_p(b)\ne 2v_p(a)$. Da har vi at $v_p(abc)\le v_p(a^{2}c+b^{2}a+c^{2}b)=min(v_p(a^{2}c),v_p(b^{2}a),v_p(c^{2}b))$. Merk at den siste likheten holder fordi alle 3 tallene har forskjellig $v_p$.
Hvis nå $v_p(b)<2v_p(a)$ har vi med en gang motstigelse, siden $v_p(abc)>v_p(b)$. Hvis det ikke holder, har vi at $v_p(abc)=v_p(ab)>v_p(a^2)=v_p(a^{2}c+b^{2}a+c^{2}b)$, en motstigelse. Da er påstanden bevist.

For å avslutte, kan vi konkludere av påstand(noe som holder for alle permutasjoner av $a,b,c$ ikke bare $a,b$) at $v_p(abc)=3v_p(b)$ hvis $v_p(a)⩽v_p(b)⩽v_p(c)$, noe som impliserer at $abc$ er et kubikktall.

[Lil_Flip39]

Finn alle $n$ slik at det eksisterer en permutasjon $a_1,a_2,......,a_n$ av $1,2,3,4,.....,n$ slik at følgene holder:
$$\sum _{i=1}^n{a}_i(-2{)}^{i-1}=0$$

[lfe]

Svar: alle $n\not\equiv 1(\mathrm{mod}3)$
Dersom vi tar summen mod 3, så får vi at $3\mid \frac{n(n+1)}{2}$. Det betyr at $n\equiv 1(\mathrm{mod}3)$ ikke går.
Videre viser vi med induksjon at det går for alle andre $n$. For 2 og 3 har vi hhv. løsningene 2, 1 og 2, 3, 1.
Anta at vi har en løsning for $n\equiv 2(\mathrm{mod}3)$ der de første $\frac{n+1}{3}$ tallene i permutasjonen er alle tall kongruent med 2 mod 3 under n i stigende rekkefølge. Det er lett å vise at
\[
-9\sum_{k=0}^{\frac{n+1}{3} (3k+2)(-2)^k = 3(n+1)(-2)^{\frac{n+1}{3}+1}
\]
For å få en permutasjon for $n+3$ kan vi sette inn $n+3,n+2,n+1$ etter tall $\frac{n+1}{3}$. Dette forskyver tallene bak med 3 plasser og bevarer egenskapene med 2 mod 3 tall i begynnelsen av permutasjonen. Summen av tallene som forskyves er lik minus summen av de $\frac{n+1}{3}$ første tallene i permutasjonen, altså \( -\sum_{k=0}^{\frac{n+1}{3} (3k+2)(-2)^k \). Forskyvelsen blir det samme som å legge til \(9\sum_{k=0}^{\frac{n+1}{3} (3k+2)(-2)^k \). Tallene vi setter inn gir oss $(n+3)(-2{)}^{\frac{n+1}{3}+1}+(n+3)(-2{)}^{\frac{n+2}{3}+2}+(n+1)(-2{)}^{\frac{n+1}{3}+3}=3(n+1)(-2{)}^{\frac{n+1}{3}+1}$. Dermed er summen uendret.

Vi kan gjøre det samme for å vise induksjonssteget for $n\equiv 0(\mathrm{mod}3)$