Abel maraton

[Lil_Flip39]

Vis at hvis \(3\mid \sigma(n^2+n+1)\) hvor \(n\) er et naturlig tall, så er det mulig å dele divisorene til \(n^2+n+1\) inn i \(3\) grupper hvor produktet av tallene i hver gruppe er lik.

[lfe]

Vi har av ordner at alle primtall $p>3$ slik at $p\mid n^3-1$ er kongruente med 1 modulo 3 eller deler $n-1$. Siden $\gcd(n-1, n^2+n+1)\mid 3$, er alle primtallsdivisorer av $n^2+n+1$ over 3 kongruent med 1 modulo 3. Videre har vi at $3\mid \sigma(n^2+n+1)$ impliserer at $n^2+n+1$ har en primtallsdivisor slik at $3\mid \frac{p^{\alpha+1}-1}{p-1}$, der $\alpha = \nu_p(n^2+n+1)$ Siden $3\mid p-1$, så har vi av LTE at $3\mid \alpha + 1$. Det betyr at $3\mid \tau(n)$. Divisorene til $n^2+n+1$ danner dermed $\frac{\tau(n)}{2}$ ulike mengder på formen $\{d, \frac{n^2+n+1}{d}\}$. Siden $n^2+n+1$ ikke kan være et kvadrattall så er størrelsen på alle disse mengdene lik 2. Vi deler opp disse parene i 3 like store mengder. Produktene av elementene i parene i alle disse mengdene er lik $n^{\frac{\tau(n)}{6}}$.

[lfe]

La $m$ og $n$ være odde positive heltall. Et $m\times n$ brett er fylt med dominobrikker slik at nøyaktig én rute ikke er dekket. Denne ruten befinner seg i hjørnet øverst til venstre. Vi kan skli vertikale brikker vertikalt og horisontale horisontalt slik at de dekker den tomme ruten. Dette vil flytte rundt på hvor den tomme ruten er. Bevis at vi kan flytte den tomme ruten til alle hjørner av brettet.

[nilpotent1]

Vurdere fargeleggingen i $4$ farger slik at,
\[
\begin{array}{|c|c|c|c}
\hline
1 & 2 & 1 & \cdots \\
\hline
3 & 4 & 3 & \cdots \\
\hline
1 & 2 & 1 & \cdots \\
\hline
\vdots & \vdots & \vdots & \ddots
\end{array}
\]
La grafens noder være ruter med $1$ og kanter gjennom $(u, v)$ hvis en domino med $u$ går i retning av $v$ fra $u$, $v$ er naboen.

Lemma: Grafen har ikke sykler.

Hvis det er en sykel, da insiden av sykelen er det odde antall ruter, men det må være partisjonert i dominoer, motsigelse! $\square$

Nå se at hver domino som har farge $1$ legger til en unik kant til grafen, så det er $\left( \frac{n + 1}{2} \right) \left( \frac{m + 1}{2} \right) - 1$ kanter i grafen. Men, grafen har $\left( \frac{n + 1}{2} \right) \left( \frac{m + 1}{2} \right)$ noder, så det er en tre og derfor har alle noder.

Algoritmen for å gå til hjørnene er å traversere grafen. $\blacksquare$

[nilpotent1]

Ny Oppgave: Bevise at det eksiterer en permutasjon av de naturlige tallene så summen av de første n er delelig på n.

[Lil_Flip39]

La denne permutasjonen av de naturlige tallene være \(a_1,a_2,\dots \), og la $S_n$ betegne summen av de første n leddene i følgen. La \(a_1\) være 1. Vi konstruerer permutasjonen induktivt. Anta vi har $a_1,\dots a_n$, og la $a$ være det minste tallet som ikke allerede er med i følgen. La $a_{n+2}=a$. Nå trenger vi å finne en $a_{n+1}$ slik at $n+1|S_{n+1}$ og $n+2|S_{n+2}$. Dette er mulig av CRT, siden $\gcd(n+1,n+2)=1$, og siden det er uendelig mange verdier som $a_{n+1}$ kan være, vil vi kunne unngå at et tall dukker opp flere ganger. Åpenbart vil hvert naturlig tall dukke opp, siden vi alltid velger det minste tallet som ikke har blitt valgt.

[Lil_Flip39]

Given $\triangle ABC$, whose all sides have different length. Point $P$ is chosen on altitude $AD$. Lines $BP$ and $CP$ intersect lines $AC, AB$ respectively and point $X, Y$.It is given that $AX=AY$. Prove that there is circle, whose centre lies on $BC$ and is tangent to sides $AC$ and $AB$ at points $X,Y$.

