Problem

Source: Kosovo MO 2012 Problem 5

Tags: combinatorics



The following square table is given with seven raws and seven columns: $a_{11},a_{12},a_{13},a_{14},a_{15},a_{16},a_{17}$ $a_{21},a_{22},a_{23},a_{24},a_{25},a_{26},a_{27}$ $a_{31},a_{32},a_{33},a_{34},a_{35},a_{36},a_{37}$ $a_{41},a_{42},a_{43},a_{44},a_{45},a_{46},a_{47}$ $a_{51},a_{52},a_{53},a_{54},a_{55},a_{56},a_{57}$ $a_{61},a_{62},a_{63},a_{64},a_{65},a_{66},a_{67}$ $a_{71},a_{72},a_{73},a_{74},a_{75},a_{76},a_{77}$ Suppose $a_{ij}\in\{0,1\},\forall i,j\in\{1,...,7\}$. Prove that there exists at least one combination of the numbers $1$ and $0$ so that the following conditions hold: $(i)$ Each raw and each column has exactly three $1$'s. $(ii)$$\sum_{j=1}^7a_{lj}a_{ij}=1,\forall l,i\in\{1,...,7\}$ and $l\neq i$.(so for any two distinct raws there is exactly one $r$ so that the both raws have $1$ in the $r$-th place). $(iii)$$\sum_{i=1}^7a_{ij}a_{ik}=1,\forall j,k\in\{1,...,7\}$ and $j\neq k$.(so for any two distinct columns there is exactly one $s$ so that the both columns have $1$ in the $s$-th place).