3. Given $S=\{(i, j) \mid i, j=1,2, \cdots, 100\}$ as the set of $100 \times 100$ integer points on the Cartesian plane. Each point in $S$ is colored with one of four given colors. Find the maximum possible number of rectangles with sides parallel to the coordinate axes, whose vertices are four points of different colors in $S$.
(Zhai Zhenhua, problem contributor)
3. The maximum value sought is 9375000.

Let the four colors be $A, B, C, D$. Let
$R_{i}=\{(x, i) \mid x=1,2, \cdots, 100\}$
be the $i$-th row of the integer point square,
$$
T_{j}=\{(j, y) \mid y=1,2, \cdots, 100\}
$$

be the $j$-th column of the integer point square.
A rectangle with four vertices of different colors in $S$ and sides parallel to the coordinate axes is called a "four-color rectangle."

Lemma: If $R_{i}$ and $R_{j}$ are exactly the same color at $k$ positions, then the number of four-color rectangles generated by these two rows does not exceed $\frac{(100-k)^{2}}{4}$.

Proof: If $R_{i}$ and $R_{j}$ are the same color at a certain position, then these two points cannot belong to a four-color rectangle. If $(x, i)$ and $(x, j)$ are colors $A$ and $B$, then the four points form a four-color rectangle if and only if $(y, i)$ and $(y, j)$ are colors $C$ and $D$. Similarly, this applies to other cases.

In 100 pairs of grid points $(x, i)$ and $(x, j) (1 \leqslant x \leqslant 100)$, let there be $l_{1}$ pairs of grid points with colors $A$ and $B$, $l_{2}$ pairs with colors $A$ and $C$, $l_{3}$ pairs with colors $A$ and $D$, $l_{4}$ pairs with colors $B$ and $C$, $l_{5}$ pairs with colors $B$ and $D$, and $l_{6}$ pairs with colors $C$ and $D$. Then
$$
l_{1}+l_{2}+\cdots+l_{6}=100-k.
$$

Note that, $R_{i}$ and $R_{j}$ generate exactly $l_{1} l_{6}+l_{2} l_{5}+l_{3} l_{4}$ four-color rectangles, and
$$
\begin{array}{l}
l_{1} l_{6}+l_{2} l_{5}+l_{3} l_{4} \\
\leqslant \frac{\left(l_{1}+l_{6}\right)^{2}}{4}+\frac{\left(l_{2}+l_{5}\right)^{2}}{4}+\frac{\left(l_{3}+l_{4}\right)^{2}}{4} \\
\leqslant \frac{\left(l_{1}+l_{2}+l_{3}+l_{4}+l_{5}+l_{6}\right)^{2}}{4} \\
=\frac{(100-k)^{2}}{4}.
\end{array}
$$

The lemma is proved.
Let $R_{i}$ and $R_{j}$ be the same color at $k_{i, j}$ positions, then $\sum_{1 \leqslant i<j \leqslant 100} k_{i, j}$ is exactly the number of same-color point pairs with the same x-coordinate. Counting from each column, let $T_{j}$ have $a_{j}, b_{j}, c_{j}, d_{j} (a_{j}+b_{j}+c_{j}+d_{j}=100)$ points of colors $A, B, C, D$, respectively. Then $T_{j}$ has $\mathrm{C}_{a_{j}}^{2}+\mathrm{C}_{b_{j}}^{2}+\mathrm{C}_{c_{j}}^{2}+\mathrm{C}_{d_{j}}^{2}$ same-color point pairs.
$$
\begin{array}{l}
\text { Hence } \sum_{1 \leqslant i<j \leqslant 100} k_{i, j} \\
=\sum_{j=1}^{100}\left(\mathrm{C}_{a_{j}}^{2}+\mathrm{C}_{b_{j}}^{2}+\mathrm{C}_{c_{j}}^{2}+\mathrm{C}_{d_{j}}^{2}\right) \\
=\sum_{j=1}^{100}\left(\frac{1}{2}\left(a_{j}^{2}+b_{j}^{2}+c_{j}^{2}+d_{j}^{2}\right)-\right. \\
\left.\frac{1}{2}\left(a_{j}+b_{j}+c_{j}+d_{j}\right)\right) \\
\geqslant \sum_{j=1}^{100}\left(\frac{1}{8}\left(a_{j}+b_{j}+c_{j}+d_{j}\right)^{2}-\right. \\
\left.\frac{1}{2}\left(a_{j}+b_{j}+c_{j}+d_{j}\right)\right) \\
=100\left(\frac{1}{8} \times 100^{2}-\frac{1}{2} \times 100\right) \\
=120000.
\end{array}
$$

Combining the lemma and the above formula, the number of four-color rectangles does not exceed
$$
\begin{array}{l}
\sum_{1 \leqslant i<j \leqslant 100} \frac{\left(100-k_{i, j}\right)^{2}}{4} \\
\leqslant \sum_{1 \leqslant i<j \leqslant 100} \frac{100 \times\left(100-k_{i, j}\right)}{4} \\
=2500 \mathrm{C}_{100}^{2}-25 \sum_{1 \leqslant i<j \leqslant 100} k_{i, j} \\
\leqslant 9375000.
\end{array}
$$
$\leqslant 9375000$
Below, we construct a coloring method such that the graph contains exactly 9375000 four-color rectangles.
Divide the $100 \times 100$ integer points into 16 regions, each region
being $25 \times 25$ integer points, and color each region as shown in
Figure 5.
By the above coloring method, when
the first grid point of two rows belongs to the same region, these two rows do not generate a four-color rectangle; when the first grid point of two rows does not belong to the same region, these two rows have 4 pairs of regions forming the same color rectangle, generating $4 \times 25^{2}=2500$ four-color rectangles. Therefore, the total number of four-color rectangles in the graph is
$$
2500\left(25 \times 25 \times \mathrm{C}_{4}^{2}\right)=9375000,
$$

satisfying the condition.
In summary, the maximum value sought is 9375000.