matematikk.net

På en tavle står alle tallene fra 1 til 100. Hvert minutt visker vi ut to tall - la oss kalle dem u og v - og erstatter dem med tallet (uv + u + v). Slik fortsetter vi til det bare er ett tall igjen på tavla. Hvor mange ulike verdier kan vi stå igjen med til slutt?

Akkurat nå føles det som om 1 kunne være det riktige svaret her. Men alltid farlig å gjøre matte etter midnatt!

Bevis?

Ville hatt en litt sikrere tone i forrige post hadde jeg hatt bevis! Tror jeg skal sette et induksjonsbevis til gjæring over natta og se hva som skjer.

morsom nøtt.

Jeg bare prøvde litt med mye færre tall (noe som er smart i slik problemløsning)
Tar 3 tall, og kaller dem [tex]a_1, a_2 og a_3[/tex]
uansett hvilke tall vi legger sammen først, ender vi opp med

[tex]a_1+a_2+a_3+a_1a_2a+a_1a_3+a_2a_3+a_1a_2a_3[/tex]

som (om man vil) faktoriseres til

[tex](a_1+1)(a_2+1)(a_3+1)-1[/tex]


Men her slipper jeg litt opp for ideer, siden dette bare er et enkelttilfelle. Mulig man kan bruke induksjon for å gå videre, men dette bør vel være i nærheten av noe.

Et hint kanskje dao ?

Joda, dette er ikke så dumt. Jeg ville kanskje gått tilbake til tilfellet med 2 tall, og sett om jeg kunne finne et liknende uttrykk. Kan det brukes til generalisering skal tro? Hva skjer når man syr sammen to tall? Hva hvis man syr sammen et tall med et allerede sammensydd tall?

En annen metode å tenke på hvis man prøver å vise at det bare en én løsning, er jo å tenke på andre funksjoner som tilfredsstiller kravet. Hva hvis vi hadde erstattet u og v med u + v? Da hadde tallet vi fikk i slutten vært enkelt å holde styr på. Hva hvis vi fjernet u og v og skrev uv? Samme her. Det samme fungerer ikke med u - v eller u/v. Hva slags egenskaper er det addisjon/multiplikasjon har som ikke subtraksjon/divisjon har, som gjør at vi får et entydig svar til slutt?

En tredje måte å tenke på er å se om man kan relatere spørsmålet til en funksjon og sin invers.

Det var noen få hint. Det finnes sikkert flere måter å løse oppgaven på óg.

Nå ble ting plutselig klart. Mange takk for alle hint. Om vi har n tall [tex][a_1, a_2 ... a_n][/tex] på tavla og fjerner to tall u og v hvert minutt for så å erstatte dem med [tex]u+v+uv[/tex] vil vi etter n minutter stå igjen med tallet [tex](\prod_{i=1}^n (a_i+1)) - 1[/tex]. Dette viser vi med induksjon. Ice har allerede vist tilfellet [tex]n=3[/tex]. Vi går så utifra at tilfellet [tex]n=k[/tex] stemmer og viser at dette fører til at tilfellet [tex]n=k+1[/tex] stemmer.

Når vi starter står tallene [tex][a_1, a_2 ... a_{k+1}][/tex] på tavla. Etter ett minutt har vi strøket to av dem - antar uten tap av generalitet at dette er [tex]a_k[/tex] og [tex]a_{k+1}[/tex]- og erstattet dem med [tex]a_k + a_{k+1} + a_k a_{k+1}[/tex]. Da står tallene [tex][a_1, ... a_{k-1}, a_k + a_{k+1} + a_k a_{k+1}][/tex] på tavla. Dette er k tall, og da har vi av induksjonshypotesen at tallet som vil stå igjen til slutt må være [tex] (\prod_{i=1}^{k-1} (a_i +1)) (a_k+a_{k+1}+a_ka_{k+1}) - 1[/tex]. Vi skriver [tex]a_k+a_{k+1}+a_ka_{k+1}+1[/tex] om til [tex](a_k+1)(a_{k+1}+1)[/tex] og setter dette inn i uttrykket vårt: [tex] (\prod_{i=1}^{k-1} (a_i +1)) (a_k+1)(a_{k+1}+1) - 1 = (\prod_{i=1}^{k+1} (a_i +1)) - 1[/tex] som var akkurat det vi ville vise. Induksjonshypotesen vår var altså bevist. Om vi setter tilfellet oppgaven handlet om inn i oppgaven ser vi at svaret må bli [tex]101!-1[/tex].

EDIT: Hva er koden for store, fine tex-parenteser igjen?

Eksempel:

[tex]\left(\prod_{k=1}^n 3nk\right)[/tex]

Ser bra ut Karl Erik, har ikke lest over beviset du skrev ned fullstendig, men du har definitivt skjønt poenget.

Slik jeg selv løste den først: Definer [tex]a \circ b = ab + a + b[/tex] Vi ser at [tex]\circ[/tex] er kommutativ. Vi ser og at [tex]a \circ (b \circ c) = (a \circ b) \circ c[/tex], som betyr at [tex]\circ[/tex] også er assosiativ. Dette betyr at [tex]x_1 \circ \cdots \circ x_n[/tex] er entydig bestemt av x'ene.

En litt mer generalisert løsningsmåte jeg så:
La f(x) være den bijektive funksjonen i heltall [tex]f(x) = x +1[/tex] Da ser vi at vi alltid erstatter u og v med [tex]f^{-1}(f(u)f(v))[/tex], noe som betyr at tallet vi ender opp med til slutt blir [tex]f^{-1}(f(x_1)\cdots f(x_n))[/tex]. Dette er i grunnen det samme som du har gjort over, men kaster kanskje litt lys på hva slags binæroperasjoner som har den ønskede egenskapen.