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.
Problem
Source: ELMO Shortlist 2010, C3; also ELMO #5
Tags: modular arithmetic, algorithm, combinatorics proposed, combinatorics, Elmo
12.06.2013 07:44
The configuration of red and blue slips after any number of operations can be completely described by a pair of constants $(c_1, c_2)$ where MOPper $i$ has on his red slip $c_1i \pmod{2011}$ and on his blue slip $c_2i \pmod{2011}$; this follows from the fact that initially $(c_1, c_2) = (A, B)$ and that the two operations correspond to $(c_1, c_2) \rightarrow (c_1/c_2, c_2)$ and $(c_1, c_2) \rightarrow (c_1, c_2/c_1)$, respectively. Write $A \equiv g^a, B \equiv g^b \pmod{2011}$ where $g$ is a primitive root modulo $2011$. We can now associate with any situation a pair of numbers $(d_1, d_2)$, modulo $2010$, such that $c_1 \equiv g^{d_1}, c_2 \equiv g^{d_2}$ where initially $(d_1, d_2) = (a, b)$. The operations $(c_1, c_2) \rightarrow (c_1/c_2, c_2), (c_1, c_2/c_2)$ are then equivalently $(d_1, d_2) \rightarrow (d_1 - d_2, d_2), (d_1, d_2 - d_1)$; by the division algorithm it's possible to reduce one of $d_1, d_2$ to zero. If we reduce $d_1$ to zero, we're done - $c_1 \equiv g^{d_1} \equiv 1 \pmod{2011}$ as desired. If instead $d_2$ is reduced to $0$, we can perform the second operation $2009$ times and then perform the first, so that \[(d_1, 0) \rightarrow (d_1, -d_1) \rightarrow \dots \rightarrow (d_1, -2009d_1) \rightarrow (2010d_1, -2009d_1)\] where $2010d_1 \equiv 0 \pmod{2010}$ so once again $c_1 \equiv 1 \pmod{2011}$ as desired.
05.06.2018 08:30
"Each MOPper gives his or her red slip to the MOPper whose number is written on his or her blue slip." Can someone explain? So??
24.08.2018 12:35
We generalize the result by replacing $2011$ by $p$ for any odd prime $p$.
Note: From here on, all numbers are considered modulo $p$ unless specified. In particular, a negative exponent means an inverse modulo $p$. Lemma 1: At any moment, if we have two good permutations, then fixing any one of them and moving the other will also result in a good permutation.
Also, as proved above, if we have the sequences $xM, yM$, then we can get to $(x \cdot y^{-1})M$ in the next move by fixing $yM$. Lemma 2: Let $g$ be a primitive root modulo $p$. Then from the original sequences $AM, BM$, we can get to $BM, gM$.
To finish it, we have the two sequences $BM, gM$. Now fix $BM$ and perform moves to get these $p-1$ sequences: $BM, (Bg^{-1})M, (Bg^{-2})M \cdots (Bg^{-(p-1)})M$. Note that $\{B, Bg^{-1}, Bg^{-2}, \cdots Bg^{-(p-1)}\}$ forms a complete residue class modulo $p$, hence there will exist the sequence $1M$ in the sequences listed above, and we are done. $\blacksquare$
19.02.2019 17:10
hidden in this problem although the main idea still falls under combinatorics I think.
30.12.2021 16:08
Unsolved_cube wrote: By repeating this process, we can further reduce $l'$ to $\frac{l'}{gcd(p-1,l')}$ and so on until we get reach a number $L$ such that $gcd(L,p-1)=1$. Can anyone help me to understand this line? Still $B=g^l$ not $g^{l'}$.
30.01.2023 18:53
any singular they enjoyers? At any given time we can describe the configuration as a pair $(c_1,c_2)$ such that MOPper $n$ has $c_1n$ on their red slip and $c_2n$ on their blue slip, where everything is in $\mathbb{F}_{2011}$. This is by induction: clearly $(A,B)$ works initially, and the two operations translate to the transformations $(c_1,c_2) \to (c_1/c_2,c_2),(c_1,c_2/c_1)$ respectively. Let $g$ be a primitive root modulo $2011$, and suppose $A\equiv g^a$, $B\equiv g^b$. If our state is $(c_1,c_2)=(g^{d_1},g^{d_2})$, then our operations correspond to transitioning from $(d_1,d_2)$ to $(d_1-d_2,d_2)$ or $(d_1,d_2-d_1)$, starting from the state $(a,b)$. But this is just the Euclidean algorithm, so we can go from $(a,b)$ to $(\gcd(a,b),\gcd(a,b))$. Then applying the first operation once yields the state $(0,\gcd(a,b))$, which corresponds to a "$(c_1,c_2)$" state of $(1,g^{\gcd(a,b)})$, in which case each MOPper holds their number on a red slip. $\blacksquare$