Twisted Square

Let the bottom left vertex of the black square be the origin $O(0,0)$ of the $xy$ -plane. Label the red square $ABCD$ as shown. Since the coordinates of $A$ , $B$ , $C$ , and $D$ are integers, we can find them using Pythagorean theorem .

Using a simple Python code as shown above (using the Coding environment of Brilliant.org), it is found that the only possible coordinates of $C$ are $(124,93)$ . Similarly, the only possible coordinates of $A$ are $(75,124)$ . We note that $AC = \sqrt 2 s$ , where $s$ is the side length of the red square. Then $\sqrt 2s=\sqrt{(124-75)^2+(93-124)^2} = 41\sqrt 2$ $\implies s = \boxed{41}$ .

The vertices that give a side length of $41$ are $A(75,124)$ , $B(115,133)$ , $C(124,93)$ , and $D(84,84)$ .