Solutions to Problems on Incidence Matrix
Problem 1.
8 singers participate in an art festival where
m
songs are performed. Eachsong is performed by 4 singers, and each pair of singers performs together in the samenumber of songs. Determine the minimum value of
m
.
Solution.
Notice that for every song performed, there are
42
=
6 ways to pair up thefour singers. Thus there were 6 pairs who performed together in each song. Supposeevery pair of singer sang together in
k
songs. There are a total of
82
=
28 pairs of singers, so by counting the total number of times each pair of singers perform, we havethe equality28
k
=
6
m
which means 14

m
thus
m
≥
14. Finally, we give a construction for
m
=
14. Bynumbering the singers from 1 to 8, divide them into 14 sets of 4 people each, to representthe singers for each of the 14 songs as follows:
{
1,2,3,4
}
,
{
3,4,5,6
}
,
{
5,6,7,8
}
,
{
1,2,7,8
}
,
{
1,2,5,6
}
,
{
2,3,6,7
}
,
{
3,4,7,8
}
,
{
1,4,5,8
}
,
{
1,3,5,7
}
,
{
2,4,6,8
}
,
{
1,3,6,8
}
,
{
2,3,5,8
}
,
{
2,4,5,7
}
,
{
1,4,6,7
}
.
Problem 2.
(Baltic Way 2001)
A set of 8 problems was prepared for an examination. Eachstudent was given 3 of them. No two students received more than one common problem.What is the largest possible number of students?
Solution.
Denote the problems by
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
, then 8 possible problem setsare
ABC
,
ADE
,
AFG
,
BDG
,
BFH
,
CDH
,
CEF
,
EGH
. Hence, there could be 8 students.Suppose that some problem (e.g.,
A
) was given to 4 students. Then each of these 4students should receive 2 different “supplementary” problems, and there should be atleast 9 problems, a contradiction. Therefore each problem was given to at most 3 students, and there were at most 8
×
3
=
24 “awardings” of problems. As each student was“awarded” 3 problems, there were at most 8 students.
Problem 3.
17 students took part in a mathematical contest with 9 problems. It is giventhat every problem was answered correctly by exactly 11 students. Prove that there weretwo students who, between them, solved all 9 problems.
Solution.
We set up an incidence matrix with columns
P
1
,
P
2
,...,
P
9
to represent theproblems and rows
a
1
,
a
2
,...,
a
17
to represent the students. The cell in row
i
and column
j
is ﬁlled with ‘1’ if student
a
i
solved problem
P
j
, and ‘0’ otherwise. Since everyproblem was answered correctly by exactly 11 students, there must be exactly six ‘0’sin each column. The number of ‘column pairs’ of ‘0’s is therefore
62
×
9
=
135. Nowsuppose that no two students solved all 9 problems between them. This means that forevery pair of students
a
i
and
a
j
, 1
≤
i
<
j
≤
17, there is at least one problem they bothdidn’t solve, contributing to at least one ‘column pair’ of ‘0’s. Thus total number of column pairs
≥
172
=
136, a contradiction.
Problem 4.
(SMO(S)2001 Round 2)
The numbers
{
1
,
2
,...,
n
2
}
are randomly arranged ona
n
2
×
n
2
board, such that each number appears exactly
n
2
times. Prove that there is arow or a column that contains at least
n
distinct numbers.
Solution.
Set up an incidence matrix with columns corresponding to the numbers 1 to
n
2
and rows
r
1
,
r
2
,...,
r
n
2
,
c
1
,
c
2
,...,
c
n
2
to represent the rows and columns of the board
Prepared by Ho Jun WeiHwa Chong Math Olympiad Programme (Open)
1
respectively. Fill cell in column
k
with a ‘1’ if the number
k
appears on that particularrow
r
i
or column
c
j
of the board, and ‘0’ if it does not appear in that row/column of theboard. Every number appears exactly
n
2
times on the board. If a certain number appearsin exactly
a
columns and
b
rows of the board, then we must have
ab
≥
n
2
⇒
a
+
b
≥
2
n
by AMGM inequality. Then in every column of our incidence matrix, there must beat least 2
n
‘1’s, thus the total number of ‘1’s in the matrix
≥
2
n
3
. Since there are 2
n
2
rows in our incidence matrix, by pigeonhole principle, there must be at least one rowthat contains at least
n
‘1’s. This means that at least one row or column on the boardcontains
n
distinct numbers.
Problem 5.
In a chess club,
n
people gathered to play chess against each other, as theypleased. No two people played against each other more than once. At the end of theday, it was observed that a total of 3
n
games had been played. Moreover, if we choseany two players, say A and B, there would be at most one other player who had playedwith both A and B. Prove that
n
>
30.
Solution.
Set up an incidence matrix with
n
rows and
n
columns, and ﬁll the cell inrow
i
and column
j
with a ‘1’ if person
i
played with person
j
, and ‘0’ otherwise (aperson cannot play against himself). Let
c
i
represent the number of ‘1’s in column
i
.Each match contributes to two ‘1’s, thus
∑
c
i
=
6
n
. By Jensen’s inequality, the function
x
2
=
x
2
−
x
2
is concave upwards, thus the total number of column pairs is
n
∑
i
=
1
c
i
2
≥
n
∑
c
i
n
2
=
n
62
=
15
n
.
Also, for every pair of people
A
and
B
, at most one person played with both
A
and
B
,thus between every two rows, there can be at most one column pair, so total numberof column pairs
≤
n
2
=
n
(
n
−
1
)
2
. Combining both inequalities, we obtain 15
n
≤
n
(
n
−
1
)
2
which implies
n
≥
31 as desired.
Problem6.
(SMO(O)2004Round2)
Let
m
,
n
beintegerssothat
m
≥
n
>
1. Let
F
1
,...,
F
k
bea collection of
n
element subsets of
{
1
,...,
m
}
so that
F
i
∩
F
j
contains at most 1 element,1
≤
i
<
j
≤
k
. Show that
k
≤
m
(
m
−
1
)
n
(
n
−
1
)
Solution.
Let
S
be the set of all possible twoelement subsets
{
X
,
Y
}⊂{
1
,
2
,
3
,...,
m
}
.Clearly

