matematikk.net

Hadde selv aldri hørt om selve konkurransen før læreren min spurte klassen om noen ville bli med i " Matte - OL", klart jeg ville det .hadde aldri sett lignende oppgaver før, så var ikke mye til tyvlesing.

Oppgavene i abelkonkurransen behøver vel ikke så mye kunnskap om høyere matte, det er om du kan finne på smarte løsninger med det du vet som teller. De fleste oppgavene baserer seg iallefall ikke på ting du behøver mer kunnskap enn forventet.
Det gjelder å være smart!

Jarle10 wrote:Oppgavene i abelkonkurransen behøver vel ikke så mye kunnskap om høyere matte, det er om du kan finne på smarte løsninger med det du vet som teller. De fleste oppgavene baserer seg iallefall ikke på ting du behøver mer kunnskap enn forventet.
Det gjelder å være smart!

Nettopp, hele poenget d. Man må se etter unike sammenhenger, løsninger og være kreativ.
Hvis man virkelig har teft for matematikk og innehar en matematisk intuisjon, oppnår man trolig bra resultat i Abelkonkurransen. Uavhengig av kunnskaper i høyere (avansert) matematikk (til en viss grad iallfall).

Ved å ta kurs i f.eks tallteori, så går det fort utrolig mye lettere;)

Helt sant Magnus. Når du kommer til problemløsningsoppgavene i Abelkonkurransen, og senere matematikkolympiaden, finnes det et knippe med teknikker som er verdt å kunne. Kreativitet og teft er helt klart påkrevd, men du kommer enda lenger med kreativitet, teft og kunnskap.

Bevisteknikker, for eksempel, er meget nyttig å ha inne. Enkle ting som induksjonsbeviser er det jo greit å kunne nokså på rams. Reduksjon ad absurdum og kontradiksjonsbevis likeså.

Når det kommer til kombinatorikk, kan kunnskaper om genererende funksjoner og grafteori hjelpe mye - likeså begreper som inkluderings-eksklusjonsprinsippet (inclusion-exclusion principle) og "the pigeonhole principle." Har du disse øverst i den matematiske verktøykassa di er det mange oppgaver som plutselig går lettere.

Vanskelige ulikheter krever ofte bruk av slike ting som på kort engelsk kalles QM-AM-GM-HM (kvadratisk snitt > det aritmetiske gjennomsnitt > geometrisk snitt > harmonisk snitt), cauchy-schwarz-teoremet, schurs ulikhet, med mer. Disse er det faktisk regnet med du kan "baklengs" før deltagelse i den internasjonale mateolympiaden.

Likeså finnes det standard problemløsningsverktøy innenfor geometrien (tangent-sekantteoremer, menelaus' teorem, ptolemaios setning...), tallteori (modulær aritmetikk og kongruensregning, wilsons teorem, farey-sekvenser...), analyse, algebra mm.

Selvsagt holder det ikke bare å lære seg disse teoremene utenatt, men har du kunnskapen, er gjerne det største problemet du har å redusere en nøtt til noe du kan bruke disse verktøyene på. I USA, østeuropa og Asia har de flere plasser matteklubber for ungdom, som samles en eller flere ganger i uka for å løse matematiske nøtter og lære problemløsningsteknikker. Det er gjerne disse landene som når lengst i olympiader og. Hvis du vil ha en fantastisk gjennomgang av mange problemløsningsteknikker med applikasjoner, anbefaler jeg deg å gå til anskaffelse av Paul Zeits' bok "The Art and Craft of Problem Solving."

Illustrasjon: Jeg tok et tilfeldig oppgaveark fra finalen i Abelkonkurransen, som viste seg å være 2001-finalearket. Siste oppgave lyder som følger

Ved en todagers lagkonkurranse i sjakk deltar tre skoler med 15 elever hver. Hver elev spiller ett parti mot hver spiller på de to andre lagene, altså 30 sjakkpartier per elev.

a)er det mulig at hver elev har spilt nøyaktig 15 partier etter første dag?

b) Vis at det er mulig at hver elev har spilt nøyaktig 16 partier etter første dag

c) Anta at hver elev har spilt nøyaktig 16 partier etter første dag. Vis at det finnes 3 elever, en fra hver skole, som har spilt sine 3 innbyrdes partier.

Nå har det seg slik at jeg kan elementær grafteori, og det tok meg rett i overkant av 10 minutter å skrive ned det følgende (tid til rådighet er i gjennomsnitt 1 time pr spørsmål):

La hver skolegruppe være undergrafer S[sub]1[/sub], S[sub]2[/sub] og S[sub]3[/sub] av konkurransegrafen T, der hver elev er representert ved en node, og et felles sjakkparti med en kant. Det følger at grafen er tripartitt.

a) Anta at hver elev har spilt 15 kamper. Deg(i) for hver node i er dermed 15, og det følger at [symbol:sum]deg(i) = 15*45 - et oddetall. Fra "the handshaking lemma" vet vi derimot at [symbol:sum]deg(i) er 2 ganger grafens størrelse, og må dermed være partallig - en kontradiksjon. Hver elev kan dermed ikke ha spilt 15 kamper.

