Julekalender - luke 24

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

En frosk hopper rundt på et $8\times 8$-rutenett. Frosken kan bare hoppe én rute mot høyre, én rute opp eller én rute diagonalt ned mot venstre om gangen.

Er det mulig for frosken å starte i ruta nederst til venstre, besøke hver rute nøyaktig én gang, og så returnere til startruta?

Bilde
stensrud
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Sted: Cambridge

Svaret er nei: Anta det motsatte - at frosken kan gjøre $64$ hopp og havne der han startet igjen. De lovlige hoppene han kan gjøre kan beskrives med vektorene $[1,0],[0,1]$ og $[-1,-1]$ (henholdsvis én til høyre, én opp, og én diagonalt ned til venstre). Si at han gjør $a,b$ og $c$ hopp av disse typene, sik at
\[ a\cdot [1,0] + b\cdot [0,1] + c\cdot [-1,-1]=[0,0] \iff [a-c,b-c] = [0,0], \]
som gir $a=b=c$. Dette betyr at frosken gjør $3a$ hopp totalt, men dette kan umulig være lik $64$, så vi har en motsigelse.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Fin løsning! Og god jul!
Svar