olikhet – Mattebloggen

Brottartävling

100 brottare med olika styrkor ställde upp i en tävling. I en match möts två brottare och den starkare vinner alltid över den svagare. Först delade brottarna upp sig i par och körde mot varandra. Sedan delade alla deltagarna upp sig i par på något annat sätt och körde mot varandra igen. Man delade ut priser till de som vann båda sina matcher. Vilket är det minsta möjliga antalet priser som kunde delats ut?

Visa lösningen

Öva på delbarhet och ekvationer inför SMT-kval

Skolornas matematiktävling närmar sig med stormsteg, nu är det bara en vecka kvar! Jag har skrivit tips inför tävlingen förut, men om du träna på verkliga problem, rekommenderar jag att kolla på vår cirkellektion, som handlade just om delbarhet, ekvationer och olikheter.

Under lektionen bevisade vi alla de viktiga fakta man använder inom de områden när man löser tävlingsproblem och diskuterade kontrollfrågor. För att lyckas bra i tävlingen bör du kunna svara på i princip alla kontrollfrågor!

Försök sedan att lösa problem 1-4. De första tre problemen kommer från riktiga SMT-tävlingar, men jag skulle rekommendera att börja med problem 2 eller 4, eftersom de är lättast att lösa. Sedan ta dig an 1:an och till sist 3:an.

Problem vecka 19

Uttrycket (3 poäng).
Man utvecklade uttrycket (x+y)^n med hjälp av binomialsatsen. Den andra termen i summan blev lika med 240, den tredje blev lika med 720 och den fjärde blev lika med 1080. Hitta x, y och n.

Ön (7 poäng).
a) På en platt cirkelformad ö finns 4 hamnar (i den ordningen): 1, 2, 3 och 4. Mellan dem finns vägar där det kan finnas korsningar, det vill säga punkter där vägarna möts, korsas eller grenas. På alla sträckor är trafiken enkelriktad, på så sätt att man aldrig kan komma tillbaka till en hamn eller korsning om man startar därifrån. Låt f_ij beteckna antalet vägar som går från hamn i till hamn j.
Visa olikheten f₁₄f₂₃≥f₁₃f₂₄
b)

Visa att om det finns 6 hamnar (1, 2, 3, 4, 5, 6 i den ordningen) så gäller

f₁₆f₂₅f₃₄+f₁₅f₂₄f₃₆+f₁₄f₂₆f₃₅≥f₁₆f₂₄f₃₅+f₁₅f₂₆f₃₄+f₁₄f₂₅f₃₆

Visa lösningar

Uttrycket (Toomas lösning, kompletterad):
Vi har alltså en utveckling av ett binom (x+y) upphöjt i ett tal n enligt binomialsatsen sådant att den andra termen är lika 240, den tredje 720 och den fjärde lika 1080.

Vi förnimmer oss att binomialsatsen kan skrivas

$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$

Detta innebär att om vi ersätter den retoriska notationen i problemtexten med symbolisk algebra får ekvationssytemet

${n \choose 1}x^{n-1}y^1=240$

${n \choose 2}x^{n-2}y^2=720$

${n \choose 3}x^{n-3}y^3=1080$

som förstås kan förenklas till

$nx^{n-1}y=240$

$\frac{1}{2}(n^2-n)x^{n-2}y^2=720$

$\frac{1}{6}(n-2)(n-1)nx^{n-3}y^3=1080$

Dividera den andra ekvationen med den första, samt den tredje ekvationen med den andra:

$\frac{1}{2}(n-1)\frac{y}{x}=3\ \ \Rightarrow \ \ (n-1)y=6x$

$\frac{1}{3}(n-2)\frac{y}{x}=\frac{3}{2}\ \ \Rightarrow \ \ (n-2)y=\frac{9}{2}x$

Subtrahera den andra ekvationen från den första

$y=\frac{3}{2}x$

och gör en ersättning i en av ekvationerna för att få n:

$(n-1)\frac{3}{2}x=6x\ \ \Rightarrow \ \ n-1=4 \ \ \Rightarrow \ \ n=5$

Nu kan vi göra ersätta n med 5 i den första ursprungliga ekvationen:

$5x^4\frac{3}{2}x=240 \ \ \Rightarrow \ \ x^5=32 \ \ \Rightarrow \ \ x=2$

