text:
# Diofantiske likninger

En likning på formen $ax + by = c$, der $a$$b$ og $c$ er vilkårlige tall, kaller vi for en lineær likning. Et annet ord for lineær likning er førstegradslikning, fordi de ukjente, $x$ og $y$, er av første grad. Dette i motsetning til en likning som f.eks. $ax^2 + by = c$, som er en andregradslikning.

Med å løse en slik likning mener vi å finne alle kombinasjoner av $x$ og $y$ som gjør at uttrykket på venstre og høyre side av likhetstegnet har samme verdi.

Eksempel 1:

Vi ser på likningen $x + 2y = 2$. (Her er $a = 1$, $b = 2$ og $c = 2$.)

Løser vi mhp. $y$, får vi $y = -{\large \frac{x}{2}} + 1$. Grafisk sett er dette ei rett linje med stigningstall $-{\large \frac{1}{2}}$, som skjærer y-aksen i $y = 1$:

I noen punkter på ei slik linje kan det være at både $x$ og $y$ er hele tall, slik som markert i grafen over.

Likninger på formen $ax + by = c$, der $a$ og $b$ er hele tall, og vi bare er ute etter løsninger der $x$ og $y$ er hele tall, kaller vi lineære, diofantiske likninger, oppkalt etter grekeren Diofantos.

Hvis vi for eksempel skal ta ut 2500 kroner av minibanken og lurer på hvordan vi kan kombinere sedler på 500 og 200 kroner, finner vi svaret ved å løse den lineære, diofantiske likningen $500x + 200y = 2500$, der $x$ er antall 500-lapper og $y$ er antall 200-lapper.

Alle diofantiske likninger vi ser på i denne artikkelen er lineære, selv om vi for enkelhets skyld av og til bare sier "diofantiske likninger".

### Eksistens av løsninger

Hvis vi i stedet for å spørre om hvordan vi kan kombinere femhundrelapper og tohundrelapper til 2500 kroner, spør om hvordan vi kan kombinere tusenlapper og tohundrelapper til 2500 kroner, skjønner vi fort at det ikke går. Det finnes altså ikke noen heltallsløsninger av likningen
$1000x + 200y = 2500$, der $x$ er antall 1000-lapper og $y$ er antall 200-lapper.

Det er nemlig slik at ikke alle diofantiske likninger har løsning. Så før vi går i gang med å prøve å løse en diofantisk likning, bør vi undersøke om den faktisk er løsbar.

Hva er egentlig grunnen til at vi kan kombinere 500-lapper og 200-lapper til 2500 kroner, men ikke 1000-lapper og 200-lapper? Med andre ord, hva er den prinsipielle forskjellen på de diofantiske likningene $500x + 200y = 2500$ og $1000x + 200y = 2500$?

Intuitivt kan vi si at det med 500-lapper og 200-lapper er mulig "å treffe på" 2500 kroner, mens vi med 1000-lapper og 200-lapper "hopper forbi" 2500 kroner. Vi kan få 2400 og 2600, men ikke 2500. Den matematiske årsaken har med største felles faktor, $SFF$, å gjøre:

Vi har $SFF(500, 200) = 100$, og $SFF(1000, 200) = 200$. Og forskjellen er at 100 går opp i totalbeløpet på 2500, mens 200 ikke gjør det. Generelt har vi:

$\fbox{$ \text{En likning } ax + by = c \text{ har heltallsløsninger hvis og bare hvis } SFF(a, b) \, | \, c$}$

Med andre ord må alle tall som går opp i $a$ og $b$ også gå opp i $c$. Største felles faktor lærte vi om i artikkelen om faktorisering.

Det kan imidlertid være at én eller begge løsningene er negative tall, slik at løsningene ikke kan representere fysiske enheter. Spør vi for eksempel hvordan vi kan kombinere vekter på 4 og 5 kilo til totalt 11 kilo, skjønner vi at det ikke går. Men det betyr ikke at likningen $4x + 5y = 11$ ikke har løsning, for $SFF(4, 5) = 1 \mid 11$. Men løsningene involverer negative tall, for eksempel $y = -1$ hvis $x = 4$. Og siden vi ikke kan ha et negativt antall vekter, finnes ingen fysisk løsning.

For å løse en diofantisk likning kan vi i enkle tilfeller prøve oss fram, for eksempel ser vi lett at $x = 0$, $y = 3$, er en løsning til $5x + 4y = 12$. I andre tilfeller kan dette imidlertid være vanskelig fordi tallene er for store, som for eksempel i $1257x + 389y = 47893$. Det kan også være vanskelig å avgjøre om vi har funnet alle relevante løsninger.

Vi skal derfor systematisk se på metoder for å løse lineære, diofantiske likninger.

### Løse ved omforming til kongruenslikninger

Hvis vi har en likning på formen $ax + by = c$, kan vi flytte leddet $by$ over på høyre side, og få $ax = c + b(-y)$. Kaller vi $-y$ for $k$, og $b$ for $n$ blir det $ax = c + kn$.

I artikkelen om kongruens lærte vi at $a \equiv b \; (mod \: n)$ betyr at det finnes et heltall, $k$, slik at $a = b + kn$.

Siden vi i en diofantisk likning bare opererer med heltall, betyr det at $ax = c + kn$ er det samme som $ax \equiv c \; (mod \: n)$.

En lineær, diofantisk likning, $ax + by = c$, kan altså skrives om til en kongruenslikning, $ax \equiv c \; (mod \, b)$ eller $by \equiv c \; (mod \, a)$, og så løses ved hjelp av de verktøyene vi har til rådighet for å løse slike likninger, slik vi lærte i artikkelen om kongruenslikninger.

Eksempel 2:

Vi kan løse problemet med 200- og 500-lappene på følgende måte:

Vi starter med likningen $500x + 200y = 2500$

Flytter y-leddet over på høyre side: $500x = 2500 – 200y$

Skriver som kongruenslikning: $500x \equiv 2500 \; (mod \; 200)$

Skulle vi fulgt standardoppskriften, skulle vi nå erstattet $500$ og $2500$ med mindre tall som er kongruente modulo $200$. Men i dette tilfellet er det så lett å finne $SFF$ at vi gjør det først og forenkler likningen ved å dividere.

Vi har $SFF(a, n) = SFF(500, 200) = 100$. Vi dividerer alle ledd med $100$ og får: $5x \equiv 25 \; (mod \; 2)$.

Vi kan her forenkle videre ved å dividere på begge sider av kongruenstegnet med $5$. Modulus forblir uendret fordi $SFF(5, 2) = 1$. Og vi får: $x \equiv 5 \; (mod \; 2)$.

Siden $5 > 2$, erstatter vi $5$ med $5 – \lfloor \frac{\displaystyle 5}{\displaystyle 2} \rfloor \cdot 2 = 5 – 2 \cdot 2 = 1$.

Det endelige resultatet blir $x \equiv 1 \; (mod \; 2)$.

(Denne erstatningen kunne vi gjort uten den omstendelige utregningen, for alle oddetall er kongruente med $5$ modulo $2$, så vi kunne puttet inn $1$ uten mer dikkedarer.)

$x = 1$ er altså en løsning.

Setter vi $x = 1$ inn i den opprinnelige likningen, får vi $500 \cdot1 + 200y = 2500$, som løst mhp. $y$ gir $y = 10$.

Vi kan altså få 2500 kroner ved å kombinere én 500-lapp og ti 200-lapper.

Vi vet at hvis en kongruenslikning modulo $n$ har løsning, har den uendelig mange, som kan være fordelt på alt fra 1 til $n$ restklasser. Det betyr at en løsbar diofantisk likning har uendelig mange løsninger. Dette kommer vi tilbake til i et senere avsnitt.

Men først spør vi oss hvorfor det var $b$ og ikke $a$ vi brukte som modulus da vi omformet den diofantiske likningen til en kongruenslikning. Hvorfor erstattet vi $ax + by = c$, med $ax \equiv c \; (mod \: b)$ og ikke med $by \equiv c \; (mod \: a)$? Svaret er at det ikke er noen grunn, det ene er like riktig som det andre. Så utregningen med pengesedlene kunne like gjerne vært slik:

