IMO 2009 Shortlist N1
A social club has n members. They have the membership numbers 1,2,...,n, respectively. From time to time members send pr...
Category: Number Theory
Problem
A social club has n members. They have the membership numbers 1,2,...,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 v1,v2,...,vn, such that there is an edge going from va to vb 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.