La $a_1,a_2,\cdots ,a_8$ være positive heltall og definer $N=\prod_{i>j}(a_i-a_j)$.
$N$ er altså produktet av alle mulige differenser mellom de åtte heltallene. For eksempel for
fire tall $a_1,a_2,a_3,a_4$ vil $N=(a_4-a_1)(a_4-a_2)(a_4-a_3)(a_3-a_1)(a_3-a_2)(a_2-a_1)$
Oppgaven er nå å finne det største tallet $D$ som alltid vil dele $N$ for alle mulige valg av
$a_1,\cdots ,a_8$.
Delelighetsnøtt
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
Ja, et eller flere av tallene kan være like, men alle heltall deler $0$ siden $n\cdot 0=0$, så dette gir ingen
informasjon om $D$.
informasjon om $D$.
Veldig usikker på om dette er riktig, men jeg tror jeg skal være inne på noe:
$A=\{ a_1,a_2,...,a_8\}$
Etter dueboksprinsippet vil minst $2$ av tallene i $A$ være kongruente modulo $7$, og dermed vil differensen mellom disse to være delelig på $7$, og dermed er også $N$ delelig på $7$. På samme måte vil vi også få minst tre par av tall fra $A$ hvor de to tallene i hvert par er kongruente modulo $5$, slik at deres differens blir delelig på $5$, og dermed vil også $N$ være delelig på $5^3$. I modulo $3$ vil vi få minst to tripler og ett par av tall fra $A$ hvor alle tallene i paret/triplene er kongruente modulo $3$. Dermed er også $N$ delelig på $3^7$. Gjør vi det samme i modulo $2$ ser vi at $N$ også er delelig på $2^{2\binom{4}{2}}=2^{12}$.
Jeg tok bare for med primtallene mindre enn $8$ her, siden jeg er ganske sikker på at delelighet på $4$ og $6$ kan oppstå hvor tilfeller for flere primtall sammenfaller i en og samme differens (hvis det i det hele tatt ga mening). Jeg tror derfor at $D=2^{12}\cdot 3^7\cdot 5^3\cdot 7=7\ 838\ 208\ 000$.
$A=\{ a_1,a_2,...,a_8\}$
Etter dueboksprinsippet vil minst $2$ av tallene i $A$ være kongruente modulo $7$, og dermed vil differensen mellom disse to være delelig på $7$, og dermed er også $N$ delelig på $7$. På samme måte vil vi også få minst tre par av tall fra $A$ hvor de to tallene i hvert par er kongruente modulo $5$, slik at deres differens blir delelig på $5$, og dermed vil også $N$ være delelig på $5^3$. I modulo $3$ vil vi få minst to tripler og ett par av tall fra $A$ hvor alle tallene i paret/triplene er kongruente modulo $3$. Dermed er også $N$ delelig på $3^7$. Gjør vi det samme i modulo $2$ ser vi at $N$ også er delelig på $2^{2\binom{4}{2}}=2^{12}$.
Jeg tok bare for med primtallene mindre enn $8$ her, siden jeg er ganske sikker på at delelighet på $4$ og $6$ kan oppstå hvor tilfeller for flere primtall sammenfaller i en og samme differens (hvis det i det hele tatt ga mening). Jeg tror derfor at $D=2^{12}\cdot 3^7\cdot 5^3\cdot 7=7\ 838\ 208\ 000$.
-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
Er enig i argumentet ditt for primtallene $3,5,7$, men for $2$ er det litt verre. Du må også passe på
eventuelle differanser som deler 4.
I tillegg burde du ha med et lite argument på hvorfor det alltid vil være den jevneste fordelingen av
tallene som gir den minste tilførselen av faktorer (for et av de aktuelle primtallene $2,3,5,7$).
Vi ser på primtallet $3$. Vi skal plassere de $8$ tallene i $3$ bokser. En boks for hver rest ved divisjon på $3$.
Her er det flere muligheter: $(3,3,2)$, $(5,2,1)$, $(4,2,2)$ (det er selvfølgelig flere enn dette).
En fordeling $(a,b,c)$ med $a+b+c=8$ gir en tilførsel på ${a\choose 2}+{b\choose 2}+{c\choose 2}$ treer faktorer.
Hvorfor er det fordelingen $(3,3,2)$ som minimerer dette uttrykket?
I denne oppgaven kan man teste alle mulighetene, så det er ikke nødvendig å bevise dette generelt, men
det er mulig.
Hvis du får ordnet dette så er det fremdeles et lite problem. Du har vist at tallet ditt må dele alle slike
produkter $N$, men du har ikke vist at dette er det største tallet som oppfyller kravet. Den enkleste måten
å gjøre dette på er å regne ut $N$ for $a_1, a_2,\cdots , a_8=1,2,\cdots , 8$. Denne verdien av $N$ må nemlig
være en øvre skranke for $D$.
eventuelle differanser som deler 4.
I tillegg burde du ha med et lite argument på hvorfor det alltid vil være den jevneste fordelingen av
tallene som gir den minste tilførselen av faktorer (for et av de aktuelle primtallene $2,3,5,7$).
Vi ser på primtallet $3$. Vi skal plassere de $8$ tallene i $3$ bokser. En boks for hver rest ved divisjon på $3$.
Her er det flere muligheter: $(3,3,2)$, $(5,2,1)$, $(4,2,2)$ (det er selvfølgelig flere enn dette).
En fordeling $(a,b,c)$ med $a+b+c=8$ gir en tilførsel på ${a\choose 2}+{b\choose 2}+{c\choose 2}$ treer faktorer.
Hvorfor er det fordelingen $(3,3,2)$ som minimerer dette uttrykket?
I denne oppgaven kan man teste alle mulighetene, så det er ikke nødvendig å bevise dette generelt, men
det er mulig.
Hvis du får ordnet dette så er det fremdeles et lite problem. Du har vist at tallet ditt må dele alle slike
produkter $N$, men du har ikke vist at dette er det største tallet som oppfyller kravet. Den enkleste måten
å gjøre dette på er å regne ut $N$ for $a_1, a_2,\cdots , a_8=1,2,\cdots , 8$. Denne verdien av $N$ må nemlig
være en øvre skranke for $D$.
Ålreit, ser nå at jeg selvfølgelig skal se etter differenser som er delelige med $4$ også. Med samme metode som tidligere får vi at minst fire differenser er delelige med $4$, men disse kan sammenfalle med differensene som er delelige med $2$, slik at dette bare tilfører $2^4$ til $D$. Da blir $D=2^{16}\cdot 3^7\cdot 5^3\cdot 7$, som også er lik minste mulige $N$ hvis jeg husker riktig.
Når det gjelder fordelingen du snakket om, har jeg ikke enda fått til noe særlig bra bevis for at det er den jevneste fordelingen som tilfører færrest mulige faktorer til $D$ (selv om ideen er ganske intuitiv). Jo forresten, når det gjelder fordelingen av primfaktoren $2$, så tror jeg at jeg fikk det til:
En fordeling $(a,b)$ med $a+b=8$ gir en tilførsel på $\binom{a}{2}+\binom{b}{2}$ toer faktorer.
Siden $b=8-a$ får vi: $\binom{a}{2}+\binom{b}{2}=\binom{a}{2}+\binom{8-a}{2}=\frac{a(a-1)}{2}+\frac{(8-a)(8-a-1)}{2}$, som er likningen til en andregradsfunksjon med bunnpunkt $a=4$, og dermed vil dette tilføre $12$ toer faktorer i $D$.
Når det gjelder fordelingen du snakket om, har jeg ikke enda fått til noe særlig bra bevis for at det er den jevneste fordelingen som tilfører færrest mulige faktorer til $D$ (selv om ideen er ganske intuitiv). Jo forresten, når det gjelder fordelingen av primfaktoren $2$, så tror jeg at jeg fikk det til:
En fordeling $(a,b)$ med $a+b=8$ gir en tilførsel på $\binom{a}{2}+\binom{b}{2}$ toer faktorer.
Siden $b=8-a$ får vi: $\binom{a}{2}+\binom{b}{2}=\binom{a}{2}+\binom{8-a}{2}=\frac{a(a-1)}{2}+\frac{(8-a)(8-a-1)}{2}$, som er likningen til en andregradsfunksjon med bunnpunkt $a=4$, og dermed vil dette tilføre $12$ toer faktorer i $D$.
-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
Nå ser det bra ut!
Når det kommer til å bevise at den jevneste fordelingen minimerer antall faktorer kan man for eksempel
gå frem som følger.
La $r_1,\cdots r_k\in\mathbb{N}$ med $r_1+r_2+\cdots+r_n=S$. Vi ønsker å minimere uttrykket
\begin{equation}
\binom{r_1}{2}+\binom{r_2}{2}+\cdots+\binom{r_n}{2}
\end{equation}
Påstand: Hvis $r_i<r_j$ så er $\binom{r_i}{2}+\binom{r_j}{2}\geq \binom{r_i+1}{2}+\binom{r_j-1}{2}$.
Benytter vi identiteten $\binom{a}{b}+\binom{a}{b+1}=\binom{a+1}{b+1}$ ser vi at
\[(\binom{r_j}{2}-\binom{r_j-1}{2})-(\binom{r_i+1}2-\binom{r_i}{2})=\binom{r_j-1}{1}-\binom{r_i}1=r_j-r_i-1\geq0\]
hvilket viser at påstanden stemmer. Det vi da har vist er at ved å trekke to av variablene nærmere hverandre uten
å forandre summen, så minsker vi uttrykket vårt. Fortsetter vi på denne måten vil vi til slutt finne minimumet.
Mer presist vil ulikheten være streng så lenge $|r_i-r_j|>1$, som medfører at minimumet er oppnådd når
$max\{|r_i-r_j|\, :\,1\leq i<j\leq n\}\leq 1$.
Det var nettopp disse utvalgene du brukte og som du sier så er dette resultatet ganske intuitivt!
Merk at idéen i dette beviset er veldig generell og er gjerne kjent som 'smoothing'; vi viser at
uttrykket vi er interessert i minker/øker når variablene trekkes nærmere hverandre, mens summen bevares.
Den kan blant annet bli brukt til å bevise AM-GM ulikheten.
Når det kommer til å bevise at den jevneste fordelingen minimerer antall faktorer kan man for eksempel
gå frem som følger.
La $r_1,\cdots r_k\in\mathbb{N}$ med $r_1+r_2+\cdots+r_n=S$. Vi ønsker å minimere uttrykket
\begin{equation}
\binom{r_1}{2}+\binom{r_2}{2}+\cdots+\binom{r_n}{2}
\end{equation}
Påstand: Hvis $r_i<r_j$ så er $\binom{r_i}{2}+\binom{r_j}{2}\geq \binom{r_i+1}{2}+\binom{r_j-1}{2}$.
Benytter vi identiteten $\binom{a}{b}+\binom{a}{b+1}=\binom{a+1}{b+1}$ ser vi at
\[(\binom{r_j}{2}-\binom{r_j-1}{2})-(\binom{r_i+1}2-\binom{r_i}{2})=\binom{r_j-1}{1}-\binom{r_i}1=r_j-r_i-1\geq0\]
hvilket viser at påstanden stemmer. Det vi da har vist er at ved å trekke to av variablene nærmere hverandre uten
å forandre summen, så minsker vi uttrykket vårt. Fortsetter vi på denne måten vil vi til slutt finne minimumet.
Mer presist vil ulikheten være streng så lenge $|r_i-r_j|>1$, som medfører at minimumet er oppnådd når
$max\{|r_i-r_j|\, :\,1\leq i<j\leq n\}\leq 1$.
Det var nettopp disse utvalgene du brukte og som du sier så er dette resultatet ganske intuitivt!
Merk at idéen i dette beviset er veldig generell og er gjerne kjent som 'smoothing'; vi viser at
uttrykket vi er interessert i minker/øker når variablene trekkes nærmere hverandre, mens summen bevares.
Den kan blant annet bli brukt til å bevise AM-GM ulikheten.
Forresten, hvor fant du denne oppgaven?-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
www.brilliant.org
Flere gode oppgaver på forskjellige nivåer, men også mange mindre gode oppgaver. I tillegg en noe uoversiktlig side.
Flere gode oppgaver på forskjellige nivåer, men også mange mindre gode oppgaver. I tillegg en noe uoversiktlig side.