Eksempel 3:

Vi starter med samme likning som i eksempel 2: $500x + 200y = 2500$.

Så flytter vi $x$-leddet over på høyre side: $200y = 2500 – 500x$.

Skriver som kongruenslikning: $200y \equiv 2500 \; (mod \; 500)$.

Vi har $SFF(a, n) = SFF(200, 500) = 100$. Vi dividerer alle ledd med $100$ og får: $2y \equiv 25 \; (mod \; 5)$.

Siden $25 > 2$, erstatter vi $25$ med $25 – \lfloor \frac{\displaystyle 25}{\displaystyle 5} \rfloor \cdot 5 = 25 – 5 \cdot 5 = 0$.

Og vi får: $2y \equiv 0 \; (mod \; 5)$.

(Denne erstatningen kunne vi også gjort uten den omstendelige utregningen, for siden $5$ går opp i $25$, skjønner vi at $25$ er kongruent med $0$ modulo $5$, og kunne puttet inn $0$ uten mer dikkedarer.)

Nå kan vi gått veien om en multiplikativ invers for å finne den endelige løsningen, men vi ser direkte at $y = 0$ er en løsning.

Setter vi $y = 0$ inn i den opprinnelige likningen, får vi $500x + 200 \cdot 0 = 2500$, som løst mhp. $x$ gir $x = 5$.

Vi kan altså få 2500 kroner ved å bruke fem 500-lapper og ingen 200-lapper.

Vi fikk ikke samme svar i eksempel 3 som i eksempel 2, da vi brukte $b$ som modulus og flyttet $y$-leddet over til høyre side, men den diofantiske likningen har altså uendelig mange løsninger, og når har vi funnet en av de andre.

Når vi skal velge om vi skal flytte $x$-leddet eller $y$-leddet over på høyre side, gjør det ofte utregningene enklere å velge slik at vi får lavest modulus. I eksempel 2 fikk vi $200$ når vi flyttet $y$-leddet, og i eksempel 3 fikk vi $500$ når vi flyttet $x$-leddet.

Oppgave 1:

Avgjør om den lineære, diofantiske likningen $21x + 14y = 147$ er løsbar, og finn i så fall en løsning.

### Finne alle løsninger

I eksemplet med sedlene fikk vi én femhundrelapp og ti tohundrelapper når vi regnet modulo $200$, og fem femhundrelapper og ingen tohundrelapper når vi regnet modulo $500$. To forskjellige svar, men begge svarene er riktige. Og en løsbar diofantisk likning har altså uendelig mange løsninger.

Generelt er det slik at vi løser diofantiske likninger ved først å finne én spesiell løsning, og så generalisere ut fra den.

I artikkelen om kongruensregning så vi at det fantes uendelig mange løsninger til en løsbar kongruenslikning, og lærte hvordan vi ut fra én løsning kunne beregne hvilke restklasser løsningene lå i. Metoden kan også brukes på diofantiske likninger, men i en diofantisk likning er vi bare interessert i selve løsningene, ikke hvilke restklasser de tilhører, og hvis vi har løst den diofantiske likningen ved hjelp av Euklids algoritme baklengs, har vi heller ikke noen kongruenslikning å arbeide ut fra.

Vi angir derfor en metode til å finne alle løsninger til en lineær, diofantisk likning basert på den opprinnelige likningen. La oss si at vi har funnet et løsningspar, to heltall $x = x_0$ og $y = y_0$, som tilfredsstiller den diofantiske likningen $ax + by = c$. Da vil alle løsninger av likningen være på formen

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k$

og

$y_k = y_0 – \frac{\displaystyle a}{\displaystyle d}k$

der $k$ er et helt tall, og $d = SFF(a, b)$.

Forklart med ord betyr dette at når vi har funnet et tallpar, $x_0$ og $y_0$, som er en løsning, kan vi finne nye løsningspar, $x_k$ og $y_k$, ved å addere heltallige multipler av $\frac{\displaystyle b}{\displaystyle d}$ til $x_0$, og å subtrahere heltallige multipler av $\frac{\displaystyle a}{\displaystyle d}$ fra $y_0$, der vi henter $a$ og $b$ fra den opprinnelige likningen og beregner $d$ som $SFF(a, b)$. For eksempel

$x_1 = x_0 + \frac{\displaystyle b}{\displaystyle d} \cdot 1$ og $y_1= y_0 – \frac{\displaystyle a}{\displaystyle d} \cdot 1$

$x_2 = x_0 + \frac{\displaystyle b}{\displaystyle d} \cdot 2$ og $y_2 = y_0 – \frac{\displaystyle a}{\displaystyle d} \cdot 2$

$x_{-1} = x_0 + \frac{\displaystyle b}{\displaystyle d}(-1)$ og $y_{-1} = y_0 – \frac{\displaystyle a}{\displaystyle d}(-1)$

$x_{-2} = x_0 + \frac{\displaystyle b}{\displaystyle d}(-2)$ og $y_{-2} = y_0 – \frac{\displaystyle a}{\displaystyle d}(-2)$

og så videre. Det finnes i utgangspunktet uendelig mange muligheter, og vi finner dem ved å sette inn forskjellige verdier av $k$. For eksempel $1, 2, -1, -2$, slik vi har vist over.

Eksempel 4:

I eksempel 2 fant vi at en løsning av den diofantiske likningen $500x + 200y = 2500$ er $x_0 = 1$ og $y_0 = 10$. Vi har da at $a = 500$, $b = 200$ og $d = SFF(200, 500) = 100$. Så som et generelt uttrykk for $x_k$ og $y_k$ får vi:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k = 1 + {\large \frac{200}{100}}k = 1 + 2k$

$y_k = y_0 – \frac{\displaystyle a}{\displaystyle d}k = 10 – {\large \frac{500}{100}}k = 10 – 5k$

Tabellen under viser løsningene for verdier av $k$ mellom $-5$ og $5$. Alle parene av $x$ og $y$ gir riktig løsning av likningen, men hvis $x$ og $y$ skal representere antall pengesedler, kan tallene ikke være negative. Løsningene der både $x$ og $y$ er større eller lik null er derfor markert med gult.

 k -5 -4 -3 -2 -1 0 1 2 3 4 5 x -9 -7 -5 -3 -1 1 3 5 7 9 11 y 35 30 25 20 15 10 5 0 -5 -10 -15

Eksempel 5:

Tar vi utgangspunkt i løsningen i eksempel 3, får vi følgende utregning når vi vil finne alle løsninger:

$x_0 = 5$ og $y_0 = 0$. Vi har som før $a = 500$, $b = 200$ og $d = 100$. Så da får vi som et generelt uttrykk for $x_k$ og $y_k$:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k = 5 + {\large \frac{200}{100}}k = 5 + 2k$

$y_k = y_0 – \frac{\displaystyle a}{\displaystyle d}k = 0 – {\large \frac{500}{100}}k = – 5k$

Tabellen under viser løsningene for verdier av $k$ mellom $-5$ og $5$. Kombinasjoner der både  $x$ og $y$ er større eller lik null er markert med gult.

 k -5 -4 -3 -2 -1 0 1 2 3 4 5 x -5 -3 -1 1 3 5 7 9 11 13 15 y 25 20 15 10 5 0 -5 -10 -15 -20 -25

Vi ser at tallene markert med gult er de samme i tabellene i eksempel 4 og 5. $k$ er forskjellig, men det har ingen betydning for løsningene.

Vi kan altså få 2500 kroner ved å kombinere

1 femhundrelapp og 10 tohundrelapper

3 femhundrelapper og 5 tohundrelapper

5 femhundrelapper og 0 tohundrelapper

Oppgave 2:

Finn et uttrykk for alle løsninger til den lineære, diofantiske likningen fra oppgave 1, $21x + 14y = 147$.

### Finne ikke-negative løsninger

Som vi så et eksempel på da vi regnet med sedler, er vi av og til ikke interessert i negative løsninger av en diofantisk likning. Slik er det ofte når vi opererer med ting fra den virkelige verden. Skruer og muttere, voksne og barn, gule og røde lodd, etc.

