Kombomaraton

[Lil_Flip39]

LIkt som Abelmaraton, bare utelukkende kombinatorikk
Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$

[popdit]

Svaret er $\fbox{$k=2n-1$}$.

Vi viser først at $d\leq 2n-1$. La hver $a_i$ være sin egen gruppe og slå grupper sammen helt til vi har $m$ grupper $g_1, g_2, \ldots, g_m$ som oppfyller $g_i+g_j>1$ for $i \neq j$. Da har vi at
\begin{align*}
n &= g_1+g_2+\ldots g_m \\
2n &= (g_1 + g_2) + (g_2 + g_3) + \ldots (g_m +g_1) \\
&> 1+1+\ldots1 \\
&= m
\end{align*}
Dette tilsier at $m\leq 2n-1$. For å vise at det er nødvendig med $2n-1$ elementer kan vi sette
\[
a_1=a_2=\ldots=a_{2n-1}=\frac{n}{2n-1}
\]
og vi er ferdig.

[popdit]

$\underline{\text{Ny oppgave:}}$
Det er endelig mange mynter i Tristan Amadeus sin lommebok. Verdien på myntene er positive heltall, og de er parvis distinkte. Er det mulig å at Tristan Amadeus har en lommebok som er slik at han har nøyaktig 2020 forskjellige måter å velge mynter, slik at summen av de valgte myntene er 2020?

[TorsteinBM]

hvis vi ser på et utvalg av $n$ mynter har vi $2^{n}$ forskjellige valg.
dermed hvis vi velger myntene ${1, 2, ..., 11}$ har vi $2048$ valg, dette betyr at hvis vi velger ${1, 2, ...,10, 11, 1954, 1955, ..., 2019, 2020}$ har vi $2048$ måter å få $2020$ på.
hvis vi ser på antall måter å få sum av myntene til å bli 0 til 6 får vi totalt 14 måter. Det betyr og at det er 14 måter å få tallene 60 til 66 på siden den 11. trekantsummen er 66.
hvis vi derfor fjærner den additive inversen til $0$ til $6$ og $60$ til $66 \quad mod \hspace{1mm} 2020$ får vi $2048-28 = 2020$ måter å få summen av mynter til å bli 2020.
dvs. med myntene ${1, 2, ..., 10, 11, 1961, 1962, ..., 2012, 2013}$ kan Tristan Amadeus få sumen av mynter til å bli $2020$ på $2020$ forskjellige måter.

Shamener

[TorsteinBM]

Andreas og Bnotøy spiller et spill på et $7\times 7$ brett. Alle brikker er én rute stor. Andreas starter med en brikke nederst til venstre og en øverst til høyre og Bnotøy har to brikker i de gjenstående hjørnene.
Andreas og Bnotøy spiller på tur hvor de på sin tur må velge én av sine to brikker og kan flytte den til en av rutene grensende vartikalt eller horisontalt. Andreas vinner dersom brikkene hans grenser vertikalt eller horisontalt.
Har Andreas en vinnende strategi dersom han starter? og har han det hvis Bnotøy starter?

[Lil_Flip38]

Del 1: Bnotøy vinner
Del 2: Andreas vinner
For del 1 av oppgaven, tenk deg at brikkene til Andreas er tårn fra sjakk. Bnotøy vinner fordi han kan alltid plassere brikkene sine i skjæringen av radene og kolonnene som blir truet av tårnene. Da er det åpenbart.
For del 2, starter vi med et lemma:
Hvis brikkene til Bnotøy og Andreas former følgene konfigurasjon:


Vinner Andreas.
Bevis: fargelegg brettet svart og hvit. Observer at Andreas og Bnotøy sine brikker starter på samme farge.
Åpenbart vinner Andreas i den situasjonen hvis det er Bnotøy sin tur.
Anta for motsigelses skyld at det er Andreas sin tur. Dette vil implisere at Bnotøy gjorde det siste trekket for å komme inn i denne situasjonen. Observer at hver gang Bnotøy gjør et trekk, har Andreas og Bnotøy har forskjellig «partiet» på fargene under brikkene sine, så Siden brikkene i vår posisjon er på samme farge for både Andreas og Bnotøy, har vi en motsigelse.

Tilbake til oppgaven:
Strategien til Andreas er som følger: hvis Bnotøy flytter ned eller til venstre med en av sine brikker, flytter Andreas sin egen brikke som er øverst til høyre på samme måte. Motsatt for brikken til Andreas nederst til venstre. Da er det åpenbart at rektangelet som blir bestemt av Andreas sine brikker blir mindre og mindre, som impliserer at vi ender opp med konfigurasjonen over. Eneste tilfelle hvor dette ikke holder er hvis noen gang Andreas sine brikker ender opp på samme rad eller kolonne, så kan det ikke være at Bnotøy har brikker mellom dem, så han kan bare flytte dem mot hverandre og vinne.

[Lil_Flip38]

Ny oppgave:
Turbo the snail sits on a point on a circle with circumference $1$. Given an infinite sequence of positive real numbers $c_1, c_2, c_3, \dots$, Turbo successively crawls distances $c_1, c_2, c_3, \dots$ around the circle, each time choosing to crawl either clockwise or counterclockwise.
Determine the largest constant $C > 0$ with the following property: for every sequence of positive real numbers $c_1, c_2, c_3, \dots$ with $c_i < C$ for all $i$, Turbo can (after studying the sequence) ensure that there is some point on the circle that it will never visit or crawl across.

[TorsteinBM]

Svar: C = 1/2

