Counting Two Ways

hbghlyj

PDF 2 Counting Pairs Sometimes a problem asks us about the properties of a pair of items. In such situations, it helps to set up a matrix such that each entry represents a pair rather than a single item. Of course, the same technique can be used to count a triple, a quadruple, and so on, as we will see in Exercises. Example 2. (IMC 2002) Two hundred students participated in a mathematical contest. They had 6 problems to solve. It is known that each problem was correctly solved by at least 120 participants. Prove that there must be two participants such that every problem was solved by at least one of these two students. Proof. We will use proof by contradiction and assume that for any pair of the students, at most 5 problems were solved between the two. Since there are 200 students, there are $\binom{200}2=19900$ pairs of students. Let’s number the pairs from 1 to 19900 and the problems from 1 to 6. Let $A = (a_{i,j})$ be a 6×19900 matrix with its rows indexed by the problems and its columns indexed by the pairs of students. Let $a_{i, j}=1$ if both of the two students in pair $j$ did not solve problem $i$ and let $a_{i, j}=0$ otherwise. We have \begin{matrix}&\text{Pairs}\\\text{Problems}&\left(\begin{array}{cccc}a_{1,1} & a_{1,2} & \cdots & a_{1,19900} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,19900} \\ \vdots & \vdots & \ddots & \vdots \\ a_{6,1} & a_{6,2} & \cdots & a_{6,19900}\end{array}\right)\end{matrix}By our assumption, any pair of students solved at most 5 problems. Thus when we count by columns, we get at least one non-zero entry in each column. Thus the sum of all the entries of matrix $A$ is no less than 19900 . On the other hand, we know that every problem was solved by at least 120 students. So for any problem, at most 80 students were unable to solve it. Thus when we count by rows, for any problem $i$, there are at most $\left(\begin{array}{c}80 \\ 2\end{array}\right)=3160$ pairs of students such that none of the students in the pair solved problem $i$. Thus, there are at most 3160 non-zero entries in row $i$. Therefore, the sum of all the entries of matrix $A$ is no more than $6 \cdot 3160=18960$. Since $18960<19900$, we get a contradiction. Therefore our original assumption is false and there must be two participants such that every problem was solved by at least one of these two students.$\square$ Example 3. (Russia 1996) In the Duma there are 1600 delegates, who have formed 16,000 committees of 80 people each. Prove that one can find two committees having no fewer than four common members. Proof. As is typical for a counting in two ways argument, we use proof by contradiction and assume that any pair of committees share at most 3 members. Let $N=16,000$. Since there are $N$ committees, there are $\left(\begin{array}{l}N \\ 2\end{array}\right)$ ways to choose a pair of committees. We number the delegates from 1 to 1600 and the pairs of committees from 1 to $\left(\begin{array}{c}N \\ 2\end{array}\right)$. Let matrix $A=\left(a_{i j}\right)$ be a 1600 by $\left(\begin{array}{l}N \\ 2\end{array}\right)$ matrix with its rows indexed by the delegates and its columns indexed by the committee pairs. Let $a_{i j}=1$ if delegate $i$ serves in both committees in pair $j$ and $a_{i j}=0$ otherwise. Let’s first count by columns. Since each committee pair has at most 3 members, each column has at most 3 non-zero entries. Thus, $S$, the sum of all the entries in the matrix $A$, satisfies the condition$$S \leq 3 \cdot\left(\begin{array}{c}N \\ 2\end{array}\right)=\frac{3}{2} N(N-1)$$Next let's count by rows. Let $n_{i}$ be the number of committees delegate $i$ serves in. We have $$ n_{1}+n_{2}+\cdots+n_{1600}=80 N $$ For a given row $i$, the number of non-zero entries in that row is $\left(\begin{array}{c}n_{i} \\ 2\end{array}\right)=$ $\frac{1}{2} n_{i}\left(n_{i}-1\right)$. Thus, adding all the rows, we have $$ S=\sum_{i=1}^{1600}\left(\begin{array}{c} n_{i} \\ 2 \end{array}\right)=\frac{1}{2}\left(\left(n_{1}^{2}+n_{2}^{2}+\cdots+n_{1600}^{2}\right)-\left(n_{1}+n_{2}+\cdots+n_{1600}\right)\right) . $$ By the Cauchy-Schwarz inequality, $$ n_{1}^{2}+n_{2}^{2}+\cdots+n_{1600}^{2} \geq \frac{\left(n_{1}+n_{2}+\cdots+n_{1600}\right)^{2}}{1600} . $$ Therefore, $$ S \geq \frac{1}{2}\left(\frac{\left(n_{1}+n_{2}+\cdots+n_{1600}\right)^{2}}{1600}-\left(n_{1}+n_{2}+\cdots+n_{1600}\right)\right) $$ $$ =\frac{1}{2}\left(\frac{(80 N)^{2}}{1600}-80 N\right) \text {. } $$ Thus, $$ \begin{aligned} \frac{1}{2}\left(\frac{(80 N)^{2}}{1600}-80 N\right) & \leq S \leq \frac{3}{2} N(N-1) \\ 4 N-80 & \leq 3(N-1) \end{aligned} $$ Since $N=16,000$, the inequality above is not attainable. Therefore, our original assumption is false and one can find two committees having no fewer than four common members.$\square$ Although using a matrix to represent information is visually helpful, sometimes it is more convenient to solve a problem without using a matrix, as we will see in our next example. Example 4. (Hong Kong 2007) In a school there are 2007 boys and 2007 girls. Each student joins no more than 100 clubs in the school. It is known that any boy and any girl join at least one club in common. Show that there is a club with at least 11 boys and 11 girls. Proof. Again, we will use proof by contradiction and assume that any club has at most 10 boys or at most 10 girls. Let $S$ be the number of the triples $(b, g, c)$. Here a triple $(b, g, c)$ represents that boy $b$ and girl $g$ are in club $c$. By our assumption, there are only two possibly overlapping cases. Case 1. A club has at most 10 boys. Considering any one of the 2007 girls, she is in at most 100 clubs, and each of those clubs has at most 10 boys. Thus the number of triples $(b, g, c)$ in this case is at most $2007 \cdot 100 \cdot 10=2007000$. Case 2. A club has at most 10 girls. By a symmetric argument, the number of triples $(b, g, c)$ in this case is at most 2007000 . Therefore, $S$, the total number of triples $(b, g, c)$ is at most $2007000+$ $2007000=4014000$. On the other hand, since any boy and any girl join at least one club in common, we have $$ S \geq 2007 \cdot 2007=4028049>4014000 \geq S . $$ This contradiction shows that our original assumption is false and there is a club with at least 11 boys and 11 girls.$\square$