S

=
m
2
. Each
F
i
contains
n
elements, there are exactly
n
2
elements in
S
thatare subsets of
F
i
. Also, note that

F
i
∩
F
j
≤
1, thus no element in
S
can be a subset of two sets
F
i
and
F
j
. This means
k
n
2
≤
S
⇒
k
≤
m
(
m
−
1
)
n
(
n
−
1
)
.
Problem 7.
(SMO(O)2006 Round 2)
Let
n
be a positive integer. Let
S
1
,
S
2
,...,
S
k
be acollection of 2
n
element subsets of
{
1
,
2
,
3
,
4
,...,
4
n
−
1
,
4
n
}
so that
S
i
∩
S
j
contains atmost
n
elements for all 1
≤
i
<
j
≤
k
. Show that
k
≤
6
(
n
+
1
)
/
2
Solution.
Let
A
be the set of all possible
(
n
+
1
)
element subsets of
{
1
,
2
,
3
,
4
,...,
4
n
−
1
,
4
n
}
. Clearly

A

=
4
nn
+
1
. Since each
S
i
contains 2
n
elements, there will be
2
nn
+
1
elements in
A
that are subsets of
S
i
. Furthermore, each element in
A
can be a subset of
Prepared by Ho Jun WeiHwa Chong Math Olympiad Programme (Open)
2
at most one
S
i
, since
S
i
∩
S
j
<
n
+
1. Thus we obtain
k
2
nn
+
1
≤
A