Skal vi holde oss til ikke-negative løsninger, betyr det at vi i den generelle løsningen må begrense $k$ slik at vi bare får løsninger der $x_k \geq 0$ og $y_k \geq 0$. Det vil si at vi i det generelle uttrykket vi fant for $x$ og $y$ må ha

$x_0 + \frac{\displaystyle b}{\displaystyle d}k \geq 0$

og

$y_0 – \frac{\displaystyle a}{\displaystyle d}k \geq 0$

Her må vi altså sette inn verdiene vi finner for $x_0$, $y_0$, $a$, $b$ og $d$ og løse ulikhetene mhp. $k$.

Eksempel 6:

I eksempel 4, da vi regnet modulo $200$, fikk vi følgende generelle uttrykk for $x$ og $y$:

$x_k = 1 + 2k$

$y_k = 10 – 5k$

Her må vi altså ha at

$1 + 2k \geq 0$, noe som gir $k \geq – 0,5$

og

$10 – 5k \geq 0$, noe som gir $k \leq 2$.

Det betyr altså at $-0,5 \leq k \leq 2$. Siden $k$ må være hele tall, tilsvarer dette $k = 0$, $k = 1$ og $k = 2$, slik vi fant i tabellen i eksempel 4.

Eksempel 7:

I eksempel 5, da vi regnet modulo $500$, fikk vi følgende generelle uttrykk for $x$ og $y$:

$x_k = 5 + 2k$

$y_k = -5k$

Her må vi altså ha at

$5 + 2k \geq 0$, noe som gir $k \geq – 2,5$

og

$-5k \geq 0$, noe som gir $k \leq 0$.

Det betyr altså at $-2,5 \leq k \leq 0$. Siden $k$ må være hele tall, tilsvarer dette $k = -2$, $k = -1$ og $k = 0$, slik vi fant i tabellen i eksempel 5.

Oppgave 3:

Finn alle ikke-negative løsninger til den lineære, diofantiske likningen fra oppgave 1 og 2, $21x + 14y = 147$.

### Grafisk framstilling av løsninger

En lineær likning på formen $ax + by = c$ kan ved hjelp av enkel algebra omformes til $y = -{\large \frac{a}{b}}x + {\large\frac{c}{b}}$. Dette kjenner vi igjen som likningen for ei rett linje med stigningstall $-{\large \frac{a}{b}}$ som skjærer y-aksen i ${\large \frac{c}{b}}$.

I introduksjonen skrev vi likningen $x + 2y = 2$ på denne måten som $y = -{\large \frac{1}{2}}x + 1$, en funksjon som har grafen under.

I grafen er punkter som er heltallige løsninger av likningen markert. Vi ser at hvis vi fra ett av disse punktene går to skritt til høyre og ett ned, kommer vi til neste punkt. Mer formelt sagt adderer vi $2$ til $x$-verdien, og adderer $-1$ til $y$-verdien

Tallene $2$ og $-1$ kommer fra stigningstallet. Generelt vil vi i grafen til $ax + by = c$, med stigningstall ${\large -\frac{a}{b}}$, komme fra én heltallsløsning, $(x, y)$, til neste ved å addere $b$ til $x$ og $-a$ til $y$: $(x + b, y – a)$.

Vi kan selvsagt også gå fra høyre mot venstre ved å subtrahere $b$ fra $x$, og $-a$ fra $y$: $(x – b, y + a)$.

I eksemplet med sedlene hadde vi likningen $500x + 200y = 2500$, som omformet og forkortet blir $y = -{\large \frac{5}{2}}x + {\large \frac{25}{2}}$, med en graf som ser slik ut:

Her har vi markert de ikke-negative, heltallige løsningene, som var $(1, 10)$, $(3, 5)$ og $(5, 0)$. Stigningstallet er ${\large -\frac{5}{2}}$, og vi ser at vi kommer fra ett løsningspunkt til det neste ved å bruke verdiene fra stigningstallet og addere $2$ til $x$, og $-5$ til $y$.

Oppgave 4:

Løs likningen fra oppgave 1, 2 og 3, $21x + 14y = 147$, som en vanlig likning med hensyn på $y$ og tegn grafen i GeoGebra. Plott inn løsningene fra oppgave 3.

Oppgave 5:

En snekker lager krakker med 3 bein og bord med 4 bein. En dag har han brukt opp 33 bein, hvor mange krakker og bord han kan ha laget?

Vi skal avslutte med å se på et alternativ til å løse diofantiske likninger ved å skrive dem om til kongruenslikninger,  Euklids algoritme baklengs.

### Løse ved Euklids algoritme baklengs

I artikkelen om faktorisering lærte vi å bruke Euklids algoritme til å finne to talls største felles faktor. Brukt baklengs kan algoritmen benyttes til å løse lineære, diofantiske likninger.

Metoden virker i utgangspunktet bare på spesialtilfeller av den diofantiske likningen $ax + by = c$, der $SFF(a, b) = 1$ og $c = 1$, men utvides lett til å fungere også når $SFF(a, b) > 1$ eller $c \ne 1$.

Prinsippet er at vi tar utgangspunkt i likningen $ax + by = 1$ og bruker Euklids algoritme til å finne $SFF(a, b)$. Så nøster vi oss tilbake gjennom utregningen for å finne en lineær kombinasjon av $a$ og $b$ som er en løsning til likningen.

Vi illustrerer med et par eksempler.

Eksempel 8:

Vi skal løse likningen $43x + 5y = 1$.

Her er $SFF(a, b) = 1$ og $c = 1$.

VI starter med å bruke Euklids algoritme til å finne $SFF(43, 5)$.

\begin{align}43 &= 8 \cdot 5 + 3\\ 5 &= 1 \cdot 3 + 2\\ 3 &= 1 \cdot 2 + 1\\ 2 &= 2 \cdot 1 + 0 \end{align}

Konklusjonen er at $SFF(43, 5) = 1$, men det visste vi jo allerede. Det vi egentlig er ute etter, er å uttrykke resten, $r$, som en lineær kombinasjon av de to andre tallene, $a$ og $b$. I siste linje er resten $0$, så den er ikke så interessant. Men de andre linjene skriver vi om som vist under, $a$ og $b$ er markert med brunt:

\begin{align}3 &= {\color{brown}{43}} – 8 \cdot {\color{brown}{5}} \\ 2 &= {\color{brown}{5}} – 1 \cdot {\color{brown}{3}} \\ 1 &= {\color{brown}{3}} – 1 \cdot {\color{brown}{2}} \\ \end{align}

I siste linje erstatter vi så 2-tallet med uttrykket i linja over

Altså

$1 = {\color{brown}{3}} – 1 \cdot {\color{brown}{2}} \\ \Downarrow \\ 1 = {\color{brown}{3}} – 1 \cdot ({\color{brown}{5}} – 1 \cdot {\color{brown}{3}}) \\ \Downarrow \\ 1 = 2 \cdot {\color{brown}{3}} – 1 \cdot {\color{brown}{5}}$

Vi passer på å ikke gjøre utregningene fullt ut, i stedet holder vi rede på hvor mange av de brune tallene vi har.

Vi har nå

\begin{align}3 &= {\color{brown}{43}} – 8 \cdot {\color{brown}{5}}\\ 1 &= 2 \cdot {\color{brown}{3}} – 1 \cdot {\color{brown}{5}} \\ \end{align}

I siste linje erstatter vi 3-tallet med uttrykket i linja over

Altså

$1 = 2 \cdot {\color{brown}{3}} – 1 \cdot {\color{brown}{5}} \\ \Downarrow \\ 1 = 2 \cdot ({\color{brown}{43}} – 8 \cdot {\color{brown}{5}}) – 1 \cdot {\color{brown}{5}} \\ \Downarrow \\ 1 = 2 \cdot {\color{brown}{43}} – 17 \cdot {\color{brown}{5}}$

Det betyr at $x = 2$, $y = 17$ er en løsning til den diofantiske likningen $43x + 5y = 1$, som vi startet med.

Eksempel 9:

Vi skal løse likningen $25x + 7y = 1$.