[lfe]

$\textbf{Påstand}$ $(AYDX)$
$\textit{Bevis.}$ La $BC\cap XY=Q$ og $XY\cap AD = Z$. Vi har at $-1=(Q, D; B, C)=(Q,Z;X,Y)$. Siden $\angle QDA =90^\circ$, så må $AD$ være vinkelhalveringslinjen til $\angle XDY$. Det er to mulig sirkler gjennom $A$ og $D$ slik at lengden $AX=AY$ korresponderer med vinkelen $\angle XDA$ og $ADY$. Disse to sirklene må ha lik radius. Det følger at $\measuredangle AXD =\measuredangle AYD$ eller $\measuredangle AXD = \measuredangle DYA$. Hvis vi har $\measuredangle AXD = \measuredangle DYA$, så følger det av $\measuredangle XDC=\measuredangle BDY$ at $\measuredangle ABD =\measuredangle BCA$, men det er umulig siden trekant $ABC$ har sider med ulik lengde. Dermed er $\measuredangle AXD =\measuredangle AYD$ som impliserer $(AYDX)$.$\square$

La $E$ være antipoden til $A$ med hensyn til $(AYDX)$. Vi har at $E$ ligger på $BC$ siden $AD\perp BC$. Videre følger det at sirkelen i $E$ med radius $EX=EY$ tangerer $AC$ og $AB$ i $X$ og $Y$.$\blacksquare$

[lfe]

Ny oppgave:
Nils er på punkt $(1,1)$ i planet. La origo være $O$. Nils kan hoppe mellom gitterpunkt så lenge følgende er oppfylt: hvis Nils hopper fra $A$ til $B$, så må arealet til trekant $AOB$ være $\frac{1}{2}$. Finn alle gitterpunkt med positive koordinater Nils kan hoppe til. Anta at Nils kan hoppe til punkt $(m,n)$. Vis at Nils kan hoppe fra $(1,1)$ til $(m,n)$ med mindre eller lik $|m-n|$ hopp.

[Lil_Flip39]

Svar: vi kan gå til alle punker \((x,y)\) hvor \(\gcd(x,y)=1\).
Vi starter med å bruke skolisse formelen, som gir at en trekant med et hjørne i origo må oppfylle \(|x_1y_2-x_2y_1|=1\) hvor \((x_1,y_1),(x_2,y_2)\) er de andre 2 hjørnene.
Dermed er det åpenbart at hvis \(\gcd(x,y)>1\) så kan ikke det punktet sammen med origo skape en trekant med areal \(\frac{1}{2}\). Vi bruker induksjon til å vise at alle punkter med \(\gcd(x,y)=1\) kan bli nått.
Vi bruker induksjon på \(|a-b|\), for punkter \((a,b)\).Base case for induksjonen er trivielt. Anta nå at vi kan nå alle punkter \((x,y)\) slik at \(|x-y|<k\). Anta vi har et punkt \((a,b)\) slik at \(|a-b|=k\). WLOG, \(b>a\).
La oss si at vi er på punktet \((c+j,c)\) hvor \(j<k\). Da har vi lyst til å velge \(c,j\) slik at
\[|aj-kc|=|(c+j)a-(a+k)c|=1\]
Merk at \(\gcd(a,k)=\gcd(a,b)=1\), så vi kan velge \(j\) til å være inversen til \(a\pmod k\), og vi kan velge \(c=\frac{aj-1}{k}\) som er et heltall, og da vil vi ha
\[|(c+j)a-(a+k)c|=1\], som impliserer at \((0,0), (c,c+j), (a,b)\) former en trekant med areal \(\frac{1}{2}\) så vi kan hoppe til \((a,b)\). Dette viser induksjonen.

Merk at måten induksjonen funker på, trenger vi maks \(|m-n|\) steg for å nå et gitterpunkt \((m,n)\), siden hvert steg kan vi øke differansen mellom \(x\) og \(y\) verdien med minst \(1\).

[Lil_Flip39]

Let triangle \(ABC\) (\(AB < AC\)). A circle \((O)\) passes through \(B\) and \(C\), and it intersects \(AC\) and \(AB\) at \(E\) and \(F\), respectively. Let \(H\) be the intersection of \(BE\) and \(CF\). Points \(P\) and \(Q\) are the intersections of the circumcircles \((OFE)\) and \((BHC\)), respectively. Prove that \(OQ\), \(PH\), and \(EF\) are concurrent on the circle \((ABC)\).