$y=\frac{3}{2}\cdot 2=3$

Den enda lösningen är alltså n=5, x=2 och y=3.

Ön (Skäggets lösning, något modifierad):

a) Vi noterar att f₁₃*f₂₄ kan ses som antalet sätt man kan gå från 1 till 3 och sedan från 2 till 4, och att f₁₄*f₂₃ är antalet sätt man kan gå från 1 till 4 och sedan från 2 till 3.

En väg från 1 till 3 delar vår ö i två delar, med 2 och 4 på olika sidor. Således måste en väg från 2 till 4 korsa varje väg från 1 till 3 vid minst en punkt.

Tag en godtycklig väg som går från 1 till 3 (kalla den A) och sedan magiskt fortsätter vid 2 och går till 4 (via en väg B). A och B måste korsa varann i någon punkt X (vi kan exempelvis välja den första korsningen på A).

Antag att vi börjar från 1 och följer A tills vi når X. Sedan fortsätter vi längs väg B tills vi når 4. Sedan hamnar vi på något magiskt vis i 2 och följer B tills vi når X, och följer sedan A till 3.

Vi ser att för varje sammansättning A och B får vi en väg från 1 till 4 och sedan 2 till 3. Detta ger upphov till en funktion som uppenbart är injektiv (två vägar måste ju ha identiska vägsegment såväl före som efter X för att ett vägskifte vid X ska ge samma resultat, och då är de samma väg).

Således har vi en injektiv funktion från mängden av vägar 1-3-2-4 (med magiskt hopp från 3 till 2) och mängden av vägar 1-4-2-3 (med magiskt hopp från 4 till 2). Dessas mängders storlekar är som vi noterat f₁₃*f₂₄ respektive f₁₄*f₂₃, och således har vi visat olikheten i fråga.

b)Vi ser att vänsterledet kan ses som unionen av alla vägar 1-6-2-5-3-4 och 1-5-2-4-3-6 och 1-4-2-6-3-5 (med magiska hopp), sådana vägar kallar vi udda. Högerledet kan ses unionen av alla vägar 1-6-2-4-3-5 och 1-5-2-6-3-4 och 1-4-2-5-3-6, sådana vägar kallar vi jämna. Om två hamnar med nummer 4, 5 eller 6 byter plats i en väg, byter vägen paritet.

Tag en väg 1-x-2-y-3-z, där {x,y,z} är en permutation av {4,5,6}. Om delsträckorna skär varandra någonstans, kalla skärningspunkten närmast 1 för M (det vill säga skärningspunkten som kommer först på sträckan 1-x om den sträckar korsar andra, annars skärningspunkten närmast 2 på sträckan 2-y). Byt plats på vägsluten efter punkten M, precis som i punkt a). (Om alla delsträckorna går genom M bestämmer vi en regel om att alltid byta plats på vägsluten av desträckorna 1-i och 2-j.)

Om man byter två stycken vägslut byter vägen paritet. På så sätt har vi bestämt en bijektion mellan udda och jämna vägar som har korsningar. Varje väg som inte har korsningar är dessutom en udda väg av typ 1-6-2-5-3-4. Därför finns det minst lika många udda vägar som jämna. Av det följer olikheten.

Mattecirkel med Anna: lektion 2

Här är ett smakprov av vår andra lektion, som handlar om att väga saker på en balansvåg och avgöra om de är lätta, tunga, falska etc. Här nedan ser ni några av lektionens svåraste problem.

lektion2

Nu kan man försöka analysera vad det är egentligen som lärs ut på mattecirkeln. På sätt och vis är lektionerna mycket mer lika spel än någon annan undervisningsform. Mycket görs på egen hand och man ”levlar” när problemernas svårighetsgrad ökar. Samtidigt används det man samlade på sig under tidigare ”levels” (lättare problem).

En bra lektion lär ut idéer. Den här lektionen lärde inte ut någon specifik idé, utan var en härlig blandning av olikheter, informationsteori, falluppdelning och kombinatorik. Som inte i sig är metoder, utan just idéer till lösningar. Jag avslutar med ett citat:

What is the difference between method and device? A method is a device which you used twice.

–George Pólya, ”How to solve it”