Put $ A$ in the bottom left corner, and $ B$ in the bottom right corner. Let a move be $ a$ squares to the right and $ b$ squares up. (Note that a and b can be negative). Then, by Pythagoras' theorem, the move is permitted iff $ r = a^{2} + b^{2}$ a) If $ 2|r$ then $ a^{2}\equiv b^{2}\mod 2$. It is clear that a move is an odd number of squares right and an odd number of square up or an even number of squares right and an even number of squares up. If the board is coloured in the regular chessboard fashion, then no permitted move can go from a white square to a black square. But the bottom left square is a different colour than the bottom right square: hence we cannot move from one to the other. If $ 3|r$ then $ a^{2} + b^{2}\equiv 0 \mod 3$ Then either $ a \equiv b \equiv 0 \mod 3$ or $ a \equiv 1 \mod 3$ and $ b \equiv 2 \mod 3$. (Or the other way round). But squares are not congruent to 2 mod 3, so $ 3|a$ and $ 3|b$. So on every good move, we move a multiple of 3 squares to the right. But the bottom right square is 19 squares to the right of the bottom left square. Since 3 does not divide 19, we cannot get from one to the other. b) If r=73, then since $ 73 = 8^{2} + 3^{2}$ we can move from one corner of a 9x4 rectangle to the opposite corner. If we denote by ($ n,m$) the square in the $ n$th column and $ m$th row, a sequence of moves from the bottom left corner to the bottom right is: $ (1,1) (9,4) (17,1) (20,9) (12,6) (4,3) (7,11) (15,8) (7,5) (15,2) (12,10) (20,7) (12,4) (20,1)$ c) The only way that 97 can be expressed as the sum of two squares is $ 97 = 9^{2} + 4^{2}$. Hence all permittable moves are from one corner of a 5x10 rectangle to the other. If we colour the board such that all squares ($ n,m$) are white if: $ n$ is odd and $ m \in \{1,2,3,4,9,10,11,12\}$ OR $ n$ is even and $ m \in \{5,6,7,8\}$. and black otherwise. Clearly all permitted moves go from a white square to a white square, or a black square to a black square. But the bottom left corner is a different colour to the bottom right square, so we cannot go from one to the other.

How did you find the construction for #2?

Try to think reverse put a mark in B square and then put mark in squares which you can go through it. If you succeed put a mark in A square you are done.

viperstrike wrote: How did you find the construction for #2? Try to think reverse put a mark in B square and then put mark in squares which you can go through it. If you succeed put a mark in A square you are done

Nice approach for c) is to look mod 5. If we start at 1,1 and need to go to 1,20 we notice that we need to go from 1,1 to 1,0 mod 5 . Number of moves is S.Note that both 4 and 9 are -1 mod 5 so we can add and substract 1 .From the first component we need to get from 1 to 1 so the number of +1s equals the numbers of -1s ,because of that S is even.Next look at the second component we need to get from 1 to 0 mod 5.If x is the number of +1s and y is the number of -1 then 1+x-y=0 y=x+1 S=x+y=2x+1 but S is even contradiction!( 1+x-y=0 is because we start from 1 and need to get to 0)

For part $(a)$ note that $2\mid a^2+b^2$ implies $2\mid a+b$ and similarly $3\mid a^2+b^2$ implies $3\mid a+b$. For part $(b)$ place $A$ in the top left, $B$ in the top right. Define a move $(x, y)$ to be moving $x$ squares to the right and $y$ squares up. Then the moves $(3, -8), (3, 8), (3, -8), (-8, 3), (8, 3), (3, -8), (-8, 3), (8, 3), (-8, 3), (-3, -8), (8, 3), (8, 3), (-3, -8), (-3, 8), (8, 3)$ work. For part $(c)$ use a "checkerboard" but with $1\times 4$ tiles. We can check that colored squares go to colored squares, and uncolored squares go to uncolored squares. So the task is not possible.

If I understand these solutions correctly, #6 doesn't work. Since $5$ is odd, the number of $+1$s does not have to have the same parity as the number of $-1$s (for example, $1+10\cdot (+1)+5\cdot (-1)\equiv 1\mod 5$.

For c): the 1x4 "checkerboard" is not essential, here is an explanation of the real essential thing. Denote m=4 and n=9. Here m and n represent "coprime numbers of different parity" (otherwise it already fails to visit every square), and 12 takes the expression m+n-1 for this structure. Arrange the numbers from 1 to m+n-1 in this order: m mod (m+n), 2m mod (m+n), ..., (m+n-1)m mod (m+n). Then two numbers differ by m or n iff they are adjacent in this sequence. Color the m+n-1 rows in red and blue by alternating colors in this sequence. Then starting from a white square in a red row, it can only jump to a black square in a blue row, and vice versa, and can never reach white squares in blue rows or black squares in red rows. But if another row is added, then they close up to a loop of odd length and is no longer bipartite.