[lfe]

Vi bruker miquelinversjon.
La $BC\cap EF = D$. La $M$ være miquelpunktet til $BCEF$. La $EF$ skjære $(ABC)$ i $K$ og $L$, der $K$ er på samme side av $AO$ som $P$. La $\phi$ være miquelinversjon i $M$. Det er velkjent at $\phi(A)=D$, $\phi(B)=E$, $\phi(C)=F$ og $\phi(O)=H$. Det følger at $(BCH)$ og $(EFO)$ byttes under $\phi$. Dermed er $\phi(P)=Q$. Videre byttes $(ABC)$ og $EF$. Det betyr at $\phi(K)=L$.

La $K'$ være skjæringen mellom $PO$ og $(ABC)$ som ligger på samme side av $AO$ som $K$. La $L'$ være symmetrisk definert.
$\textbf{Påstand:}$ $(K'PHM)$ og $(L'QMH)$
$\textit{Bevis.}$ Vi inverterer med hensyn på $(ABCD)$. Det er velkjent at $H$ sendes til $M$. Det betyr at $(BCH)$ sendes til $(ABC)$. Det følger at $(K'PHM)$. Av symmetri er også $(L'QMH)$. $\square$

Av epp er $(KLPQ)$.
$\textbf{Påstand:}$ $A$ er senter av $(KLPQ)$
$\textit{Bevis.}$ Vinkeljakt: $\measuredangle BFL=\measuredangle BCE = \measuredangle BGA =\measuredangle BLA$ Dermed tangerer $(BFL)$ $AL$. Det betyr av epp og symmetri er $AL^2 = BA\cdot FA =CA \cdot EA = AK^2$. $\square$

La $H'=PL\cap KQ$. Brocard i $BCEF$ gir $AO\perp DH$. Da gir brocard i $KLPQ$ at $H'=H$.

[lfe]

Ny oppgave:
La $\{a_n\}$ og $\{b_n\}$ være to ikke-konstante rasjonale følger slik at $(a_i-a_j)(b_i-b_j)$ er et heltall for allr $i$ og $j$. Vis at det eksisterer et rasjonalt tall $r$ slik at $r(a_i-a_j)$ og $\frac{b_i-b_j}{r}$ begger er heltall.

[Lil_Flip39]

Først, har vi et lemma: Hvis \(a,b\) er rasjonale tall, og \(ab, a+b\in \mathbb{Z}\) så er \(a,b\) heltall.
Bevis: Dette følger direkte av rasjonal rot teoremet på polynomet \((x-a)(x-b)\).
Nå, kan vi anta \(a_1=0\), siden vi kan endre hele følgen med en konstant. Vi antar også at \(a_i,b_i\) er skrevet på simplest form. Dermed følger det at \(a_ib_i\) er et heltall for alle \(i\).
Påstand: \(a_ib_j\) er et heltall for alle \(i,j\).
Nå, har vi \((a_i-a_j)(b_i-b_j)=a_ib_i+a_jb_j-a_jb_i-a_ib_j\), men siden \(a_ib_i\) er heltall så har vi \(a_ib_j+a_jb_i\in \mathbb{Z}\). Nå, har vi da av lemma at \(a_ib_j, a_jb_i\in \mathbb{Z}\) som er det vi ville vise.

Herifra, så ser vi at ethvert primtall som deler nevneren til \(a_i\) for en \(i\) må være en divisor av \(b_j\) for alle \(j\), som impliserer at mengden primtall som deler nevneren til en eller annen \(a_i\) er endelig,
og potensene til primtallene må også åpenbart være endelig. La da produktet at alle disse primtallspotensene være \(x\). På samme måte, har vi også en mengde primtall som er endelig, som inneholder alle primtall
som deler nevneren til \(b_j\) for alle \(j\), og potensen til primtallene er begrenset. La produktet av disse primtallspotensene da være \(y\). La \(r=\frac{x}{y}\), dette funker, fordi \(y\) er en divisor av alle tellerne til \(a_i\), og \(x\)
er en divisor av alle \(b_j\).

[Lil_Flip39]

Let $a_1$ be a positive integer and $a_n = \sum_{i=1}^{n-1} \gcd(n, a_i)$ for any $n\geq 2$. Prove that $a_{n+1} \leq a_n$ for infinitely many $n$.