在 $n$ 名学生中，每名学生恰认识 $d$ 名男生和 $d$ 名女生（认识是相互的）。求所有可能的正整数数对 $(n,d)$ 。
【难度】
【出处】
2014第13届CGMO试题
【标注】
【答案】
略
【解析】
以这 $n$ 名学生为顶点，认识关系为边，构造简单图 $G=\left( V,E \right)$ 。设共有 $x$ 名女生，$y$ 名男生，$x,y>d$ 。则男生与女生之间的边的条数为 $xd=yd\Rightarrow x=y=\frac{n}{2}\geqslant d+1$；女生与女生之间边的条数为 $\frac{xd}{2}=\frac{nd}{4}$ 。因此，$n$、$d$ 满足 $\frac{n}{2}$、$\frac{nd}{4}\in\mathbb{Z}$，$n\geqslant 2d+2$ 。下面说明，对于所有满足上式的正整数数对 $(n,d)$，均存在图 $G=\left( V,E \right)$ 满足题设。
例如，设 $V=\left\{ {{u}_{1}},{{u}_{2}}.\cdots,{{u}_{m}},{{v}_{1}},{{v}_{2}},\cdots ,{{v}_{m}} \right\},n=2m$ 。
当 $d$ 为奇数时，$E=\left\{{{u}_{i}}{{u}_{j}},{{v}_{i}}{{v}_{j}},{{u}_{i}}{{v}_{j}}\left| i-j\in \left\{\pm 1,\pm 2,\cdots ,\pm \frac{d-1}{2},\frac{m}{2} \right\}(\bmod m) \right.\right\}$；
当 $d$ 为偶数时，$E=\left\{{{u}_{i}}{{u}_{j}},{{v}_{i}}{{v}_{j}},{{u}_{i}}{{v}_{j}}\left| i-j\in \left\{\pm 1,\pm 2,\cdots ,\pm \frac{d}{2} \right\}(\bmod m) \right. \right\}$ 。
例如，设 $V=\left\{ {{u}_{1}},{{u}_{2}}.\cdots,{{u}_{m}},{{v}_{1}},{{v}_{2}},\cdots ,{{v}_{m}} \right\},n=2m$ 。
当 $d$ 为奇数时，$E=\left\{{{u}_{i}}{{u}_{j}},{{v}_{i}}{{v}_{j}},{{u}_{i}}{{v}_{j}}\left| i-j\in \left\{\pm 1,\pm 2,\cdots ,\pm \frac{d-1}{2},\frac{m}{2} \right\}(\bmod m) \right.\right\}$；
当 $d$ 为偶数时，$E=\left\{{{u}_{i}}{{u}_{j}},{{v}_{i}}{{v}_{j}},{{u}_{i}}{{v}_{j}}\left| i-j\in \left\{\pm 1,\pm 2,\cdots ,\pm \frac{d}{2} \right\}(\bmod m) \right. \right\}$ 。
答案
解析
备注
