Dedekind Cuts YouTube channel is among the best programmes about top tier math competition problems and solving skill instruction. The style of teaching is always clear and inspiring.
In this IMO combinatorics problem he uses incidence matrix to help find the solution. But you will find his definition is slightly different from the IncidenceMatrix/IncidenceGraph syntax we can use for graph representation. I will show you how to generate the graph mentioned in the comment section of this video with surprisingly short code (like 4-5 lines).
Problem
Problem
17 students took part in a math competition with 9 problems. It is given that every problem was solved by exactly 11 students. Prove that there were two students such that union of their solved problems covers all 9 problems.
Sketch of the solution
Sketch of the solution
According to his method construction, the problem can be translated into the following for example:
(
1
)What we need to find is if it is ALWAYS possible to find two rows in the matrix without zeros in the same place. Let’s check Student 3 and 4. Student 3 solved all problems but P6 and P8. Student 4 failed to solve P2, 4, 5, 9 in the exam.
(
2
)Because there is no zero in the same place for the two rows, there union covers all 9 problems:
{1,2,3,4,5,7,8,9}⋃{1,3,6,7,8}
Out[]=
{1,2,3,4,5,6,7,8,9}
Its complement is empty set:
Complement[Range[9],%]
Out[]=
{}
Similar observation shows that we cannot choose Student 1 and 6:
(
3
)Because there is several zeros in the same places for the two rows, there union will miss problems at these places:
{2,3,5,6,7}⋃{3,5,6}
Out[]=
{2,3,5,6,7}
Its complement is the mutually failed attempts:
Complement[Range[9],%]
Out[]=
{1,4,8,9}
To show row pairs like 3 and 4 always exists, the argument is quite clever in the video. Notice that each column there are exactly six zeros (every problem solved by 11 participants, so six participants missed solution), there are pair of vertical zeros. In total, there are pairs.
6 |
2 |
9·
135
6 |
2 |
9*Binomial[6,2]
Out[]=
135
This number includes duplications. For instance, the pair of Student 1 and 6 occurs in column P1, P8 and P9. If all pairs of students have zeros in the same place, there are at least pairs of .
136
17 |
2 |
0 |
0 |
Binomial[17,2]
Out[]=
136
136 is more than the all possible 135 pairs, clearly this is contradiction. I also did some deeper analysis and there should be tighter bound for the number of students required, so far I think 15 might be enough. This is saved for the next blog post.
Graph Representation
Graph Representation
If you use (1) as incidence matrix, it won’t work. Let’s take a look at the definition of the build-in function:
The incidence matrix for a graph with vertices and edges is an matrix with entries given by:
{,…,}
v
1
v
n
{,…,}
e
1
e
m
n×m
a
ij
0 | v i is not incident to v k v i |
1 | v i v k v k v i v k v i |
-1 | e j v i v k |
2 | e j v i v i |
-2 | e j v i v i |
Take a look at the simplest example:
With[{g=CycleGraph[4,VertexLabels"Name"]},{g,TableForm[IncidenceMatrix[g],TableHeadings{{"V1","V2","V3","V4"},{"e1","e2","e3","e4"}}]}]
Out[]=
,
e1 | e2 | e3 | e4 | |
V1 | 1 | 1 | 0 | 0 |
V2 | 1 | 0 | 1 | 0 |
V3 | 0 | 0 | 1 | 1 |
V4 | 0 | 1 | 0 | 1 |
The most nature way to look at the matrix is by column. For undirected graph each column has two 1’s, indicating that the row name is the ending point of the edge. Here edge 1 connects and , edge 2 connects and , and it goes like this for edge 3 and 4. Therefore is not a valid incidence matrix in our application.
Before we start write code, the important question is what is the incidence graph composed of?
The comment section of this YouTube video one chooses a very plausible representation: set students as vertices and an edge connects two students with common zero in column.
Then the problem turns to this question: is it possible to find a complete graph with 17 vertices? If so, all student pairs get connected and none of the unions of pair covers all 9 problems.
V
1
V
2
V
1
V
4
Before we start write code, the important question is what is the incidence graph composed of?
The comment section of this YouTube video one chooses a very plausible representation: set students as vertices and an edge connects two students with common zero in column.
Then the problem turns to this question: is it possible to find a complete graph with 17 vertices? If so, all student pairs get connected and none of the unions of pair covers all 9 problems.
Let’s construct the graph. First we need a random valid dataset satisfying the condition of the problem.
In[]:=
SeedRandom[1234];pos=Table[RandomSample[Range[17],6],9];
For row of the dataset, I randomly generate 6 distinct numbers, representing the students DID NOT solve the problem (like the 0’s in ). In this case the Student 2, 6, 9, 11,17,19 did not manage to find a solution in time:
th
n
th
n
pos[[1]]
Out[]=
{2,11,6,16,9,17}
These 6 students forms a complete graph because each pair shares (0,0) on P1. This is true for every row in the dataset.
edges=UndirectedEdge@@@Flatten[Subsets[#,{2}]&/@pos,1];Short[edges]
You can also choose to delete the duplicated edges:
And this is graph we need:
Now we can obtain the incidence matrix and visualize it with ArrayPlot
The maximum complete graph in this case is:
Possible tighter bound
Possible tighter bound
For most of the time you will see a list of 8-9 numbers. There is a reason for this. The minimum clique is of size 6. To build anything beyond 10, it needs some careful construction. Currently the max one I have found is a clique of size 14. After some calculation and I think we only need 15 students to guarantee that a pair of students cover all 9 problems:
Convert the table to a graph
Therefore you unlikely to see them from random generator.
Summary
Summary
◼
This is a very good problem combining with
◼
IncidenceMatrix in WL need certain requirement
◼
The longest and shortest clique vertex list are very unlikely to appear in simulation with random
◼
Use preset data to draw a graph like Millennium Falcon