=
4
nn
+
1
⇒
k
≤
4
nn
+
1
2
nn
+
1
=
4
n
×
(
4
n
−
1
)
×
...
×
3
n
2
n
×
(
2
n
−
1
)
×
...
×
n
.
Finally, we prove by induction that4
n
×
(
4
n
−
1
)
×
...
×
3
n
2
n
×
(
2
n
−
1
)
×
...
×
n
≤
6
(
n
+
1
)
/
2
.
For
n
=
1 the result is trivially true. Now suppose it holds for
n
=
r
.Let
µ
=
4
r
×
(
4
r
−
1
)
×
...
×
3
r
2
r
×
(
2
r
−
1
)
×
...
×
r
≤
6
(
r
+
1
)
/
2
,
⇒
(
4
r
+
4
)
×
(
4
r
+
3
)
×
...
×
(
3
r
+
3
)(
2
r
+
2
)
×
(
2
r
+
1
)
×
...
×
(
r
+
1
)=(
4
r
+
4
)(
4
r
+
3
)(
4
r
+
2
)(
4
r
+
1
)(
r
)(
3
r
+
2
)(
3
r
+
1
)(
3
r
)(
2
r
+
2
)(
2
r
+
1
)
·
µ
≤
(
4
r
+
4
)(
4
r
+
3
)(
4
r
+
2
)(
4
r
+
1
)(
r
)(
3
r
+
2
)(
3
r
+
1
)(
3
r
)(
2
r
+
2
)(
2
r
+
1
)
·
6
(
r
+
1
)
/
2
=(
4
r
+
4
)(
4
r
+
2
)(
2
r
+
2
)(
2
r
+
1
)
·
(
4
r
+
3
)(
4
r
+
1
)(
3
r
+
2
)(
3
r
+
1
)
·
r
3
r
·
6
(
r
+
1
)
/
2
≤
4
·
169
·
13
·
6
(
r
+
1
)
/
2
=
6427
·
6
(
r
+
1
)
/
2
≤√
6
·
6
(
r
+
1
)
/
2
=
6
(
r
+
2
)
/
2
The induction is complete. Thus
k
≤
4
n
×
(
4
n
−
1
)
×
...
×
3
n
2
n
×
(
2
n
−
1
)
×
...
×
n
≤
6
(
n
+
1
)
/
2
for all integers
n
.
Problem 8.
Consider the set
A
=
{
1
,
2
,
3
,...,
100
}
. Let
S
1
,
S
2
,
S
3
, ...,
S
5
n
be subsets of
A
, such that every element of
A
appears in exactly 4
n
of these subsets. Prove that thereexists
i
,
j
,
k
, such that
S
i
∪
S
j
∪
S
k
=
A
.
Solution.
We set up an incidence matrix with 100 columns and rows
S
1
,
S
2
,...,
S
5
n
.The cell in row
S
i
and column
j
is ﬁlled with ‘1’ if ‘j’ appears in
S
i
and ‘0’ otherwise.Since each number appears in exactly 4
n
subsets, thus every column has exactly 4
n
‘1’sand
n
‘0’s. We deﬁne a ‘column triplet’ as a triplet of ‘0’s occuring in a column. Thusif there are
c
i
‘0’s in column
i
, the number of column triplets in that column is
c
i
3
. Thetotal number of ‘column triplets’ is therefore 100
n
3
. Suppose to the contrary that forall
i
<
j
<
k
, we have
S
i
∪
S
j
∪
S
k
=
A
, then each selection of
(
i
,
j
,
k
)
must admit at leastone column triplet. Thus there are at least
5
n
3
column triplets. We therefore obtain theinequality
5
n
3
≤
100
n
3
⇒
5
n
3
n
3
≤
100
⇒
5
n
(
5
n
−
1
)(
5
n
−
2
)
n
(
n
−
1
)(
n
−
2
)
≤
100
,
but this is a contradiction, since5
n
(
5
n
−
1
)(
5
n
−
2
)
n
(
n
−
1
)(
n
−
2
)
≥
5
n
(
5
n
−
5
)(
5
n
−
10
)
n
(
n
−
1
)(
n
−
2
)=
125.
Prepared by Ho Jun WeiHwa Chong Math Olympiad Programme (Open)
3
Problem 9.
(USAMO 1984)
A math exam has two papers, where each paper consists of atleast one question and both papers have 28 questions altogether. Each pupil attempted 7questions. Each pair of questions was attempted by just two pupils. Show that one pupilattempted either zero or at least four questions in the ﬁrst paper.
Solution.
Each pupil attempts 7 questions and hence 21 ‘pairs’ of questions. Thereare
282
=
378 pairs of questions in total and each is attempted by 2 pupils. So theremust be
378
×
221
=
36 pupils. Suppose
n
pupils solved question 1. Each solved 6 ‘pairs’involving question 1, so there must be 3
n
pairs involving question 1. But there are 27pairs involving question 1, so
n
=
9. The same applies to any other question. So eachquestion was solved by 9 pupils.Suppose the result is false. Suppose there are
m
questions in the ﬁrst paper, and that thenumber of pupils solving 1, 2, 3 questions in the ﬁrst paper is
a
,
b
,
c
respectively. So
a
+
b
+
c
=
36,
a
+
2
b
+
3
c
=
9
m
. Now consider pairs of problems in the ﬁrst paper.There are
m
(
m
−
1
)
2
such pairs. Pupils solving just 1 solve no pairs, those solving 2 solve 1pair and those solving 3 solve 3 pairs, so we have
b
+
3
c
=
m
(
m
−
1
)
. Solving for
b
weget
b
=
−
2
m
2
+
29
m
−
108
=
−
2
(
m
−
294
)
2
−
238
<
0
.
This is a contradiction, so the result must be true.
Problem 10.
(China 1994)
Given that
S
=
{
1
,
2
,
3
,...,
10
}
and
A
1
,
A
2
, ...,
A
k
are subsetsof
S
satisfying