hbghlyj

A combinatorial geometry problem is usually a combinatorics problem disguised as a geometry problem. So a good approach to this type of problems is to first extract combinatorial information from its geometric content. Then we solve it just as we solve a normal combinatorics problem.
Example 5. (IMO 1987) Let $n$ and $k$ be positive integers and let $S$ be a set of $n$ points in the plane such that:
(1) no three points in $S$ are collinear, and
(2) for every $P$ in $S$, there are at least $k$ points in $S$ equidistant from $P$.
Prove that
$$
k<\frac{1}{2}+\sqrt{2 n} .
$$
Proof. The desired inequality is equivalent to $2 k-1<2 \sqrt{2 n}$. Since both sides are nonnegative, it is equivalent to $4 k^{2}-4 k+1<8 n$, or
$$
n>\frac{1}{2} k(k-1)+\frac{1}{8}
$$
Since both $k$ and $n$ are integers, this is equivalent to
$$
n-1 \geq \frac{1}{2} k(k-1)
$$
We will try to prove this last inequality. We count the number of pairs $\left(P_{i}, P_{j}\right)$ of points in $S$. Since there are $n$ points in total, the number of pairs of points is $\left(\begin{array}{l}n \\ 2\end{array}\right)$. On the other hand, we notice that for each point $P \in S$, there are at least $k$ points on a circle centered at $P$ by condition (2). So for each $P$, there are at least $\left(\begin{array}{l}k \\ 2\end{array}\right)$ concyclic pairs of points. Therefore, we get at least $n\left(\begin{array}{l}k \\ 2\end{array}\right)$ pairs of points when we consider all the points in $S$. But we overcounted because any two circles may share (at most) one chord. Since there are $n$ circles, we overcounted at most $\left(\begin{array}{l}n \\ 2\end{array}\right)$ pairs. Thus, the total number of pairs $\left(P_{i}, P_{j}\right)$ of points in $S$ is at least $n\left(\begin{array}{l}k \\ 2\end{array}\right)-\left(\begin{array}{l}n \\ 2\end{array}\right)$. Therefore,$$\begin{array}{l}\left(\begin{array}{l}n \\ 2\end{array}\right) \geq n\left(\begin{array}{l}k \\ 2\end{array}\right)-\left(\begin{array}{l}n \\ 2\end{array}\right) \\ 2\left(\begin{array}{l}n \\ 2\end{array}\right) \geq n\left(\begin{array}{l}k \\ 2\end{array}\right) \\ 2(n-1) \geq k(k-1) \\ n-1 \geq \frac{1}{2} k(k-1)\end{array}$$which is exactly what we wanted.$\square$
Example 6. (Iran 2010) There are $n$ points in the plane such that no three of them are collinear. Prove that the number of triangles whose area is 1 and whose vertices are chosen from these $n$ points is not greater than $\frac{2}{3}\left(n^{2}-n\right)$.
Proof. Let $m$ be the number of such triangles. Let's count the number of pairs (edge, triangle) where "edge" is an edge of the "triangle." On one hand, since each triangle has three edges, the number of such pairs is $3m$.
On the other hand, the $n$ points give us $\left(\begin{array}{l}n \\ 2\end{array}\right)$ edges. Since the area of a triangle is one-half the base times the height, and no three of the points are collinear, with any given edge as base, at most four other points can be used as the third vertex to form a triangle of area 1: two on one side of the base, another two on the other side of the base. Therefore, the number of such (edge, triangle) pairs is at most $4\left(\begin{array}{l}n \\ 2\end{array}\right)$. Combining these two ways of counting, we get
$$
\begin{aligned}
&3 m \leq 4\left(\begin{array}{c}
n \\
2
\end{array}\right) \\
&m \leq \frac{2}{3}\left(n^{2}-n\right)
\end{aligned}
$$$\square$

