Abel maraton

[lfe]

La $n$ og $k$ være positive heltall. Vis at det for hver $k$ eksisterer $N$ slik at $n\geq N$ impliserer $\binom{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(\binom{n}{k})}<n$.
Bevis:
vi bruker legendre's formel.
Da får vi $v_p(\binom{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}\leqslant \frac{p-1(log_p(k)+log_p(n-k)-log_p(n))}{p-1}=log_p(\frac{(n-k)k}{n})\leqslant log_p(n)$ av AM-GM. Dette viser påstanden.
Nå har vi $\binom{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$, $\angle A$ is biggest. On the circumcircle of $\triangle 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 $\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 $\angle JBC = \angle DAC = \angle JXA$ og $\angle JCB = \angle EAB = \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 \geq 2$ hvor det eksisterer $x_1, x_2..., x_{n-1}$ som tilfredsstiller betingelsen hvis $0 < i < n$ og $0 < j < n, i\neq j$ og $n | 2i + j$ så $x_i < x_j$

[noaherkul1234567890]

Skrevet av Torstein.

Svaret er alle $n = 2^k$ for $k\geq 1$ og alle $n = 3\cdot 2^k$ for $k\geq 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\neq 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\geq 5$ er teite.

Bevis
Anta for motsigelse at $p\geq 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\neq 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$.$\square$

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$.$\square$


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 $ki_1, ki_2, \dots, ki_l, ki_1$ er en sykel i grafen til $kn$.$\square$

Fra Lemmaer 1, 2 og 3 er det klart at alle tall som ikke er på formen $2^k$ for $k\geq 1$ eller $3\cdot 2^k$ for $k\geq 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$.$\square$

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.
$\blacksquare$

[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.

$\textbf{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$.
$\textbf{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 \pmod{n}$

$\textbf{Lemma 2:}$ Det eksisterer alternerende multipler av $2^n$ og $5^n$ for alle naturlige tall $n$.
$\textbf{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} \pmod{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 \pmod{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 \pmod{k}$. En slik $r\geq 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)\phi(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)\neq 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^kp$ for stor nok $k$, hvor $p$ er odde primtall. Da er det balansert, så $2^kp+1$ er ubalansert. Siden $2^kp+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}\left\lfloor\frac{a_k}{k}\right\rfloor\] over all permutations $(a_1,\dots,a_n)$ of $\{1,\dots,n\}.$

[popdit]

Minste summen er $\fbox{$1+\left\lfloor\log_2(n)\right\rfloor$}.$

Vi kan oppnå dette med følgende konstruksjon:

Gitt $n$ finner vi $k$ slik at $2^k \leq 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 \leq n$ kan vi velge $a_i = i-1$, og vi kan se at denne konstruksjonen gir ønsket sum.

La
\[
g(n) = \min_{\sigma \in P_n} \left\{ \sum_{k=1}^n \left\lfloor \frac{\sigma(k)}{k} \right\rfloor\right\}
\]
Det er åpenbart at $g$ ikke synker. Vi skal vise med induksjon at følgende gjelder
$\hspace{5mm}\text{i}) \hspace{2.8mm}g(2^k)=k+1$
$\hspace{5mm}\text{ii}) \hspace{1.4mm}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\leq 2^k$. Det vil si at $a_j = 2^k$ for en $j\leq 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)\geq 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, \ldots, a_{2^k} = 1, 3, 2, 7, 4, 5, 6, \ldots, 2^k-1, 2^{k-1}, 2^{k-1}+1, \ldots, 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]

$\underline{\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$.