Question 33
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.
"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.