Special Parity

First of all, I claim that $U(s)=\begin{cases}\dfrac{s^2}{4},\quad\text{if }s\text{ is even} \\ \dfrac{s^2-1}{4},\quad\text{if }s\text{ is odd}\end{cases}$

Here is a sketch of the proof, you can find the full details of this proof in my solution to I Want Me More Unit Squares , if you've already seen it, you can safely skip this part. :D

Proof:

Suppose the width of the grid is $a$ , the height of the grid is $b$ , and the semiperimeter of the grid is $s=a+b$ . Then the number of unit squares in this $a\times b$ grid is $ab$ .

If $s$ is even , either $a\geqslant\frac{s}{2}$ , $b\leqslant\frac{s}{2}$ or $a\leqslant\frac{s}{2}$ , $b\geqslant\frac{s}{2}$ . Without loss of generality, let's suppose that $a=\frac{s}{2}+d$ , $b=\frac{s}{2}-d$ $(d<\frac{s}{2},\,d\in\mathbb{Z^+}\cup\{0\})$ . Then $ab=\left(\frac{s}{2}+d\right)\left(\frac{s}{2}-d\right)=\frac{s^2}{4}-d^2\leqslant\frac{s^2}{4}$ .

If $s$ is odd , either $a\geqslant\frac{s+1}{2}$ , $b\leqslant\frac{s-1}{2}$ or $a\leqslant\frac{s-1}{2}$ , $b\geqslant\frac{s+1}{2}$ . Without loss of generality, let's suppose that $a=\frac{s+1}{2}+d$ , $b=\frac{s-1}{2}-d$ $(d<\frac{s-1}{2},\,d\in\mathbb{Z^+}\cup\{0\})$ . Then $ab=\left(\frac{s+1}{2}+d\right)\left(\frac{s-1}{2}-d\right)=\frac{s^2-1}{4}-d^2\leqslant\frac{s^2-1}{4}$ .

Therefore, $U(s)=\begin{cases}\dfrac{s^2}{4},\quad\text{if }s\text{ is even} \\ \dfrac{s^2-1}{4},\quad\text{if }s\text{ is odd}\end{cases}$ . $_\square$

Now, since $|s_1-s_2|$ is an odd multiple of 2, let $s_1-s_2=2(2k-1)$ where $k$ is an integer. Then $s_1+s_2=2(2k-1)+2s_2=2(2k-1+s_2)$

Since $s_1+s_2$ is an odd multiple of 2, we know that $2(2k-1+s_2)$ is also an odd multiple of 2 and $2k-1+s_2$ must be odd, thus we conclude that $s_2$ must be even.

And since $s_2$ is even and $s_1=s_2+2(2k-1)$ is even, we conclude that $s_1$ is also even.

Hence let $s_1=2s_3$ , $s_2=2s_4$ , we have $\begin{aligned}|U(s_1)-U(s_2)|&=\left|\frac{s_1^2-s_2^2}{4}\right| \\ &=|s_3^2-s_4^2| \\ &=|(s_3+s_4)(s_3-s_4)|\end{aligned}$

Meanwhile, from $s_1-s_2=2(2k-1)\implies s_3-s_4=2k-1$ , we know that one of $s_3$ , $s_4$ must be odd and the other must be even, we conclude that $s_3+s_4$ and $s_3-s_4$ are both odd.

Therefore, we can conclude that $|U(s_1)-U(s_2)|=|(s_3+s_4)(s_3-s_4)|$ must be indeed odd.

$\text {1.) We will show that both } s_1 \text { and } s_2 \text { are even. }$

$\text {Due to symmetry, we may assume (without the loss of generality), that } s_1\geq s_2$

Then:

$s_1 + s_2 = 4m + 2$

and

$s_1 ﹰ- s_2 = 4n + 2$

$\text { where } m, n \in \mathbb {N}$

$\text {We can get the values of } s_1 \text { and } s_2 \text { by adding / subtracting the two equations above, respectively. }$

$2s_1= 4m +4n + 4$

$s_1= 2(m + n + 1)$

and

$2s_2 = 4m - 4n$

$s_2 = 2(m - n)$

$\text { Hence both } s_1 \text { and } s_2 \text { are even. }$

2.) Now it is easy to see, that one of $s_1$ and $s_2$ has to be an even multiple of 2, and the other has to be an odd multiple of 2

(that is the only way, that we can get an odd multiple as a sum, since even + odd = odd + even = odd, but odd + odd = even and even + even = even.)

3.) Here we will show, that if s is even, then:

$U(s) = \frac {s^2}{4}$

Let l be the length and w be the width of the rectangle. Then s = l + w and U(s) = max (l × w).

According to the AM - GM inequality:

$\sqrt { l × w } \leq \frac {l + w}{2}$

$\sqrt { l × w } \leq \frac {s}{2}$

After squaring both sides:

$l × w \leq \frac {s^2}{4}$

Therefore:

$U(s) = \frac {s^2}{4}$

At this point, it is easy to find that if:

a) s is an even multiple of 2 (divisible by 4, so its square is divisible by 16 and then U(s) will be divisible by 4 (it will be an even square number)

b) s is an odd multiple of 2 (so its square is divisible by 4 but not divisible by 8), which means that U(s) will be an odd square number)

4.) Based on our findings above, our expression:

$| U(s_1) - U(s_2) |$ will be a difference of an even and an odd square number, which is:

$\boxed { \text {Always odd. } }$