b) Reglene om at ingen elev spiller mot en medelev krever at vi holder grafen tripartitt. Denne grafen er en undergraf av K[sub]15, 15, 15[/sub]. Vi kan dermed maksimum plassere ut 3*15*15 = 675 kanter, eller felles sjakkspill, i grafen. Dersom hver elev har spilt 16 kamper, er deg(i) = 16 *45 = 720, og grafens størrelse 360. 360 < 675, og hver elev kan dermed ha spilt 16 kamper etter første dag.

c) Anta at hver elev har spilt 16 partier. La oss prøve å konstruere T, slik at det ikke finnes 3 elever som alle har spilt et innbyrdes parti, og prøve å maksimere antall partier, uten å skape en løkke med lengde 3. Vi starter, uten tap av generalitet, med S[sub]1[/sub]. Ved "pigeonhole principle" må minste antall kanter i S[sub]1[/sub] union S[sub]2[/sub] nå være 16. (Siden S[sub]1[/sub] union S[sub]3[/sub] ved maksstørrelse er isomorf til K[sub]15, 15[/sub]) Men det samme gjelder, med samme argumentasjon, for unionen av alle par av S-grafene(!) Siden graden av hver S-graf er 15, og 15 < 16, betyr det et vi er nødt til å skape en innbyrdes løkke mellom grafene, og det vil måtte finnes 3 elever som har spilt 3 innbyrdes sjakkspill.


Likeså kan problemløsningsteknikker automatisere løsningen av mange andre oppgaver. Det hadde nok ikke vært så fryktelig mye vanskeligere å bevise dette på annet vis, men det sparer tid å ha litt ekstrakunnskap.

Pent Daofeishi!

Har du noen bøker å anbefale i grafteori?

Jada, se om du finner en av disse på biblioteket:

Pearls in Graph Theory, a Comprehensive Introduction - Nora Hartsfield og Gerhard Ringel
Introduction to Graph Theory - Richard J. Trudeau
Schaum's Outline of Graph Theory - V.K. Balakrishnan

Edit: Læreren min sier at Modern Graph Theory - Bela Bollobas skal være en av de virkelig gode bøkene på feltet, med massevis av eksempler på applikasjoner. Men den er også grådig tungt skrevet hvis du leser den som "undergraduate student."

Pearls in Graph Theory, a Comprehensive Introduction - Nora Hartsfield og Gerhard Ringel

Står nå i bokhylla!

Det hjelper ikke med kunnskap om grafteori om ikke bevisene holder vann.

Så vidt jeg har sett har du løst verken b) eller c):

daofeishi wrote:b) Reglene om at ingen elev spiller mot en medelev krever at vi holder grafen tripartitt. Denne grafen er en undergraf av K[sub]15, 15, 15[/sub]. Vi kan dermed maksimum plassere ut 3*15*15 = 675 kanter, eller felles sjakkspill, i grafen. Dersom hver elev har spilt 16 kamper, er deg(i) = 16 *45 = 720, og grafens størrelse 360. 360 < 675, og hver elev kan dermed ha spilt 16 kamper etter første dag.

Så jeg kan samtidig argumentere med at alle spillerne kan ha spilt 15 kamper etter første dag, fordi 15*45/2 < 675, som du (korrekt) motbeviste i a)?

daofeishi wrote:c) Anta at hver elev har spilt 16 partier. La oss prøve å konstruere T, slik at det ikke finnes 3 elever som alle har spilt et innbyrdes parti, og prøve å maksimere antall partier, uten å skape en løkke med lengde 3. Vi starter, uten tap av generalitet, med S[sub]1[/sub]. Ved "pigeonhole principle" må minste antall kanter i S[sub]1[/sub] union S[sub]2[/sub] nå være 16. (Siden S[sub]1[/sub] union S[sub]3[/sub] ved maksstørrelse er isomorf til K[sub]15, 15[/sub]) Men det samme gjelder, med samme argumentasjon, for unionen av alle par av S-grafene(!) Siden graden av hver S-graf er 15, og 15 < 16, betyr det et vi er nødt til å skape en innbyrdes løkke mellom grafene, og det vil måtte finnes 3 elever som har spilt 3 innbyrdes sjakkspill.[/i]

Er argumentet ditt: Det finnes minst 16 kanter i S[sub]1[/sub] U S[sub]2[/sub], 16 kanter i S[sub]2[/sub] U S[sub]3[/sub], og 16 kanter i S[sub]3[/sub] U S[sub]1[/sub], så derfor er det en løkke i T = S[sub]1[/sub] U S[sub]2[/sub] U S[sub]3[/sub]?

Dette argumentet holder ikke, for jeg kan konstruerer en graf (det hadde vært lettere med en tegning..) der S[sub]1[/sub] = {A[sub]1[/sub], ..., A[sub]15[/sub]}, S[sub]2[/sub] = {B[sub]1[/sub], ..., B[sub]15[/sub]}, S[sub]3[/sub] = {C[sub]1[/sub], ..., C[sub]15[/sub]}, med kantene (A[sub]1[/sub], B[sub]1[/sub]), ...,(A[sub]1[/sub], B[sub]15[/sub]), (A[sub]2[/sub], B[sub]1[/sub]),(A[sub]3[/sub], C[sub]1[/sub]), ...,(A[sub]3[/sub], C[sub]15[/sub]), (A[sub]4[/sub], C[sub]1[/sub]), og 16 vilkårlige kanter mellom S[sub]2[/sub] og S[sub]3[/sub], som har egenskapene over, men ingen løkker.