God blanding

[Gustav]

$(4) \enspace$ Gitt mengden $M = \{1,2,3,\dots,2017,2018 \}$ og den tomme mengden $S$. Du plukker et og et tall tilfeldig, "fjerner" de fra mengden $M$ og legger de i mengden $S$. Hvor mange tall må det være i mengden $S$ før du er ABSOLUTT SIKKER på at MINST et par av tallene i mengden $S$ summerer til $2019$?

Vi lager oss tomme bokser/mengder som vi kaller {1,2018}, {2,2017},...,{1009,1010}, som hver har plass til 2 baller. Mengden M kan vi tenke på som 2018 baller som vi skal flytte over i de nevnte boksene. Problemet omformuleres til hvor mange baller vi må flytte fra M over i boksene for å være garantert at det fins en boks med to baller. Dueboksprinsippet sier da at vi minst må flytte 1010 baller.

[Markus]

Løsning

Interessant løsning! Når jeg løste den selv første gang skrev jeg bare opp noen av leddene, og fant fort mønsteret. En alternativ løsning er å se at vi kan skrive om differenslikningen til $a_{n+2} = 3a_{n+1} - 2a_{n}$, som har det karakteristiske polynomet $r^2 - 3r + 2$, som har de to reelle løsningene $r_1 = 1$ og $r_2 = 2$, når polynomet blir satt lik $0$. Da vet vi at den eksplisitte formelen til følgen er $x_n = C1^n + D2^n = C + D2^n$. Initialbetingelse gir likningssystemet;

$x_0 = C + D \Longrightarrow 0 = C + D$
$x_1 = C + 2D \Longrightarrow 1 = C + 2D$

Der løsningene er $C = -1$, $D= 1$

Da er den eksplisitte formelen til følgen $x_n = 2^n - 1$. Resten løste jeg helt likt som deg.

Løsning

Selvfølgelig helt korrekt. Brukte dueboksprinsippet selv også.

[zzzivert]

$(11) \enspace$ Fermat-tallene $F_n$ er definert ved $\displaystyle F_n = 2^{2^n} +1$ for $n=0,1,2,\dots$. Vis at to Fermat-tall $F_n$ og $F_m$, der $n \neq m$ er relativt primiske.

Anta til motsetning at $p$ deler både $F_n$ og $F_m$, der $m < n=m+d$. Da får vi
$F_n = 2^{2^n} +1= 2^{2^{m+d}} +1=2^{2^m 2^d} +1=(2^{2^m})^{2^d}+1$
$F_m \equiv 0 \ \ \text{mod} \ p$
$ 2^{2^m} +1 \equiv 0 \ \ \text{mod} \ p$
$ 2^{2^m} \equiv -1 \ \ \text{mod} \ p$
$(2^{2^m})^{2^d} \equiv (-1)^{2^d}=1 \ \ \text{mod} \ p$
$F_n \equiv 2 \ \ \text{mod} \ p$
Som er en motsetning da $p \neq 2$.

[Markus]

Anta til motsetning at $p$ deler både $F_n$ og $F_m$, der $m < n=m+d$. Da får vi
$F_n = 2^{2^n} +1= 2^{2^{m+d}} +1=2^{2^m 2^d} +1=(2^{2^m})^{2^d}+1$
$F_m \equiv 0 \ \ \text{mod} \ p$
$ 2^{2^m} +1 \equiv 0 \ \ \text{mod} \ p$
$ 2^{2^m} \equiv -1 \ \ \text{mod} \ p$
$(2^{2^m})^{2^d} \equiv (-1)^{2^d}=1 \ \ \text{mod} \ p$
$F_n \equiv 2 \ \ \text{mod} \ p$
Som er en motsetning da $p \neq 2$.

Fint vist! Selv gjorde jeg det litt annerledes;

Jeg brukte følgende lemma; For $n \geq 1$ er $F_n = F_0 \cdots F_{n-1} + 2$. Denne kan lett bevises ved induksjon, men jeg tar ikke det med i denne svaret. Jeg bruker også det faktum at alle Fermat-tall er odde, noe man lette ser ved å se at $2^{2^n}$ alltid er partall, så da må $2^{2^n} + 1$ alltid være oddetall.

Vi bruker lemmaet, og lar et Fermat-tall $F_n= F_0 \cdot F_1 \cdots F_m \cdots F_{n-1} + 2$. Anta at $\exists a$ slik at $a \mid F_m$ og $a \mid F_n$. Siden $a$ er en faktor i $F_m$ må det være også være en faktor i $F_0 \cdot F_1 \cdots F_m \cdots F_{n-1}$. Dette impliserer at $2 \mid F_n - F_0 \cdot F_1 \cdots F_m \cdot F_{n-1}$. Siden oddetall multiplisert med oddetall alltid gir oddetall, og alle Fermat-tall er oddetall, følger det at produktet $F_0 \cdot F_1 \cdots F_m \cdot F_{n-1}$ er oddetall, og $F_n$ er også oddetall da det er et Fermat-tall. Siden $2$ kun har faktorene $2$ og $1$, og venstresidens to ledd begge er oddetall, er den eneste mulige verdien for $a=1$. Da er $F_n$ og $F_m$ relativt primiske.