hbghlyj

In a graph, vertex $w$ is called a neighbor of vertex $v$ if $v$ and $w$ are connected by an edge. In this case, we also say that $v$ and $w$ are adjacent. The degree of vertex $v$, denoted by $\operatorname{deg}(v)$, is the number of edges that touch $v$. A graph is planar if it can be drawn in a plane without graph edges crossing. Euler's Formula states that if $G$ is a connected planar graph, then $V-E+F=2$, where $V, E$, and $F$ are the number of vertices, edges, and faces in $G$, respectively.

Example 7. (St. Petersburg 1997) The faces of a convex polyhedron are all triangles. At least 5 edges meet at each vertex, and no two vertices of degree 5 are connected by an edge. Prove that this polyhedron has a face whose vertices have degree $5,6,6$, respectively.

Proof. Since every edge is on two faces and every face is a triangle, we have $3 F=2 E$. This equality together with $V-E+F=2$ gives us $E=3 V-6$. For any graph the sum of the degrees of the vertices equals twice the number of edges. So the sum of the degrees in our graph is less than $6V$. We will use proof by contradiction and assume that our polyhedron has no faces whose vertices have degree $5,6,6$, respectively.$\square$

5 Exercises
1. In an $n \times n$ matrix where $n=m^{2}$ for some $m \in \mathbb{N}$, each of the numbers $1,2, \ldots, n$ appear exactly $n$ times. Show that there is a row or a column in the matrix with at least $m$ distinct numbers.
2. (Hong Kong) In a school there are $b$ teachers and $c$ students satisfying the following conditions:
(1) Each teacher teaches exactly $k$ students;
(2) For any two distinct students, there are exactly $h$ teachers teaching them.
Prove that
$$
\frac{b}{h}=\frac{c(c-1)}{k(k-1)} .
$$
3. (China) 16 students took part in a competition. All problems were multiple choice questions with four choices. Students were required to choose one and only one of the choices for each question. It was said that any two students had at most one answer in common. Find the maximum number of problems.
4. (France) In an international meeting of $n \geq 3$ participants, 14 languages are spoken. We know that any 3 participants speak a common language, and no language is spoken by more than half of the participants. What is the least value of $n$ ?
5. An exterior angle of a convex polygon at a vertex $v$ is the angle formed by a side of the polygon and the extension of its adjacent side. It is $\pi$ minus the interior angle of the polygon at vertex $v$. Similarly, we define an angular defect of a convex polyhedron at a vertex $v$ as $2 \pi$ minus the sum of face angles of the polyhedron at $v$. The total angular defect of a polyhedron is the sum of the angular defects of all the vertices of the polyhedron. Note that the sum of all the exterior angles of a convex polygon is $2 \pi$. Prove the analogous Descartes' Theorem: The total angular defect of a convex polyhedron is $4 \pi$.

