Japan 2013 Initial Round

Let $n=2013$ throughout the subsequent discussion on this problem. For any real number $r$ denote by $\lfloor r\rfloor$ the smallest integer greater than or equal to $r$. In order to obtain the desired solution, we prove the following two lemmas.

Lemma 1. For $1\le i\le n$ and $0\le x\le n-1$, we have $\lfloor \frac{i(x+1)}{n}\rfloor -\lfloor \frac{ix}{n}\rfloor =1$ holds if the card with number $x$ is turned over at the operation $i$, and $\lfloor \frac{i(x+1)}{n}\rfloor -\lfloor \frac{ix}{n}\rfloor =0$, otherwise.

Proof: We note first that for any such pair $(i,x)$, we have $\lfloor \frac{i(x+1)}{n}\rfloor -\lfloor \frac{ix}{n}\rfloor =0$ or $1$, since $0\le \frac{i(x+1)}{n}-\frac{ix}{n}=\frac{i}{n}\le 1$ holds. Now we have card numbered $x$ is turned over at the operation $i$ $$⟺\text{there exists a non-negative integer }j\text{ satisfying }\lfloor \frac{nj}{i}\rfloor =x$$ $$⟺\text{there exist a non-negative integer }j\text{ satisfying }x\le \frac{nj}{i}<x+1$$ $$⟺\text{there exists a non-negative integer }j\text{ satisfying }\frac{ix}{n}\le j<\frac{i(x+1)}{n}.$$ Note that the last statement is equivalent to $\lfloor \frac{i(x+1)}{n}\rfloor -\lfloor \frac{ix}{n}\rfloor >0$, and therefore, this completes the proof of Lemma 1 in view of the opening remark for the proof.

For each integer $i$, $1\le i\le n-1$, let us say that the operations $\{i,n-i\}$ are performed if the operation $i$ and operation $n-i$ are applied consecutively.

Lemma 2. The following assertion is valid:

The card numbered $x$ is turned over once during the operations $\{i,n-i\}\leftrightarrow$ neither $\frac{i(x+1)}{n}$ nor $\frac{ix}{n}$ is an integer.

