Litt kombinatorikk fra tidligere år av Abelkonkurransen.
$\mathbf{[1]}$ Hvor mange følger av heltall $a_1,a_2,\dots,a_{10}$ tilfredstiller $$0<a_1<a_2<a_3<a_4<a_5<a_6<a_7<a_8<a_9<a_10<13$$ $\mathbf{[2]}$ Hvor mange syvsifrede tall kan lages ved å bytte om på sifrene i $1234567$ slik at hvert av oddetallssifrene har nøyaktig ett annet oddetallssiffer ved siden av seg?
$\mathbf{[3]}$ Hvor mange delmengder av $\{1,2,\dots,2016\}$ inneholder minst et oddetall?
$\mathbf{[4]}$ Finn antall tripler $(a,b,c)$ der $a,b,c$ er positive heltall slik at $a,b,c$ tilfredstiller likningene $a+b+c=111$ og $a+2b+3c=123$. Bonus: Hvilke tripler er dette?
Litt Abelkombinatorikk
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
OPPG. 1
Ulikskapen 0 < [tex]a_{1}[/tex] <........................ < [tex]a_{10}[/tex] < 13
[tex]\Leftrightarrow[/tex]
1 [tex]\leq[/tex] [tex]a_{1}[/tex][tex]\leq[/tex]................[tex]\leq[/tex] [tex]a_{10}[/tex] [tex]\leq[/tex] 12
Ulikskapen 0 < [tex]a_{1}[/tex] <........................ < [tex]a_{10}[/tex] < 13
[tex]\Leftrightarrow[/tex]
1 [tex]\leq[/tex] [tex]a_{1}[/tex][tex]\leq[/tex]................[tex]\leq[/tex] [tex]a_{10}[/tex] [tex]\leq[/tex] 12
Tal følgja [tex]a_{1}, .............., a_{10}[/tex] inneheld 10 element , og desse skal hentast frå ei samling på 12 element
( 1 [tex]\leq[/tex] [tex]a_{n}[/tex] [tex]\leq[/tex] 12 , 1 [tex]\leq[/tex] n [tex]\leq[/tex] 10 )
Dette talsettet kan setjast saman på [tex]\binom{12}{10}[/tex] ulike måtar = [tex]\binom{12}{2}[/tex] = [tex]\frac{12\cdot 11}{2\cdot 1}[/tex] = 66
( 1 [tex]\leq[/tex] [tex]a_{n}[/tex] [tex]\leq[/tex] 12 , 1 [tex]\leq[/tex] n [tex]\leq[/tex] 10 )
Dette talsettet kan setjast saman på [tex]\binom{12}{10}[/tex] ulike måtar = [tex]\binom{12}{2}[/tex] = [tex]\frac{12\cdot 11}{2\cdot 1}[/tex] = 66
OPPG. 4
Subtraherer likning ( 1 ) fra likning ( 2 ) , og får
b + 2c = 123 - 111 = 12
Dette er ei diofantisk likning .
Allmenn løysing: b = 36 + 2m og c = -12 - m
Da er a = 111 - b - c = 87 - m
Akseptabel løysing: a > 0 [tex]\wedge[/tex] b > 0 [tex]\wedge[/tex] c > 0
[tex]\Leftrightarrow[/tex] -17 [tex]\leqslant[/tex] m [tex]\leq[/tex] -13
Svar: 5 taltrippel tilfredsstiller likningssettet.
Subtraherer likning ( 1 ) fra likning ( 2 ) , og får
b + 2c = 123 - 111 = 12
Dette er ei diofantisk likning .
Allmenn løysing: b = 36 + 2m og c = -12 - m
Da er a = 111 - b - c = 87 - m
Akseptabel løysing: a > 0 [tex]\wedge[/tex] b > 0 [tex]\wedge[/tex] c > 0
[tex]\Leftrightarrow[/tex] -17 [tex]\leqslant[/tex] m [tex]\leq[/tex] -13
Svar: 5 taltrippel tilfredsstiller likningssettet.
Flotters mattegjest! Løste oppgavene mer eller mindre likt som deg. På sistnevnte vil jeg derimot si det er litt overkill å finne den generelle løsningen for den diofantiske likningen $b+2c=12$, siden det er kun en håndfull tilfeller å sjekke (sett $c=1,2,3,4,5$ og du er i mål)
Totalt antall delmengder av $\{1, 2,\dots, 2016\}$ er $2^{2016}$. Antall delmengder som inneholder minst et oddetall er $2^{2016}-n$, der $n$ er antall delmengder av $\{1, 2,\dots, 2016\}$ som ikke inneholder et eneste oddetall. $n$ er da lik antall delmengder av $\{2, 4, \dots, 2016\}$, som er $2^{1008}$. Svaret er dermed $2^{2016}-2^{1008}$.Markus skrev:$\mathbf{[3]}$ Hvor mange delmengder av $\{1,2,\dots,2016\}$ inneholder minst et oddetall?
Flotters! Noen som tar $[2]$ også?MatIsa skrev:Totalt antall delmengder av $\{1, 2,\dots, 2016\}$ er $2^{2016}$. Antall delmengder som inneholder minst et oddetall er $2^{2016}-n$, der $n$ er antall delmengder av $\{1, 2,\dots, 2016\}$ som ikke inneholder et eneste oddetall. $n$ er da lik antall delmengder av $\{2, 4, \dots, 2016\}$, som er $2^{1008}$. Svaret er dermed $2^{2016}-2^{1008}$.Markus skrev:$\mathbf{[3]}$ Hvor mange delmengder av $\{1,2,\dots,2016\}$ inneholder minst et oddetall?
Modulo 2 (på hvert siffer) kan vi danne følgende seks permutasjoner: (fire oddetall og tre partall )Markus skrev:$\mathbf{[2]}$ Hvor mange syvsifrede tall kan lages ved å bytte om på sifrene i $1234567$ slik at hvert av oddetallssifrene har nøyaktig ett annet oddetallssiffer ved siden av seg?
1101100
1100110
1100011
0110110
0110011
0011011
For hver av disse er det $4!\cdot 3!$ permutasjoner, så totalt kan vi lage $6\cdot 4!\cdot 3!=864$ tall.
Fin og enkel løsning! Fra årets Abel.Gustav skrev:Modulo 2 (på hvert siffer) kan vi danne følgende seks permutasjoner: (fire oddetall og tre partall )Markus skrev:$\mathbf{[2]}$ Hvor mange syvsifrede tall kan lages ved å bytte om på sifrene i $1234567$ slik at hvert av oddetallssifrene har nøyaktig ett annet oddetallssiffer ved siden av seg?
1101100
1100110
1100011
0110110
0110011
0011011
For hver av disse er det $4!\cdot 3!$ permutasjoner, så totalt kan vi lage $6\cdot 4!\cdot 3!=864$ tall.