MathDB
Problems
Contests
National and Regional Contests
Kosovo Contests
Kosovo National Mathematical Olympiad
2012 Kosovo National Mathematical Olympiad
2012 Kosovo National Mathematical Olympiad
Part of
Kosovo National Mathematical Olympiad
Subcontests
(5)
5
1
Hide problems
Kosovo MO 2012 Problem 5
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_{11},a_{12},a_{13},a_{14},a_{15},a_{16},a_{17}
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_{21},a_{22},a_{23},a_{24},a_{25},a_{26},a_{27}
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_{31},a_{32},a_{33},a_{34},a_{35},a_{36},a_{37}
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_{41},a_{42},a_{43},a_{44},a_{45},a_{46},a_{47}
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_{51},a_{52},a_{53},a_{54},a_{55},a_{56},a_{57}
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_{61},a_{62},a_{63},a_{64},a_{65},a_{66},a_{67}
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
a_{71},a_{72},a_{73},a_{74},a_{75},a_{76},a_{77}
a
71
,
a
72
,
a
73
,
a
74
,
a
75
,
a
76
,
a
77
Suppose
a
i
j
∈
{
0
,
1
}
,
∀
i
,
j
∈
{
1
,
.
.
.
,
7
}
a_{ij}\in\{0,1\},\forall i,j\in\{1,...,7\}
a
ij
∈
{
0
,
1
}
,
∀
i
,
j
∈
{
1
,
...
,
7
}
. Prove that there exists at least one combination of the numbers
1
1
1
and
0
0
0
so that the following conditions hold:
(
i
)
(i)
(
i
)
Each raw and each column has exactly three
1
1
1
's.
(
i
i
)
(ii)
(
ii
)
∑
j
=
1
7
a
l
j
a
i
j
=
1
,
∀
l
,
i
∈
{
1
,
.
.
.
,
7
}
\sum_{j=1}^7a_{lj}a_{ij}=1,\forall l,i\in\{1,...,7\}
∑
j
=
1
7
a
l
j
a
ij
=
1
,
∀
l
,
i
∈
{
1
,
...
,
7
}
and
l
≠
i
l\neq i
l
=
i
.(so for any two distinct raws there is exactly one
r
r
r
so that the both raws have
1
1
1
in the
r
r
r
-th place).
(
i
i
i
)
(iii)
(
iii
)
∑
i
=
1
7
a
i
j
a
i
k
=
1
,
∀
j
,
k
∈
{
1
,
.
.
.
,
7
}
\sum_{i=1}^7a_{ij}a_{ik}=1,\forall j,k\in\{1,...,7\}
∑
i
=
1
7
a
ij
a
ik
=
1
,
∀
j
,
k
∈
{
1
,
...
,
7
}
and
j
≠
k
j\neq k
j
=
k
.(so for any two distinct columns there is exactly one
s
s
s
so that the both columns have
1
1
1
in the
s
s
s
-th place).
4
4
Show problems
3
4
Show problems
2
4
Show problems
1
4
Show problems