Her er $SFF(a, b) = 1$ og $c = 1$.

VI starter med å bruke Euklids algoritme til å finne $SFF(25, 7)$:

\begin{align}25 &= 3 \cdot 7 + 4\\ 7 &= 1 \cdot 4 + 3\\ 4 &= 1 \cdot 3 + 1\\ 3 &= 3 \cdot 1 + 0 \end{align}

Vi dropper den siste linja, i de andre uttrykker vi resten, $r$, som en lineær kombinasjon av $a$ og $b$, markert med brunt:

\begin{align}4 &= {\color{brown}{25}} – 3 \cdot {\color{brown}{7}} \\ 3 &= {\color{brown}{7}} – 1 \cdot {\color{brown}{4}} \\ 1 &= {\color{brown}{4}} – 1 \cdot {\color{brown}{3}} \\ \end{align}

I siste linje erstatter vi så 3-tallet med uttrykket i linja over

$1 = {\color{brown}{4}} – 1 \cdot {\color{brown}{3}} \\ \Downarrow \\ 1 = {\color{brown}{4}} – 1 \cdot ({\color{brown}{7}} – 1 \cdot {\color{brown}{4}}) \\ \Downarrow \\ 1 = 2 \cdot {\color{brown}{4}} – 1 \cdot {\color{brown}{7}}$

Vi har nå

\begin{align}4 &= {\color{brown}{25}} – 3 \cdot {\color{brown}{7}}\\ 1 &= 2 \cdot {\color{brown}{4}} – 1 \cdot {\color{brown}{7}} \\ \end{align}

I siste linje erstatter vi 4-tallet med uttrykket i linja over

$1 = 2 \cdot {\color{brown}{4}} – 1 \cdot {\color{brown}{7}} \\ \Downarrow \\ 1 = 2 \cdot ({\color{brown}{25}} – 3 \cdot {\color{brown}{7}}) – 1 \cdot {\color{brown}{7}}\\ \Downarrow \\ 1 = 2 \cdot {\color{brown}{25}} – 7 \cdot {\color{brown}{7}}$

Det betyr at $x = 2$, $y = -7$ er en løsning til den diofantiske likningen $25x + 7y = 1$, som vi startet med.

Oppgave 6:

Finn en løsning til den diofantiske likningen $11x + 3y = 1$, ved hjelp av Euklids algoritme baklengs.

Så langt har vi altså sett på spesialtilfeller av den diofantiske likningen $ax + by = c$, der $SFF(a, b) = 1$ og $c = 1$. Nå skal vi generalisere metoden ved hjelp av to enkle triks.

Siden vi må ha $SFF(a, b) \mid c$ for at likningen skal ha løsning, vil vi alltid kunne forkorte likningen med $SFF(a, b)$, slik at vi får $SFF(a, b) = 1$.

Eksempel 10:

Vi skal løse den diofantiske likningen $50x + 14y = 10$. Her har vi $SFF(50, 14) = 2$. Siden $2 \mid 10$, har likningen løsning. Vi forkorter med $2$ og får

$25x + 7y = 5$, som vi arbeider videre med i eksempel 11.

Siden vi kan multiplisere med samme tall på begge sider i en likning, vil vi, hvis $a$ og $b$ er løsninger til $ax + by = 1$, ha at  $ca$ og $cb$ er løsninger til $ax + by = c$. Vi kan altså løse likningen $ax + by = c$ ved først å løse $ax + by = 1$, og så multiplisere svarene med $c$.

Eksempel 11:

Vi skal løse den diofantiske likningen $25x + 7y = 5$. Vi ser da først på likningen $25x + 7y = 1$. Denne likningen løste vi i eksempel 9, og fikk

$x = 2$, $y = -7$.

Derfor er $x = 5 \cdot 2 = 10$, $y = 5 \cdot (-7) = -35$ løsninger til likningen $25x + 7y = 5$.

Oppgave 7:

Finn en løsning til likningen fra oppgave 1,  $21x + 14y = 147$, ved hjelp av Euklids algoritme baklengs.

Vi så tidligere at en lineær, diofantisk likning kan gjøres om til en kongruenslikning, og selvsagt kan vi også gå andre veien, gjøre en kongruenslikning om til en diofantisk likning. Det betyr at Euklids algoritme baklengs også kan brukes til å løse kongruenslikninger ved at vi først gjør dem om til diofantiske likninger.

### Kilder

• Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
• Rinvold, A. R. (2009). Visuelle perspektivTallteori. Caspar Forlag.
• Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
• Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.
• Wikipedia
•


text:
[Updated] Goldman Sachs Aptitude Test Questions and Answers
Practice List of TCS Digital Coding Questions !!!
Take 50+ FREE!! Online Data Interpretation Mock test to crack any Exams.

# Input / Output Questions

NA
SHSTTON
28
Solv. Corr.
185
Solv. In. Corr.
213
Attempted
2 M:7 S
Avg. Time

1 / 6

Choose the correct option.

fputs function is used to

AWrite characters to a file

BTakes 2 parameters

CReturns a character

DRequires a file pointer

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
131
Solv. Corr.
63
Solv. In. Corr.
194
Attempted
0 M:0 S
Avg. Time

2 / 6

Choose the correct option.

The function fprintf is used in a program

Awhen too many printf calls have been already used in the program

Bin place of printf, since printf uses more memory

Cwhen the output is to be printed on to a file

Dwhen the type of the variables to be printed are not known apriori

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
102
Solv. Corr.
100
Solv. In. Corr.
202
Attempted
0 M:0 S
Avg. Time

3 / 6

What is the following C Program doing?
#include <stdio.h>
void main ()
{
char line [80];
gets (line);
puts (line);
}

Aprints horizontal straight lines on screens

Bprints 80 vertical lines on screen

Creads in a line of 80 characters

Dreads and prints lines composed of characters

Explanation:

In line 3, we are declaring a character array 'line' of exactly 80 bytes. In the next line, 'gets' is used to read a line of text from standard input device(stdin), and in the next line 'puts' is used to print the string or line of text. So the coreect option is D.

Workspace

NA
SHSTTON
67
Solv. Corr.
135
Solv. In. Corr.
202
Attempted
0 M:0 S
Avg. Time

4 / 6

Choose the correct option.

if i,j,k are integers, the scanf function to enter i,j,k such that i is decimal,j is octal and k is hexadecimal would be

Ascanf("%x %x %8x",i,j,k)

Bscanf("%d %o %x", i,j,k)

Cscanf("%d %o %x",&i, &j, &k)

Dscanf("%d %8d %16d", &i, &j, &k)

Explanation:

Following are the format specifiers for the above cases-

1. %d- to scan an integer value.

2. %o- to scan an octal value.

3. %x- to scan value in hexadecimal format.

Workspace

NA
SHSTTON
92
Solv. Corr.
93
Solv. In. Corr.
185
Attempted
0 M:0 S
Avg. Time

5 / 6

What would be the output of the following C program if input to the program is 'e'?
#include <stdio.h>
void main ()
{
char lower, upper;
lower = getchar();
upper= toupper (lower);
putchar (upper);
}

A53

Be

CE

DNothing

Explanation:

As lower=getchar(), and the input is 'e', so lower will contain 'e'. In the next line 'e' will get converted to its upper case i.e, upper will contain 'E'. In the next line 'E' will get printed, so the correct option is option C.

Workspace

NA
SHSTTON
115
Solv. Corr.
79
Solv. In. Corr.
194
Attempted
0 M:0 S
Avg. Time

6 / 6

float x, y, z;
scanf ("%f %f", &x, &y);

If input stream contains "4.2 3 2.3 ..."
What will x and y contain after scanf?

A4.2, 3.0

B4.2, 2.3

C4.2 2.0

DNone of the above

Explanation:

Here is no explanation for this answer

Workspace

## C Programming Input / Output Questions and Answers pdf

