Er det mulig for frosken å starte i ruta nederst til venstre, besøke hver rute nøyaktig én gang, og så returnere til startruta?
Julekalender - luke 24
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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?
Er det mulig for frosken å starte i ruta nederst til venstre, besøke hver rute nøyaktig én gang, og så returnere til startruta?
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.
\[ 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.