«

»

Feb 13

Programmering, matematik och bevisföring

Spread the love

Hur man kan använda programmering för att tjäna matematikundervisningen är något som upptar mina tankar. Ett konkret exempel är vid bevisföring. Användningen av program kräver att man antingen letar efter ett motexempel (motbevis) eller genomför ett bevis som kräver att ett ändligt antal fall kontrolleras.

Ett exempel på det senare är fyrfärgssatsen som 1976 bevisades av Appel och Haken genom att de reducerat problemet till ett ändligt antal fall som sedan kontrollerades med hjälp av ett program. Fyrfärgssatsen är dock ett för avancerat problem att genomföra med sina elever.

Ett bättre exempel är Eulers förmodan om summor med samma exponent. Det är en utvidgning av Fermats stora sats och säger att för att ekvationen a_1^k+a_2^k+\cdots+a_n^k=b^k enbart har heltalslösningar om n \geq k. Det första motbeviset publicerades 1966 av Lander och Parker.

Artikeln är kort då det är ett motbevis, dock står det att de använde ett datorprogram för att hitta motexemplet. Det står ingenting om hur detta datorprogram såg ut. Det kan vara en ingång till att som lärare diskutera med klassen hur ett sådant program skulle kunna se ut. Men kan ge eleverna i uppgift att skriva ett enkelt program som letar just efter artikelns motexempel. Frågor som kan hjälpa eleverna är

  • Hur vet man att man hittat en lösning?
  • Hur väljer man en gräns för de ingående talens storlek? (Vi måste ju reducera letandet till ett ändligt antal fall)

Om man vill kan man utvidga det, och få en mycket svårare uppgift, till att börja med att undersöka summan av 3 tal med exponenten 4 som sedan automatiskt utvidgar problemet till 4 tal med exponenten 5 o s v.

Man kan också demonstrera olämpligheten med att försöka använda programmering till att bevisa satser som kräver ett ändligt antal fall genom att försöka bevisa Collatz förmodan. Collatz förmodan säger att oavsett vilket tal man startar med som kommer man om man upprepar följande algoritm

  • Om talet är jämt dela med 2, a_n=a_{n-1}/2
  • Om talet är udda tredubbla talet och lägg till 1, a_n=3\cdot a_{n-1} +1

till slut hamna på talet 1. Oavsett hur många fall programmet visar så finns det oändligt många fler fall att undersöka.

En annan spännande uppgift som hör samman med Collatz förmodan som inte har med bevisföring att göra är att undersöka vilket som är det största antalet steg algoritmen behöver utföra för att komma till talet 1 i ett givet intervall.

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *

Du kan använda följande HTML etiketter och attribut: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>