Abel maraton

[lfe]

La $n$ og $k$ være positive heltall. Vis at det for hver $k$ eksisterer $N$ slik at $n\ge N$ impliserer $(\genfrac{}{}{0ex}{}{n}{k})$ minst har $k$ ulike primdivisorer.

[Lil_Flip39]

FTSOC, anta $n$ har $m<k$ primfaktorer.
For å løse oppgaven bruker vi følgene lemma:
lemma:
$p^{v_p((\genfrac{}{}{0ex}{}{n}{k}))}<n$.
Bevis:
vi bruker legendre's formel.
Da får vi $v_p((\genfrac{}{}{0ex}{}{n}{k)})=v_p(n!)-v_p(k!)-v_p((n-k)!)=\frac{S_p(k)+S_p(n-k)-S_p(n)}{p-1}$ hvor $S_p(x)$ er siffersummen til $x$ i base $p$.
Nå får vi $\frac{S_p(k)+S_p(n-k)-S_p(n)}{p-1}⩽\frac{p-1(lo{g}_p(k)+lo{g}_p(n-k)-lo{g}_p(n))}{p-1}=lo{g}_p(\frac{(n-k)k}{n})⩽lo{g}_p(n)$ av AM-GM. Dette viser påstanden.
Nå har vi $(\genfrac{}{}{0ex}{}{n}{k})<n^m<n^{k-1}$ av lemma.
Det er lett å se at dette ikke holder for store nok $n$ motstigelse.

[Lil_Flip39]

Ny oppgave
In the triangle $ABC$, $\mathrm{\angle }A$ is biggest. On the circumcircle of $\mathrm{△}ABC$, let $D$ be the midpoint of $\widehat{ABC}$ and $E$ be the midpoint of $\widehat{ACB}$. The circle $c_1$ passes through $A,D$ and is tangent to $AC$ at $A$, the circle $c_2$ passes through $A,E$ and is tangent $AB$ at $A$. $c_1$ and $c_2$ intersect at $A$ and $P$. Prove that $AP$ bisects $\mathrm{\angle }BAC$.

Hint: Introduser skjæringen mellom $AP$ og $BC$

[noaherkul1234567890]

La $BD$ og $CE$ skjære i $J$ og merk at $J$ er $A$-utsenteret til $ABC$. La også $BD$ skjære $c_1$ igjen i $X$, og la $CE$ skjære $c_2$ igjen i $Y$.

Vi har at $\mathrm{\angle }JBC=\mathrm{\angle }DAC=\mathrm{\angle }JXA$ og $\mathrm{\angle }JCB=\mathrm{\angle }EAB=\mathrm{\angle }JYA$, så $X$, $Y$ og $A$ er kolineære og $XY\parallel BC$. Dermed gir Reims at $(DEXY)$ er syklisk, så $J$ er potenssenteret til $c_1$, $c_2$ og $(DEXY)$, og resultatet følger.

[noaherkul1234567890]

Ny oppgave:

Vi sier at et positivt heltall $a$ inneholder et positivt heltall $b$ dersom man kan stryke ut ett eller flere av sifrene i $a$ for å oppnå $b$. For eksempel har vi at $12345$ inneholder $234$, men ikke $154$.

Avgjør om det finnes en uendelig mengde av positive heltall slik at ingen elementer inneholder noen andre elementer.

[TorsteinBM]

Ved bruk av Kruskal's tree theorem får vi at det eksisterer et tall som er inneholdt i et annet

Hvis vi lar mengden av labels være {0, 1, 2,..., 8, 9} og gjør så hvert siffer bare kan sammenlignes med seg selv, og i tillegg gjør hvert tall om til en linjegraf hvor det første sifferet blir roten og hvor hvert siffer er koblet til det neste sifferet i tallet.

sier Kruskal's tree theorem at et tre er inf-embeddable i et annet som er det samme som at tallet det ene representerer er inneholdt i det andre

[TorsteinBM]

Ny Oppgave:
Bestem alle $n\ge 2$ hvor det eksisterer $x_1,x_2...,x_{n-1}$ som tilfredsstiller betingelsen hvis $0<i<n$ og $0<j<n,i\ne j$ og $n|2i+j$ så $x_i<x_j$

