Abel maraton

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

lfe
Cayley
Cayley
Innlegg: 80
Registrert: 30/11-2023 16:16
Sted: Trondheim

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
Noether
Noether
Innlegg: 25
Registrert: 25/04-2024 12:57
Sted: Abelmaraton

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
Noether
Noether
Innlegg: 25
Registrert: 25/04-2024 12:57
Sted: Abelmaraton

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
Fibonacci
Fibonacci
Innlegg: 4
Registrert: 09/09-2024 11:41

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.
Sist redigert av noaherkul1234567890 den 25/10-2024 21:29, redigert 1 gang totalt.
noaherkul1234567890
Fibonacci
Fibonacci
Innlegg: 4
Registrert: 09/09-2024 11:41

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
Noether
Noether
Innlegg: 23
Registrert: 13/12-2023 07:55

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
Noether
Noether
Innlegg: 23
Registrert: 13/12-2023 07:55

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
Fibonacci
Fibonacci
Innlegg: 4
Registrert: 09/09-2024 11:41

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$
Sist redigert av noaherkul1234567890 den 28/10-2024 21:24, redigert 1 gang totalt.
noaherkul1234567890
Fibonacci
Fibonacci
Innlegg: 4
Registrert: 09/09-2024 11:41

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
Cayley
Cayley
Innlegg: 80
Registrert: 30/11-2023 16:16
Sted: Trondheim

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
Cayley
Cayley
Innlegg: 80
Registrert: 30/11-2023 16:16
Sted: Trondheim

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
Noether
Noether
Innlegg: 25
Registrert: 25/04-2024 12:57
Sted: Abelmaraton

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
Noether
Noether
Innlegg: 25
Registrert: 25/04-2024 12:57
Sted: Abelmaraton

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\}.$
Svar