nedreskranke: 1/2 funker
bevis: hvis vi alltid går mot starts possisjonen vil vi aldri nå motsatt side av sirkelen
øvreskranke: C > 1/2 funker ikke.
bevis: beviset er konstruksjon. Vi vet at det finnes en 1/2 < a < C, hvis vi da [tex]c_i = a[/tex] for odde i og [tex]c_i = 1/2[/tex] for par i vil vi alltid minimum dekke et nytt område på a-1/2 på hver odde i så vi kommer til å dekke hele sirkelen.
Shamener

[TorsteinBM]

Ny oppgave:
Tristan Amadeus har de første 100 bøkene i Harrie Totter bokserien. Vi kaller et par (i, j) revers dersom i < j og bok j kommer før bok i i bokhyllen hans, hvor i og j er utgivelses nummeret på boken.
Tristan Amadeus kaller bokhyllen sin god dersom for alle i, j, k er ikke både (i, j) og (j, k) reverse. Finn det største antallet reverse par i en god bokhylle.

[lfe]

Svaret er 50.
Det får vi for eksempel av \(2,1,4,3,6,5,...,100,99\).
Nå viser vi at 50 er maksimal.
La \(G\) være en graf med 100 noder markert fra 1 til 100.
Det er en kant mellom \(i,j\) dersom \(i,j\) er et revers par.
Fra oppgaven følger det at \(deg \, i\leq 1\) for alle \(i\).
Det gir oss at antall kanter maksimalt er \(\frac{1}{2} \sum_{i=1}^{100} deg \, i\)

[lfe]

Ny oppgave:
Tristan Amadeus tilbringer dessverre julen alene, som vanlig. For å more seg spiller han et spill med seg selv. Tristan Amadeus skriver ett heltall på hver av taggene til en 5 tagget julestjerne. Disse tallene summerer til 218374612837648132764821. Et trekk består av at Tristan Amadeus subtraherer 1 fra to nabotagger for så å legge til 2 på motstående tagg av disse to nabotaggene. Vis at Tristan Amadeus kan gjøre en rekke trekk slik at en tagg har tallet 218374612837648132764821. Vis også at taggen som til slutt har tallet 218374612837648132764821 er unik. Altså at startkonfigurasjonen bestemmer hvilken tagg som kan ende på 218374612837648132764821.

[Lil_Flip38]

Vi viser først at tallet bare kan ende opp på et hjørne.
La \(a_i\) være verdien på hjørne nr \( i\). Da påstår jeg at \(\sum ia_i \) er invariant (mod 5). Dette følger bare av å regne ut operasjonen, siden 2+3=5.
nå er resten av oppgaven triviell, siden man kan bare løse liknings system hvis vi introduserer \(b_i\), hvor mange ganger operasjonen blir brukt i hvert hjørne, og løser for \(b_i\) og viser at det er et heltall.

[Lil_Flip39]

Ny oppgave:
We have \(n \geq 2\) lamps \( L_{1}, . . . ,L_{n}\) in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp \( L_{i}\) and its neighbours (only one neighbour for \( i = 1\) or \( i =n\), two neighbours for other \( i\)) are in the same state, then \( L_{i}\) is switched off; – otherwise, \( L_{i}\) is switched on.
Initially all the lamps are off except the leftmost one which is on.

\( (a)\)Prove that there are infinitely many integers \( n\) for which all the lamps will eventually be off.
\( (b)\) Prove that there are infinitely many integers \( n\) for which the lamps will never be all off.

[TorsteinBM]

Oppgave a)
svar: alle $n=2^k$ fungerer
vi starter med å se på sekvensen første gangen den tredje lampen lyser opp, da vil sekvensen se slik ut
...
her ser vi at hvis du bare ser på de fire første får du at den speiles over midten som betyr at hvis $n=4$ vet vi at alt kommer til å lyse opp ettersom det er helt symmetrisk over midten så det blir det samme som om $n=2$ fungerer. Dette skjer på etter ett trekk til så $n=4$ blir ferdig på 3 trekk. hvis vi nå ser på $n=8$ får vi at etter 3 trekk ser sekvensen slik ut:

siden lampene til høyre for den fjerde lampen ikke kan bli påvirket ettersom vi bare er på tredje trekket. etter ett trekk til vil vi få:

og av samme argument som i stad er dette bare to $n=4$ cases som vi vet skjer etter 3 trekk.
så 8 er full etter 7 trekk
dette er bare illustrasjon av induksjon så hvis vi gjør det litt mer rigorøst
hvis vi har at det tar $2^k-1$ trekk å fylle $2^k$ lamper får vi at etter $2^k$ trekk på $2^{k+1}$ noder har vi at bare de to midterste lampene lyser opp og siden den er helt symmetrisk får vi at etter $2^k-1$ trekk til er $2^{k+1}$ lamper fullt lyst opp så vi har da at $2^{k+1}$ lamper er lyst opp på $2^{k+1}-1$ trekk så vi har vist induskjons steget og vi har allerede bevist grunntilfelle så det er uendelig mange n slik at n lamper vil være lyst opp.

Oppgave b)
svar: aller $2^k+1$ fungerer
hvis vi bruker resultatet fra a får vi at hvis vi har $2^k+1$ lamper vil bare de siste to lampene være lyst opp etter $2^k$ trekk som er det samme som etter ett trekk bare speilvendt så vi vet at det alle lampene aldri kommer til å lyse samtidig

[TorsteinBM]

ny oppgave:
A natural number is written in each box of the $13 \times 13$ grid area. Prove that you can choose $2$ rows and $4$ columns such that the sum of the numbers written at their $8$ intersections is divisible by $8$.