ISL 2009 N1
A social club has members. They have the membership numbers , 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 is permitted to send a present to a member with membership number if and only if is a multiple of ." 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 be a directed graph with vertices , such that there is an edge going from to if and only if and are distinct and is a multiple of . Prove that this graph does not contain a directed cycle.
Official text Transcription from NuminaMath olympiads, checked word for word against the official paper. Quoted with source.
Official text: IMO 2009 Shortlist booklet, page 12.
Solutions
Official solution Solution 1 by the IMO Problem Selection Committee
The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).
Similar problems
These problems have the most words in common with this statement.