Tjena gänget,
Härlig träff igår! Nedan kommer lösningarna till seminarieuppgifterna som vi diskuterade igår.
Uppgift 1:
- - - - - - - -
a) För varje \(x: 1 \leq x \leq 99\) finns det \(\binom{100}{x}\) sätt att välja grupp \(A\) av storlek \(x\). Så fort vi bestämt grupp \(A\) så bestäms grupp \(B\) automatiskt och det följer att svaret till uppgiften ges av
\(\sum_{x=1}^{99} \binom{100}{x}\).
b) Skillnaden här är att två fördelningar av grupper i den föregående uppgiften klassas som samma om vi kan få den ena från den andra genom att byta plats på gruppnamnen. För varje fördelning av grupper finns det därför exakt en annan unik fördelning som är helt ekvivalent. Därför är svaret hälften av det vi fick fram i den föregående uppgiften.
OBS! Några av er var fundersamma över fallet \(x =50\), vilket är bra! Men notera att detta inte är något specialfall här. Med andra ord, oavsett storleken på gruppen finns det för varje fördelning av grupper exakt en annan unik fördelning som är helt ekvivalent.
Uppgift 2:
- - - - - - - -
Låt \(x_{1} < x_{2} < ...< x_{5}\) representera vårt val av naturliga tal från mängden \(M = \{1 , 2 ,3 , ..., 18\}\)
där \(|x_{j} - x_{i}| < 2\) håller för varje par \((i,j)\). Definiera nu \(6\) nya variabler enligt
\(y_{1}\) := Antalet ej valda tal innan \(x_{1}\)
\(y_{2}\) := Antalet ej valda tal emellan \(x_{1}\) och \(x_{2}\)
\(y_{3}\) := Antalet ej valda tal emellan \(x_{2}\) och \(x_{3}\)
\(y_{4}\) := Antalet ej valda tal emellan \(x_{3}\) och \(x_{4}\)
\(y_{5}\) := Antalet ej valda tal emellan \(x_{4}\) och \(x_{5}\)
\(y_{6}\) := Antalet ej valda tal efter \(x_{5}\)
(Så t.ex. om vårt val av siffror var \(x_{1} = 1 , x_{2} = 5 , x_{3} = 8 , x_{4} = 14 , x_{5} = 17\) så skulle
\(y_{1} =0 , y_{2} = 3 , y_{3} = 2 , y_{4} = 5 , y_{5} = 2 , y_{6} = 1\).)
Det går nu att visa att det ursprungliga problemet är helt ekvivalent med att räkna antalet heltalslösningar till ekvationen (Lämnar beviset som en övning. Om man vill vara riktigt rigorös behöver man visa att man kan definiera en bijektiv avbildning mellan mängden lösningar till det ursprungliga problemet till mängden lösningar till det nya problemet.)
\(y_{1} + y_{2} + y_{3} + y_{4} + y_{5} +y_{6} = 13\)
där \(y_{1} , y_{6} \geq 0\) och \(y_{2} , ... , y_{5} \geq 1\).
Med variabelbytet \(z_{1} = y_{1} , z_{2} = y_{2} - 1 , z_{3} = y_{3} -1 , z_{4} = y_{4} - 1 , z_{5} = y_{5} -1 , z_{6} = y_{6}\) övergår ekvationen till att lösa den nya ekvationen
\(z_{1} + (z_{2} +1) + (z_{3}+ 1) + (z_{4} + 1) + (z_{5} + 1) + z_{6} = 13\)
\(z_{i} \geq 0 , \forall i\)
\(\iff\)
\(z_{1} + z_{2} + z_{3} + z_{4} + z_{5} + z_{6} = 9\)
\(z_{i} \geq 0 , \forall i\)
och svaret till detta är \(\binom{9 + (6-1)}{6-1} = \binom{14}{5}\) enligt
"Stars and bars" teoremet.
Uppgift 3:
- - - - - - - -
Jag kanske bör ha lagt denna som uppgift \(2\) :(. Hursomhelst så
är intuitionen följande: Vi tänker oss att vi har \(n-1\) avdelare (bars) och
\(k\) prickar (stars) som omordnas. Notera nu att varje omordning av dessa, kodar
en unik lösning till det ursprungliga problemet och vice versa. Antalet prickar till vänster om den första
baren bestämmer värdet på \(x_{1}\), antalet prickar emellan den första och den andra baren bestämmer värdet på \(x_{2}\) , ..., antalet prickar efter den sista baren (bar \(n-1\)) bestämmer värdet på \(x_{n}\). Eftersom antalet sätt att omordna \(k\) prickar och \(n-1\) avdelare ges av \(\binom{k +(n-1)}{n-1}\) följer det att detta även är antalet heltalslösningar till den givna ekvationen.
För er som fortfarande inte är helt övertygade över "Stars and bars" teoremet så kan det vara värt att kika följande video från "Numberphile" (Från minut \(6\) ungefär):
https://www.youtube.com/watch?v=UTCScjoPymA
Om ni har frågor eller funderingar så är det bara att höra av er till oss via vår mailadress som är
utmanande-matematik@math.su.se.
För er som redan deltagit i tidigare seminarier, ni får jättegärna maila oss
och skriva hur många seminarier ni deltagit i så att vi inte skriver ner felaktig information.
Vi ses igen nästa vecka. Allt gott och ta hand om er!
Med vänliga hälsningar,
Emil Eriksson
Uppgift 3:
- - - - - - - -
Lösningar till seminarieuppgifter 24/6 + Information kring närvarolista
av Emil Eriksson -
Antal svar: 0