Problem

Source: ELMO Shortlist 2010, C3; also ELMO #5

Tags: modular arithmetic, algorithm, combinatorics proposed, combinatorics, Elmo



2010 MOPpers are assigned numbers 1 through 2010. Each one is given a red slip and a blue slip of paper. Two positive integers, A and B, each less than or equal to 2010 are chosen. On the red slip of paper, each MOPper writes the remainder when the product of A and his or her number is divided by 2011. On the blue slip of paper, he or she writes the remainder when the product of B and his or her number is divided by 2011. The MOPpers may then perform either of the following two operations: Each MOPper gives his or her red slip to the MOPper whose number is written on his or her blue slip. Each MOPper gives his or her blue slip to the MOPper whose number is written on his or her red slip. Show that it is always possible to perform some number of these operations such that each MOPper is holding a red slip with his or her number written on it. Brian Hamrick.