[noaherkul1234567890]

Skrevet av Torstein.

Svaret er alle $n=2^k$ for $k\ge 1$ og alle $n=3\cdot 2^k$ for $k\ge 0$.

For hvert positive heltall $n$, lager vi en graf med noder $1$, $2$, $\dots$, $n-1$, og sier at det er en rettet kant fra $i$ til $j\ne i$ dersom $n|2i+j$.
Vi skriver at et heltall $n$ er teit dersom det finnes en sykel i grafen.

Lemma 1
Alle primtall $p\ge 5$ er teite.

Bevis
Anta for motsigelse at $p\ge 5$ er et odde tall og at det finnes tall $x_1,\dots ,x_{p-1}$ som oppfyller kriteriet. . Vi ser at hver node har nøyaktig én inn-kant, fordi for hver odde $j$ vil $i=\frac{p-j}{2}$ gi $p|2i+j$ og for hver like $j$ vil $n-\frac{j}{2}$ gi $p|2i+j$, og siden $p\ne 3$ vil ingen av disse gi $j=i$. Dette gir også at hver node må ha en ut-kant, ettersom hver node har en inn-kant og ingen noder har flere enn en ut-kant (siden $j<p$). Vi har nå en graf der hver node har inn- og ut-grad lik $1$, så det vil finnes en sykel $i_1,i_2,\dots ,i_l,i_1$.$◻$

Lemma 2
Tallet $9$ er teit.

Bevis
Vi ser at $9|2\cdot 1+7$, at $9|2\cdot 7+4$ og at $9|2\cdot 4+1$, så $(1,7,4)$ danner en sykel i grafen til $9$.$◻$


Lemma 3
Dersom $n$ er teit, så er $kn$ teit for alle positive heltall $k$.

Bevis
Hvis $n$ er teit finnes det en sykel i grafen $i_1,i_2,\dots ,i_l,i_1$ til $n$, og da er det klart at $k{i}_1,k{i}_2,\dots ,k{i}_l,k{i}_1$ er en sykel i grafen til $kn$.$◻$

Fra Lemmaer 1, 2 og 3 er det klart at alle tall som ikke er på formen $2^k$ for $k\ge 1$ eller $3\cdot 2^k$ for $k\ge 0$ er teite.

Lemma 4
Dersom $n$ ikke er teit, er heller ikke $2n$ teit.

Bevis
I grafen til $2n$ vil ingen oddetall ha inn-grad $>0$ siden $2n|2i+j$ impliserer at $2|j$.
Dersom det var en sykel i grafen til $2n$ måtte den derfor ha bestått utelukkende av partall $2i_1,2i_2,\dots ,2i_l,2i_1$, men da ville $i_1,i_2,\dots ,i_l,i_1$ vært en sykel i grafen til $n$.$◻$

Vi ser at for $n=2$ oppfyller listen $1$ kriteriet, og for $n=3$ oppfyller listen $1,2$ kriteriet.
Av Lemma 4 er vi ferdige.
$◼$

[noaherkul1234567890]

Ny oppgave:

Et positivt heltall kalles alternerende dersom annenhvert siffer er av forskjellig paritet (når tallet er skrevet i titallssystemet). For eksempel er $12345$ og $3876901$ alternerende, mens $134$ og $742$ ikke er det.

Finn alle positive heltall $n$ slik at $n$ har et multippel som er alternerende.

[lfe]

Dersom et tall er delelig på 20, er de to siste siffrene partall. Vi ønsker å vise at alle tall som ikke er delelig på 20 har en multippel som er alternerende.

$\mathbf{\text{Lemma 1:}}$ Vi definerer følgen $\{a_n\}$ rekursivt. La $a_i=10a_{i-1}+10$ og $a_0=0$. For alle $k$ innbyrdes primisk med 10 eksisterer det uendelig mange $j$ slik at $k\mid a_j$.
$\mathbf{\text{Bevis:}}$
Åpenbart blir følgen $\{a_n\}$ etterhvert periodisk modulo $k$. La $f(x)=10x+10$. Siden inversen til $f$, $f^{-1}(x)=\frac{x-10}{10}$, eksisterer, må $\{a_n\}$ være periodisk. Dermed eksisterer uendelig mange $j$ slik at $a_j\equiv a_0(\mathrm{mod}n)$

