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
11.08.2019 22:35
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.