Side 1 av 1

Julekalender #4

Lagt inn: 04/12-2017 16:31
av Emilga
Fyll ut tall i en tabell med $m$ rader og $n$ kolonner, slik at summen av tallene langs hver rad er 1, og summen av tallene langs hver kolonne er 1. Vis at $m=n$.

Re: Julekalender #4

Lagt inn: 04/12-2017 17:17
av Gustav
Summen av alle radene er lik $m$, mens summen av alle kolonnene er lik $n$. De må nødvendigvis være like, da begge er summen av alle elementene i tabellen.

Oppfølger:

La $x$ være et reelt tall slik at $x+x^{-1}$ er et heltall. Vis at $x^n+x^{-n}$ er heltall for alle positive heltall $n$.

Re: Julekalender #4

Lagt inn: 04/12-2017 18:40
av OYV
Jeg tror at påstanden kan bevises ved induksjon:

1) Gitt x + [tex]\frac{1}{x}[/tex] = heltall

Da er x[tex]_2[/tex] + [tex]\frac{1}{x^2}[/tex] = (x + [tex]\frac{1}{x}[/tex])[tex]^2[/tex] - 2 = heltall.

Antar nå at påstanden gjelder for n = k -1 og n = k , k [tex]\geq[/tex] 2

Da har vi at (x[tex]^k[/tex] + [tex]\frac{1}{x^k}[/tex] )(x + [tex]\frac{1}{x}[/tex]) = x[tex]^{k+1}[/tex] + [tex]\frac{1}{x^{k-1}}[/tex] + x[tex]^{k-1}[/tex] + [tex]\frac{1}{x^{k+1}}[/tex] som gir

x[tex]^{k+1}[/tex] + 1/x[tex]^{k+1}[/tex] = heltall

Dermed har vi vist at påstanden gjelder for alle positive heltall n større eller lik 1

Re: Julekalender #4

Lagt inn: 04/12-2017 20:13
av Gustav
Ser bra ut!

Enda en oppfølger:

Vi starter med mengden $\{1,2,3,...,100\}$, og sletter hvert minutt ut to tall $u,v$ som vi erstatter med $uv+u+v$ helt til vi ender opp med kun ett tall. Bestem dette tallet.

Hint:
[+] Skjult tekst
Finn en invariant

Re: Julekalender #4

Lagt inn: 04/12-2017 22:43
av Markus
Edit: tenkte feil, legger foreslått feil løsning i spoiler.
[+] Skjult tekst
Mulig jeg tenker helt feil her, men her er hvertfall det jeg
Opprinnelig tankeresonnement:
Prosessen kan beskrives som $-u - v + (uv + u + v) \to uv$, så produktet av $u$ og $v$ er invariant.
Siden alle tallene i mengden må multipliseres med hverandre før vi har en mengde med kun et element, må det som står igjen være resultatet av at alle tall i den opprinnelige mengden har blitt multiplisert sammen. Dette er akkurat dette fakultet-operasjonen gjør, så det tallet som står igjen må være $100!$.

Nytt tankeresonnement
Feilen med mitt forrige er det at den prosessen som beskrives er hvordan summen endrer seg, ikke hvordan den nye "plassen i mengden" vil se ut. Prosessen er heller at $u$ og $v$ går til å bli $uv + u + v$, så svaret må bli MER enn $100!$. Jeg ser at vi kan skrive om $uv + u + v$ til $(u+1)(v+1)$. Så det tallet du får etter prosessen er altså produktet av de to faktorene, der begge faktorene har blitt addert $1$ til. Det vil si at vi altså øker alle faktorer med $1$, så da er den maksimale faktoren $101$ og den minimale faktoren $2$, så det vi står igjen med må være $101!$, ved å bruke samme argumentasjon som i det opprinnelige tankeresonnementet.

Re: Julekalender #4

Lagt inn: 04/12-2017 22:49
av Emilga
Definer $x \circ y = xy+x+y$.

Ser at $x \circ y = y \circ x$ og $x \circ (y \circ z) = (x \circ y) \circ z$.

Altså er $1\circ 2 \circ \ldots \circ 100$ veldefinert.

Observerer også at $uv + u + v = (u+1)(v+1)-1$.

La $\{x_1, x_2, \ldots, x_n\}$.

Anta at dette settet reduseres til $R(n) = \prod_{i=1}^n (x_i + 1) - 1$.

Ser da at $\{x_1, x_2, \ldots, x_n, x_{n+1}\} \rightarrow \{R(n), x_{n+1}\}$

Altså: $R(n+1) = R(n)\cdot x_{n+1} + R(n) + x_{n+1} = \left( \prod_{i=1}^n (x_i + 1) - 1 \right)x_{n+1} + \prod_{i=1}^n (x_i + 1) - 1 + x_{n+1} = \left( \prod_{i=1}^n (x_i + 1) \right) x_{n+1} + \prod_{i=1}^n (x_i + 1) - 1 = \left( \prod_{i=1}^n (x_i + 1) \right) (x_{n+1} + 1) - 1 = \prod_{i=1}^{n+1} (x_i + 1) - 1$.

