Julekalender #4
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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$.
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$.
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$.
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
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
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:
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:
Edit: tenkte feil, legger foreslått feil løsning i spoiler.
Sist redigert av Markus den 04/12-2017 23:56, redigert 2 ganger totalt.
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 \}$
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 \}$
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$.
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$.
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...
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...
Obs: $(u+1)(v+1) = uv + u + v+ 1 \neq uv + u + v$.Markus skrev:Jeg ser at vi kan skrive om $uv + u + v$ til $(u+1)(v+1)$.
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?
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 - takk for at du pekte meg i riktig retning, og jeg håper at denne løsninga holder vann.
Så
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 - takk for at du pekte meg i riktig retning, og jeg håper at denne løsninga holder vann.
Så