6 References

• Po-Shen Loh, Graph Theory,
  math.cmu.edu/~ploh/docs/math/mop2011/graph-theory.pdf
• Pranav Sriram, Olympiad Combinatorics,
  artofproblemsolving.com/community/c6h601134
• Yufei Zhao, Counting in Two Ways,
  yufeizhao.com/olympiad/doublecounting_mop.pdf

hbghlyj

尝一下习题
1.假设每行至多有$m-1$个不同的数.考虑一个$n\times n$的矩阵$M$,第$(i,x)$元素为0,若数$i$不出现在题中的矩阵第$x$行;为$k-1$,若$k(>0)$为数$i$出现在题中的矩阵第$x$行的次数.
题中的矩阵每行都出现$n$个元素,但至多有$m-1$个不同的数,所以$M$每列的和$≥n-(m-1)$.
题中的矩阵每个元素都出现$n$次,所以$M$每行的和$≤\frac n2$.
计算$M$的总和,得$n·\frac n2≥n·(n-(m-1))$,所以$-1≥m^2-2m+1$,矛盾.
所以存在一行,它至少有$m$个不同的数.类似地,存在一列,它至少有$m$个不同的数.
2.考虑$b\times c$的0-1矩阵$M$,其中第$i$行第$j$列为1当且仅当第$i$个老师教授第$j$名学生.
设$M$的列向量为$c$个$b$维向量$v_1,\cdots,v_c$,则
(i)$\sum_{i=1}^cv_i=(k,⋯,k)$
(ii)$v_i·v_j=h,\forall i,j\in[1,c],i\ne j$
(iii)考虑$M$的总和,由(i),可知$\sum_{i=1}^cv_i·v_i=bk$
由(i)知$(\sum_{i=1}^cv_i)^2=bk^2$,
由(ii)(iii)知$(\sum_{i=1}^cv_i)^2=bk+hc(c-1)$
所以$bk(k-1)=hc(c-1)$,即$\frac{b}{h}=\frac{c(c-1)}{k(k-1)}$.
3.
4.见math.stackexchange.com
5.先把每个面上的多边形分成三角形,每增加1条边,$E,F$都增加1,所以$E'-F'=E-F$,而$2E'=3F'$,解得$F'=2(E-F)$,代入欧拉定理,得$F'=2V-4$.
划分以后每个面都是三角形,内角和为$π$,共有$F'$个面,因此,角亏之和$=2πV-πF'=π(2V-F')=4π$.

Czhang271828

hbghlyj 发表于 2022-3-18 03:32
尝一下习题
1.假设每行至多有$m-1$个不同的数.考虑一个$n\times n$的矩阵$M$,第$(i,x)$元素为0,若数$i$不出 ...

T3 解答: 设共 $m$ 题, 则于 $\forall i$ 题处实现事件 "某两人有相同答案" 之次数至少为 $24$. 据题知 $24m\leq \binom{16}{15}$, 故 $m\leq 5$.

检验: 取等时, 每一题的所有选项在答卷中恰出现 $4$ 次, 任意两人恰有一题相同.
A A A A B B B B C C C C D D D D
A B C D A B C D A C D B A D B C
A B C D B A D C C A B D D A C B
A B C D C D A B D B A C B C A D
A B C D D C B A B D C A C B D A