Mattebloggen

Posts tagged ‘olikhet’

Problem vecka 19

10 maj 2011, 18:47

De här problemen ingår i mattebloggens tävling vårterminen 2011, men man kan inte skicka in lösningar på dem längre. Kolla istället tävlingens regler och den aktuella poängställningen. Lösningarna kan du titta på nedan.

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.

Etiketter:binomialsatsen, injektion, olikhet, paritet, väg
Category: Roliga mattegåtor | Kommentar

Lösning till gåta vecka 45

17 november 2009, 16:19

Robert tänker på två positiva tal: x och y. Han skriver ner 4 tal på ett papper: x+y, x-y, xy och $\frac{x}{y}$ , men säger inte i vilken ordning han skriver ner dem. Hur kan Adam lista ut vilka tal Robert tänker på genom att bara titta på pappret (Adam vet alltså inte vilken operation varje tal motsvarar)?

Bra att känna till:

Det aritmetiska medelvärdet (AM) av två tal $a$ och $b$ är talet $\frac{a+b}{2}$ . Man brukar också bara säga ”medelvärde” om det aritmetiska medelvärdet.

Det geometriska medelvärdet (GM) av två tal $a$ och $b$ är talet $\sqrt{a\cdot b}$ .

AM-GM-olikheten: Det aritmetiska medelvärdet är alltid större än eller lika med det geometriska medelvärdet för två tal:

$\frac{a+b}{2} \geq \sqrt{a\cdot b}$

Lösning:

Adam vet att det finns två tal, vars geometriska medelvärde är lika med det andra talparets aritmetiska medelvärde. Hitta en sådan uppdelning av de fyra talen i par, så att det villkoret är uppfyllt. Det vill säga vi har hittat a, b, c, d sådana att

$\frac{a+b}{2}=\sqrt{c\cdot d}$ .

Men är de talen verkligen vad vi tror att de är? Det vill säga, måste det vara så att a och b är x+y och x-y (i någon ordning) och c och d motsvarar xy och x/y (också i någon ordning)?

Vi skall visa att det verkligen måste vara så.

Antag att x+y och x-y inte gömmer sig på samma sida om likheten

$\frac{a+b}{2}=\sqrt{c\cdot d}$ .

Det vill säga, man har tagit likheten

$\frac{(x+y)+(x-y)}{2}=\sqrt{xy\cdot \frac{x}{y}}$

och bytt plats på en av termerna i vänsterledet med en av termerna i högerledet och det ändå blev lika.

Men sådant händer bara om talen vi bytte plats på är lika (annars skulle resultatet på ena ledet minska och på den andra öka, och då skulle de inte varit lika längre).

Och om talen ändå varit lika, så spelar det ingen roll, vilket av dem vi väljer som a (eller b).

Så hur vet vi att a och b är paret $\{x+y, x-y\}$ och inte paret $\{xy, \frac{x}{y}\}$ ? Enda sättet att blanda ihop det hela om följande likhet också gäller:

$\frac{xy+\frac{x}{y}}{2}=\sqrt{(x+y)\cdot (x-y)}$ .

Men tillämpa då AM-GM-olikheten:

$\frac{xy+\frac{x}{y}}{2} \geq \sqrt{xy\cdot \frac{x}{y}}=x$ .

Således får vi:

$\sqrt{(x+y)\cdot (x-y)} \geq x$

och

$(x+y)\cdot (x-y) = x^2 - y^2 \geq x^2$

vilket är omöjligt för positiva tal x och y.

Vi vet alltså att ena talet i paret a, b är x-y (nämligen det minsta av dem) och andra är x+y (det största av dem).

Man kan räkna ut x genom att ta (det aritmetiska) medelvärdet av de talen och man räknar sedan ut y, genom att ta det största talet utav a och b och subtrahera x.

Etiketter:medelvärde, olikhet, talteori
Category: Problemlösning | Kommentar

Mattecirkel med Anna: lektion 2

29 mars 2009, 22:57

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”

Etiketter:balansvåg, idé, mattecirkel, olikhet
Category: Roliga mattegåtor | Kommentar

Lösning till gåta vecka 22 (4)
- Lisa: Mmm, man kan ju tänka så att börjar man i toppen på pyramiden finns endast en möjlighet....
- JohanB: Man kan också tänka på följande sätt: Vi noterar att om ödlan någonsin läser till höger...
Polisbilen (4)
- Val: Lösningen är uppe! :)
- JohanB: Då ser jag fram emot lösningen :)
En lektion för små barn i topologi (5)
- JohanB: det finns flera stycken torusspel, (ca 10 st tror jag). Alla spelen utspelar sig på en...
Hungrig student (11)
- JS: Jag tror jag bevisat en ganska så formell lösning för det generella fallet med n burgare, k...

Problem vecka 19

Visa lösningar

Lösning till gåta vecka 45

Bra att känna till:

Lösning:

Mattecirkel med Anna: lektion 2

Roligaste gåtorna

Länklista

Nya kommentarer

Kategorier