Let $ X: = \{x_1,x_2,\ldots,x_{29}\}$ be a set of $ 29$ boys: they play with each other in a tournament of Pro Evolution Soccer 2009, in respect of the following rules: i) every boy play one and only one time against each other boy (so we can assume that every match has the form $ (x_i \text{ Vs } x_j)$ for some $ i \neq j$); ii) if the match $ (x_i \text{ Vs } x_j)$, with $ i \neq j$, ends with the win of the boy $ x_i$, then $ x_i$ gains $ 1$ point, and $ x_j$ doesn’t gain any point; iii) if the match $ (x_i \text{ Vs } x_j)$, with $ i \neq j$, ends with the parity of the two boys, then $ \frac {1}{2}$ point is assigned to both boys. (We assume for simplicity that in the imaginary match $ (x_i \text{ Vs } x_i)$ the boy $ x_i$ doesn’t gain any point). Show that for some positive integer $ k \le 29$ there exist a set of boys $ \{x_{t_1},x_{t_2},\ldots,x_{t_k}\} \subseteq X$ such that, for all choice of the positive integer $ i \le 29$, the boy $ x_i$ gains always a integer number of points in the total of the matches $ \{(x_i \text{ Vs } x_{t_1}),(x_i \text{ Vs } x_{t_2}),\ldots, (x_i \text{ Vs } x_{t_k})\}$. (Paolo Leonetti)
Problem
Source: Own, from Oliforum math contest, problem 5
Tags: induction, modular arithmetic, linear algebra, matrix, vector, algebra, system of equations
Zhero
01.10.2009 00:42
I managed to get two different interpretations of this problem... sadly I did not get much progress on either one, had to go sleep, and failed to solve it. :/
View it as a graph of 29 nodes, with an edge going between two nodes if and only if they tie. We want to show we can pick a subset of the nodes such that the for all nodes $ n$, the parity of the number of vertices in our set is even.
I think we may be able to use induction, but I'm not sure.
Enumerate the 29 boys by $ a_1, a_2, \ldots, a_{29}$. Let $ e_1, e_2, \ldots, e_{29}$ be residue classes mod 2. Let $ v_{i,j}$ be 1 if there is an edge between $ a_i$ and $ a_j$, and 0 otherwise (or if $ i = j$). We want to show that the system of equations $ \sum_{k=1}^{29} e_k v_{i,k} \equiv 0 \pmod 2$ for all $ i$ from 1 to 29 has a nonzero solution mod for $ e_1, \ldots, e_{29}$ for all possible sets of $ v_{i,j}$. To each solution, put $ e_i \in S$ if and only if $ e_i = 1$.
I tried using Chevalley on this interpetation, but the number of variables I had was always the same as the number of equations. I tried to eliminate one, but failed to do so. I'm inexperienced with Chevalley (and didn't really try hard on this approach) so if anyone solves it using this approach, please tell me.
I also tried interpreting this as a linear algebra problem. I think that we want to show that the coefficient matrix is not invertible in $ F_2$. Sadly I know no linear algebra and this is all speculation, and I could not progress on this problem at all with linear algebra, considering how I didn't know any.
azjps
01.10.2009 04:53
So I only found out about this today and didn't have enough time to try the questions, but perhaps this works?
Let $ A \in M_{29 \times 29}(\mathbb{F}_2)$ with column vectors $ A^1, A^2, \ldots, A^{29}$ denote the adjacency matrix of the graph in Zhero's first interpretation; it is symmetric and has a main diagonal with elements zero. We want to show that there exists $ O \neq X \in (\mathbb{F}_2)^{29}$ such that $ AX = O$ (if $ X_i = 1$ then player $ x_i$ is in our set), or that is there is a statement of linear dependency between $ A^1, A^2, \ldots, A^{29}$, or equivalentally that $ \det(A) = 0$.
Then for all permutations $ \sigma: J_n \to J_n$, we use the determinant formula $ \det (A) = \sum_{\sigma} \epsilon(\sigma) \prod_{i = 1}^{29} a_{i,\sigma(i)} \equiv \sum_{\sigma} \prod_{i = 1}^{29} a_{i,\sigma(i)} \pmod{2}$. We can ignore all permutations $ \sigma$ with an index $ 1 \le i \le n$ such that $ i = \sigma(i)$, because $ a_{i,\sigma(i)} = 0$. For the remaining permutations $ \sigma$, each can be paired with a distinct inverse $ \sigma^{ - 1} \neq \sigma$ (otherwise $ \sigma$ is an involution and pairs up an even number of elements; this generalizes to all odd numbers, but not evens) such that $ \prod_{i = 1}^{29} a_{i, \sigma(i)} + \prod_{i = 1}^{29} a_{i, \sigma^{ - 1}(i)} = \prod_{i = 1}^{29} a_{i, \sigma(i)} + \prod_{i = 1}^{29} a_{\sigma^{ - 1}(i) , i} \equiv 0$ because $ A$ is symmetric. Hence $ \det(A) = 0$ as desired.
[edit: amusingly enough, I didn't even read your second interpretation, haha ]
Zhero
01.10.2009 05:30
oh god I was randomly asking people if they knew how to take determinants of symmetric matrices with odd dimensions whose entires were all 1's and 0's with a main diagonal of 0. I should really learn linear algebra...