A
i

=
5 for 1
≤
i
≤
k
and

A
i
∩
A
j
≤
2 for 1
≤
i
<
j
≤
k
, ﬁnd the maximum value of
k
.
Solution.
We construct an incidence matrix of 10 columns and rows
A
1
to
A
k
. Weﬁll each cell in column
i
and row
A
j
with ‘1’ if the number
i
appears in
A
j
, and ‘0’otherwise. Let
c
i
be the number of ‘1’s in column
i
. Since

A
i

=
5, we have a totalof 5
k
‘1’s in the matrix, thus
∑
c
i
=
5
k
. Next we count column pairs of ‘1’s. For eachpair
(
A
i
,
A
j
)
, we have at most 2 column pairs since they contain at most two commonelement. Therefore,
10
∑
i
=
1
c
i
2
≤
2
k
2
=
k
(
k
−
1
)
.
However, by Jensen’s inequality, the function
x
2
=
x
2
−
x
2
is concave upwards, thus thetotal number of column pairs is
10
∑
i
=
1
c
i
2
≥
10
∑
c
i
10
2
=
10
k
2
2
=
5
(
k
2
)(
k
2
−
1
)
.
Combining the inequalities, we obtain5
(
k
2
)(
k
2
−
1
)
≤
k
(
k
−
1
)
⇒
k
≤
6
,
Finally, we can easily verify that the following 6 sets satisfy the condition.
{
1
,
2
,
3
,
4
,
5
}
,
{
1
,
2
,
6
,
7
,
8
}
,
{
1
,
3
,
6
,
9
,
10
}
,
{
2
,
4
,
7
,
9
,
10
}
,
{
3
,
5
,
7
,
8
,
10
}
,
{
4
,
5
,
6
,
8
,
9
}
Thus the maximum value of
k
is 6.
Prepared by Ho Jun WeiHwa Chong Math Olympiad Programme (Open)
4