2009 IMO Shortlist N1

AUS A social club has $n$ members. They have the membership numbers $1,2, \ldots, n$, respectively. From time to time members send presents to other members, including items they have already received as presents from other members. In order to avoid the embarrassing situation that a member might receive a present that he or she has sent to other members, the club adds the following rule to its statutes at one of its annual general meetings: "A member with membership number $a$ is permitted to send a present to a member with membership number $b$ if and only if $a(b-1)$ is a multiple of $n$." Prove that, if each member follows this rule, none will receive a present from another member that he or she has already sent to other members. Alternative formulation: Let $G$ be a directed graph with $n$ vertices $v_{1}, v_{2}, \ldots, v_{n}$, such that there is an edge going from $v_{a}$ to $v_{b}$ if and only if $a$ and $b$ are distinct and $a(b-1)$ is a multiple of $n$. Prove that this graph does not contain a directed cycle.

澳大利亚 某社交俱乐部拥有 $n$ 名会员。他们的会员编号分别为 $1,2、\ldots、n$。成员有时会向其他成员发送礼物，包括他们已经从其他成员那里收到的礼物。为了避免出现会员可能收到自己送给其他会员的礼物的尴尬情况，俱乐部在一次年度会员大会上在章程中增加了以下规则：“当且仅当$a(b-1)$是$n$的倍数时，会员号为$a$的会员才可以向会员号为$b$的会员发送礼物。”证明，如果每个成员都遵循此规则，则没有人会收到另一个成员发送给其他成员的礼物。替代表述：设 $G$ 为具有 $n$ 个顶点 $v_{1}、v_{2}、\ldots、v_{n}$ 的有向图，这样当且仅当 $a$ 和 $b$ 不同且 $a(b-1)$ 是 $n$ 的倍数时，存在从 $v_{a}$ 到 $v_{b}$ 的边。证明该图不包含有向环。