At C Programming topic Input / Output, you will get multiple online quiz difficulty wise, which will have a total of 6 quizzes, categorized as easy, medium, and moderate level. While preparing for any Input / Output, take all the list quiz and check your preparation level for that topic. Each quiz have 10 different question, which needs to be answered in 20 min., all the listed quiz here is free, however, you will get only one chance for each quiz to attempt(Take Quiz seriously), so it is always recommended to take one quiz in each section before you start solving Input / Output MCQs practice question, and one after solving all the question of the respective level, you can refer back your Input / Output quiz result any time or you can download it as pdf for reference.

## C Programming Input / Output Customize Online Mock Test

This is own type of mock test, where At this C Programming Input / Output MCQs mock test section, you will able to attempt only the questions related to Input / Output, in that question will be a different level, important, and all the questions will be part of some of the mock tests across Q4interview FREE Mock test. You need to choose the topic as Input / Output, and click on Double click to generate your customize mock test. While attempting the mock test you need to choose any of the one options out of given option. It is recommended to go through the direction given along with each question, as these questions will be randomly and so that same direction will not be applicable across the entire test. Once you submit your mock test, the result will be generated for Input / Output Customize mock test, where your performance point points will be highlighted. Q4interview analysis every single point which helps you to improve your topic understanding and help you to know your type of mistakes and way to improve Input / Output questions, by providing the same type of practice questions from practice exercise. The best part of this Input / Output, all these mock tests listed here are free and you can take as Many time, as many you want. When you continue to give Input / Output Customize Online Mock Test here regularly, then you will understand how much you have developed your accuracy on a topic, after that you will be able to decide how much attention you need to focus on. Your continued practice will increase your confidence, speed and thinking ability intensely, the Input / Output Customize topic on which you will practice more will beneficial for you in future during campus placement.

## C Programming Input / Output Quiz Online Test

The details of the C Programming Input / Output quiz are as follows. There are 10 questions for you. You have to answer them in 20 minutes. Within 20 minutes you have to see the errors in the sentences given as a question. Four options are also given to you, and you have to choose your opinion. You must be confident in your answer that the choices are difficult. Therefore, below we provide you with some information about C Programming Input / Output that you see and keep them in mind while answering questions.

## C Programming Input / Output MCQs Practice Questions with Answer

On this Input / Output section of page you will find the easiest quickest ways to solve a question, formulas, shortcuts and tips and tricks to solve various easiest methods to solve Input / Output Question Quickly. It contains all the C Programming topic Input / Output questions which are common in any of the preliminary exams of any company. The solution is provided along with the questions. The practice of these questions is a must as they are easy as well as scoring and asked in all the exams They will confirm the selection if all the questions attempted wisely with little practice. It is recommanded to Take Mock test based on C Programming topic and Input / Output topic based quiz.

## C Programming Input / Output solved examples question

You can get here fully solved Input / Output examples with a detailed answer and description. You can solve Input / Output problems with solutions, the questions by companies wise by filtering the questions, additionally, you can check what type of questions are being asked in IT companies Written Round from Input / Output. Input / Output became one of the most important sections in the entire competitive exams, Companies Campus, and entrance online test. Go through Input / Output Examples, Input / Output sample questions. You can Evaluate your level of preparation in Input / Output by Taking the Q4Interivew Input / Output Online Mock Test based on most important questions. All the Input / Output practice questions given here along with answers and explanations are absolutely free, you can take any number of time any mock Test.

## Why C Programming Input / Output?

In this practice section, you can practice C Programming Questions based on "Input / Output" and improve your skills in order to face the interview, competitive examination, IT companies Written exam, and various other entrance tests (CAT, GATE, GRE, MAT, Bank Exam, Railway Exam etc.) with full confidence.

## Where can I get C Programming Input / Output questions and answers with explanation?

Q4Interview provides you lots of fully solved C Programming (Input / Output) questions and answers with Explanation. Solved examples with detailed answer description, explanation are given and it would be easy to understand. You can download C Programming Input / Output quiz questions with answers as PDF files and eBooks.

## Where can I get C Programming Input / Output Interview Questions and Answers (objective type, multiple-choice, quiz, solved examples)?

Here you can find objective type C Programming Input / Output questions and answers for interview and entrance examination. Multiple choice and true or false type questions are also provided.

format: plain


text:
# How to get the home directory in Python?

PythonServer Side ProgrammingProgramming

To get the homedir in python, you can use os.path.expanduser('~') from the os module. This also works if its a part of a longer path like ~/Documents/my_folder/. If there is no ~ in the path, the function will return the path unchanged. You can use it like −

import os
print(os.path.expanduser('~'))

You can also query the environment variables for the HOME variable −

import os
print(os.environ['HOME'])
Published on 27-Dec-2017 06:54:01


text:
RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Dal'nevost. Mat. Zh.: Year: Volume: Issue: Page: Find

 Dal'nevost. Mat. Zh., 2000, Volume 1, Number 1, Pages 3–7 (Mi dvmg72)

On three disjoint domains

L. V. Kovalev

Institute of Applied Mathematics, Far-Eastern Branch of the Russian Academy of Sciences

Abstract: The paper deals with the following problem, stated in [Zbl.830.30014] by V. N. Dubinin and earlier, in different form, by G. P. Bakhtina [Zbl.585.30027]. Let $a_0=0$, $|a_1|=…=|a_n|=1$, $a_k\in B_k\in\overline{\mathbb C}$, where $B_0,…,B_n$ are disjoint domains, and $B_1,…,B_n$ are symmetric about the unit circle. Find the exact upper bound for $\prod_{k=0}^n r(B_k,a_k)$, where $r(B_k,a_k)$ is the inner radius radius of $B_k$ with respect to $a_k$. For $n\ge3$ this problem was recently solved by the author. In the present paper, it is solved for $n=2$.

Full text: PDF file (161 kB)
References: PDF file   HTML file

Document Type: Article
UDC: 517.54
MSC: 30C75

Citation: L. V. Kovalev, “On three disjoint domains”, Dal'nevost. Mat. Zh., 1:1 (2000), 3–7

Citation in format AMSBIB
\Bibitem{Kov00} \by L.~V.~Kovalev \paper On three disjoint domains \jour Dal'nevost. Mat. Zh. \yr 2000 \vol 1 \issue 1 \pages 3--7 \mathnet{http://mi.mathnet.ru/dvmg72} \elib{http://elibrary.ru/item.asp?id=5019944}


text:
# Compute Westtown Company’s (A) inventory turnover ratio and (B) number of days’ sales in inventory ratio, using the following information.

FindFindarrow_forward

### Principles of Accounting Volume 1

19th Edition
OpenStax
Publisher: OpenStax College
ISBN: 9781947172685

#### Solutions

Chapter
Section
FindFindarrow_forward

### Principles of Accounting Volume 1

19th Edition
OpenStax
Publisher: OpenStax College
ISBN: 9781947172685
Chapter 10, Problem 16EB
Textbook Problem
1 views

## Compute Westtown Company’s (A) inventory turnover ratio and (B) number of days’ sales in inventory ratio, using the following information.

To determine

(a)

Concept introduction:

Inventory Turnover Ratio:

Inventory Turnover Ratio measures the efficiency of the company in converting its inventory into sales. It is calculated by dividing the Cost of goods sold by Average inventory. The formula of the Inventory Turnover Ratio is as follows:

Inventory Turnover Ratio=Cost of goods soldAverage inventory

Note: Average inventory is calculated with the help of following formula:

Average inventory=(Beginning inventory + Ending inventory)2

Day’s sales in inventory:

Days sales in inventory represent the number of days the inventory waits for the sale. It is calculated using the following formula:

Day Sales in Inventory =  Inventory *365Cost of Goods Sold

To calculate:

The Inventory Turnover Ratio

### Explanation of Solution

The Inventory Turnover Ratio is calculated as follows:

...
 Cost of Goods Sold (A) $156,000 Beginning Inventory (B)$ 14,500
To determine

(b)

Concept introduction:

Inventory Turnover Ratio:

Inventory Turnover Ratio measures the efficiency of the company in converting its inventory into sales. It is calculated by dividing the Cost of goods sold by Average inventory. The formula of the Inventory Turnover Ratio is as follows:

Inventory Turnover Ratio=Cost of goods soldAverage inventory

Note: Average inventory is calculated with the help of following formula:

