La $a_{i,j}$ være tallet i rad i kolonne j. La $v_{i,k}(j) = a_{i,j}+a_{k,j}$ og $w_{i,k}(j) = \frac{a_{i,j}+a_{k,j}}{2}$. Vi viser først en påstand.
$\textbf{Påstand:}$ Hvis vi ser på radene modulo 2, så eksisterer det to rader med like tall på 7 av plassene.
$\textit{Bevis:}$ Vi sier at differansen mellom to rader er antall kolonner hvor de har ulike tall modulo 2. Vi ser at $v_{i,k}(j) = 1$ hviss rad i og rad k har to ulike tall i kolonne j. Vi summerer nå over alle differansene mellom radene:
\[
\sum_{j=1}^{13} \sum_{1\leq i < k \leq 13} v_{i,k}(j) =\sum_{j=1}^{13} f(j)(13-f(j)) \leq 13\cdot (6\cdot 7)
\]
Her er $f(j)$ lik antall enere modulo 2 i kolonne j. Vi har at $\sum_{1\leq i < k \leq 13} v_{i,k}(j) = f(j)(13-f(j))$ fordi hver $v_{i,k}(j) =1$ korresponderer med et valg av ener og et valg av nuller. Antall valg av to rader er $\binom{13}{2} = 78$. Vi har altså at gjennomsnittsdifferansen mellom to rader er mindre eller lik $\frac{13\cdot 6\cdot 7}{78} = 7$. Det betyr at det eksisterer to rader med differanse 6 eller mindre, eller så er differansen mellom to rader alltid nøyaktig 7. Hvis det eksisterer to rader med differanse 6 eller mindre så er de like i 7 av kolonnene.
Det holder nå å vise at det ikke er mulig at alle radene innbyrdes har differanse 7. Vi kan tenke på radene som binærstrenger. Differansen mellom to rader er da lik hamming-avstanden mellom deres korresponderende binærstrenger. La $g$ være en funksjon som gir antall enere i en binærstreng. Vi har da at differansen mellom binærstreng x og y er $g(x\oplus y) = g(x)+g(y)-2g(x\land y) = 7$ for alle x og y. La oss si at vi har tre binærstrenger x, y og z. Da vet vi at en av $g(x) + g(y)$, $g(y)+g(z)$ eller $g(z)+g(x)$ er delelig på 2. UTAG anta at det er $g(x)+g(y)$. Dette er en motsigelse fordi $g(x)+g(y)\equiv g(x\oplus y) =7 \pmod 2$. Dermed er påstanden vist.
Vi kan nå ta fatt på oppgaven. Av påstanden ovenfor kan vi UTAG anta at $a_{1,j} \equiv a_{2,j} \pmod 2$ for $1\leq j \leq 7$. Da er $w_{1,2}(j)$ også et heltall. Det følger av EGZ teoremet på disse $2\cdot 4-1$ tallene at det eksisterer $w_{1,2}(j_1)$, $w_{1,2}(j_2)$, $w_{1,2}(j_3)$ og $w_{1,2}(j_4)$. Slik at summen deres er delelig på 4. Dermed har vi at
\[
0 \equiv 2\sum_{k=1}^4 w_{1,2}(j_k) \equiv \sum_{k=1}^4 v_{1,2}(j_k) \pmod 8
\]
Kombomaraton
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Observer at mengden plan [tex]R = {x+y+z-n=0 | n \in [1,3n] [/tex]
Oppfyller kriteriene.
AFMS det går ann med 3n-1 plan, hver med ligning [tex]R_i | a_ix+b_i y +c_i z - k_i= 0[/tex]
Observer at hver k_i er ikkenull av antagelsen om at planene ikke går igjennom (0,0,0).
Vi tar for oss produktet [tex]\prod_1^{3n} (a_i x+b_i y +c_i z -k_i) * (x+y+z)[/tex]
Dette polynomet har forhåpentligvis grad 3n, hvis ikke sliter vi. Tar vi videre for oss koordinataksene får vi tre mengder på størrelse n+1.
Om [tex]x^n y^n z^n[/tex] finnes i utvidelsen vil polynomet ha et ikkenullpunkt i de 3 koordinataksene, som vil være en motsigelse, siden vi ved å anta planene dekket gitterpunktene også antok det er et polynom med det punktet som nullpunkt.
Om koefissienten til [tex]x^n y^n z^n[/tex] ikke er null kan vi bare legge til [tex]k \prod_{i=0} ^{i=n} (x-i)(y-i)(z-i)[/tex], og polynomet får koefissienten ikkenull, og er likt på alle gitterpunktene. Vi bruker da CNS, og får en motsigelse
Oppfyller kriteriene.
AFMS det går ann med 3n-1 plan, hver med ligning [tex]R_i | a_ix+b_i y +c_i z - k_i= 0[/tex]
Observer at hver k_i er ikkenull av antagelsen om at planene ikke går igjennom (0,0,0).
Vi tar for oss produktet [tex]\prod_1^{3n} (a_i x+b_i y +c_i z -k_i) * (x+y+z)[/tex]
Dette polynomet har forhåpentligvis grad 3n, hvis ikke sliter vi. Tar vi videre for oss koordinataksene får vi tre mengder på størrelse n+1.
Om [tex]x^n y^n z^n[/tex] finnes i utvidelsen vil polynomet ha et ikkenullpunkt i de 3 koordinataksene, som vil være en motsigelse, siden vi ved å anta planene dekket gitterpunktene også antok det er et polynom med det punktet som nullpunkt.
Om koefissienten til [tex]x^n y^n z^n[/tex] ikke er null kan vi bare legge til [tex]k \prod_{i=0} ^{i=n} (x-i)(y-i)(z-i)[/tex], og polynomet får koefissienten ikkenull, og er likt på alle gitterpunktene. Vi bruker da CNS, og får en motsigelse
In a mathematical challenge, positive real numbers $a_{1}\geq a_{2} \geq ... \geq a_{n}$ and an initial sequence of positive real numbers $(b_{1}, b_{2},...,b_{n+1})$ are given to Secco. Let $C$ a non-negative real number. In a sequence $(x_{1},x_{2},...,x_{n+1})$, consider the following operation:
Subtract $1$ of some $x_{j}$, $j \in \{1,2,...,n+1\}$, add $C$ to $x_{n+1}$ and replace $(x_{1},x_{2},...,x_{j-1})$ for $(x_{1}+a_{\sigma (1)}, x_{2}+a_{\sigma (2)}, ..., x_{j-1}+a_{\sigma (j-1)})$, where $\sigma$ is a permutation of $(1,2,...,j-1)$.
Secco's goal is to make all terms of sequence $(b_{k})$ negative after a finite number of operations. Find all values of $C$, depending of $a_{1}, a_{2},..., a_{n}, b_{1}, b_{2}, ..., b_{n+1}$, for which Secco can attain his goal.
Subtract $1$ of some $x_{j}$, $j \in \{1,2,...,n+1\}$, add $C$ to $x_{n+1}$ and replace $(x_{1},x_{2},...,x_{j-1})$ for $(x_{1}+a_{\sigma (1)}, x_{2}+a_{\sigma (2)}, ..., x_{j-1}+a_{\sigma (j-1)})$, where $\sigma$ is a permutation of $(1,2,...,j-1)$.
Secco's goal is to make all terms of sequence $(b_{k})$ negative after a finite number of operations. Find all values of $C$, depending of $a_{1}, a_{2},..., a_{n}, b_{1}, b_{2}, ..., b_{n+1}$, for which Secco can attain his goal.
La $P = \prod_{i=1}^{n} (1+a_i)$. Da kan Secco nå sitt mål hviss $C< \frac{1}{P}$.
Vi viser først at $C<\frac{1}{P}$ er nødvendig.
La $\phi (x_1, \dots, x_{n+1}) = x_{n+1} + C\sum_{k=1}^n \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) x_k$.
Hvis Secco gjør et trekk på $j < n+1$ med en permutasjon $\sigma$ så er endringen lik
\[
\Delta \phi =C+C\sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{\sigma (k)} - C\prod_{i=1}^{j-1} (1+a_i)
\]
Dersom $j=n+1$, så er endringen
\[
\Delta \phi = C-1 + C\sum_{k=1}^n \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{\sigma (k)}
\]
Av omstokkingsulikheten er
\[
\min_{\sigma} \sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{\sigma (k)} = \sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{k}
\]
Videre har vi at
\[
C + C\sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{k} = C\prod_{i=1}^{j-1} (1+a_i)
\]
Dermed er $\Delta \phi \geq 0$ for $j<n+1$.
For $j=n+1$ har vi
\[
\Delta \phi \geq C-1 + C\sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{k}= C-1 + C(P-1) = CP-1
\]
Det starter med at $\phi (b_1,\dots, b_{n+1}) >0$ siden $b_i>0$ for alle $1\leq i \leq n+1$
Målet til Secco er å nå $x_i <0$ for alle $1\leq i \leq n+1$ som gir $\phi (x_1,\dots, x_{n+1}) < 0$. Hvis $C\geq \frac{1}{P}$, så er $CP-1\geq 0$. Det betyr at $\Delta \phi \geq 0$ for alle valg av $j$, noe som gjør målet til Secco umulig.
Nå viser i en strategi for Secco å nå målet sitt gitt at $0\leq C < \frac{1}{P}$. Strategien gjør tallene negative fra høyre til venstre. Videre bruker vi identitetspermutasjonen i alle trekk.
Start med å gjøre trekket $j=n+1$, $t_{n+1}$ ganger. Vi bestemmer $t_n+1$ senere.
La $t_i$ være antall ganger vi gjør trekket $j=i$. Ved steg $k$ gjør vi trekk $j=k$, $t_k$ ganger. La $U_k = \sum_{i=k+1}^{n+1} t_i$. Vi lar rekursivt $t_k = \lfloor b_k + a_kU_k \rfloor + 1 \leq b_k + a_kU_k + 1$. Det gir oss at
\[
U_0 \leq Pt_{n+1} + \sum_{k=1}^{n} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) (b_k+1)
\]
Etter steg $k$, er garantert $x_k, \dots, x_n$ negative. Det holder dermed å vise at $x_{n+1}$ er negativ etter steg 1. Vi har etter steg 1
\[
x_{n+1}= b_{n+1} +C(U_0)-t_{n+1} \leq b_{n+1} +C(\sum_{k=1}^{n} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) (b_k+1) + (CP-1)t_{n+1}
\]
Siden $CP-1 < 0$ kan vi garantere $x_{n+1}<0$ ved å velge stor nok $t_{n+1}$.
Vi viser først at $C<\frac{1}{P}$ er nødvendig.
La $\phi (x_1, \dots, x_{n+1}) = x_{n+1} + C\sum_{k=1}^n \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) x_k$.
Hvis Secco gjør et trekk på $j < n+1$ med en permutasjon $\sigma$ så er endringen lik
\[
\Delta \phi =C+C\sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{\sigma (k)} - C\prod_{i=1}^{j-1} (1+a_i)
\]
Dersom $j=n+1$, så er endringen
\[
\Delta \phi = C-1 + C\sum_{k=1}^n \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{\sigma (k)}
\]
Av omstokkingsulikheten er
\[
\min_{\sigma} \sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{\sigma (k)} = \sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{k}
\]
Videre har vi at
\[
C + C\sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{k} = C\prod_{i=1}^{j-1} (1+a_i)
\]
Dermed er $\Delta \phi \geq 0$ for $j<n+1$.
For $j=n+1$ har vi
\[
\Delta \phi \geq C-1 + C\sum_{k=1}^{j-1} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) a_{k}= C-1 + C(P-1) = CP-1
\]
Det starter med at $\phi (b_1,\dots, b_{n+1}) >0$ siden $b_i>0$ for alle $1\leq i \leq n+1$
Målet til Secco er å nå $x_i <0$ for alle $1\leq i \leq n+1$ som gir $\phi (x_1,\dots, x_{n+1}) < 0$. Hvis $C\geq \frac{1}{P}$, så er $CP-1\geq 0$. Det betyr at $\Delta \phi \geq 0$ for alle valg av $j$, noe som gjør målet til Secco umulig.
Nå viser i en strategi for Secco å nå målet sitt gitt at $0\leq C < \frac{1}{P}$. Strategien gjør tallene negative fra høyre til venstre. Videre bruker vi identitetspermutasjonen i alle trekk.
Start med å gjøre trekket $j=n+1$, $t_{n+1}$ ganger. Vi bestemmer $t_n+1$ senere.
La $t_i$ være antall ganger vi gjør trekket $j=i$. Ved steg $k$ gjør vi trekk $j=k$, $t_k$ ganger. La $U_k = \sum_{i=k+1}^{n+1} t_i$. Vi lar rekursivt $t_k = \lfloor b_k + a_kU_k \rfloor + 1 \leq b_k + a_kU_k + 1$. Det gir oss at
\[
U_0 \leq Pt_{n+1} + \sum_{k=1}^{n} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) (b_k+1)
\]
Etter steg $k$, er garantert $x_k, \dots, x_n$ negative. Det holder dermed å vise at $x_{n+1}$ er negativ etter steg 1. Vi har etter steg 1
\[
x_{n+1}= b_{n+1} +C(U_0)-t_{n+1} \leq b_{n+1} +C(\sum_{k=1}^{n} \left ( \prod_{i=1}^{k-1} (1+a_i) \right ) (b_k+1) + (CP-1)t_{n+1}
\]
Siden $CP-1 < 0$ kan vi garantere $x_{n+1}<0$ ved å velge stor nok $t_{n+1}$.
Last edited by lfe on 02/09-2025 20:05, edited 2 times in total.
Denne oppgaven var kanskje litt for vanskelig. Ny oppgave:
10 aper har 60 bananer. Hver ape har minst 1 banan og to aper har ikke samme antall bananer. Vis at alle grupper av 6 aper kan fordele sin bananer blant de andre 4 apene slik at hver av dem har et likt antall bananer.
10 aper har 60 bananer. Hver ape har minst 1 banan og to aper har ikke samme antall bananer. Vis at alle grupper av 6 aper kan fordele sin bananer blant de andre 4 apene slik at hver av dem har et likt antall bananer.
-
Lil_Flip39
- Cantor
- Posts: 116
- Joined: 25/04-2024 12:57
- Location: Oslo
OiOiOi dette var en tøff en!Påstand: En apekatt kan ikke ha mer enn \(15\) bananer.
Bevis: Anta de andre apekattene har minimal mulig bananer, og da har de andre apekattene minst \(1+2+\dots +9=45\) bananer, så den siste apekatten har maks \(15\) bananer.
Nå, legg merke til at siden alle de \(4\) apekattene har mindre enn \(15=60/4\) bananer, følger det at de kan fordele bananene sine slik at apekattene får akkurat \(15\) bananer hver.
-
Lil_Flip39
- Cantor
- Posts: 116
- Joined: 25/04-2024 12:57
- Location: Oslo
]Let $n$ be a positive integer. There are $n$ ants walking along a line at constant nonzero speeds. Different ants need not walk at the same speed or walk in the same direction. Whenever two or more ants collide, all the ants involved in this collision instantly change directions. (Different ants need not be moving in opposite directions when they collide, since a faster ant may catch up with a slower one that is moving in the same direction.) The ants keep walking indefinitely.
Assuming that the total number of collisions is finite, determine the largest possible number of collisions in terms of $n$.
Assuming that the total number of collisions is finite, determine the largest possible number of collisions in terms of $n$.