olymmath

ISL 2009 N1

A social club has nn members. They have the membership numbers 1,2,…,n1,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 aa is permitted to send a present to a member with membership number bb if and only if a(b−1)a(b-1) is a multiple of nn." 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 GG be a directed graph with nn vertices v1,v2,…,vnv_{1}, v_{2}, \ldots, v_{n}, such that there is an edge going from vav_{a} to vbv_{b} if and only if aa and bb are distinct and a(b−1)a(b-1) is a multiple of nn. 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.

Locator isl/2009/n1 · Tag PRYCBH7ATY · Edit this page on GitHub · Keys: j next, k previous