Side 1 av 1

Litt Abelkombinatorikk

Lagt inn: 12/08-2018 23:53
av Markus
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?

Re: Litt Abelkombinatorikk

Lagt inn: 13/08-2018 12:15
av Mattebruker
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

Re: Litt Abelkombinatorikk

Lagt inn: 13/08-2018 12:29
av Mattebruker
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

Re: Litt Abelkombinatorikk

Lagt inn: 13/08-2018 13:17
av Mattebruker
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.

Re: Litt Abelkombinatorikk

Lagt inn: 13/08-2018 22:23
av Markus
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)

Re: Litt Abelkombinatorikk

Lagt inn: 13/08-2018 22:35
av Mattebruker
Heilt enig ! Moral: Gå ikkje over bekken etter vatn !

Re: Litt Abelkombinatorikk

Lagt inn: 15/08-2018 16:43
av MatIsa
Markus skrev:$\mathbf{[3]}$ Hvor mange delmengder av $\{1,2,\dots,2016\}$ inneholder minst et oddetall?
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}$.

Re: Litt Abelkombinatorikk

Lagt inn: 03/09-2018 13:31
av Markus
MatIsa skrev:
Markus skrev:$\mathbf{[3]}$ Hvor mange delmengder av $\{1,2,\dots,2016\}$ inneholder minst et oddetall?
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}$.
Flotters! Noen som tar $[2]$ også?

Re: Litt Abelkombinatorikk

Lagt inn: 09/09-2018 15:40
av Gustav
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?
Modulo 2 (på hvert siffer) kan vi danne følgende seks permutasjoner: (fire oddetall og tre partall )
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.

Re: Litt Abelkombinatorikk

Lagt inn: 17/09-2018 00:26
av Markus
Gustav skrev:
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?
Modulo 2 (på hvert siffer) kan vi danne følgende seks permutasjoner: (fire oddetall og tre partall )
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.