$\mathbf{\text{Lemma 2:}}$ Det eksisterer alternerende multipler av $2^n$ og $5^n$ for alle naturlige tall $n$.
$\mathbf{\text{Bevis:}}$
Vi viser først lemma 2 for $2^n$. La $b_n$ være et alternerende positivt heltall med $n$ siffer blant $\{1,2,3,4\}$ slik at $2^n\mid b_n$. Vi skal nå vise med induksjon at det eksisterer mulige $b_n$ for alle naturlige tall $n$. Induksjonsgrunnlaget vårt er $2^1\mid 2=b_1$. Anta at $b_{n-1}$ er et alternerende tall på $n-1$ siffer blant $\{1,2,3,4\}$ der det fremste sifferet er 1 eller 2. Vi lar $b_n=b_{n-1}+x\cdot {10}^{n-1}+2y\cdot {10}^{n-2}$, der $x$ er lik 1 eller 2 basert på pariteten til det fremste sifferet i $b_{n-1}$ og $y$ er lik 0 eller 1 bestemt av om $b_n=b_{n-1}+x\cdot {10}^{n-1}$ er kongruent med 0 eller $2^{n-1}$ modulo $2^n$. Av induksjonshypotesesen er det nest fremste sifferet i $b_n$ mindre eller lik 4. Dermed har vi vist at det for alle $n$ eksisterer $b_n$.

For $5^n$ er beviset lignende. La $c_n$ være et alternerende positivt heltall med $n$ eller $n-1$ siffer (i $n-1$ tilfellether ser vi på tallet med 0 som første siffer) slik at $5^n\mid c_n$. Vi viser at $c_n$ eksisterer med induskjon. La $c_1=5$. Anta at $c_{n-1}$ eksisterer. Vi har at $c_{n-1}\equiv z\cdot 5^{n-1}(\mathrm{mod}{5}^n)$, der $z\in \{0,1,2,3,4\}$. Vi kan dermed konstruere $c_n=c_{n-1}+w\cdot {10}^{n-1}\equiv 0(\mathrm{mod}{5}^n)$, der $w\in \{0,2,4,6,8\}$ eller $w\in \{1,3,5,7,9\}$ basert på pariteten til det første sifferet i $c_{n-1}$. Det må eksistere en slik $w$ fordi både $\{0,2,4,6,8\}$ og $\{1,3,5,7,9\}$ danner komplette restklassesystemer modulo 5. Dermed er lemmaet også vist for $5^n$


Vi tar nå fatt på oppgaven. La $k$ være et positivt heltall innbyrdes primisk med 10. Av lemma 1 eksisterer det en alternerende multippel av $k$. Vi trenger derfor bare å se på tilfellene $2^n\cdot k$, $5^n\cdot k$ og $2\cdot 5^n\cdot k$.
Først konstruerer vi en alternerende multippel av $2^n\cdot k$. La de $n$ første siffrene være $b_n$. Dersom $b_n$ starter med et partall, setter vi på sifferet 1 foran. Videre kan vi av lemma 1 finne en lang NOK $a_j$ slik at $k\mid a_j$. Vi fester denne $a_j$ foran tallet vi nå har. La det tallet vi nå har være kongruent med $-2r(\mathrm{mod}k)$. En slik $r\ge 0$ eksisterer av at 2 ikke deler $k$. Dersom vi nå adderer tallet vi nå har med $\sum _{m=1}^{r}2\cdot {10}^{(m+2n)\varphi (k)}\equiv 2r$, får vi et tall som er alternerende og delelig på $2^n\cdot k$.

Konstruksjonen for et alternerende tall delelig på $5^n\cdot k$ er identisk med $c_n$. Dette tallet kan vi gange med 10 for å få et alternerende tall delelig på $2\cdot 5^n\cdot k$ siden $c_n$ er odde.

[lfe]

Ny oppgave:
Vi kaller et positivt heltall er balansert dersom det har partall mange ulike primtallsfaktorer. Vis at det eksisterer uendelig mange positive heltall $n$ slik at nøyaktig 2 av tallene $n$, $n+1$ $n+2$ og $n+3$ er balanserte.