Average inventory=(Beginning inventory + Ending inventory)2

Day’s sales in inventory:

Days sales in inventory represent the number of days the inventory waits for the sale. It is calculated using the following formula:

Day Sales in Inventory =  Inventory *365Cost of Goods Sold

To calculate:

Number of Day’s sales in inventory ratio

### Still sussing out bartleby?

Check out a sample textbook solution.

See a sample solution

#### The Solution to Your Study Problems

Bartleby provides explanations to thousands of textbook problems written by our experts, many with advanced degrees!

Get Started

Find more solutions based on key concepts
How are inflation and unemployment related in the short run?

Essentials of Economics (MindTap Course List)

What are the steps in entering international markets?

Foundations of Business (MindTap Course List)

EXCHANGE GAINS AND LOSSES You are the vice president of International InfoXchange, headquartered in Chicago, Il...

Fundamentals of Financial Management, Concise Edition (with Thomson ONE - Business School Edition, 1 term (6 months) Printed Access Card) (MindTap Course List)

What is a database?

Accounting Information Systems

How do unions affect the natural rate of unemployment?

Principles of Macroeconomics (MindTap Course List)

Describe a firms macro environment.

Principles of Management


text:
# Exam 1 Solutions

Question 1.  (a)  Suppose that $S$ is a set of real numbers that is bounded from below, and let $x = \inf S$.  (By the way, we know that this infimum exists since the set

$\displaystyle -S := \{ -s : s \in S \}$

can be shown to be bounded above and so has a supremum.  It is not hard to argue that $\sup \left(-S\right) = -\inf S$ and so $\inf S$ exists.)

Proof.  If $x \in S$, then we are done.  Therefore, suppose $x \notin S$.  To show that $x = \inf S$ is an accumulation point, let $\varepsilon > 0$ be given.  We will argue that

$\displaystyle \left(x-\varepsilon, x+\varepsilon\right) \bigcap S$

contains at least one element that is different from $s$.  By the Lemma on page 35. (and the one discussed in class), this is equivalent to the original definition of accumulation point.

Since $x = \inf S$, it follows that $x- \varepsilon < x < s$ for every $s \in S$.  By definition of infimum, the real number $x + \varepsilon$ must fail to be a lower bound for $S$.  This means that there must exist an element $y \in S$ that satisfies $y < x + \varepsilon$.  We therefore have

$\displaystyle y \in \left(x-\varepsilon, x+\varepsilon\right) \bigcap S$.

Since $y \in S$ and, by assumption, $x \notin S$, it follows that $y \neq x$.  Since such an element $y \in S$ exists for every $\varepsilon > 0$, we have that $x = \inf S$ is an accumulation point.  $\square$

(b) There are lots of way to answer this question, but first let’s consider an incorrect answer.  The set $T = (a, b)$ where $a, b \in \mathbb{R}$ with $a < b$ is an open interval.  The infimum of this set, $\inf T = a \notin T$ and $a$ is an accumulation point.

One may think to adjust this example by instead defining the interval $T' = [a, b)$ so that $a = \inf T '\in T'$, however this example still does not work since $a$ is still an accumulation point for $T'$.

We need to construct a set that (1) has an infimum, (2) contains its infimum, and for which (3) the infimum is not an accumulation point — that is, we want $S$ to not accumulate around $\inf S$, so we would like this point to be isolated.  Here is one way to take our attempt from before and “fix” it:  define the set $S$ to be

$\displaystyle S = \{-3\} \bigcup (-1, 1)$.

Then, clearly, $\inf S = -3 \in S$ but there are $\varepsilon$-neighborhoods of the point $-3$ that do not intersect $S$ (except in the point $-3$ itself).

Question 2.  There are many ways to prove that this sequence converges.  Here is a proof using the definition of convergence.

Claim: The sequence $a_n = (5n)/(3n+2)$ converges to $A = 5/3$.

Proof.  Let $\varepsilon > 0$ be given.

Choose $N \displaystyle > \frac{10}{9\varepsilon}-\frac{6}{9}$ and suppose $n \geq N$.  Then

$\displaystyle d\left(a_n, A\right) = \left|\frac{5n}{3n+2} - \frac{5}{3}\right| = \left| \frac{-10}{9n+6} \right| = \frac{10}{9n+6} < \varepsilon$

where the final inequality is a direct result of our choice for $n \geq N$.  $\square$

Question 3.  (a) Claim.  The set $X = \mathbb{R}$ is bounded under the given (discrete) metric.

Proof.  To verify our claim we need to find a point $x_0 \in X$ and a non-negative real number $R \geq 0$ so that the set containment

$\displaystyle \mathbb{R} \subseteq B_R\left(x_0\right)$

is true.  As it turns out, there are infinitely many choices for $x_0$ and infinitely many choices for $R \geq 0$.  In particular, for every $x_0 \in \mathbb{R}$ and for every $R \in (1, \infty)$, the ball $B_R(x_0)$ contains every real number.  To prove this stronger statement, let $x_0 \in \mathbb{R}$ and $R \in (1, \infty)$ be arbitrary.

Let $x \in \mathbb{R}$ be arbitrary.  To show that $x \in B_R(x_0)$ we need to show that $d(x, x_0) < R$.  However, because $R > 1$ and $d(x,x_0) = 0 \text{ or } d(x, x_0) = 1$, it follows that $d(x, x_0) < R$.  Hence $\mathbb{R} \subseteq B_R(x_0)$.

As a particular example, we have that $\mathbb{R} = B_2(\pi)$.  $\square$.

(b)  Claim.  If $\{a_n\}$ is a convergent sequence of points in the metric space $(\mathbb{R}, d)$, then there exists $N \in \mathbb{N}$ so that whenever $n \geq N$ it follows that $a_n = a$.  (In other words: a convergent sequence is eventually constant.)

Proof.  Suppose $\{a_n\}$ converges to $a \in \mathbb{R}$ in the given metric space.  By definition of convergence this means that for every $\varepsilon > 0$ there exists $N \in \mathbb{N}$ so that

$\displaystyle d\left(a_n, a\right) < \varepsilon \text{ whenever } n \geq N$.

Since this happens for every positive $\varepsilon$, it must hold when $\varepsilon = 1/2$.  As in our statement above, let $N$ denote the index beyond which we have

$\displaystyle d\left(a_n, a\right) < \frac{1}{2}$.

Because this metric can only return values of $0$ or $1$, it follows that whenever $n \geq N$

$\displaystyle d\left(a_n, a\right) = 0$.

Because this is a metric space, the above line implies that whenever $n \geq N$, $a_n = a$, as desired.  $\square$

(c ) The Bolzano-Weierstrass Theorem is false in this metric space.  As a concrete counter-example, consider the set

$\displaystyle S = \left\{1, \frac{1}{2}, \frac{1}{3}, \cdots \right\}$.

Because $S \subset \mathbb{R}$ and $\mathbb{R}$ is bounded, the set $S$ is bounded, too.  The set $S$ is infinite since there are infinitely many distinct real numbers of the form $1/n$.

However, $S$ does not have any accumulation points.  Under our usual metric for $\mathbb{R}$, the number $0$ would be an accumulation point, but under this discrete metric all of the points of $S$ remain of distance $1$ away from $0$.  Indeed, this is true for all real numbers $x \notin S$.

Indeed, one can prove a much more striking fact: in this metric space, no set $S$ has any accumulation points.  The idea underlying this fact can be stated in a rather simple, English sentence: infinitely many points of any set $S$ will fail to accumulate anywhere since they are all distance one away from every other point!

Question 4.  Oh, boy.  I am skipping this one as I would babble endlessly about failed ideas and how much they (eventually) taught me.  Trust me, I’m doing you a favor.

Question 5. Before we address either part of this problem, we establish the following helpful lemma.  It will be used in both parts (a) and (b).

Lemma 1.  If $S \subseteq T \subseteq \mathbb{R}$ are subsets of real numbers that each have a supremum, then $\sup S \leq \sup T$.  (An analogous statement is true for infimuma, but with a reversed inequality.)