Siden $R(2)$ åpenbart stemmer, vil $\{x_1, x_2, \ldots, x_n\} \rightarrow \{ R(n) \}$ for alle $n \geq 2$.

Altså reduseres $\{1,2,3,...,100\} \rightarrow \{ 2\cdot 3\cdot 4\cdot \ldots \cdot 100 \cdot 101 - 1 \} = \{ 101! - 1 \}$

Re: Julekalender #4

Lagt inn: 04/12-2017 23:34
av Gustav
Fin og interessant løsning!

Jeg brukte funksjonen $f(x_1,x_2,...,x_{100}):=\prod_i (x_i+1)$, som er invariant under hver transformasjon $(u,v)\to (0,uv+u+v)$ siden $(u+1)(v+1)=(0+1)(uv+u+v+1)$. Dermed må det siste tallet som står igjen, $x$, tilfredsstille ligningen $x+1=(1+1)(2+1)...(99+1)(100+1)=101!$, ergo er $x=101!-1$.

Re: Julekalender #4

Lagt inn: 04/12-2017 23:36
av Emilga
En litt mer elegant løsning enn min forrige, der vi benytter oss av hintet:

La $\{x_1, x_2, \ldots, x_n\}$.

Definer $S(x_1, x_2, \ldots, x_n) = \prod_{i=1}^n (x_i + 1) - 1$.

Vi vil vise at verdien til $S(\cdot )$ er invariant under operasjonen $x_j, x_k \rightarrow x_j \circ x_k = x_j x_k + x_j + x_k$.

Ser at dersom vi erstatter $x_j$ og $x_k$ med $x_j \circ x_k$, får vi:

$S(x_{i \neq j,k}, x_j \circ x_k) = \left( \prod_{i \neq j,k} (x_i + 1) \right)(x_j x_k + x_j + x_k + 1) - 1 = \left(\prod_{i \neq j,k} (x_i + 1) \right)(x_j + 1)(x_k + 1) - 1 = \prod_{i=1}^n (x_i + 1) - 1$.

Altså er $S$ invariant.

Observerer også at $S( x_1 \circ x_2 \circ \ldots \circ x_n ) = x_1 \circ x_2 \circ \ldots \circ x_n + 1 - 1 = x_1 \circ x_2 \circ \ldots \circ x_n$

Altså er:

$x_1 \circ x_2 \circ \ldots \circ x_n = \prod_{i=1}^n (x_i + 1) - 1$.

EDIT: liker dog din løsning litt bedre, Gustav! Mindre å skrive... :lol:

Re: Julekalender #4

Lagt inn: 04/12-2017 23:57
av Emilga
Markus skrev:Jeg ser at vi kan skrive om $uv + u + v$ til $(u+1)(v+1)$.
Obs: $(u+1)(v+1) = uv + u + v+ 1 \neq uv + u + v$.

Men du er inne på noe!

Hvis $u,v \rightarrow (u+1)(v+1) - 1$

Hva skjer med $u,v,w \rightarrow $?

Ser du noe mønster?

Re: Julekalender #4

Lagt inn: 05/12-2017 16:00
av Markus
Tror det gikk opp et lite lys nå, med litt algebraisk triksing!

Hvis $u,v \to (u+1)(v+1) - 1$,

vil operasjonen $a + b + ab$ gi
$u,v,w \to (u+1)(v+1)-1 + w + w((u+1)(v+1)-1) = (w+1)((u+1)(v+1)-1)) + w = (w+1)(u+1)(v+1) - w - 1 + w = (w+1)(u+1)(v+1) - 1$

Da må videre $u,v,w,x \to (w+1)(u+1)(v+1) + x + x((w+1)(u+1)(v+1)-1) = (x+1)((w+1)(u+1)(v+1)-1)+ x = (x+1)(w+1)(u+1)(v+1) - 1 - x + x= (x+1)(w+1)(u+1)(v+1) - 1$

Prøver med en til "variabel" for å se om mønsteret fortsatt holder;
$u,v,w,x,y \to (x+1)(w+1)(u+1)(v+1) - 1 + y + y((x+1)(w+1)(u+1)(v+1)-1) = (y+1)((x+1)(w+1)(u+1)(v+1)-1) + y = (y+1)(x+1)(w+1)(u+1)(v+1) - y + y - 1 = (y+1)(x+1)(w+1)(u+1)(v+1) - 1$

Det ser ut som at mønsteret holder. Hvis mønsteret holder vil den høyeste variabelen være $100$, og den laveste $2$, men siden vi har at faktorene er $a + 1$, vil den høyeste faktoren i det vi ender opp med være $101$, og den laveste være $2$. Altså vil produktet være $101!$, også må vi trekke ifra $1$ slik som mønsteret viser over.

Altså ender vi opp med $101!-1$. Nå har jeg i alle fall fått samme svar som dere da :P - takk for at du pekte meg i riktig retning, og jeg håper at denne løsninga holder vann.


Re: Julekalender #4

Lagt inn: 05/12-2017 16:18
av Gustav
Ser bra ut! Har du en nøtt i luke #5 med det samme?

Re: Julekalender #4

Lagt inn: 05/12-2017 16:30
av Markus
Jeg skal da finne en ;)
Poster i ny tråd i alle fall.