[Lil_Flip39]

La $P(n)$ være lik antall balanserte i $n,n+1,n+2,n+3$.
La oss anta for motsigelse at $P(n)\ne 2$ for alle store nok $n$. Da er det lett å se at det $P(n)$ enten alltid er større eller mindre enn $2$, siden ellers må den "krysse" $2$.

1. $P(n)>2$ for store nok $n$.
Vi ser på $2^k$ for stor nok $k$. Da er det ubalansert, så $2^k+1$ er balansert. Siden $2^k+1$ er odde, vil da $2^{k+1}+2$ være ubalansert. Men da vil jo $P(2^{k+1})$ være mindre eller lik $2$, en motsigelse.

2. $P(n)<2$ for store nok $n$
Vi ser på $2^{k}p$ for stor nok $k$, hvor $p$ er odde primtall. Da er det balansert, så $2^{k}p+1$ er ubalansert. Siden $2^{k}p+1$ er odde, vil da $2^{k+1}p+2$ være balansert. Men da vil jo $P(2^{k+1}p)$ være større eller lik $2$, en motsigelse.

[Lil_Flip39]

For each integer $n\ge 1,$ compute the smallest possible value of $$\sum _{k=1}^n\lfloor \frac{a_k}{k}\rfloor$$ over all permutations $(a_1,\dots ,a_n)$ of $\{1,\dots ,n\}.$

[popdit]

Minste summen er $\boxed{1+\lfloor {\log }_2(n)\rfloor }.$

Vi kan oppnå dette med følgende konstruksjon:

Gitt $n$ finner vi $k$ slik at $2^k\le n<2^{k+1}$. For alle $l<k$ lar vi $a_{2^l}=2^{l+1}-1$, for $l=k$ lar vi $a_{2^l}=n$ og for alle andre indekser $i\le n$ kan vi velge $a_i=i-1$, og vi kan se at denne konstruksjonen gir ønsket sum.

La
$$g(n)=\underset{\sigma \in P_n}{min}\left\{\sum _{k=1}^n\lfloor \frac{\sigma (k)}{k}\rfloor \right\}$$
Det er åpenbart at $g$ ikke synker. Vi skal vise med induksjon at følgende gjelder
$\text{i})g(2^k)=k+1$
$\text{ii})g(2^k-1)=k$
Dersom vi viser dette, så følger svaret.

Vi starter med base-casen, og det er tydelig at $g(1)=1$ og $g(2)=2$ Vi antar at $g(2^{k-1})=k$, og ser på $g(2^k)$.

Det er tydlig at for alle permutasjoner av tallene $1$ til $2^k$, så er første halvdel av ønskede sum minst dersom den inneholder tallene $1$ til $2^{k-1}$, og vi vet at det finnes en permutasjon som gir at denne summen blir $k$.

Videre antar vi for motsigelse at $g(2^k)=k$. Da må vi ha at $a_i<i$ for alle $2^{k-1}<i\le 2^k$. Det vil si at $a_j=2^k$ for en $j\le 2^{k-1}$. Det vil si at første halvdel av summen vil øke med minst 1, og vi har at $g(2^k)>k$, som er en motsigelse. Dermed har vi at $g(2^k)\ge k$. Vi viser en konstruksjon for $g(2^k)=k+1$, konstruksjonen beskrevet i starten, som fullfører første delen av induksjonsbeviset:
$$a_1,a_2,\dots ,a_{2^k}=1,3,2,7,4,5,6,\dots ,2^k-1,2^{k-1},2^{k-1}+1,\dots ,2^k-2,2^k$$
Vi ser tydelig at alle 2-er potens indeksene bidrar til 1 hver i summen, så summen med denne permutasjonen blir $k+1$. For å fullføre induksjonsbeviset må vi vise at $g(2^k-1)=k$, og det funker med konstruksjonen gitt i starten, og vi er ferdig.

[popdit]

$\underset{―}{\text{Ny oppgave}:}$
La $b,n>1$ være heltall. Anta at for hvert heltall $k>1$ finnes det et heltall $a_k$ slik at $b-a_k^n$ er delelig med $k$. Vis at $b$ er på formen $c^n$ for et heltall $c$.