AoPS - Problem

Problem

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

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

Zhero

05.07.2012 04:35

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.

hyperbolictangent

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.

Gh324

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??

Unsolved_cube

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$

shankarmath

19.02.2019 17:10

hidden in this problem although the main idea still falls under combinatorics I think.

Switch $2011$ with an odd prime $p$; the conclusion still holds. This will allow us to provide easier examples for claims we make in this proof rather than writing out $2010$ numbers. Define $R_k(P)$ be term $k$ of a sequence $R(P)$. Let the first move be called $\spadesuit$ and the second be called $\clubsuit$. Fix the blue slips; it turns out that $\clubsuit$ is not even needed to finish this problem. Now, we see that as we apply $\spadesuit$ multiple times to the permutation of red slips, each number has a supplier (a number which gives it the red slip it previously had) and each number has a receiver (a number which it gives it's previous red slip to). Define the $S(k)$ to be the supplier for the number $k$ and $R(k)$ to be the receiver for the number $k$. Now, we see that the red slips cycle in some number of cycles; for example, for $p=7$, if $B=4$, then we would have the two cycles $1,2,4$ and $3,5,6$ where $1$ supplies $2$ which supplies $4$ which supplies $1$, and a similar case for the other cycle. Now, we are ready to get into the math. Once again, we fix $B$ and the blue slips. Now take the $k$ such that $kB \equiv 1$ (mod $p$). From basic number theoretical principles, such a $k$ exists. Now we have that $k$ supplies $1$; $k$'s blue slip is $1$. From here, we have that the remaining blue slips can be expressed as $1,k,\cdots k^{p-2}$ (call this sequence $P(B)$) . Define $Q(R)$ as the sequence of red slips corresponding to $P(B)$ ; for example, if we had $p=7$, $A=2,B=3$ (leading to the following arrangement: $$2-4-6-1-3-5$$and $$3-6-2-5-1-4$$are the red and blue slip orderings, respectively), then we would have that the cycle of suppliers for the blue slips is $P(3)=1-5-4-6-2-3$ and these correspond to $Q(2)=2-3-1-5-4-6$. We claim that $P(B)$ and $Q(R)$ are cyclic permutations of each other; if this is true, then the problem is easy to finish as we can just apply $\spadesuit$ enough times to make them equal, which would mean that each person $m$ has red slip $m$. This is simple enough to prove; note that $Q(R)$ is simply each term of $P(B)$ multiplied by $R$; therefore, taking the constant $t$ such that $Q_t(R)=1$; from here, we see that the next term is $k$, the next is $k^2$, etc., so indeed, $Q(R)$ is a cyclic permutation of $P(B)$. I *believe* this proof still works if $P(B)$ is not a $p-1$-term permutation and instead the permutations are a set of cycles rather than one cycle, as the corresponding $Q(R)$ sequences would just be cyclic permutations of the $P(B)$ and therefore we could cyclically permute each sequence using $\spadesuit$ until we achieved the desired objective but I will check on this and add more to this proof if needed. $\blacksquare$

SerdarBozdag

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'}$.

IAmTheHazard

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$