MathDB

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).

Problem Statement