Proof: First note that the following holds in general for any pair of real numbers $r$ and $s$ for which $r+s$ is an integer: $$[r]+[s]=\{\begin{array}{ll}r+s& (r\text{ is an integer}),\\ r+s+1& (r\text{ is not an integer}).\end{array}$$ From Lemma 1 it follows that The card numbered $x$ is turned over once during the operations $\{i,n-i\}$ $$\leftrightarrow \left(\lfloor \frac{i(x+1)}{n}\rfloor -\lfloor \frac{ix}{n}\rfloor \right)+\left(\lfloor \frac{(n-i)(x+1)}{n}\rfloor -\lfloor \frac{(n-i)x}{n}\rfloor \right)=1$$ $$\leftrightarrow \left(\lfloor \frac{i(x+1)}{n}\rfloor +\lfloor \frac{(n-i)(x+1)}{n}\rfloor \right)-\left(\lfloor \frac{ix}{n}\rfloor +\lfloor \frac{(n-i)x}{n}\rfloor \right)=1\cdots (†)$$ From the remark made above, we have $$\lfloor \frac{i(x+1)}{n}\rfloor +\lfloor \frac{(n-i)(x+1)}{n}\rfloor =\{\begin{array}{ll}x+1& \left(\frac{i(x+1)}{n}\right)\text{ is an integer}\\ x+2& \left(\frac{i(x+1)}{n}\right)\text{ is not an integer}\end{array}$$ and also $$\lfloor \frac{ix}{n}\rfloor +\lfloor \frac{(n-i)x}{n}\rfloor =\{\begin{array}{ll}x& \left(\frac{ix}{n}\right)\text{ is an integer}\\ x+1& \left(\frac{ix}{n}\right)\text{ is not an integer}.\end{array}$$ Therefore, we can conclude that ($†$) holds $\leftrightarrow$ either both $\frac{i(x+1)}{n}$ and $\frac{ix}{n}$ are integers, or neither is an integer. But since $\frac{i(x+1)}{n}-\frac{ix}{n}=\frac{i}{n}$ is not an integer, it is impossible to have both $\frac{i(x+1)}{n}$ and $\frac{ix}{n}$ to be integers simultaneously. This proves the assertion of the Lemma.

Now, since we have $$\frac{ix}{n}\text{ is an integer}\leftrightarrow x\text{ is a multiple of }\frac{n}{\text{gcd}(i,n)}$$ where $\text{gcd}(i,n)$ denotes the greatest common divisor of $i$ and $n$, we now have the following assertion: During the operations $\{i,n-i\}$ the card numbered $x$ is turned over once $$\leftrightarrow \text{ neither }x\text{ nor }x+1\text{ is a multiple of }\frac{n}{\text{gcd}(i,n)}\cdots \cdots (††)$$

Next, we note that the result of applying each of the operations $1,2,\dots ,2013$ once and only once the end result does not depend on the order these operations are applied. Therefore, in order to get the answer to the question of the problem, we may assume we apply operations $\{1,2012\}$, $\{2,2011\}$, $\dots$, $\{1006,1007\}$ and the operation $2013$ in any order.

From $2013=3\cdot 11\cdot 61$, we see that there are $$(3-1)(11-1)(61-1)=1200\text{ i’s, satisfying }\gcd (i,2013)=1.$$ $$(11-1)(61-1)=600\text{ i’s, satisfying }\gcd (i,2013)=3.$$ $$(3-1)(61-1)=120\text{ i’s, satisfying }\gcd (i,2013)=11.$$ $$(3-1)(11-1)=20\text{ i’s, satisfying }\gcd (i,2013)=61.$$ $$61-1=60\text{ i’s, satisfying }\gcd (i,2013)=3\cdot 11.$$ $$11-1=10\text{ i’s, satisfying }\gcd (i,2013)=3\cdot 61.$$ $$3-1=2\text{ i’s, satisfying }\gcd (i,2013)=11\cdot 61.$$ Since we have $\gcd (i,2013)=\gcd (2013-i,2013)$, among $i=1,2,\dots ,1006$ there are precisely half, namely, $600$, $300$, $60$, $210$, $30$, $5$, $1$ i's satisfying the corresponding conditions on $\gcd (i,2013)$ stated above. In particular, for $i=1,2,\dots ,1006$ there are odd numbers of i's for which $\gcd (i,2013)=3\cdot 61$ or $11\cdot 61$ and there are even number of i's for which $\gcd (i,2013)$ takes other values. According to the statement $(††)$ if we apply the operations $\{i,2013-i\}$ for even number of i's for which $\gcd (i,2013)$ take the same value, the face-side-arrangement of the cards remain the same. Consequently, it is enough to consider the result of applying each of the following operations once.

(a) Operations $\{i,2013-i\}$ for each $i$ for which $\gcd (i,2013)=3\cdot 61$, (b) Operations $\{i,2013,i\}$ for each $i$ for which $\gcd (i,2013)=11\cdot 61$, (c) Operation $2013$.

Because of the statement $(††)$, after the application of the type (a) above, those cards having numbers which have remainder $1,2,\dots ,9$ after the division by $11$ change their sides. After the application of the type (b) above, those cards having numbers which have remainder $1$ after division by $3$ also changes their sides. Consequently, by the Chinese Remainder Theorem, we obtain the fact that the number of cards with their side with their number facing down (i.e., the face-side state is the same as in the initial state) after the applications of the types (a) and (b) is given by $(9\times 1+(11-9)\times (3-1))\times 61=793$. With the operation of the type (c) all of the cards will be turned over, and therefore, the number of cards which show their side with their number facing up after the application of all the operations $i,1\le i\le 2013$, is $793$.