proof.  Suppose $S \subseteq T$ are subsets of real numbers, each with suprema.  To prove that $\sup S \leq \sup T$, we need only argue that $\sup T$ is also an upper bound for the set $S$.  Since, by definition, $\sup S$ is the least upper bound for $S$, the inequality will have to follow.

Of course, that $\sup T$ is an upper bound for $S$ is instant.  After all, the $\sup T$ is an upper bound for $T$ and so $\sup T \geq t$ for all $t \in T$.  Now let $s \in S$ be arbitrary.  Then since $s \in S \subseteq t$, it follows that $s \in T$ and so $s \leq \sup T$.  Therefore $\sup T$ is an upper bound for $S$.  $\square$

(a) To prove that for a bounded sequence of real numbers, $\{a_n\}$, the e-sup always exist we use Lemma 1 to prove that the sequence of suprema

$\displaystyle \left\{s_1, s_2, s_3, \cdots \right\}$

is a decreasing sequence.

By definition we have that

$\displaystyle s_1 = \sup \left\{a_1, a_2, a_3, \cdots \right\}$ and that $\displaystyle s_2 = \sup \left\{a_2, a_3, \cdots \right\}$.

Using $S = \left\{a_1, a_2, a_3, \cdots \right\}$ and $T = \left\{a_2, a_3, \cdots \right\}$ we have that $S \subseteq T$ and so, by Lemma 1, $s_1 \leq s_2.$

Similarly, since $\left\{a_n, a_{n+1}, a_{n+2}, \cdots \right\} \subseteq \left\{a_{n+1}, a_{n+2}, \cdots \right\}$ holds for all $n \in \mathbb{N}$, Lemma 1 implies that $s_n \leq s_{n+1}$.  Therefore the sequence $\{s_n\}$ is decreasing.

Note that we now have an automatic upper bound for $\{s_n\}$, namely $s_1 \geq s_n$ for all $n \in \mathbb{N}$.  To establish a lower bound for $\{s_n\}$ we use (again) the fact that the original sequence $\{a_n\}$ is bounded.  This means that there exist $\alpha, \beta \in \mathbb{R}$ so that

$\displaystyle \alpha \leq a_n \leq \beta \text{ for every } n \in \mathbb{N}$.

Hence, for every $n \in \mathbb{N}$, it follows that since $s_n = \sup \{a_n, a_{n+1}, \cdots \}$ then $s_n \geq \alpha$, too.

The monotone convergence theorem implies that the decreasing, bounded sequence $\{s_n\}$ converges.  Its limit — which is defined to be the e-sup of $\{a_n\}$ — therefore exists.  $\square$

Note: A very similar proof can be used to prove that the e-inf — which is defined to be the limit of a sequence of infimuma — also exists.

(b) We will handle this iff proof with two different if-then proofs.

proof (of $\Rightarrow$).  Suppose that $\{a_n\}$ converges to $a$.  We will show that the e-sup = $a$, too.  This will be accomplished by proving that for every $\varepsilon > 0$, it follows that

$\displaystyle a \leq \text{e-sup} \leq a + \varepsilon$.

The first inequality above follows from Theorems in 1.3.  In particular, note that by definition of $s_n$, for each $n \in \mathbb{N}$, it follows that $s_n \geq a_n$.  Since both sequences have a limit, theorems from 1.3 imply that $\text{e-sup} \geq a$.

For the second inequality, let $\varepsilon > 0$ be given.  Since, by assumption, $a_n \to a$, there exists $N \in \mathbb{N}$ so that whenever $n \geq N$, it follows that $d(a_n, a) < \varepsilon$.  Worded differently,

$\displaystyle \left\{a_N, a_{N+1}, a_{N+2}, \cdots \right\} \subset \left(a-\varepsilon, a+\varepsilon\right)$.

Lemma 1 implies that the supremum of the first set is therefore bounded above by the supremum of the second set.  The supremum of the first set is of course $s_N$, and the supremum for the $\varepsilon$-ball is $a+\varepsilon$.  That is, we have

$\displaystyle s_N \leq a + \varepsilon$.

Since $\{s_n\}$ is a decreasing sequence we actually have that for all $n \geq N$, the suprema $s_n \leq a + \varepsilon$.  Taking a limit as $n \to \infty$ then produces the desired inequality, namely that

$\displaystyle \text{e-sup} \leq a + \varepsilon$.

Since $\varepsilon$ is arbitrary, this establishes that $\text{e-sup} = a$.  A similar argument can be made to conclude that $\text{e-inf}=a$.

proof (of $\Leftarrow$).  Now suppose that the e-inf and e-sup exist and equal the same number $a \in \mathbb{R}$.  We will prove that $a_n \to a$ by appealing to our squeeze theorem.

Note, again, that by definition of $s_n$,

$\displaystyle s_n = \sup \left\{a_n, a_{n+1}, a_{n+2}, \cdots \right\} \geq a_n$.

Similarly, by definition of $i_n$,

$\displaystyle i_n = \inf \left\{a_n, a_{n+1}, a_{n+2}, c\dots \right\} \leq a_n$.

We therefore have for each $n \in \mathbb{N}$,

$\displaystyle i_n \leq a_n \leq s_n$.

Since, by assumption, $\displaystyle \lim_{n\to\infty} i_n = \text{e-inf} = a = \text{e-sup} = \lim_{n\to\infty} s_n$, the squeeze theorem implies that

$\displaystyle \lim_{n\to\infty} a_n = a$

as desired.  $\square$

Question 6. (Skipped for now — but, yes, these are very similar or outright identical to homework problems, and a proof for part (a) can be used to prove one of the cases you’d naturally set up for part (b).)

Question 7.  There are lots of ways to prove this “stronger” Nested Interval Property.  My favorite way uses the Monotone Convergence Theorem.

Let $I_n = [a_n, b_n]$ be an indexed family of closed, non-empty, bounded intervals that are nested.  Observe that we therefore have $a_n < b_n$ for all $n \in \mathbb{N}$; observe also that since the intervals are nested it follows that

$\displaystyle a_1 \leq a_2 \leq a_3 \leq \cdots \text{ and } b_1 \geq b_2 \geq b_3 \cdots$.

(We can also note that $a_1 \leq a_2 < b_2 \leq b_1$ and that $a_1 \leq a_2 \leq a_3 < b_3 \leq b_2 \leq b_1$ and so on.)

In other words, we have that the sequence $\{a_n\}$ is increasing, and the sequence $\{b_n\}$ is decreasing.  Since both of these sequences are bounded — $a_1 \leq a_n < b_1 \text{ for all } n$ and $b_1 \geq b_n > a_1 \text{ for all } n$ — the Monotone Convergence Theorem implies that each sequence converges.

Let us write $\displaystyle a = \lim_{n\to\infty} a_n$ and $\displaystyle b = \lim_{n\to\infty} b_n$, and recall from the proof of the Monotone Convergence Theorem, that these two limits satisfy $a = \sup \{a_n\}$ and $b = \inf \{b_n\}$.  We now treat the following sub-claim:

Sub-Claim:  If $x \in \bigcap I_n$ then $a \leq x \leq b$.

sub-proof.  Suppose $x \in \bigcap I_n$ but that, say, $x < a$.  Since $a$ is the supremum of $\{a_n\}$, this means that there exists a term in the sequence, $a_N$ so that $a_N > x$.  This inequality implies that

$\displaystyle x \notin \left[a_N, b_N\right]$

and so $x \notin \bigcap I_n$ as assumed.  The case when $x > b$ is handled similarly.  $\Rightarrow\Leftarrow$.

We will now use the assumption that $\ell_n \to 0$ to prove that $a = b$.  From useful Theorems in sectoin 1.3, we know that since each sequence $\{a_n\}$ and $\{b_n\}$ converges to $a$ and $b$ (respectively), the sequence $\{b_n - a_n \}$ also converges to $b-a$.  However, we also know that

$\displaystyle \ell_n = \text{Length}\left([a_n, b_n]\right) = b_n - a_n$

and so

$\displaystyle 0 = \lim_{n\to\infty} \ell_n = \lim_{n\to\infty} (b_n - a_n) = \left(\lim_{n\to\infty} b_n\right) - \left(\lim_{n\to\infty} a_n \right) = b - a$.

