Square $P Q R S$ has sides of length 8 . It is split into four rectangular regions by two line segments, one parallel to $P Q$ and another parallel to $Q R$. There are $N$ ways in which these lines can be drawn so that the area of each of the four rectangular regions is a positive integer. What is the remainder when $N^{2}$ is divided by 100 ?
(A) 9
(B) 61
(C) 1
(D) 41
(E) 36
We begin by drawing a well-labelled diagram, as shown.

Since $P S=8$, by letting $P T=x$ we get $T S=8-x$. Similarly if $P V=y$, then $V Q=8-y$.

The value of $x$, where $08$ ).

When $x$ is equal to $\frac{1}{2}, \frac{3}{2}, \frac{5}{2}, \frac{7}{2}, \frac{9}{2}, \frac{11}{2}, \frac{13}{2}$, or $\frac{15}{2}$, what are the possible values of $y$ ?

Recall that we are considering cases in which exactly one of $x$ and $y$ is an integer and thus we require $y$ to be an integer.

The area of rectangle $P V Z T$ is an integer and so $(P V)(P T)=x y$ is an integer. (We note that the area of each of the other 3 rectangles is also an integer.)

When $x$ is equal to a fraction of the form $\frac{a}{2}$ (where $a$ is odd and comes from the list above),
and $x y$ is an integer, then 2 is a factor of $y$ and so $y$ is an even integer.

Since $08$ ).

When $x$ is equal to $\frac{1}{4}, \frac{3}{4}, \frac{5}{4}, \ldots \frac{27}{4}, \frac{29}{4}$, or $\frac{31}{4}$, what are the possible values of $y$ ?

Recall that we are considering cases in which exactly one of $x$ and $y$ is an integer and thus we require $y$ to be an integer.

Since $x y$ is an integer and $x$ is equal to a fraction of the form $\frac{a}{4}$, then 4 is a factor of $y$.

Since $0<y<8$, then $y=4$.

For each of the 16 choices for $x$, there is 1 choice for $y$ and so in this case there are $16 \times 1=16$ ordered pairs $(x, y)$ which give integer areas for each of the four rectangles $P V Z T, T Z W S$, $V Q U Z$, and $Z U R W$.

As an example, consider $(x, y)=\left(\frac{5}{4}, 4\right)$.

In this case, $8-x=\frac{27}{4}, 8-y=4$ and the areas of the four rectangles $P V Z T, T Z W S, V Q U Z$, and $Z U R W$ are the integers $\frac{5}{4} \times 4=5, \frac{27}{4} \times 4=27, \frac{5}{4} \times 4=5$, and $\frac{27}{4} \times 4=27$, respectively. When $y$ is equal to $\frac{1}{4}, \frac{3}{4}, \frac{5}{4}, \ldots \frac{27}{4}, \frac{29}{4}$, or $\frac{31}{4}$, and $x=4$, there are 16 additional ordered pairs $(x, y)$.

To complete the cases for which exactly one of $x$ and $y$ is an integer, we consider $b=8$.

Since $x y$ is an integer and $x$ is equal to a fraction of the form $\frac{a}{8}$, then 8 is a factor of $y$.

However, $y<8$ and thus cannot have a factor of 8 and so there are no ordered pairs $(x, y)$ when $b=8$.

Finally, we consider cases in which both $x$ and $y$ are not integers.

As previously determined, if $x$ is not an integer, then it is of the form $\frac{a}{2}$ or $\frac{a}{4}$ for some positive odd integers $a$.

If $y$ is not an integer, then it is similarly of the form $\frac{a}{2}$ or $\frac{a}{4}$ for some positive odd integers $a$.

However, if $x$ and $y$ are each of this form, then their product $x y$ is of the form $\frac{c}{4}, \frac{c}{8}$ or $\frac{c}{16}$ where $c$ is the product of two odd integers and thus is odd.

Since it is not possible for 4,8 or 16 to be a factor of an odd number, then $x y$ cannot be an integer and so the area of rectangle $P V Z T$ cannot be an integer in this case.

Thus, there are no cases for which both $x$ and $y$ are not integers.

Therefore, the value of $N$ is equal to $49+(2 \times 24)+(2 \times 16)=49+48+32=129$, and so the remainder when $N^{2}=16641$ is divided by 100 is 41 .

ANSWER: (D)