There are $2019$ coins on a table. Some are placed with head up and others tail up. A group of $2019$ persons perform the following operations: the first person chooses any one coin and then turns it over, the second person choses any two coins and turns them over and so on and the $2019$-th person turns over all the coins. Prove that no matter which sides the coins are up initially, the $2019$ persons can come up with a procedure for turning the coins such that all the coins have smae side up at the end of the operations.
Problem
Source: Indian TST 2019 Practise test Day 2 P3
Tags: indian olympiad, graph, combinatorics, TST
Inco
11.08.2019 22:35
Induct on the odd numbers.
Induct on the odd numbers $n = 2k + 1$. The base case, $n = 1,$ involves $1$ person flipping $1$ coin, so it is true that all the coins will face the same way at the end. Assume this is true for $n = 2k - 1,$ and consider $2k + 1$ coins.
If there are two coins facing opposite ways, $H$ and $T,$ then by the inductive hypothesis the first $2k - 1$ moves can flip the remaining $2k - 1$ coins all the same way (WLOG assume they are now all $T,$). The last two moves are to flip all $2k$ $T$'s to $H$'s, then flip all $2k + 1$ coins to $T$'s.
If all the coins face the same way, flip the first coin, then the next two, then the next three, going around in a circle. Then, the $1 + 2 + \cdots + 2009 = 2009 \cdot 1005$ flips cycle around the coins $1005$ times, so that they are each flipped $1005$ times and thus face the same way.
dgrozev
04.01.2020 19:27
Another approach. Some brief theory before that. Suppose we have a biparite graph $ G(A,B)$ and some integer valued function $ f:A\cup B\to \mathbb{Z}_{\ge 0}$. The question is: Can we delete some edges of $ G$, such that the degree of any vertex $ v\in A\cup B$ equals $ f(v)$ ? In other words, does there exist a subgraph of $G$ with some prescribed degrees? If so, we say $G$ has an $f$ - factor. Theorem (Ore - Ryser). A graph $G$ has an $f$ - factor if and only if the following two conditions hold. \begin{align*} & (i)\quad \sum_{a\in A}f(a)= \sum_{b\in B}f(b) \\ & (ii) \quad \sum_{x\in X} f(x)\leq \sum_{y\in B\setminus Y}f(y)+m(X,Y), \text{ for any } X,Y; X\subset A, Y\subset B, \end{align*}where $ m(X,Y)$ denotes the number of edges connecting $X$ and $Y$. Now, back to the problem. Consider the full bipartite graph $ G(A,B)$ on the set of persons - $ A=\{A_1,A_2,\dots,A_{2019}\}$ and coins - $ B=\{B_1,B_2,\dots,B_{2019}\}$. Suppose $ b=(b_1,b_2,\dots,b_{2019})$ is any ordered sequence of bits $ b_i\in \{0,1\},i=1,2,\dots,2019$. It boils down to show we can delete some edges of $G$ and obtain a graph $G'(A,B)$ which degrees are special. They must satisfy $\deg_{G'}(v)=f(v), \forall v\in A\cup B$, where $f$ satisfies: $ f(A_i)=i, f(B_i)\equiv c_i \pmod{2}, i=1,2,\dots,2019$ and the binary sequence $ c=(c_1,c_2,\dots,c_{2019})$ is either $ b$ or the negation $ \overline{b}$ of $ b$. We choose $ c$ to be the one among $ b, \overline{b} $ which consists of even number of $ 1$'s and let that number is $ 2r, 0\le r\le 1009$. We define $ f$ over $ B$ as follows \begin{align*} &f(B_i):= 1011,i=1,2,\dots,r\\ &f(B_i):=1009, i=r+1, r+2,\dots, 2r\\ &f(B_i)=1010, i=2r+1,2r+2,\dots,2019. \end{align*} As said $ f(A_i)=i,i=1,2,\dots,2019$. We prove now, $ G$ has a $ f$ factor. The first condition of Ore-Ryser holds by definition of $ f$ since $ \sum_{a\in A}f(a)=2019\cdot 1010$. So, for any $ X\subset A, Y\subset B$ we have to check the second condition, which is a routine calculation. Comment. A full solution and another application of the same method can be found in my blog.