$\pm1\pm2\cdots\pm100$

[Brahmagupta]

Hvor mange forskjellige tall kan skrives på formen
$\pm1\pm2\pm3\pm\cdots\pm99\pm100$,
gitt at alle mulige kombinasjoner av fortegn er tillatt?

[PøttePott]

Et lurt tips når du skal løse sånne oppgaver som dette er å forsøke med mindre tall.
Prøv deg fram med bare 1 og 2 og se hvor mange ulike tall du får, derretter kan du prøve med 1,2 og 3 så med 1,2,3 og 4 osv. Du finner et mønster som du kan bruke til å lage en formel også anvender du den på en liste med de 100 første tallene.

Hint: Det er 4, 7 og 11 ulike tall for de 2, 3 og 4 første tallene.

[stensrud]

Alle mulige summer av $\pm1\pm2\cdots\pm100$ er kongruente modulo 2, da man ved å bytte et plusstegn med et minustegn eller motsatt legger til/trekker fra et partall. Den minste summen vi kan få er $\sum_{i=1}^{100}-i=-\binom{101}{2}=-5050$, så alle summer er partall. Vi kan legge til $2n$ til $-5050$ ved å bytte om pluss/minus foran tall som har sum $n$, og dermed kan vi lage alle partall fra og med $-5050$ til og med $5050$, så svaret er $\boxed{5051}$. Kan også generaliseres, som jeg ser PøttePott har hintet til allerede.

[Brahmagupta]

Alle mulige summer av $\pm1\pm2\cdots\pm100$ er kongruente modulo 2, da man ved å bytte et plusstegn med et minustegn eller motsatt legger til/trekker fra et partall. Den minste summen vi kan få er $\sum_{i=1}^{100}-i=-\binom{101}{2}=-5050$, så alle summer er partall. Vi kan legge til $2n$ til $-5050$ ved å bytte om pluss/minus foran tall som har sum $n$, og dermed kan vi lage alle partall fra og med $-5050$ til og med $5050$, så svaret er $\boxed{5051}$. Kan også generaliseres, som jeg ser PøttePott har hintet til allerede.

Ser bra ut dette! Du burde kanskje legge til et kort argument, hvorfor det for ethvert tall $0\leq n\leq5050$
faktisk er mulig å gjøre et passende utvalg fra $\{1,2,...,n\}$ slik at de utvalgte tallene summerer til $n$.
Det er ganske åpenbart at dette er mulig, men det er greit å nevne det.

[stensrud]

Påstand: for hver $0<n\leq5050$ er det mulig å gjøre et utvalg fra $M={1,2,...,100}$ slik at summen av de utvalgte elementene har sum lik $n$.

Bevis:

Hvis det er valgt elementer fra $M$ slik at summen av disse trukket fra $n$ er et tall som fortsatt finnes i, og ikke er valgt fra $M$, er vi ferdige. Vi bruker følgende algoritme:

1. $n$ mindre enn 101? Alle tall under 101 finnes i $M$, og vi er ferdige. Hvis ikke, velg 100 fra $M$.
2. $n-100$ mindre enn 100? Alle tall under 100 finnes i $M$, og vi er ferdige. Hvis ikke, velg 99 fra $M$.
3. $n-100-99$ mindre enn 99? Alle tall under 99 finnes i $M$, og vi er ferdige. Hvis ikke, velg 98 fra $M$.
$\vdots$

Ved å bruke denne algoritmen vil vi før eller senere få et utvalg fra $M$ med sum $n$, da $n\leq100+99+...+1$. Vi vil heller aldri få et negativt tall i algoritmen, siden den ved velge $k$ fra $M$ forutsetter at $n-(100+99+...+(k+1))\geq (k+1)$.$\blacksquare$

(Mye mer knotete enn jeg liker det. Hvordan ville du/noen andre gått fram for å vise det samme?)

[PøttePott]

Æsj jeg som trodde du faktisk trengte hjelp.... huff. Jeg så ikke kategorien, men nå som jeg alt har brukt tid på dette kan jeg jo fortelle deg min mer "simple" løsning (merk med simpel mener jeg ikke nødvendigvis "lettere" eller "bedre").

