Litt Abelkombinatorikk

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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?
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
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
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.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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)
Mattebruker

Heilt enig ! Moral: Gå ikkje over bekken etter vatn !
MatIsa
Dirichlet
Dirichlet
Innlegg: 150
Registrert: 12/06-2013 12:09
Sted: Trondheim

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}$.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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å?
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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.
Svar