Therefore $b = a$.

The Nested Interval Property tells us that there exists at least one point $x \in \bigcap I_n$, and by our sub-claim this point must lie inbetween $a$ and $b$.  However, since $\ell_n \to 0$ implies that $b = a$, there is only one value that $x$ can equal.  In particular, this all shows

$\displaystyle \bigcap_{n=1}^{\infty} I_n = [a, a] = \{a\} = \{b\} = [b, b]$

which completes the proof.  $\square$

Question 8.  Let $a_n = \sqrt{n}$ and define $b_n = \sqrt{n+1} - \sqrt{n}$.  There are lots of ways to argue that $b_n \to 0$.  My personal favorite uses an algebraic “trick” that let’s us rewrite the terms as

$\displaystyle b_n = \sqrt{n+1} - \sqrt{n} = \frac{\sqrt{n+1}-\sqrt{n}}{\sqrt{n+1}+\sqrt{n}}\,\left(\sqrt{n+1}+\sqrt{n}\right) = \frac{1}{\sqrt{n+1}+\sqrt{n}}$

We can now use various theorems and techniques from Section 1.3 to argue that this sequence converges to zero.  For example one can prove (either by induction or more direct methods) that

$\displaystyle 2\sqrt{n} \leq \sqrt{n+1} + \sqrt{n} \leq 2\sqrt{n+1} \, \text{ for all } n \in \mathbb{N}$

from which we can conclude that

$\displaystyle \frac{1}{2\sqrt{n}} \geq b_n \geq \frac{1}{2\sqrt{n+1}}$.

Some of our results from Section 1.3 then imply that the sequences $1/(2\sqrt{n})$ and $1/(2\sqrt{n+1})$ both converge to zero.  By our Squeeze Theorem, this implies that $\{b_n\}$ converges to $0$, too.  $\square$

We have shown that the sequence of successive distances $d\left(a_n, a_{n+1}\right)$ converges to zero, and this seems like it should imply that the original sequence is Cauchy.  However, this is not the case!  In particular, that these distances converge to zero does not necessarily tell us anything about the distances between other terms further out in the sequence; that is, we do not necessarily know that

$\displaystyle d\left(a_n, a_{n+2}\right) \to 0$

or that, more generally, for any pair $m \geq n$,

$\displaystyle d\left(a_n, a_m\right) \to 0$.

Indeed, we can argue that while the sequence $\{b_n\}$ converges to zero, the original sequence is not Cauchy.  We can accomplish this via a proof by contradiction.

Suppose that $\{a_n\} = \{\sqrt{n}\}$ is Cauchy.  This is means that $\{a_n\}$  converges.  As a consequence, we know that this sequence must therefore be bounded.  That is, there must exist a real number $B \in \mathbb{R}$ so that

$\displaystyle \sqrt{n} \leq B \, \text{ for all } n \in \mathbb{N}$.

This inequality is equivalent to claiming that there exists $B \in \mathbb{R}$ so that

$\displaystyle n \leq B^2 \, \text{ for all } n \in \mathbb{N}$.

Given our familiarity with natural numbers, we can cite a contradiction right here.  Therefore, the sequence $a_n = \sqrt{n}$ does not converge and so is not Cauchy.  $\square$

Note: Some of you very cleverly proved directly that $a_n = \sqrt{n}$ is not Cauchy.  If you would like to see one of these proofs, ask around!

Question 9.  We will approach this problem by proving two claims.  Assume the hypotheses of the question, then

Claim 1.  If $a_n$ converges, then it must converge to zero.

Claim 2.  The sequence $a_n$ converges.

The second claim is actually the trickier of the two (imo).  The first claim can be proven by appealing to our arithmetic laws that govern convergent sequences.

Proof (of claim 1).  For a contradiction, suppose that $a_n$ converges to a non-zero number, $A \in \mathbb{R}$ with $A \neq 0$.  Note further that, by assumption, none of the terms of $a_n$ are equal to zero, and so we may form the sequence

$\displaystyle b_n = \frac{a_{n+1}}{a_n}$.

Moreover, by using our results from section 1.3, since $a_n$ converges to $A \neq 0$, and since $a_{n+1}$ also converges to $A$ we have that

$\displaystyle b_n = \frac{a_{n+1}}{a_n} \text{ converges to } \frac{A}{A} = 1$.

The claim that $A/A = 1$ only holds if, as we’ve assumed, $A \neq 0$.  This conclusion, however, contradicts the assumption that $b_n$ converges to a number $b < 1$.

Therefore, if $a_n$ converges, it must converge to $A = 0.$  $\square$

There are also many ways to prove claim 2.  The proof below will show that the sequence $\{a_n\}$ is monotone and bounded, and therefore must converge by the Monotone Convergence Theorem.  Actually, we will prove that the sequence is eventually monotone and bounded.

Proof (of claim 2).  We are told that the sequence contains only positive numbers, and so we immediately have a lower bound: $0 < a_n$ for all $n$.

Now we will show that this sequence is eventually decreasing.  That is, that there exists $N \in \mathbb{N}$ so that whenever $n \geq N$, $a_{n+1} \leq a_n$.  The idea for this claim comes from the fact that the sequence $b_n$ converges to $b \in (0, 1)$, and so the fractions $a_{n+1}/a_n$ eventually look very close to the number $b$.  This implies that, far enough out in the sequence, $a_{n+1} \approx b\,a_n$ and so $a_{n+1} \leq a_n$.

To make this idea more precise, we know that for any $\varepsilon > 0$ there exists $N \in \mathbb{N}$ so that

$\displaystyle \left|\frac{a_{n+1}}{a_n} - b \right| < \varepsilon$

holds whenever $n \geq N$.  Since $b \in (0, 1)$ there exists a positive number $\varepsilon > 0$ so that $b + \varepsilon \in (0, 1)$ — choose such an $\varepsilon$, and denote the associated index by $N_1$.  We have that whenever $n \geq N_1$

$\displaystyle -\varepsilon < \frac{a_{n+1}}{a_n} - b < \varepsilon$

and this inequality is equivalent to

$\displaystyle b-\varepsilon < \frac{a_{n+1}}{a_n} < b + \varepsilon.$

The upper bound inequality above is what we focus on now.  By choice of $\varepsilon$, we have

$\displaystyle n \geq N_1 \Rightarrow \frac{a_{n+1}}{a_n} < b + \varepsilon < 1$

and so

$\displaystyle n \geq N_1 \Rightarrow \frac{a_{n+1}}{a_n} < 1.$

Since this last inequality is equivalent to $a_{n+1} < a_n$, we have that beyond the index $N_1$, our remaining sequence is decreasing.  Note that this provides for us an upper bound for the sequence $\{a_{N_1}, a_{N_1 + 1}, \cdots \}$, namely the number $a_{N_1}$.

The Monotone Convergence Theorem implies that this sequence $\{a_{N_1}, \cdots \}$ converges.  This, of course, implies that the original sequence $\{a_1, a_2, \cdots \}$ converges, too.  $\square$

Question 10. (skipped for now)


text:
# Thread: problem with sets and counting again

1. ## problem with sets and counting again

I am having a lot of problems with this problem, I went to a tutor and showed me what to do, but I still get it wrong. Im on the verge of failing, so i want to get the best possible grades on my homework. Please help me with this problem:

If a die is rolled 40 times, there are 640 different sequences possible. What fraction of these sequences have exactly 8 numbers less than or equal to 3? (Round your answer to the nearest 0.0001.)

2. Originally Posted by Flamed02
If a die is rolled 40 times, there are 640 different sequences possible. What fraction of these sequences have exactly 8 numbers less than or equal to 3? (Round your answer to the nearest 0.0001.)
First a correction: there are $6^{40}$ different sequences possible.
On any toss of the die there is a probability of 0.5 that the die shows 3 or less.
There are ${40 \choose 8}$, 40 places choosing 8, to have success.
So the answer: ${40 \choose 8}(0.5)^{40}$

3. thank you, my answer was 6.994440355 E-5 What does the E-5 mean?