Let $n$ be a fixed positive integer. Oriol has $n$ cards, each of them with a $0$ written on one side and $1$ on the other. We place these cards in line, some face up and some face down (possibly all on the same side). We begin the following process consisting of $n$ steps: 1) At the first step, Oriol flips the first card 2) At the second step, Oriol flips the first card and second card . . . n) At the last step Oriol flips all the cards Let $s_0, s_1, s_2, \dots, s_n$ be the sum of the numbers seen in the cards at the beggining, after the first step, after the second step, $\dots$ after the last step, respectively. a) Find the greatest integer $k$ such that, no matter the initial card configuration, there exists at least $k$ distinct numbers between $s_0, s_1, \dots, s_n$. b) Find all positive integers $m$ such that, for each initial card configuration, there exists an index $r$ such that $s_r = m$. Proposed by Dorlir Ahmeti
Problem
Source: Mexico National Olympiad Mock Exam (OMMock) P3
Tags: combinatorics, cards, Binary
10.11.2020 17:24
Who is gonna give it a try at this problem?
07.01.2021 15:13
For (a) the answer is $2$ and for (b) the answer is $\lfloor\frac{n}{2} \rfloor$ and $\lceil \frac{n}{2} \rceil$. (a) Since $s_{1}=s_{0} \pm 1$, we must have $k \geq 2$. Let $a$ be the sequence $0011$. Given $n=4k+r$, $0 \leq r \leq 3$, let $x=a\dots a a_{0} \dots a_{r}$ be obtained by repeating $a$ $k$ times, with $a_{1},\dots,a_{r}$ added at the end. Note that under this operator, $a$ transforms as follows: $0011 \rightarrow 1011 \rightarrow 0111 \rightarrow 1001 \rightarrow 0110$. Let $x(m)$ be the sequence obtained after the $m^{th}$ step, and set $b=0110$ and $c=1001$. Let $m=4y+z$ with $0 \leq z \leq 3$ (this is the initial sequence of cards). If $z$ is odd, it is easy to see that $x_k = c \dots c a(z) a\dots a a_{0}\dots a_{r}$ (with $y$ $c$'s at the start), and if $z$ is even then ' $x_k = b \dots b a(z) a\dots a a_{0}\dots a_{r}$. In particular, it is easy to see that $s(x(m)) - s(x(0)) = s(a(z))- s(a(0))$ (recall that $m=4y+z$), where $s(y)$ is the sum of the coordinates of $y$. Since $s(a(m))- s(a(0))$ attains only two values (as $s(a(0))=s(a(3))=s(a(4))=2$ and $s(a(1))=s(a(2))=3$), it follows that the sequence $\{s_{m}\}$ attains only two distinct values, as required. (b) By considering the card configurations obtained by having all cards face up, and all cards face down, it is easy to check that $\lfloor\frac{n}{2} \rfloor$ and $\lceil \frac{n}{2} \rceil$ are the only possible values. Indeed, if all cards are face up at the start (i.e. the face containing 1), we have $s_{2i-1}=s_{2i}=n-i$ for all $i$ and hence the values that are attained are $\lfloor{\frac{n}{2}}\rfloor, \dots, n$. Similarly, if all faces are down, the values are $0, \dots, \lceil{\frac{n}{2}}\rceil$. We certainly have $s_{1}=s_{0} \pm 1$, and we also have $s_{i+2}=s_{i} \pm 1$. The second equality follows from the fact that when comparing $x(i+2)$ and $x(i)$, the cards $1,\dots ,i+1$ are flipped twice, the card $i+2$ is flipped once, and the cards $i+3,\dots ,n$ remain untouched. In particular, it follows that the set $\{s_{0}, \dots , s_{n}\}$ is an interval of consecutive integers, say $[a,b]\cap \mathbb{Z}$. Note that $s_{n-1}+s_{n}=n$, as every card is flipped during the last step. Thus we must have $a \leq \frac{n}{2} \leq b$, and the claim follows.