Som jeg hintet til tidligere vil antall løsninger øke med n+1 for det n-te tallet du adderer med så for 1 tall vil du ha 2 løsninger, 1. økning gir 2 flere løsninger, 2. økning gir 3 flere løsninger osv.
Med andre ord vil det totale antall løsninger starte med 2 og videre øke med 3, 4, 5 osv. for hvert tall vi tar med.
Dette betyr at antall unike tall du får er gitt ved rekken 2 + 2 + 3 + 4 ... 99 + 100. Dette kan man skrive om til formen
(1+1) + 2 + 3 ... + 98 + 99 + 100
1+ (1+99) + (2+98) + (3+97) ... (49+51) + 100 + 50
1 + 100*50 + 50 = 5051 unike løsninger.

Jeg lagde et python program som kan gjøre dette for deg.

number = 2
for i in range(1, 100):
[tex]\quad[/tex]number += i+1
print number

Programmet kan kjøres her:
http://pythontutor.com/visualize.html#mode=edit

[Brahmagupta]

Påstand: for hver $0<n\leq5050$ er det mulig å gjøre et utvalg fra $M={1,2,...,100}$ slik at summen av de utvalgte elementene har sum lik $n$.

Bevis:

Hvis det er valgt elementer fra $M$ slik at summen av disse trukket fra $n$ er et tall som fortsatt finnes i, og ikke er valgt fra $M$, er vi ferdige. Vi bruker følgende algoritme:

1. $n$ mindre enn 101? Alle tall under 101 finnes i $M$, og vi er ferdige. Hvis ikke, velg 100 fra $M$.
2. $n-100$ mindre enn 100? Alle tall under 100 finnes i $M$, og vi er ferdige. Hvis ikke, velg 99 fra $M$.
3. $n-100-99$ mindre enn 99? Alle tall under 99 finnes i $M$, og vi er ferdige. Hvis ikke, velg 98 fra $M$.
$\vdots$

Ved å bruke denne algoritmen vil vi før eller senere få et utvalg fra $M$ med sum $n$, da $n\leq100+99+...+1$. Vi vil heller aldri få et negativt tall i algoritmen, siden den ved velge $k$ fra $M$ forutsetter at $n-(100+99+...+(k+1))\geq (k+1)$.$\blacksquare$

(Mye mer knotete enn jeg liker det. Hvordan ville du/noen andre gått fram for å vise det samme?)

Jeg synes egentlig dette ser bra ut. Det var samme konstruksjon jeg hadde i tankene. En alternativ
måte å formulere seg på kan være som følger. La $0\leq n\leq5050$ være gitt og la $k>0$ være det minste
tallet slik at $s=n-(100+99+\cdots+k)>0$. Det følger at $0<s\leq k-1$ (ellers kunne $k$ blitt valgt mindre)
og dermed har vi funnet en lovlig representasjon av $n$; $n=100+99+\cdots+k+s$. Eksistensen til $k$
følger selvfølgelig fra at $n\leq 5050=1+2+\cdots+100$.

[Brahmagupta]

Som jeg hintet til tidligere vil antall løsninger øke med n+1 for det n-te tallet du adderer med så for 1 tall vil du ha 2 løsninger, 1. økning gir 2 flere løsninger, 2. økning gir 3 flere løsninger osv.
Med andre ord vil det totale antall løsninger starte med 2 og videre øke med 3, 4, 5 osv. for hvert tall vi tar med.
Dette betyr at antall unike tall du får er gitt ved rekken 2 + 2 + 3 + 4 ... 99 + 100. Dette kan man skrive om til formen
(1+1) + 2 + 3 ... + 98 + 99 + 100
1+ (1+99) + (2+98) + (3+97) ... (49+51) + 100 + 50
1 + 100*50 + 50 = 5051 unike løsninger.

Observasjonen din er selvfølgelig riktig, men kan du bevise at dette mønsteret stemmer og dermed
generalisere resultatet?

[PøttePott]

Som jeg hintet til tidligere vil antall løsninger øke med n+1 for det n-te tallet du adderer med så for 1 tall vil du ha 2 løsninger, 1. økning gir 2 flere løsninger, 2. økning gir 3 flere løsninger osv.
Med andre ord vil det totale antall løsninger starte med 2 og videre øke med 3, 4, 5 osv. for hvert tall vi tar med.
Dette betyr at antall unike tall du får er gitt ved rekken 2 + 2 + 3 + 4 ... 99 + 100. Dette kan man skrive om til formen
(1+1) + 2 + 3 ... + 98 + 99 + 100
1+ (1+99) + (2+98) + (3+97) ... (49+51) + 100 + 50
1 + 100*50 + 50 = 5051 unike løsninger.

Observasjonen din er selvfølgelig riktig, men kan du bevise at dette mønsteret stemmer og dermed
generalisere resultatet?

Nei det får jeg ikke til :S